td2-tema07 karnaugh

1

9.9. SimplificaciSimplificacióón de funciones ln de funciones lóógicasgicascon el mcon el méétodo de todo de KarnaughKarnaughOliverio J. Santana Jaria

Sistemas DigitalesIngeniería Técnica en Informática de Sistemas

Curso 2006 – 2007

Simplificación de funciones lógicas con el método d e Karnaugh 2

IntroducciIntroduccióónn� La efectividad de la simplificación booleana no debe depender de nuestra habilidad usando leyes y reglas� Es necesaria la utilización de una metodología sistemática para simplificar las funciones booleanas� Los objetivos de este tema son:� Describir el método de Karnaugh para la simplificación de funciones lógicas en forma de suma de productos y de producto de sumas� Definir el concepto de función incompletamente especificada� Introducir la necesidad de minimizar de forma conjunta las funciones correspondientes a circuitos con salida múltiple

2


Estructura del temaEstructura del tema� Introducción� Método de simplificación de Karnaugh� Simplificación de una suma de productos� Simplificación de un producto de sumas� Funciones incompletamente especificadas� Circuitos con salida múltiple� Funciones con más de cuatro variables� Resumen y bibliografía


MMéétodo de Karnaughtodo de Karnaugh� El método de Karnaugh proporciona una forma sistemática para simplificar funciones booleanas� La clave para realizar este proceso consiste en representar la función que se desea simplificar usando lo que se conoce como mapa de Karnaugh� Si se aplica adecuadamente, este método genera las expresiones más simples posibles, tanto en forma de suma de productos como de producto de sumas

3


Mapas de KarnaughMapas de Karnaugh� Un mapa de Karnaugh es similar a una tabla de verdad, ya que muestra todos los posibles valores de la salida para cada combinación posible de las entradas� En lugar de organizarse en filas y columnas, un mapa de Karnaugh es un conjunto de celdas en el que cada celda representa un valor binario de las entradas� Las celdas se distribuyen de manera que simplificar una determinada expresión consiste en agrupar adecuadamente algunas de las de celdas


Mapas de KarnaughMapas de Karnaugh� El número de celdas de un mapa de Karnaugh es igual al número total de posibles combinaciones de los valores de las variables de entrada� Por ejemplo, un mapa de Karnaugh de 3 variables tendría un total de 23 = 8 celdas y uno de 4 variables tendría 24 = 16 celdasAB

C0 1

00

01

11

10

ABCD

00

01

11

10

00 01 11 10

4


Adyacencia de celdasAdyacencia de celdas� Las celdas de un mapa de Karnaugh se disponen de manera que entre dos celdas adyacentes sólo cambie el valor de una única variable (sólo cambia 1 bit)� Físicamente, cada celda es adyacente a las que están situadas inmediatamente junto a cualquiera de sus cuatro lados� Una celda no es adyacente a aquellas que tocan diagonalmente alguna de sus esquinas


Adyacencia de celdasAdyacencia de celdas� Además existe adyacencia cíclica� Las celdas de la fila inferior son adyacentes a la superior� Las celdas de la columna izquierda son adyacentes a la derecha� Podemos pensar que el mapa de Karnaugh se dobla como si fuera un cilindro, de manera que se toquen los extremos inferior-superior o izquierda-derecha

5




MinimizaciMinimizacióón de la suma de productosn de la suma de productos� Una expresión suma de productos minimizada por el método de Karnaugh estará formada por el mínimo número de términos producto posible� Además, cada término producto de una expresión minimizada estará compuesto por el mínimo número posible de variables� Esta simplificación dará lugar a una expresión que, en general, podrá ser implementada usando menos puertas lógicas de las que necesitaría su forma canónica

6


GeneraciGeneracióón del mapa de la suma de productosn del mapa de la suma de productos� Lo más conveniente para generar el mapa de Karnaugh de una expresión suma de productos es que la expresión esté en forma canónica� El primer paso de este proceso es colocar un 1 en la celda correspondiente a cada combinación de valores de las variables que hagan valer 1 a algún término producto � Cuando se haya terminado, el mapa tendrá tantas celdas con un 1 como términos producto haya en la expresión� Las celdas vacías son aquellas para las que la expresión vale 0, aunque no es necesario escribirlos


GeneraciGeneracióón del mapa de la suma de productosn del mapa de la suma de productos� Ejemplo: ABC + ABC + ABC + ABC

ABC 0 1

00

01

11

10

001 110 100

1 1

1

1

000

7


GeneraciGeneracióón del mapa de la suma de productosn del mapa de la suma de productos� Ejemplo: ABC + ABC + ABC + ABC

ABC 0 1

00

01

11

10

010 110 111

1

1

1 1

001


GeneraciGeneracióón del mapa de la suma de productosn del mapa de la suma de productos� Ejemplo: ABCD + ABCD + ABCD + ABCD

ABCD

00

01

11

10

0011 0100 1111

1

1

1

000110110100

1

8


SimplificaciSimplificacióón de la suma de productosn de la suma de productos� La minimización de una suma de productos comienza agrupando los 1 que estén situados en celdas adyacentes del mapa� Un grupo debe contener el mayor número posible de celdas▫ Toda celda del grupo debe ser adyacente a otra celda del grupo▫ El número de celdas de cada grupo debe ser potencia de dos� Cada 1 del mapa debe estar incluido en al menos un grupo, aunque un 1 puede estar incluido en varios grupos solapados� Puede haber varias agrupaciones válidas posibles, pero siempre teniendo en cuenta que el objetivo final de este proceso es maximizar el tamaño de los grupos al mismo tiempo que se trata de minimizar el número de grupos


SimplificaciSimplificacióón de la suma de productosn de la suma de productos� Ejemplos:AB

C 0 1

00

01

11

10

1

1

1 1

ABC 0 1

00

01

11

10

1 1

1

1

1

1

9


SimplificaciSimplificacióón de la suma de productosn de la suma de productos� Cada grupo de celdas da lugar a un término producto compuesto por todas las variables que aparecen en el grupo con un único valor� Las variables que aparecen con dos valores distintos en un grupo no se tienen en cuenta� La expresión mínima en forma de suma de productos se obtiene sumando todos los términos producto obtenidos a partir de los grupos del mapa


SimplificaciSimplificacióón de la suma de productosn de la suma de productos� Ejemplo:AB

C 0 1

00

01

11

10

1

1

1 1

AB + BC + ABCBC

AB

ABC

10



C 0 1

00

01

11

10

1 1

1

1

1

1

B

AC

AC

B + AC + AC



CD

00

01

11

10

1

1

1

10110100

1

1

1

1

1

1

1

1

D

BC

ABC

ABC + BC + D

11


ObtenciObtencióón a partir de la tabla de verdadn a partir de la tabla de verdad� Los 1 de una tabla de verdad se pueden trasladar directamente a un mapa de Karnaugh� Por ejemplo: F(A,B,C) = ∑(0,4,6,7)

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

000

0

A B C

1

1

11

� ABC� ABC� ABC

� ABC

ABC 0 1

00

01

11

10

1

1

1 1

0)

1)

2)

3)

4)

5)

6)

7)


ObtenciObtencióón a partir de la tabla de verdadn a partir de la tabla de verdad� El mapa generado nos permite obtener la forma minimizada de la funciónAB

C 0 1

00

01

11

10

1

1

1 1Forma canónica:

ABC + ABC + ABC + ABC

BC

AB

Forma minimizada:

AB + BC

12




MinimizaciMinimizacióón del producto de sumasn del producto de sumas� Una expresión producto de sumas minimizada por el método de Karnaugh estará formada por el mínimo número de términos suma posible� Además, cada término suma de una expresión minimizada estará compuesto por el mínimo número posible de variables� Esta simplificación dará lugar a una expresión que, en general, podrá ser implementada usando menos puertas lógicas de las que necesitaría su forma canónica

13


GeneraciGeneracióón del mapa del producto de sumasn del mapa del producto de sumas� Lo más conveniente para generar el mapa de Karnaugh de una expresión producto de sumas es que la expresión esté en forma canónica� El primer paso de este proceso es colocar un 0 en la celda correspondiente a cada combinación de valores de las variables que hagan valer 0 a algún término suma � Cuando se haya terminado, el mapa tendrá tantas celdas con un 0 como términos suma haya en la expresión� Las celdas vacías son aquellas para las que la expresión vale 1, aunque no es necesario escribirlos


GeneraciGeneracióón del mapa del producto de sumasn del mapa del producto de sumas� Ejemplo: (A+B+C)(A+B+C)(A+B+C)(A+B+C)

ABC 0 1

00

01

11

10

010 110 101

0

0

0

0

000

14


GeneraciGeneracióón del mapa del producto de sumasn del mapa del producto de sumas� Ejemplo: (A+B+C+D)(A+B+C+D)(A+B+C+D)

ABCD

00

01

11

10

0101 1111

0

0

001110110100

0


SimplificaciSimplificacióón del producto de sumasn del producto de sumas� La minimización de un producto de sumas comienza agrupando los 0 que estén situados en celdas adyacentes del mapa� Un grupo debe contener el mayor número posible de celdas▫ Toda celda del grupo debe ser adyacente a otra celda del grupo▫ El número de celdas de cada grupo debe ser potencia de dos� Cada 0 del mapa debe estar incluido en al menos un grupo, aunque un 0 puede estar incluido en varios grupos solapados� Puede haber varias agrupaciones válidas posibles, pero siempre teniendo en cuenta que el objetivo final de este proceso es maximizar el tamaño de los grupos al mismo tiempo que se trata de minimizar el número de grupos

15


SimplificaciSimplificacióón del producto de sumasn del producto de sumas� Ejemplos:AB

C 0 1

00

01

11

10

0 0

0

0

ABC 0 1

00

01

11

10

0 0

0

0

0


SimplificaciSimplificacióón del producto de sumasn del producto de sumas� Cada grupo de celdas da lugar a un término suma compuesto por todas las variables que aparecen en el grupo con un único valor� Las variables que aparecen con dos valores distintos en un grupo no se tienen en cuenta� La expresión mínima en forma de producto de sumas se obtiene multiplicando todos los términos suma obtenidos a partir de los grupos del mapa

16


SimplificaciSimplificacióón del producto de sumasn del producto de sumas� Ejemplo:(A+B)(A+C)(A+C)

ABC 0 1

00

01

11

10

0 0

0

0

0

A+B

A+C

A+C


SimplificaciSimplificacióón del producto de sumasn del producto de sumas� Ejemplo:AB

C 0 1

00

01

11

10

0 0

0

0

(A+C)(B+C)

B+C

A+C

17


SimplificaciSimplificacióón del producto de sumasn del producto de sumas� Ejemplo:AB

CD

00

01

11

10

0

0

0

10110100

0

0

0

0

0

C

B+D

C(B+D)

0

0


ObtenciObtencióón a partir de la tabla de verdadn a partir de la tabla de verdad� Los 0 de una tabla de verdad se pueden trasladar directamente a un mapa de Karnaugh� Por ejemplo: F(A,B,C) = ∏(1,2,3,5)

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

1

1

11

A B C

000

0

� A+B+C� A+B+C� A+B+C

ABC 0 1

00

01

11

10

0

0

0

0)

1)

2)

3)

4)

5)

6)

7)

0� A+B+C

18


ObtenciObtencióón a partir de la tabla de verdadn a partir de la tabla de verdad� El mapa generado nos permite obtener la forma minimizada de la funciónAB

C 0 1

00

01

11

10

0

0

0 0

Forma canónica:

(A+B+C)(A+B+C)(A+B+C)(A+B+C)

B+C

A+B

Forma minimizada:

(A+B)(B+C)


0

ConversiConversióón entre formas estn entre formas estáándarndar� La conversión entre suma de productos y producto de sumas es sencilla utilizando un mapa de Karnaugh, ya que donde no hay un 1 hay un 0 y viceversaAB

C 0 1

00

01

11

10

1

11 1F(A,B,C) = ∑(0,4,6,7)

F(A,B,C) = ∏(1,2,3,5)

ABC 0 1

00

01

11

10

0

0

0

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

10001011

A B C

0)

1)

2)

3)

4)

5)

6)

7)

19




Funciones incompletamente especificadasFunciones incompletamente especificadas� En algunas situaciones hay combinaciones de las variables de entrada que no están permitidas� Dado que estas combinaciones no ocurren nunca, se las puede considerar como términos indiferentes a efectos de calcular el valor de la salida� Esto significa que a la celda del mapa de Karnaugh correspondiente a un término indiferente le podemos asignar tanto un 0 como un 1, según convenga

20


Indiferencias en la suma de productosIndiferencias en la suma de productos� Los términos indiferentes se representan con una X, por ejemplo:A B C D

0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1

111

ABCD

00

01

11

10

x

10110100

ABC

1

x

1

x

x

x

x

1

+ ABCD

x

F(A,B,C,D) = ∑(7,8,9) + ∑x(0,10,11,12,13,14,15)

X

XXXXXX

000000

0)1)2)3)4)5)6)7)8)9)

10)11)12)13)14)15)


Indiferencias en la suma de productosIndiferencias en la suma de productos� Los términos indiferentes pueden aprovecharse para simplificar la función si suponemos que valen 1A B C D

0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1

ABCD

00

01

11

10

x

10110100

A

1

x

1

x

x

x

x

1

+ BCD

x

0)1)2)3)4)5)6)7)8)9)

10)11)12)13)14)15)

111

X

XXXXXX

000000

21


Indiferencias en el producto de sumasIndiferencias en el producto de sumas� En un producto de sumas también puede haber términos indiferentes:A B C D

0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1

0000

ABCD

00

01

11

10

x

10110100

(A+B+C)

0

x

0

x

x

x

x

0

(A+B+C)

x

0

F(A,B,C,D) = ∏(6,7,8,9) + ∏x(0,10,11,12,13,14,15)

0)1)2)3)4)5)6)7)8)9)

10)11)12)13)14)15)

X

XXXXXX

11111


Indiferencias en el producto de sumasIndiferencias en el producto de sumas� Los términos indiferentes pueden aprovecharse para simplificar la función si suponemos que valen 0A B C D

0 0 0 00 0 0 10 0 1 00 0 1 10 1 0 00 1 0 10 1 1 00 1 1 11 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1

ABCD

00

01

11

10

x

10110100

A

0

x

0

x

x

x

x

0

(B+C)

x

0

0)1)2)3)4)5)6)7)8)9)

10)11)12)13)14)15)

0000

X

XXXXXX

11111

22




Circuitos con salida mCircuitos con salida múúltipleltiple� Con frecuencia, los circuitos digitales tienen múltiples salidas, cada una representada por funciones lógicas diferentes pero que dependen de las mismas entradas� Si se simplificaran las funciones por separado no se tendría la seguridad de obtener el circuito mínimo, ya que puede que varias funciones se solapen� Por lo tanto hay que simplificar las funciones de forma conjunta, intentando buscar términos comunes a las funciones para minimizar el circuito total

23


MMéétodo de Karnaugh para multitodo de Karnaugh para multi--funcionesfunciones� La minimización de multifunciones usando el método de Karnaugh puede realizarse generando los mapas para cada función individual y para combinaciones de ellas� Por ejemplo, un circuito con tres salidas puede simplificarse dando los siguientes pasos:� Buscar los términos que sean comunes a las tres funciones� Buscar los términos que sean comunes a dos de las funciones y que no estén cubiertos en el paso anterior� Buscar los términos que aparecen únicamente en una función y que no estén cubiertos en el paso anterior


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� Aquí podemos ver un ejemplo de 3 funciones:0001

11

10

00 01 11 10

1

00

011110

00 01 11 10

0001

11

10

00 01 11 10

ABCD

ABCD

F1

F2

F3

1

1111

1

111

1

1 111 11

1

F1(A,B,C,D) = ∑(5,6,9,12,13,14,15)

F2(A,B,C,D) = ∑(0,4,8,9,11,12,13,15)

F3(A,B,C,D) = ∑(3,5,6,7,13,14,15)

11

11

ABCD

24


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� Se calculan los productos posibles de las funciones00

0111

10

00 01 11 10

1

ABCD

00

0111

10

00 01 11 10

00

0111

10

00 01 11 10

ABCD

ABCD

F1

F2

F3

1

1111

1

1 111 11

1

1

1

1 111 11

00

0111

10

00 01 11 10ABCD

F1F2 111

1

00

0111

10

00 01 11 10

1

ABCD

F1F31111

00

0111

10

00 01 11 10ABCD

F2F3 11

00

0111

10

00 01 11 10ABCD

F1F2F3 11

� En cada producto hay que detectar las combinaciones que no se cubren en productos superiores que los incluyan


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� La función F1 no tiene ningún término que sólo aparezca en ellaAB

CD

00

01

11

10

1

10110100

1

1

1 1

1 1F1

25


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� En la función F2 existen términos que sólo aparecen en ella, por lo que debemos cubrirlos obteniendo la mínima expresión posibleAB

CD

00

01

11

10

1

10110100

1

1

1

1

1

1CD

1

+ ADF2


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� En la función F3 existen términos que sólo aparecen en ella, por lo que debemos cubrirlos obteniendo la mínima expresión posibleAB

CD

00

01

11

10

1

10110100

1

1 1 1

1ACD

1

F3

26


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� El producto de funciones F1F2 tiene términos comunes a las dos funciones pero que no aparecen en las tres, asíque se cubren obteniendo la mínima expresión posibleAB

CD

00

01

11

10

1

10110100

1

1

1F1 F2 ACD + ABC


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� El producto de funciones F1F3 tiene términos comunes a las dos funciones pero que no aparecen en las tres, asíque se cubren obteniendo la mínima expresión posibleAB

CD

00

01

11

10

1

10110100

1

1

1F1 F3 BCD + BCD

1

27


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� El producto de funciones F2F3 no tiene términos que sean comunes a las dos funciones pero que no aparezcan en las tresAB

CD

00

01

11

10

10110100

1 1F2F3


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� El producto de funciones F1F2F3 tiene términos comunes a las tres funciones, por lo que hay que cubrirlos obteniendo la mínima expresión posibleAB

CD

00

01

11

10

10110100

1 1F1F2F3 ABD

28


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� A partir de los mapas anteriores podemos obtener las expresiones de las tres funcionesACD + ABCF1 =

F1F2

+ BCD+ BCD

F1F3

+ ABD

F1F2F3

F2 = CD + AD

F2

+ ACD+ ABC

F1F2

+ ABD

F1F2F3

F3 = ACD

F3

+ BCD+ BCD

F1F3

+ ABD

F1F2F3


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� Todos los términos de la expresión obtenida para la función F1 son necesarios, ya que cada uno de ellos es el único que cubre al menos una de las combinacionesACD + ABCF1 = + BCD+ BCD + ABD

F1(A,B,C,D) = ∑(5,6,9,12,13,14,15)

ACD � 9,13

ABC � 12,13

BCD � 5,13

BCD � 6,14

ABD � 13,15

29


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� Los dos primeros términos de la función F1 son necesarios, ya que cada uno de ellos es el único que cubre al menos una de las combinaciones� Estos dos términos son suficientes para cubrir todas las combinaciones, por lo que los demás no son necesariosCD � 0,4,8,12

AD � 9,11,13,15

ABD � 13,15

F2(A,B,C,D) = ∑(0,4,8,9,11,12,13,15)

F2 = CD + AD + ACD+ ABC + ABD

ACD � 9,13

ABC � 12,13


SimplificaciSimplificacióón de multin de multi--funcionesfunciones� Todos los términos de la expresión obtenida para la función F3 son necesarios, ya que cada uno de ellos es el único que cubre al menos una de las combinaciones� Tres de los términos coinciden con los de la función F1, por lo que no se necesitarán puertas lógicas adicionalesACD � 3,7

BCD � 5,13

BCD � 6,14

ABD � 13,15

F3 = ACD + BCD+ BCD + ABD

F3(A,B,C,D) = ∑(3,5,6,7,13,14,15)√ √√

30




Funciones con mFunciones con máás de cuatro variabless de cuatro variables� Las funciones booleanas de cinco variables pueden simplificarse usando un mapa de Karnaugh de 32 celdas� Para poder mantener la adyacencia será necesario representar este mapa de 32 celdas usando dos mapas de 16 celdas cada unoBC

DE

00

01

11

10

00 01 11 10BCDE

00

01

11

10

00 01 11 10

A = 0 A = 1

31


Funciones con mFunciones con máás de cuatro variabless de cuatro variables� La mejor manera de visualizar la adyacencia entre los dos mapas es imaginar que el mapa para A = 0 está situado encima del mapa para A = 1BC

DE

00

01

11

10

00 01 11 10BCDE

00

01

11

10

00 01 11 10A = 0 A = 1

1

1

1

1

1 1

1 1 1

1 1

1� Obviamente, este procedimiento complica mucho la simplificación, a parte de que sería todavía más difícil simplificar funciones con más de cinco variablesADE

BCE

ACDE

BCD



32


ResumenResumen� La expresión minimizada de un circuito será aquella que requiera un menor número de puertas y, por tanto, requerirá un menor coste de implementación, sufrirá un retardo menor y consumirá menos energía � El método de Karnaugh permite obtener, de forma sistemática, la función lógica mínima que representa un circuito digital� Este método permite trabajar con funciones incompletamente especificadas y con funciones de salida múltiple, aprovechando sus características particulares para minimizar aún más las funciones


BibliografBibliografííaaFundamentos de Sistemas Digitales (7ª edición)Capítulo 4Thomas L. FloydPrentice Hall, 2000Principios de Diseño DigitalCapítulo 4Daniel D. GajskiPrentice Hall, 1997Sistemas Electrónicos DigitalesCapítulo 3Enrique MandadoMarcombo, 1991

td2-tema07 karnaugh

Documents