Mapas de Karnaugh

Un mapa de Karnaugh (también conocido como tabla de Karnaugh o diagrama de Veitch) es un diagrama utilizado para la simplificación de funciones algebraicas en forma canónica. A partir de la tabla de Karnaugh se puede obtener una forma canónica mínima (con el mínimo número de términos). En este texto emplearemos indistintamente los términos “mapa” y “tabla” de Karnaugh.

La tabla de Karnaugh consiste en una representación bidimensional de la función que se quiere simplificar. Si la función viene expresada como una tabla de verdad, entonces la tabla de Karnaugh puede verse como una forma alternativa de representación 2D. Puesto que la tabla de verdad de una función de n variables posee 2n filas, la tabla de Karnaugh correspondiente debe poseer también 2n celdas. La construcción de la tabla de Karnaugh pasa por codificar cada celda en código binario reflejado (o código Gray) de manera que celdas adyacentes tengan un código que difiere en un solo dígito.

figura 1

En la Fig. 1 puede verse un ejemplo de codificación Gray para el caso de funciones lógicas de 4 variables. Cada variable lógica (A, B, C, D en la figura) se corresponde con un bit del código Gray.

En la práctica, no es necesario explicitar el código de cada celda; basta con expresar las cabeceras de las filas y columnas en código Gray (el código de la celda se construye combinando la fila y columna correspondiente), según se desprende de la figura.

Simplificación de una función lógica expresada en DNF

1.   Un grupo está formado por un número variable de celdas con valor ‘1’.

2.   El número de celdas con valor ‘1’ dentro de un grupo debe ser potencia de dos: 1, 2, 4, 8, 16.

3.   A efectos de la formación de grupos se debe considerar la tabla como toroidal, pues los extremos de la tabla son adyacentes: el extremo derecho es adyacente al izquierdo, y el inferior al superior. Se puede apreciar mejor en la Fig. 2.

4.   Todas las celdas con valor ‘1’ deben pertenecer al menos a un grupo.

5.   Una celda con valor ‘1’ puede pertenecer a varios grupos distintos.

6.   El número de grupos debe ser mínimo.

7.   Cuanto mayor sea el tamaño del grupo, mayor será la simplificación, tanto en número de términos como en número de literales por cada término.

8.   No es necesario que todos los grupos tengan el mismo tamaño.

9.   Por último, puede darse el caso de que la función contenga alguna interpretación ‘x’ que no sea posible (por ejemplo, por representar parte de un sistema físico con combinaciones de entradas que son físicamente imposibles). A las celdas correspondientes a esas interpretaciones se les asigna un valor ‘x’. Dichas celdas no tienen por qué pertenecer a ningún grupo, pero pueden emplearse para agrandar grupos ya existentes.

figura 2

En segundo lugar, cada grupo generará un minitérmino en la función mínima resultante. Ese minitérmino estará formado por aquellos literales comunes dentro del grupo correspondiente, con signo negativo o positivo si toman el valor ‘0’, o ‘1’ en la codificación Gray. Los literales que aparecen con códigos distintos en el grupo se eliminan.

La función resultante DNF, compuesta por la suma de los minitérminos correspondientes de cada grupo, es mínima.

Ventajas del mapa de Karnaugh

• El mapa-k nos permite convertir la tabla de verdad de una ecuación booleana en una forma SOP(Suma de productos) o POS(Productos de suma) minimizada.
• Reglas básicas y sencillas para la simplificación.
• La facilidad del método permite que sea más rápido y más eficiente que otras técnicas de simplificación en el Álgebra de Boole.

Reglas del mapa de Karnaugh

• Las agrupaciones o el término a considerar únicamente será del número “1”

• Las agrupaciones únicamente se deben hacer en horizontal y vertical.
• Las agrupaciones a considerar deben contener 2n elementos. Es decir cada agrupación que contiene cada grupo tendrá 1, 2, 4,8,…, 2n cantidad de número de uno o unos.

• Para una mejor simplificación se debe considerar el grupo más grande posible.

• Se debe considerar todo número “1”

• Es posible solapar grupos de “1”

• La formación de grupos también se pueden producir con las celdas extremas de la tabla.
• Debemos considerar el menor número de agrupaciones o grupos posibles obedeciendo las reglas anteriores.