ELO211: Sistemas Digitales Toms Arredondo Vidal 1er Semestre 2009
Este material est basado en:
textos y material de apoyo:
Borriello and Randy Katz. Prentice Hall, 1994, 2005 material del curso ELO211 del Prof. Leopoldo Silva material en el sitio [Link]
Contemporary Logic Design 1st / 2nd edition. Gaetano
3: Cannicas
3-Formas Canonicas
3.1 Expresiones cannicas: minterminos y maxterminos 3.2 Expansin a las formas cannicas 3.3 Sntesis de las formas cannicas 3.4 Diseo lgico y simplificacin
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 minterminos r producto de sumas o expansin de maxterminos
r
Permiten asociar a una funcin una
expresin algebraica nica La tabla de verdad tambin es una representacin nica para una funcin booleana
3: Cannicas 3
Suma de productos
Tambin conocida como expansin de
minterminos
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)
r
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)
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 (ejemplo de 3 terminos o 23 = 8 minterms)
A 0 0 0 0 1 1 1 1
Producto de sumas
Tambin conocida como expansin de
maxterminos
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 6
Producto de sumas
Trminos son sumas (o maxterminos)
r
suma OR de literales para las combinacion de input para los que el output es falso en cada producto cada variable aparece exactamente una ves (puede estar invertida)
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)
A 0 0 0 0 1 1 1 1
B 0 0 1 1 0 0 1 1
forma corta de escribir minterminos (ejemplo de 3 trminos o 23 = 8 minterminos)
3: Cannicas
Conversin entre formas cannicas
Es posible convertir entre ambas formas cannicas Para n variables (0 i 2n-1)
mi = Mi Mi = m i mi = Mi Mi = mi
3: Cannicas 8
Conversin entre formas cannicas
Suma de productos
r
F = ABC + ABC + ABC (F) = (ABC + ABC + ABC) F = (A + B + C) (A + B + C) (A + B + C)
Usando de Morgans: f(X1,X2,...,Xn,0,1,+,) = f(X1,X2,...,Xn,1,0,,+)
r r
Producto de sumas
r
F = (A + B + C) (A + B + C) (A + B + C) (A + B + C) (A + B + C) (F) = ( (A + B + C)(A + B + C)(A + B + C)(A + B + C)(A + B + C) ) F = ABC + ABC + ABC + ABC + ABC
3: Cannicas 9
Usando de Morgans
r r
Conversin entre formas cannicas
Conversin de minterminos a maxterminos
r r
usar maxterminos cuyos ndices no aparecen en expansin de minterminos e.g., F(A,B,C) = m(1,3,5,6,7) = M(0,2,4) usar minterminos cuyos ndices no aparecen en expansin de maxterminos e.g., F(A,B,C) = M(0,2,4) = m(1,3,5,6,7) usar minterminos cuyos ndices no aparecen e.g., F(A,B,C) = m(1,3,5,6,7) F(A,B,C) = m(0,2,4) usar maxterminos 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
Conversin de maxterminos a minterminos
r
Conversin de expansin de minterminos de F a F
r r
Conversin de expansin de maxterminos de F a F
r r
Implementaciones alternativas en dos niveles
Ejemplo: F=ab+c
A B F1 C
suma de productos
suma de productos minimizada
F2
producto de sumas
F3
producto de sumas minimizada
F4 3: Cannicas 11
Seales para las cuatro alternativas
Esencialmente idnticas r excepto por perturbaciones r retardos son muy similares r otros ejemplos mas adelante
3: Cannicas
12
3-Formas Canonicas
3.1 Expresiones cannicas: minterminos y maxterminos 3.2 Expansin a las formas cannicas 3.3 Sntesis de las formas cannicas 3.4 Diseo lgico y simplificacin
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:
r
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:
r
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) = (a+b+c)(a+b+c) = M1 M5 Entonces, f(a, b, c) = M0 M1 M5
3: Cannicas 16
3-Formas Canonicas
3.1 Expresiones cannicas: minterminos y maxterminos 3.2 Expansin a las formas cannicas 3.3 Sntesis de las formas cannicas 3.4 Diseo lgico y simplificacin
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
Sntesis usando suma de productos
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
Sntesis usando suma de productos
Tambin puede implementarse usando
solamente compuertas NAND
r
Ejemplo: f = ab+cd
3: Cannicas
20
Sntesis usando suma de productos
La tcnica anterior se denomina mtodo de
doble complementacin:
Se puede visualizar en forma grfica segn:
El siguiente es el equivalente grafico 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 f C D A B C D
Aplicando De Morgan y complementando: A A B B f C D 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
3.1 Expresiones cannicas: minterminos y maxterminos 3.2 Expansin a las formas cannicas 3.3 Sntesis de las formas cannicas 3.4 Diseo lgico y simplificacin
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 - o ut. Fan - in es el numero 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 -
o ut es el numero de compuertas que pueden ser alimentadas o comandada por una salida de la compuerta. Un mayor numero de niveles en un circuito causa que este tenga un comportamiento mas lento ya que la conmutacin debe propagarse a travs de mas compuertas. Un menor numero 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: Numero binarios codificados (BCD) incrementado por 1
r
BCD codifica nmeros decimales 0 9 en los patrones de bits 0000 1001
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
A 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
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)
r r r
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:
r r
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
r r
Simplificacin de lgica combinacional de dos niveles
Encontrar una realizacin mnima de suma de productos o
productos de suma r explotar informacin X (dont care) en el proceso
Simplificacin algebraica
r r
no hay procedimiento algortmico/sistemtico como se sabe cuando la mnima realizacin se encontr? 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 optimo global)
Herramientas computacionales
r
3: Cannicas
29
Simplificacin de lgica combinacional de dos niveles
Mtodos a mano son relevantes
r
para encontrar las herramientas automticas y sus fuerzas y debilidades se pueden verificar resultados (en casos pequeos)
3: Cannicas
30
Simplificacin de lgica combinacional de dos niveles
Teorema de unificacin, clave para la simplificacin :
A (B + B) = A
Esencia de la simplificacin de lgica de dos niveles
r
encontrar (o crear) subconjuntos de dos elementos del onset en los cuales solo una variable cambia de valor esta variable puede ser eliminada y un termino puede remplazar al los dos termimos previos
F = AB+AB = (A+A)B = B A 0 0 1 1 B 0 1 0 1 F 1 0 1 0 A tiene valores diferentes en ambas filas A se elimina
3: Cannicas 31
B tiene el mismo valor en las dos filas B se mantiene
Simplificacin de lgica combinacional de dos niveles
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 para B Cin + A Cin + A B 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 mas de dos niveles pueden generarse perturbaciones con mas 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 mas 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)
r
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
r r
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)
X X Z X X Z t Carrera en seales de entrada
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
Y A B C D Z X X' P
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
A C D
Mas ejemplos en los apuntes...
3: Cannicas 39