Minimizacion y mapas de karnaugh

Tema 2. Funciones Lógicas
• Algebra de Conmutación.
• Minimización de funciones Lógicas.
• Introducción al VHDL.

Minimización de Funciones Lógicas
• Minimización en dos niveles. Mapas de Karnaugh de 3
y 4 variables. K-cubos. Definición de una función
mínima en dos niveles.
• Implicantes primos. Implicantes primos esenciales.
Minimización en dos niveles mediante el mapa de
Karnaugh enproblemas lógicos completa e
incompletamente especificados.
• Mapas de Karnaugh de 5 y 6 variables. Minimización
multifunción. Minimización en dos niveles mediante el
mapa de Karnaugh en problemas lógicos completa e
incompletamente especificados.
• Minimización algorítmica en dos niveles (una y varias
salidas) y multinivel.

• Minimización en dos niveles de una función lógica.Encontrar una forma SOP o POS mínima.
Extensión a problemas de varias funciones
Objetivo básico: encontrar formas lógicas con el menor
número de términos productos (sumas) y el menor
número de literales por término producto (sumas).
F(A, B, C, D) = A C D + A C D + B C D + B C D
A

B

C

D

U1A

L1
U1B
U3A

U4A

U1C

F
U2A

• Síntesis multinivel. Realizar una serie deoperaciones
sobre funciones lógicas que encuentren una buena
forma factorizada (varios niveles AND/OR/AND/OR…).
Objetivo básico: reducir el número de literales de la
expresión lógica.
F(A, B, C, D) = A [ B C + D (C + B) ] + A D
A

B

C

D

U6B
L2
U6D
U7A

U7B
U6C
U7C
U6A

Minimización en dos niveles
• El paso de funciones canónicas a funciones estándar
mediante álgebra deconmutación no garantiza
encontrar una solución mínima si no se usa un método
algorítmico.
F(x,y,z) = x z + x y z + x z + x y z = x z + x y + x z + x y
Sin embargo una solución mínima es:
F(x,y,z) = y z + x y + x z
La aplicación de los teoremas “a mano” no permite ver
relaciones de simplificación “ocultas”. A veces sería
necesario expandir la función para luego simplificarla.
Para ver bien lasrelaciones se usan métodos gráficos.

Mapa de Karnaugh
• El Mapa de Karnaugh es un método para observar
una tabla de verdad de forma gráfica y observar la
relaciones de adyacencia entre los 1s ó 0s de la
tabla. Cada grupo de 1, 2, 4, 8, 16, …, 1s (0s) de la
tabla que formen un cuadrado o un rectángulo en el
Mapa son un cubo de la función y corresponden a un
término producto (término suma).CD
Cada casilla está marcada en
AB 00 01 11 10
notación decimal.
1
3
2
00 0
B

0

1

0

0

1

1

2

3

A

BC 00 01 11 10
A
0 0 1 3 2
1

4

5

7

6

01

4

5

7

6

11

12

13

15

14

10

8

9

11

10

• Los valores en los entradas de los Mapas de Karnaugh
se sitúan de forma que entre cada casilla adyacente del
Mapa deKarnaugh (izquierda, derecha, arriba, abajo)
tengan distancia de Hamming 1. Hay que considerar
que los bordes están unidos y que hay adyacencia
entre las filas de abajo y arriba, y las columnas derecha
e izquierda.
• Cada casilla es adyacente a tantas casillas como
entradas haya en la función.
• Los cubos o agrupaciones de 1s ó 0s de la función son
de un orden determinado (k-cubos):
1casilla: 0-cubo; 2 casillas 1-cubo; 4 casillas 2-cubo;
etc.
El número de literales de un k-cubo en función de N
entradas es N-k.

Siguiendo la notación de las formas canónicas, al tomar los 1s de
se forman términos productos:
Si X está siempre a 1 => literal X; si X está siempre a 0 => literal X
Si X toma valores 0 y 1 => no se utiliza X
B

0

1

0

0

1

1

0

0

A

B

01

0

0

1

1

0

1

A

B

0

1

0

1

1

1

0

0

A

B

AB

A

Siguiendo la notación de las formas canónicas, al tomar los 0s de
se forman términos sumas:
Si X está siempre a 1 => literal X; si X está siempre a 0 => literal X
Si X toma valores 0 y 1 => no se utiliza X
B

0

1

0

1

0

1

1

1

A

A+ B

B

0

1

0...