03-Formas Canonicas PDF

3-Formas Cannicas
3.1 Expresiones cannicas: mintrminos y

maxtrminos
3.2 Expansin a las formas cannicas
3.3 Sntesis de las formas cannicas
3.4 Diseo lgico y simplificacin
3: Cannicas
Expresiones Cannicas
Las
formas
cannicas
son
representaciones
de
expresiones
booleanas utilizando una expansin de
mintrminos o una expansin de
maxtrminos.
Permiten asociar a una funcin una
expresin algebraica nica.
La tabla de verdad tambin es una
representacin nica para una funcin
booleana.
3: Cannicas
Expresiones Cannicas
Existen
dos
formas
bsicas
de
expresiones cannicas que pueden ser
implementadas en dos niveles de
compuertas:
suma de productos o expansin de

mintrminos
producto de sumas o expansin de
maxtrminos
3: Cannicas
Suma de productos
Tambin conocida como expansin de
mintrminos.
F = 001
011
101
110
111
F = ABC+ ABC+ ABC + ABC + ABC

A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
1
0
1
0
1
1
1
F
1
0
1
0
1
0
0
0
F = ABC + ABC + ABC
3: Cannicas
Suma de productos
Trminos son productos (o minterms)

Productos AND de literales para las combinacion de input
para los que el output es verdad.
En cada producto cada variable aparece exactamente una
ves (puede estar invertida).
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
minterms
ABC m0
ABC m1
ABC m2
ABC m3
ABC m4
ABC m5
ABC m6
ABC m7
F en forma cannica:
F(A, B, C) = m(1,3,5,6,7)
= m1 + m3 + m5 + m6 + m7
= ABC + ABC + ABC + ABC + ABC
forma cannica forma minima

F(A, B, C) = ABC + ABC + ABC + ABC + ABC
= (AB + AB + AB + AB)C + ABC
= ((A + A)(B + B))C + ABC
= C + ABC
= ABC + C
forma corta de escribir minterms
= AB + C
3: Cannicas
5
Producto de sumas
Tambin conocida como expansin de
maxtrminos.
F=
000
010
100
F = (A + B + C)(A + B + C)(A + B + C)
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
1
0
1
0
1
1
1
F
1
0
1
0
1
0
0
0
F = (A + B + C) (A + B + C) (A + B + C) (A + B + C) (A + B + C)
3: Cannicas
Producto de sumas
A
0
0
0
0
1
1
1
1
Trminos son sumas (o maxterminos)

Suma OR de literales para las combinacion de input para
los que el output es 0.
En cada producto cada variable aparece exactamente una
ves (puede estar invertida).
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
maxterms
A+B+C
A+B+C
A+B+C
A+B+C
A+B+C
A+B+C
A+B+C
A+B+C
M0
M1
M2
M3
M4
M5
M6
M7
F en forma cannica:
F(A, B, C) = M(0,2,4)
= M0 M2 M4
= (A + B + C) (A + B + C) (A + B + C)
forma cannica forma minima
F(A, B, C) = (A + B + C) (A + B + C) (A + B + C)
= (A + B + C) (A + B + C)
(A + B + C) (A + B + C)
= (A + C) (B + C)
forma corta de escribir maxterminos

3: Cannicas
Conversin entre formas cannicas

Es posible convertir entre ambas formas
cannicas
Para n variables (0 i 2n-1)
mi = Mi
Mi = mi
mi = Mi
Mi = mi
3: Cannicas
Suma de productos
F = ABC + ABC + ABC
Usando de Morgans: f(X1,X2,...,Xn,0,1,+,) = f(X1,X2,...,Xn,1,0,,+)

(F) = (ABC + ABC + ABC)
F = (A + B + C) (A + B + C) (A + B + C)
Producto de sumas
F = (A + B + C) (A + B + C) (A + B + C) (A + B + C) (A + B + C)
Usando de Morgans
(F) = ( (A + B + C)(A + B + C)(A + B + C)(A + B + C)(A + B + C
F = ABC + ABC + ABC + ABC + ABC
3: Cannicas
Conversin de mintrminos a maxtrminos

usar maxtrminos cuyos ndices no aparecen en
expansin de mintrminos.
e.g., F(A,B,C) = m(1,3,5,6,7) = M(0,2,4)
Conversin de maxtrminos a mintrminos

usar mintrminos cuyos ndices no aparecen en
expansin de maxtrminos.
e.g., F(A,B,C) = M(0,2,4) = m(1,3,5,6,7)
Conversin de expansin de mintrminos de F a F

usar mintrminos cuyos ndices no aparecen.
e.g., F(A,B,C) = m(1,3,5,6,7) F(A,B,C) = m(0,2,4)
Conversin de expansin de maxtrminos de F a F

usar maxtrminos cuyos ndices no aparecen.
e.g., F(A,B,C) = M(0,2,4)
F(A,B,C) = M(1,3,5,6,7)
3: Cannicas
10
Implementaciones
alternativas en dos niveles
Ejemplo: F=ab+c
A
B
suma de productos
F1
suma de productos minimizada

F2
producto de sumas
F3
producto de sumas minimizada

F4
3: Cannicas
11
Seales para las cuatro alternativas

Esencialmente idnticas
Excepto por perturbaciones.
Retardos son muy similares.
Otros ejemplos mas adelante.
3: Cannicas
12
3-Formas Canonicas
maxtrminos
3: Cannicas
13
Expansin a las formas cannicas

Cualquier funcin booleana puede ser
representada en forma cannica.

El proceso de obtener la forma cannica
se denomina expansin
Un mtodo directo consiste en obtener
la tabla de verdad, y luego identificar
los mintrminos o los maxtrminos
Otra posibilidad, que se estudia a
continuacin, es mediante un desarrollo
algebraico basado en los postulados y
teoremas del lgebra de Boole
3: Cannicas
14
Expansin a suma de productos

Basado
en el uso repetitivo del teorema de

unificacin:
a = ab + ab
Ejemplo: f(a, b, c) = a + bc + abc
Trmino a:
a = ab + ab
= (ab + ab)c + (ab + ab)c
= abc + abc + abc + abc
= m7 + m5 + m6 + m4
Trmino bc:
bc = abc + abc
= m6 + m2
Entonces, f(a, b, c) = m2 + m4 + m5 + m6 + m7
3: Cannicas
15
Expansin a productos de sumas

Basado en el uso repetitivo del teorema de
unificacin:
a = (a + b)(a + b)
Ejemplo: f(a, b, c) = (a + b)(b + c)
Trmino (a+b): (a+b)
= (a+b+c)(a+b+c)
= M0 M1
Trmino (b+c): (b+c)
= M1 M5
= (a+b+c)(a+b+c)
Entonces, f(a, b, c) = M0 M1 M5
3: Cannicas
16
3-Formas Canonicas
maxtrminos
3: Cannicas
17
Sntesis usando suma de productos

Dada una funcin mediante una suma de
productos, sta puede implementarse

usando un OR de AND's
Ejemplo: implementacin en dos niveles
de f(a, b, c, d) = ab + cd, se logra
directamente
3: Cannicas
18

Una red es de n niveles, cuando una seal
de entrada debe pasar a travs de n

compuertas para llegar a la salida.
La seal de entrada que recorra ms
compuertas hasta llegar a la salida, es la
que define la cantidad de niveles; el
recorrido se denomina ruta crtica y define
el retardo de propagacin de la red.
Debe notarse que se considera que se
dispone de entradas invertidas (e.g. b) ya
que si slo se dispone de variables (e.g. b)
se requiere un nivel adicional.
3: Cannicas
19

Tambin puede implementarse usando
solamente compuertas NAND
Ejemplo: f = ab+cd
3: Cannicas
20

La tcnica anterior se denomina mtodo de
doble complementacin:
Se puede visualizar en forma grfica segn:
El siguiente es el equivalente grfico del
Teorema de De Morgan:
3: Cannicas
21
Conversin de producto de sumas a

suma de productos
Si tenemos una funcin de tipo producto de
sumas se puede convertir usando doble

complementacin en suma de productos
A
B
A
B
C
D
C
D
Aplicando De Morgan y complementando:

A
B
C
D
A
B
C
D
3: Cannicas
22
Conversin de producto de sumas a

suma de productos
Hay que notar que la implementacin como
suma de productos tiene todas las variables de

entrada y salida complementadas respecto a su
forma inicial.
Tambin se puede convertir una expresin de
tipo suma de productos a la forma producto de
sumas al cambiar los ANDs del primer nivel por
ORs y en el segundo nivel los ORs por ANDs
adems de complementar variables de entrada y
salida.
3: Cannicas
23
3-Formas Canonicas
maxtrminos
3: Cannicas
24
Diseo lgico: fan-in y fan-out

Las
compuertas
lgicas
tienen
ciertas
caractersticas
concretas
dadas
por
su
implementacin fsica. Dos de ellas son el fan-in
y el fan-out.
Fan-in es el nmero de circuitos o compuertas de
entrada
(e.g. de dos entradas) que puede
soportar una compuerta.
Una compuerta con un fan-in mayor tienden a
ser mas lentas por que se incrementa la
capacitancia de la compuerta.
3: Cannicas
25
Diseo lgico: fan-in y fan-out

Fan-out es el nmero de compuertas que pueden
ser alimentadas o comandada por una salida de

la compuerta.
Un mayor nmero de niveles en un circuito causa
que este tenga un comportamiento mas lento ya

que la conmutacin debe propagarse a travs de
ms compuertas.
Un
menor nmero de
niveles requiere
compuertas con un mayor fan-in lo que
generalmente implica ocupar mas pastillas en la
implementacin.
3: Cannicas
26
Funciones incompletamente
especificadas
Ejemplo: Nmero binarios codificados (BCD) incrementado por 1

BCD codifica nmeros decimales 0 9 en los patrones de bits
0000 1001
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
W
0
0
0
0
0
0
0
1
1
0
X
X
X
X
X
X
X
0
0
0
1
1
1
1
0
0
0
X
X
X
X
X
X
Y
0
1
1
0
0
1
1
0
0
0
X
X
X
X
X
X
Z
1
0
1
0
1
0
1
0
1
0
X
X
X
X
X
X
off-set de W
on-set de W
dont care (DC) set d
W
estos patrones de input nunca
se deberan encontrar en la
practica "dont care" sobre sus
valores de salida se pueden utilizar
en la minimizacin
3: Cannicas
27
Descripcin de funciones
incompletamente especificadas
Formas cannicas y dont cares (X)

Hasta ahora solo han representado on-set
Formas cannicas tambin representan conjunto dont-care
Se necesitan dos de los tres conjuntos (on-set, off-set, dc-set)
Representacin cannicas de la funcin BCD incrementada por 1:
Z = m0 + m2 + m4 + m6 + m8 + d10 + d11 + d12 + d13 + d14

+ d15
Z = [ m(0,2,4,6,8) + d(10,11,12,13,14,15) ]
Z = M1 M3 M5 M7 M9 D10 D11 D12 D13 D14
D15
Z = [ M(1,3,5,7,9) D(10,11,12,13,14,15) ]
3: Cannicas
28
Simplificacin de lgica
combinacional de dos niveles
Encontrar una realizacin mnima de suma de productos o

productos de suma.
Explotar informacin X (dont care) en el proceso.
Simplificacin algebraica
no hay procedimiento algortmico/sistemtico.
como se sabe cuando la mnima realizacin se
encontr?
Herramientas computacionales
Soluciones precisas requieren tiempos de computacin
largos especialmente para funciones con muchos inputs
(> 10).
Heursticas se usan para encontrar buenos resultados
(generalmente no son el ptimo global).
3: Cannicas
29
Mtodos a mano son relevantes
Para encontrar las herramientas automticas y

sus fuerzas y debilidades.
Se pueden verificar resultados (en casos
pequeos).
3: Cannicas
30
Teorema de unificacin, clave para la simplificacin :

A (B + B) = A
Esencia de la simplificacin de lgica de dos niveles

encontrar (o crear) subconjuntos de dos elementos
del on-set en los cuales solo una variable cambia de
valor esta variable puede ser eliminada y un
trmino puede remplazar al los dos trmimos previos
F = AB+AB = (A+A)B = B
A
B tiene el mismo valor en las dos filasB se

mantiene
A tiene valores diferentes en ambas filasA

se elimina
3: Cannicas
31
Usando teoremas para minimizar (e.g. idempotencia,

commutatividad, distributividad, unificacin,
complementariedad, identidad,...)
Ejemplo:
Cout
=
=
=
=
=
=
=
=
=
=
=
=
A B Cin + A B Cin + A B Cin + A B Cin

A B Cin + A B Cin + A B Cin + A B Cin + A B Cin
A B Cin + A B Cin + A B Cin + A B Cin + A B Cin
(A + A) B Cin + A B Cin + A B Cin + A B Cin
(1) B Cin + A B Cin + A B Cin + A B Cin
B Cin + A B Cin + A B Cin + A B Cin + A B Cin
B Cin + A B Cin + A B Cin + A B Cin + A B Cin
B Cin + A (B + B) Cin + A B Cin + A B Cin
B Cin + A (1) Cin + A B Cin + A B Cin
B Cin + A Cin + A B (Cin + Cin)
B Cin + A Cin + A B (1)
sumar terminos
B Cin + A Cin + A B
para factorizar
3: Cannicas
32
Diseo lgico: perturbaciones

Implementaciones
de circuitos lgicos
pueden incluir condiciones que causan
perturbaciones (como resultados de
carreras)
en
los
outputs
de
implementaciones de circuitos.
En
circuitos con ms de dos niveles

pueden generarse perturbaciones con ms
de un cambio momentneo.
3: Cannicas
33
Ejemplo: perturbaciones
Implementaciones de circuitos lgicos pueden
incluir condiciones que causan perturbaciones

(como resultados de carreras) en los outputs de
implementaciones de circuitos.
Una
perturbacin esttica es un cambio
momentneo de un nivel constante en el output
(un falso cero o un falso uno).
En circuitos con ms de dos niveles pueden
generarse perturbaciones con mas de un cambio
momentneo.
Una perturbacin dinmica es una perturbacin
que ocurre durante el cambio de una variable de
salida.
3: Cannicas
34
Diseo lgico: perturbaciones

Ejemplo: P = (((A+B) + (D+C))+A) =
A(AB+CD)
Con {B=0 y C=1} o {B=0 y D=0} se presentan
perturbaciones en el canto de bajada de A
atrasado
A
B
C
D
Actividad: Mostrar porque y como ocurre

esto e indicar como eliminar el problema
3: Cannicas
35
Actividad: Diseo lgico y

perturbaciones
Porque ocurre las perturbaciones? Recordemos
que las perturbaciones ocurren cuando una

misma seal tiene mltiples caminos que causan
carreras en los inputs a una compuerta.
X
X
X
X
3: Cannicas
36
Actividad: Diseo lgico y

perturbaciones
Ejemplo: z = x + x
En una tabla de verdad se aprecia que y nunca debera ser 0

Pero dado que hay carreras z si es 0 en el diagrama temporal
(perturbacin)
Carrera en seales de entrada
X
X
Z
t
X
X
Z
perturbacin
3: Cannicas
37
Actividad: Diseo lgico y perturbaciones

Anlisis: Si se hace una tabla de verdad se puede
apreciar que la salida P nunca es igual a 1.

X
X'
A
B
C
D
P
Z
Cuando A = 1 y {B=0 y C=1} o {B=0 y D=0}
despus de un tiempo de propagacin X = 1 y X = 0.

Despus del cambio de a A = 0 y de una propagacin
en la ruta mas rpida X = 0 y X = 0.
Es durante este tiempo de propagacin que P se
convierte en 1 causando la perturbacin.
3: Cannicas
38
Actividad: Diseo lgico y perturbaciones

Solucin: Para eliminar la perturbacin se puede
simplificar ms (para eliminar la carreras de X con

X...):
P = (((A+B) + (D+C))+A) = A(AB+CD)
= AAB + ACD = ACD
A
B
C
D
Mas ejemplos en los apuntes...
A
C
D
3: Cannicas
39

03-Formas Canonicas PDF

Cargado por

Copyright:

Formatos disponibles

03-Formas Canonicas PDF

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

03-Formas Canonicas PDF

Cargado por

Copyright:

Formatos disponibles

3-Formas Cannicas

3.1 Expresiones cannicas: mintrminos y

suma de productos o expansin de

F = ABC+ ABC+ ABC + ABC + ABC

F = ABC + ABC + ABC

Trminos son productos (o minterms)

forma cannica forma minima

Trminos son sumas (o maxterminos)

forma corta de escribir maxterminos

Conversin entre formas cannicas

Conversin entre formas cannicas

Usando de Morgans: f(X1,X2,...,Xn,0,1,+,) = f(X1,X2,...,Xn,1,0,,+)

Conversin entre formas cannicas

Conversin de mintrminos a maxtrminos

Conversin de maxtrminos a mintrminos

Conversin de expansin de mintrminos de F a F

Conversin de expansin de maxtrminos de F a F

suma de productos minimizada

producto de sumas minimizada

Seales para las cuatro alternativas

Expansin a las formas cannicas

representada en forma cannica.

Expansin a suma de productos

en el uso repetitivo del teorema de

Expansin a productos de sumas

Sntesis usando suma de productos

productos, sta puede implementarse

Sntesis usando suma de productos

de entrada debe pasar a travs de n

Sntesis usando suma de productos

solamente compuertas NAND

Sntesis usando suma de productos

Se puede visualizar en forma grfica segn:

El siguiente es el equivalente grfico del

Conversin de producto de sumas a

sumas se puede convertir usando doble

Aplicando De Morgan y complementando:

Conversin de producto de sumas a

suma de productos tiene todas las variables de

Diseo lgico: fan-in y fan-out

Diseo lgico: fan-in y fan-out

ser alimentadas o comandada por una salida de

que este tenga un comportamiento mas lento ya

Ejemplo: Nmero binarios codificados (BCD) incrementado por 1

Formas cannicas y dont cares (X)

Representacin cannicas de la funcin BCD incrementada por 1:

Z = m0 + m2 + m4 + m6 + m8 + d10 + d11 + d12 + d13 + d14

Encontrar una realizacin mnima de suma de productos o

Para encontrar las herramientas automticas y

Teorema de unificacin, clave para la simplificacin :

Esencia de la simplificacin de lgica de dos niveles

B tiene el mismo valor en las dos filasB se

A tiene valores diferentes en ambas filasA

Usando teoremas para minimizar (e.g. idempotencia,

A B Cin + A B Cin + A B Cin + A B Cin

Diseo lgico: perturbaciones

circuitos con ms de dos niveles

incluir condiciones que causan perturbaciones

Diseo lgico: perturbaciones