Download - Algebra Boole

3: Canónicas 1

ELO211: Sistemas Digitales

Tomás Arredondo Vidal1er Semestre – 2009

Este material está basado en:

❒ textos y material de apoyo: Contemporary Logic Design 1st / 2nd 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 10 0 1 1 00 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 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’ + ABCA’B’C

3: Canónicas 5

forma corta de escribir minterms

(ejemplo de 3 terminos o 23 = 8 minterms)

A B C minterms

0 0 0 A’B’C’ m0

0 0 1 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 10 0 1 1 00 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 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 23 = 8 minterminos)

F en forma canónica:

F(A, B, C) = ΠM(0,2,4)

= 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 ≤ 2n-1)

mi = Mi

Mi = mi

∑ mi = ∏ Mi

∏ Mi = ∑ mi

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: Canónicas 14

Expansión a las formas canónicas

❒ Cualquier función booleana puede ser representada en forma canónica.

❒ El proceso de obtener la forma canónica se 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’ + abcTérmino a: a = ab + ab’

= (ab + ab’)c + (ab + ab’)c’

= abc + ab’c + abc’ + ab’c’

= m7 + m5 + m6 + m4

Término bc’: bc’ = abc’ + a’bc’

= m6 + m2

Entonces, f(a, b, c) = m2 + m4 + m5 + m6 + m7

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’)

= M0 M1

Término (b+c’): (b+c’) = (a+b+c’)(a’+b+c’)

= M1 M5

Entonces, f(a, b, c) = M0 M1 M5

3: Canónicas 17

3-Formas Canonicas





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


❒ 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.

❒ La señal de entrada que recorra máscompuertas 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


❒ 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:

❒ Se puede visualizar en forma gráfica segú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:

AB’

CD

f

AB’

CD

f

AB’

CD

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: 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 Z0 0 0 0 0 0 0 10 0 0 1 0 0 1 00 0 1 0 0 0 1 10 0 1 1 0 1 0 00 1 0 0 0 1 0 10 1 0 1 0 1 1 00 1 1 0 0 1 1 10 1 1 1 1 0 0 01 0 0 0 1 0 0 11 0 0 1 0 0 0 01 0 1 0 X X X X1 0 1 1 X X X X1 1 0 0 X X X X1 1 0 1 X X X X1 1 1 0 X X X X1 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 susvalores 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 combinacionalde 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 combinacionalde 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 outputsde 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

AB

CD

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.

XX’

X

X’

3: Canónicas 37


❒ 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

AB

CD

P

X

X'

Y

Z

3: Canónicas 39


❒ 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...

AB

CD

PA’C’D

P

Download - Algebra Boole

Top Related