06_algDEERERERERERERFDFDFDFDFDFDFDebrabooleC.ppt

DFDFDFDFD

1. [ Sistemas Operativos ]
Präsentat
ion
Universidad de Magallanes
Facultad de Ingeniería
Departamento de Ingeniería en Computación
MIC3181
Algebra de Boole
… continuación
Eduardo Peña J.
Edopena 1
Microprocesadores

2. [ Algebra de Boole ]
Präsentat
ionEdopena 2
Microprocesadores
Indice
Temario:
Métodos de minimización
Método mapas de Karnaugh
Método tabular Quine McCluskey
Información extraída de:
http://www.cic.unb.br/docentes/jacobi/ensino/circuitos/DoisNiveis/sld001.htm

3. Suma de productos es una forma de representación
de funciones booleanas constituida por operaciones
lógicas o sobre un conjunto de términos formados
por la operación.
[ Algebra de Boole ]
Edopena 3
Microprocesadores
Suma de Productos
SUMA DE PRODUCTOS

4. El producto de sumas es otra forma de
representación de funciones booleanas
caracterizadas por la aplicación de operación sobre
un conjunto de operaciones o sobre las entradas
[ Algebra de Boole ]
Edopena 4
Microprocesadores
Producto de Suma
PRODUCTO DE SUMA

5. •Un minterm es un término producto que vale 1 en al
menos un punto del dominio de una función
booleana.
•Es definido por un producto (AND) donde cada variable
aparece al menos una vez directa o complementada.
[ Algebra de Boole ]
Edopena 5
Microprocesadores
Minterms
MINTERMS

6. •Un maxterm es un término suma que vale 0 en al menos un
punto del dominio de la función.
•Es determinado por una adición (OR) donde cada variable
aparece al menos una vez, directa o complementada.
[ Algebra de Boole ]
Edopena 6
Microprocesadores
Maxterms
MAXTERMS

7. •Una tabla de verdad es una firma que identifica
inequívocamente una función booleanas.
•Expresiones booleanas diferentes pueden representar una
misma función booleana.
[ Algebra de Boole ]
Edopena 7
Microprocesadores
Formas canónicas
FORMAS CANÓNICAS

8. •Las formas canónicas son representaciones únicas de
funciones booleanas.
Ej. Una suma de productos es una forma canónica.
[ Algebra de Boole ]
Edopena 8
Microprocesadores
Formas canónicas
FORMAS CANÓNICAS DE DOS NIVELES

9. •Las formas canónicas son representaciones únicas de
funciones booleanas.
Ej. Un producto de sumas es otra forma canónica.
[ Algebra de Boole ]
Edopena 9
Microprocesadores
Formas canónicas

10. •Notación para suma de minterms.
•Notación para producto de maxterms.
[ Algebra de Boole ]
Edopena 10
Microprocesadores
Formas canónicas

11. [ Algebra de Boole ]
Edopena 11
Microprocesadores
SIMPLIFICACION DE SUMAS DE MINTERMS
Formas canónicas

12. •Es posible obtener un producto de maxterms a partir de una
suma de minterms o viceversa aplicando De Morgan sobre el
complemento de la función.
[ Algebra de Boole ]
Edopena 12
Microprocesadores
MINTERMS X MAXTERMS
Formas canónicas

13. •Estas son las funciones para las cuales algunas combinaciones
de valores de entrada nunca ocurren.
Ej. Decodificador de display de 7 segmentos para dígitos BCD.
[ Algebra de Boole ]
Edopena 13
Microprocesadores
FUNCIONES INCOMPLETAS
Funciones Incompletas

14. •Las funciones incompletas mapean puntos del dominio de
una función en tres valores posibles.
•Los dominios de puntos donde F vale {0 , 1 X} son
denominados, respectivamente, de:
•F puede ser descrita definiendo dos de sus tres
conjuntos.
[ Algebra de Boole ]
Edopena 14
Microprocesadores
Funciones Incompletas

15. Manipulación Algebraica:
•Difícil de determinar un orden y qué transformaciones aplicar.
•Cómo sabes si se localizó una mejor solución.
Herramientas de auxilio:
•No consiguen tratar problemas de forma exacta.
•Se basan en heurísticas y criterios de costo.
Métodos manuales, al menos para fines didácticos y
funciones muy simples
[ Algebra de Boole ]
Edopena 15
Microprocesadores
Minimización lógica de dos niveles
MINIMIZACIÓN LÓGICA DE DOS NIVELES

16. •Idea base: Aplicación de distribución y complemento.
[ Algebra de Boole ]
Edopena 16
Microprocesadores
Minimización lógica de dos niveles

17. •Un espacio booleano n-
dimensional puede ser visualizado
espacialmente.
•Los productos de literales son
llamados cubos.
[ Algebra de Boole ]
Edopena 17
Microprocesadores
Cubos
CUBOS

18. •Puntos adjacentes difieren en un
bit.
•Todos los puntos de la función
están en una cara.
•Y y Z varían mientras que X
permanece inalterable: Y y Z
pueden ser eliminados de la
expresión.
[ Algebra de Boole ]
Edopena 18
Microprocesadores
Cubos
VISUALIZACIÓN DE CUBOS

19. •Visualización del dominio de una función en forma matricial.
•Puntos del dominio están dispuestos siguiendo el código Gray,
pares adjacentes difieren en un bit.
[ Algebra de Boole ]
Edopena 19
Microprocesadores
Mapas de Karnaugh
MAPAS DE KARNAUGH

20. •Los elementos extremos de las columnas y filas son
adjacentes.
[ Algebra de Boole ]
Edopena 20
Microprocesadores
Mapas de Karnaugh
ADJACENCIA DEL MAPA DE KARNAUGH

21. •El cubo obtenido es definido por las variables que no
cambian de cara en todos sus minterms.
[ Algebra de Boole ]
Edopena 21
Microprocesadores
Mapas de Karnaugh

22. •La agrupación obtenida es definida por las variables que no
cambian de cara en todos sus minterms.
[ Algebra de Boole ]
Edopena 22
Microprocesadores
Mapas de Karnaugh

23. [ Algebra de Boole ]
Edopena 23
Microprocesadores
Mapas de Karnaugh

24. [ Algebra de Boole ]
Edopena 24
Microprocesadores
Mapas de Karnaugh
COMPLEMENTO DE UNA FUNCIÓN

25. [ Algebra de Boole ]
Edopena 25
Microprocesadores
Mapas de Karnaugh

26. [ Algebra de Boole ]
Edopena 26
Microprocesadores
Mapas de Karnaugh
KARNAUGH DE CUATRO VARIABLES

27. [ Algebra de Boole ]
Edopena 27
Microprocesadores
Mapas de Karnaugh

28. •Los puntos irrelevantes pueden ser considerados como un 1 o
un 0 en el mapa de Karnaugh.
•Son utilizados para formar agrupaciones mayores,
simplificando una función.
[ Algebra de Boole ]
Edopena 28
Microprocesadores
Mapas de Karnaugh
MINIMIZACIÓN CON IRRELEVANTES

29. [ Algebra de Boole ]
Edopena 29
Microprocesadores
Mapas de Karnaugh
EJEMPLO COMPARADOR DE DOS BITS

30. [ Algebra de Boole ]
Edopena 30
Microprocesadores
Mapas de Karnaugh
EJEMPLO COMPARADOR DE DOS BITS

31. [ Algebra de Boole ]
Edopena 31
Microprocesadores
Mapas de Karnaugh
EJEMPLO COMPARADOR DE DOS BITS

32. •La minimización de dos niveles busca obtener las sumas del producto con
un número mínimo de productos y literales.
• Minimizándose el número de productos se está reducido la altura de la
implementación y, por consiguiente, su área.
• Estando reducido el número de literales, se reduce el número de
transistores de la implementación digital, lo que minimiza la potencia
disipada.
Ej Sumador de 1 bit
[ Algebra de Boole ]
Edopena 32
Microprocesadores
Mapas de Karnaugh
MINIMIZACIÓN LÓGICA EN DOS NIVELES

33. Conceptos Básicos
• Implicante: una agrupación c es un implicante de una función f si
para todo vector x donde c(x) = 1, tenemos que f(x) = 1. O sea c  f
•En álgebra Booleana “²” es una relación de orden parcial, análoga
a relación "está contenido en" entre conjuntos. Puede ser definida
como “un conjunto de minterms de c está contenido en f”.
[ Algebra de Boole ]
Edopena 33
Microprocesadores
Mapas de Karnaugh

34. Conceptos Básicos
•Implicante primo: es una agrupación que
no está contenida en ninguna otra
agrupación de la función (o, no puede ser
mas expandido)
•Implicante primo esencial: es un
implicante primo que contiene al menos
un minterm que no está contenido en
ningún otro implicante de la función.
[ Algebra de Boole ]
Edopena 34
Microprocesadores
Mapas de Karnaugh

35. •Una cobertura de una función f y una
suma de productos que contienen todos
los minterms de f (cobre f) Una
cobertura prima es aquella compuesta
apenas por implicantes primos
• Una cobertura irredundante es aquella
en que ninguno de las dos
agrupaciones puede ser removida sin
alterar la función.
[ Algebra de Boole ]
Edopena 35
Microprocesadores
Mapas de Karnaugh

36. Ejemplos
[ Algebra de Boole ]
Edopena 36
Microprocesadores
Mapas de Karnaugh

37. 1.Seleccione un minterm m
i
de la función.
2.Expanda m
i
en todas las direcciones posibles, generando así todos
los implicantes primos que cubren m
i
.
3.Repita los pasos anteriores para todos los minterms de la función,
generando todos los implicantes primos posibles.
4.Identifique y separe los implicantes esenciales. Los minterms
cubiertos por ellos pueden ser considerados como puntos
irrelevantes.
5.Seleccione un conjunto mínimo de implicantes que cubra los
minterms restantes.
[ Algebra de Boole ]
Edopena 37
Microprocesadores
Mapas de Karnaugh
COBERTURA MÍNIMA CON MAPA DE
KARNAUGH

38. Ejemplo
[ Algebra de Boole ]
Edopena 38
Microprocesadores
Mapas de Karnaugh

39. Continuación
Ejemplo
[ Algebra de Boole ]
Edopena 39
Microprocesadores
Mapas de Karnaugh

40. •Tome los minterms de la función y expanda sucesivamente los
minterms en todas direcciones posibles (variables en espacio
Booleano).
• Obtener así todos los implicantes primos de la función.
• Seleccione un subconjunto que cubra la función que tenga un
costo mínimo.
• Detección y remoción de primos esenciales.
• Dominancia de línea y de columna.
• Branch and bound cuando no hay dominancia.
[ Algebra de Boole ]
Edopena 40
Microprocesadores
Quine McClusky
MÉTODO DE QUINE McCLUSKY

41. McCluskey:
•Representar los implicantes en notación
binaria :
X= {x1, x2, x3}
•Tabular los implicantes en grupos de mismo peso (1's) para reducir el número de
comparaciones .
x
1
·x
3
' -> 1-0
x
3
-> --1
x
1
'·x
2
'·x
3
-> 001
[ Algebra de Boole ]
Edopena 41
Microprocesadores
Quine McClusky

42. Expansión de minterms
Ejemplo: F =

Expansión de
los minterms
de los
implicantes.
[ Algebra de Boole ]
Edopena 42
Microprocesadores
Quine McClusky

43. Implicantes Primos:
p1 = x
1
·x
0
p3 = x
2
'·x
1
p5 = x
3
·x
1
'·x
0
'p7 = x
3
·x
2
·x
1
'
p2 = x
2
·x
0
p4 = x
3
'·x
0
p6 = x
3
·x
2
'·x
0
'
[ Algebra de Boole ]
Edopena 43
Microprocesadores
Quine McClusky

44. Cobertura de función
[ Algebra de Boole ]
Edopena 44
Microprocesadores
Quine McClusky

45. Cobertura de función
•Dominancia de Línea: si todos los minterms de una línea l
x
están
contenidos en una línea l
y
, entonces l
y
domina a l
x
y l
x
puede ser
removida de la tabla esto indica que el implicante p
y
cubre al
implicante p
x

[ Algebra de Boole ]
Edopena 45
Microprocesadores
Quine McClusky

46. Cobertura de función
•Dominancia de columna: si todos los minterms de una columna c
x

están contenidos en una columna c
y
, entonces c
y
domina a c
x
y c
y

puede ser removida de la tabla cubriendo el minterm m
x

automáticamente se cubre m
y

[ Algebra de Boole ]
Edopena 46
Microprocesadores
Quine McClusky

47. Problemas con el método de Quine:
• Computacionalmente es ineficiente
• Genera todos los implicantes primos
Complejidad de: (3 ^ n)/n
• Parte de los minterms de la función
Complejidad de: 2n-1
[ Algebra de Boole ]
Edopena 47
Microprocesadores
Quine McClusky
CAD PARA MINIMIZACIÓN

48. •Punto de partida: una suma de productos (no mintermos)
• Respete iterativamente la secuencia de operaciones:
Expand: Expande los implicantes hasta su tamaño máximo
Extraer esenciale primos
Cobertura Irredundante: generar una cobertura irredundante
Reducir: reduzca los implicantes hasta su tamaño mínimo
Respete los pasos anteriores hasta no obtener ganancias
Last gasp: la inserción de un primo cualquiera no puede llevar a
eliminación de dos primos de la cobertura
[ Algebra de Boole ]
Edopena 48
Microprocesadores
Resumen
RESUMEN

49. [ Algebra de Boole ]
Edopena 49
Microprocesadores
Resumen

50. [ Algebra de Boole ]
Edopena 50
Microprocesadores
Resumen

51. [ Algebra de Boole ]
Edopena 51
Microprocesadores
Resumen