Elo211: Sistemas Digitales Tomás Arredondo Vidal
Download 166.12 Kb. Pdf ko'rish
|
3-Formas Canonicas
- Bu sahifa navigatsiya:
- "don’t care"
|
3: Canónicas 1 ELO211: Sistemas Digitales Tomás Arredondo Vidal 1er Semestre – 2009 Este material está basado en: ❒ textos y material de apoyo: Contemporary Logic Design 1 st / 2 nd edition. Gaetano Borriello and Randy Katz. Prentice Hall, 1994, 2005 ❒ material del curso ELO211 del Prof. Leopoldo Silva ❒ material en el sitio http://es.wikipedia.org
3: Canónicas 2 3-Formas Canonicas 3.1 Expresiones canónicas: minterminos y maxterminos 3.2
Expansión a las formas canónicas 3.3
Síntesis de las formas canónicas 3.4
Diseño lógico y simplificación 3: Canónicas 3 Expresiones Canónicas ❒ Existen dos formas básicas de expresiones canónicas que pueden ser implementadas en dos niveles de compuertas: ❍ suma de productos o expansión de minterminos ❍ producto de sumas o expansión de maxterminos ❒ Permiten asociar a una función una expresión algebraica única
❒ La
tabla de verdad también es una representación única para una función booleana
3: Canónicas 4 A B C F F’ 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 F = F’ = A’B’C’ + A’BC’ + AB’C’ Suma de productos ❒ También conocida como expansión de minterminos F =
001 011 101 110 111 + A’BC + AB’C + ABC’ + ABC A’B’C
3: Canónicas 5 forma corta de escribir minterms (ejemplo de 3 terminos o 2 3 = 8 minterms) A B C minterms 0 0 0 A’B’C’ m0 0 0
A’B’C m1 0 1 0 A’BC’ m2 0 1 1 A’BC
m3 1 0 0 AB’C’
m4 1 0 1 AB’C
m5 1 1 0 ABC’
m6 1 1 1 ABC
m7 F en forma canónica: F(A, B, C) = Σ m(1,3,5,6,7) = m1 + m3 + m5 + m6 + m7 = A’B’C + A’BC + AB’C + ABC’ + ABC forma canónica ≠ forma minima F(A, B, C) = A’B’C + A’BC + AB’C + ABC + ABC’ = (A’B’ + A’B + AB’ + AB)C + ABC’ = ((A’ + A)(B’ + B))C + ABC’ = C + ABC’ = ABC’ + C = AB + C Suma de productos ❒ Términos 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) 3: Canónicas 6 A B C F F’ 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 F = 000 010 100 F =
F’ = (A + B + C’) (A + B’ + C’) (A’ + B + C’) (A’ + B’ + C) (A’ + B’ + C’) Producto de sumas ❒ También conocida como expansión de maxterminos (A + B + C) (A + B’ + C) (A’ + B + C) 3: Canónicas 7 A B C maxterms 0 0 0 A+B+C M0 0 0 1 A+B+C’ M1 0 1 0 A+B’+C
M2 0 1 1 A+B’+C’
M3 1 0 0 A’+B+C
M4 1 0 1 A’+B+C’
M5 1 1 0 A’+B’+C
M6 1 1 1 A’+B’+C’
M7 forma corta de escribir minterminos (ejemplo de 3 términos o 2 3 = 8 minterminos) F en forma canónica: F(A, B, C) = Π
= M0 • M2 • M4 = (A + B + C) (A + B’ + C) (A’ + B + C) forma canónica ≠ 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) Producto de sumas ❒ Términos son sumas (o maxterminos) ❍ 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) 3: Canónicas 8 Conversión entre formas canónicas ❒ Es posible convertir entre ambas formas canónicas ❒ Para n variables (0 ≤ i ≤ 2 n -1)
m i = M i M i = m i ∑ m i = ∏ M
i ∏ M
i = ∑ m
i 3: Canónicas 9 Conversión entre formas canónicas ❒ Suma de productos ❍ F’ = A’B’C’ + A’BC’ + AB’C’ ❒ Usando de Morgan’s: f’(X1,X2,...,Xn,0,1,+,•) = f(X1’,X2’,...,Xn’,1,0,•,+) ❍ (F’)’ = (A’B’C’ + A’BC’ + AB’C’)’ ❍ 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 Morgan’s ❍ (F’)’ = ( (A + B + C’)(A + B’ + C’)(A’ + B + C’)(A’ + B’ + C)(A’ + B’ + C’) )’ ❍ F = A’B’C + A’BC + AB’C + ABC’ + ABC 3: Canónicas 10 Conversión entre formas canónicas ❒ Conversión de minterminos a maxterminos ❍ usar maxterminos cuyos índices no aparecen en expansión de minterminos ❍ e.g., F(A,B,C) = Σ m(1,3,5,6,7) = Π M(0,2,4)
❒ Conversión de maxterminos a minterminos ❍ usar minterminos cuyos índices no aparecen en expansión de maxterminos ❍ e.g., F(A,B,C) = Π M(0,2,4) = Σ m(1,3,5,6,7) ❒ Conversión de expansión de minterminos de F a F’ ❍ 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) ❒ Conversión de expansión de maxterminos de F a F’ ❍ 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: Canónicas 11 suma de productos suma de productos minimizada producto de sumas producto de sumas minimizada F1 F2 F3 B A C F4 Implementaciones alternativas en dos niveles ❒ Ejemplo: F=ab+c 3: Canónicas 12 Señales para las cuatro alternativas ❒ Esencialmente idénticas ❍ excepto por perturbaciones ❍ retardos son muy similares ❍ otros ejemplos mas adelante 3: Canónicas 13 3-Formas Canonicas 3.1 Expresiones canónicas: minterminos y maxterminos 3.2
Expansión a las formas canónicas 3.3
Síntesis de las formas canónicas 3.4
Diseño lógico y simplificación 3: Canónicas 14 Expansión a las formas canónicas ❒ Cualquier función booleana puede ser representada en forma canónica . ❒
denomina expansión ❒ Un método directo consiste en obtener la tabla de verdad, y luego identificar los mintérminos o los maxtérminos ❒ Otra posibilidad, que se estudia a continuación, es mediante un desarrollo algebraico basado en los postulados y teoremas del álgebra de Boole 3: Canónicas 15 Expansión a suma de productos ❒ Basado en el uso repetitivo del teorema de unificación: ❍ a = ab + ab’ ❒ Ejemplo: f(a, b, c) = a + bc’ + abc Término a: a = ab + ab’ = (ab + ab’)c + (ab + ab’)c’ = abc + ab’c + abc’ + ab’c’ = m 7
5 + m
6 + m
4 Término bc’: bc’ = abc’ + a’bc’ = m
6 + m
2 Entonces, f(a, b, c) = m 2 + m
4 + m
5 + m
6 + m
7 3: Canónicas 16 Expansión a productos de sumas ❒ Basado en el uso repetitivo del teorema de unificación: ❍ a = (a + b)(a + b’) ❒ Ejemplo: f(a, b, c) = (a + b)(b + c’) Término (a+b): (a+b) = (a+b+c)(a+b+c’) = M
0 M 1 Término (b+c’): (b+c’) = (a+b+c’)(a’+b+c’) = M
1 M 5 Entonces, f(a, b, c) = M 0 M 1 M 5 3: Canónicas 17 3-Formas Canonicas 3.1 Expresiones canónicas: minterminos y maxterminos 3.2
Expansión a las formas canónicas 3.3
Síntesis de las formas canónicas 3.4
Diseño lógico y simplificación 3: Canónicas 18 Síntesis usando suma de productos ❒ Dada una función mediante una suma de productos, ésta puede implementarse usando un OR de AND's ❒ Ejemplo: implementación en dos niveles de f(a, b, c, d) = ab + cd, se logra directamente 3: Canónicas 19 Síntesis usando suma de productos ❒ Una red es de n niveles
, cuando una señal de entrada debe pasar a través de n compuertas para llegar a la salida . ❒
más compuertas hasta llegar a la salida, es la que define la cantidad de niveles; el recorrido se denomina ruta crítica y define
el retardo de propagación de la red. ❒ Debe notarse que se considera que se dispone de entradas invertidas (e.g. b‘) ya que si sólo se dispone de variables (e.g. b) se requiere un nivel adicional.
3: Canónicas 20 Síntesis usando suma de productos ❒ También puede implementarse usando solamente compuertas NAND ❍ Ejemplo: f = ab’+cd 3: Canónicas 21 Síntesis usando suma de productos ❒ La técnica anterior se denomina método de doble complementación : ❒
❒ El siguiente es el equivalente grafico del Teorema de De Morgan:
3: Canónicas 22 Conversión de producto de sumas a suma de productos ❒ Si tenemos una función de tipo producto de sumas se puede convertir usando doble complementación en suma de productos ❒ Aplicando De Morgan y complementando: A B’ C D f A B’ C D f A B’ C D f f ’ A’ B C’ D’
3: Canónicas 23 Conversión de producto de sumas a suma de productos ❒ Hay que notar que la implementación como suma de productos tiene todas las variables de entrada y salida complementadas respecto a su forma inicial. ❒ También
se puede convertir una expresión 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 además de complementar variables de entrada y salida.
3: Canónicas 24 3-Formas Canonicas 3.1 Expresiones canónicas: minterminos y maxterminos 3.2
Expansión a las formas canónicas 3.3
Síntesis de las formas canónicas 3.4
Diseño lógico y simplificación 3: Canónicas 25 Diseño lógico: fan-in y fan-out ❒ Las compuertas lógicas tienen ciertas características concretas dadas por su implementación física. Dos de ellas son el fan- in y el fan- out. ❒ 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: Canónicas 26 Diseño lógico: fan-in y fan-out ❒ Fan- out
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 conmutación debe propagarse a través de mas compuertas. ❒ Un menor numero de niveles requiere compuertas con un mayor fan- in lo que generalmente implica ocupar mas pastillas en la implementación. 3: Canónicas 27 A B C D W X Y Z 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 X X X X 1 0 1 1 X X X X 1 1 0 0 X X X X 1 1 0 1 X X X X 1 1 1 0 X X X X 1 1 1 1 X X X X off-set de W estos patrones de input nunca se deberían encontrar en la practica – "don’t care" sobre sus valores de salida se pueden utilizar en la minimización Funciones incompletamente especificadas ❒ Ejemplo: Numero binarios codificados (BCD) incrementado por 1 ❍ BCD codifica números decimales 0 – 9 en los patrones de bits 0000 – 1001 don’t care (DC) set d W on-set de W
3: Canónicas 28 Descripción de funciones incompletamente especificadas ❒ Formas canónicas y don’t cares (X)
❍ hasta ahora solo han representado on-set ❍ formas canónicas también representan conjunto don’t-care ❍ se necesitan dos de los tres conjuntos (on-set, off-set, dc-set) ❒ Representación canónicas de la función 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: Canónicas 29 Simplificación de lógica combinacional de dos niveles ❒ Encontrar una realización mínima de suma de productos o productos de suma ❍ explotar información X (don’t care) en el proceso ❒ Simplificación algebraica ❍ no hay procedimiento algorítmico/sistemático ❍ ¿como se sabe cuando la mínima realización se encontró? ❒ Herramientas computacionales ❍ soluciones precisas requieren tiempos de computación largos especialmente para funciones con muchos inputs (> 10) ❍ heurísticas se usan para encontrar “buenos” resultados (generalmente no son el optimo global) 3: Canónicas 30 Simplificación de lógica combinacional de dos niveles ❒ Métodos a mano son relevantes ❍ para encontrar las herramientas automáticas y sus fuerzas y debilidades ❍ se pueden verificar resultados (en casos pequeños) 3: Canónicas 31 A B F 0 0 1 0 1 0 1 0 1 1 1 0 B tiene el mismo valor en las dos filas– B se mantiene A tiene valores diferentes en ambas filas– A se elimina F = A’B’+AB’ = (A’+A)B’ = B’ Simplificación de lógica combinacional de dos niveles ❒ Teorema de unificación, clave para la simplificación : A (B’ + B) = A ❒ Esencia de la simplificación de lógica 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 termino puede remplazar al los dos termimos previos
3: Canónicas 32 Simplificación de lógica combinacional de dos niveles ❒ Usando teoremas para minimizar (e.g. idempotencia, commutatividad, distributividad, unificación, 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)
= B Cin + A Cin + A B sumar terminos para factorizar
3: Canónicas 33 Diseño lógico: perturbaciones ❒ Implementaciones de circuitos lógicos 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 momentáneo 3: Canónicas 34 Ejemplo: perturbaciones ❒ Implementaciones de circuitos lógicos pueden incluir
condiciones que causan perturbaciones (como resultados de carreras) en los outputs de implementaciones de circuitos ❒ Una
perturbación estática es un cambio momentáneo 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 momentáneo ❒ Una
perturbación dinámica es una perturbación que ocurre durante el cambio de una variable de salida
3: Canónicas 35 Diseño lógico: perturbaciones ❒ Ejemplo: P = (((A’+B)’ + (D’+C)’)’+A)’ = A’(AB’+C’D) ❍ Con {B=0 y C=1} o {B=0 y D=0} se presentan perturbaciones en el canto de bajada de A atrasado ❒ Actividad: Mostrar porque y como ocurre esto e indicar como eliminar el problema A B C D P 3: Canónicas 36 Actividad: Diseño lógico y perturbaciones ❒ ¿Porque ocurre las perturbaciones? Recordemos que las perturbaciones ocurren cuando una misma señal tiene múltiples caminos que causan carreras en los
inputs a una compuerta. X X’ X X’
3: Canónicas 37 Actividad: Diseño lógico y perturbaciones ❒ Ejemplo: z = x + x’ ❍ En una tabla de verdad se aprecia que y nunca debería ser 0 ❍ Pero dado que hay carreras z si es 0 en el diagrama temporal (perturbación) X X’ Z X X’ Z t perturbación Carrera en señales de entrada 3: Canónicas 38 Actividad: Diseño lógico y perturbaciones ❒ Análisis: Si se hace una tabla de verdad se puede apreciar que la salida P nunca es igual a 1 ❒ Cuando A = 1 y {B=0 y C=1} o {B=0 y D=0} después de un tiempo de propagación X = 1 y X’ = 0 ❒ Después del cambio de a A = 0 y de una propagación en la ruta mas rápida X = 0 y X’ = 0 ❒ Es durante este tiempo de propagación que P se convierte en 1 causando la perturbación A B C D P X X' Y Z 3: Canónicas 39 Actividad: Diseño lógico y perturbaciones ❒ Solución: Para eliminar la perturbación se puede simplificar más (para eliminar la carreras de X con X’...): ❒ P = (((A’+B)’ + (D’+C)’)’+A)’ = A’(AB’+C’D) = A’AB’ + A’C’D = A’C’D ❒ Mas ejemplos en los apuntes... A B C D P A’ C’ D
Download 166.12 Kb. Do'stlaringiz bilan baham: 
|