Mapas de Karnaugh: simplificación booleana visual

TL;DR: Un mapa de Karnaugh (K-map) dispone una tabla de verdad en una cuadrícula 2D codificada en Gray donde las celdas adyacentes difieren en una sola variable. Agrupar los 1 adyacentes en rectángulos cuyo tamaño sea potencia de dos produce directamente expresiones mínimas en Suma de Productos, sin álgebra. Los K-maps minimizan de forma fiable funciones de hasta 4 variables; para 5-6 se usa Quine–McCluskey, y más allá, síntesis algorítmica al estilo ESPRESSO.

La simplificación algebraica usando las leyes de Boole funciona, pero depende de detectar la factorización correcta en el momento correcto. Si se te escapa una oportunidad, terminas con un resultado subóptimo. Para expresiones de cuatro o más variables, el número de manipulaciones posibles explota.

El mapa de Karnaugh (K-map) resuelve este problema convirtiendo la simplificación algebraica en reconocimiento visual de patrones. Desarrollado en 1953 por el físico de Bell Labs Maurice Karnaugh, organiza una tabla de verdad en una cuadrícula bidimensional donde las celdas adyacentes difieren exactamente en una variable. Agrupar los 1 adyacentes en la cuadrícula produce directamente expresiones mínimas en Suma de Productos: no se requiere manipulación algebraica.

Diagrama del componente puerta AND

La tabla de verdad visual: ¿qué es un K-map?

En esencia, un mapa de Karnaugh es una tabla de verdad disfrazada. Mientras que una tabla de verdad lista entradas y salidas de forma lineal y vertical, el K-map las redistribuye en una cuadrícula bidimensional. Esto no es solo cuestión de estética. El genio del K-map reside en la disposición específica de sus celdas.

En una tabla de verdad estándar, las filas siguen un conteo binario (00, 01, 10, 11). En un K-map, las filas y columnas siguen una secuencia conocida como código Gray. En una secuencia de código Gray, cada número adyacente —ya muevas horizontal o verticalmente— difiere en un solo bit. Esta propiedad, conocida como adyacencia lógica, es el motor que impulsa la simplificación. Cuando agrupas celdas adyacentes que contienen ‘1’, identificas visualmente las variables que cambian (y por tanto no afectan al resultado) y las eliminas, dejando un término booleano mínimo.

Antes de zambullirnos en los mapas de 4 variables que se usan en el diseño moderno de ALU, veamos el mapa fundamental de 2 variables para las entradas $A$ y $B$ . Consta de $2^2 = 4$ celdas, que representan los cuatro mintérminos posibles.

	$B=0$ ( $\overline{B}$ )	$B=1$ ( $B$ )
$A=0$ ( $\overline{A}$ )	$m_0$ ( $\overline{A}\overline{B}$ )	$m_1$ ( $\overline{A}B$ )
$A=1$ ( $A$ )	$m_2$ ( $A\overline{B}$ )	$m_3$ ( $AB$ )

Observa la adyacencia: al pasar de $m_0$ a $m_1$ solo cambia la variable $B$ . Al pasar de $m_1$ a $m_3$ solo cambia la variable $A$ . Esta proximidad física en la cuadrícula representa una relación lógica que podemos explotar para reducir el número de puertas.

Mira la lógica básica en acción

El arte de agrupar: del mapa a la lógica mínima

El objetivo al usar un K-map es cubrir todos los ‘1’ del mapa con los grupos rectangulares más grandes posibles. Pero hay una trampa: el número de celdas de cada grupo debe ser potencia de dos (1, 2, 4, 8, 16, etc.). Cada grupo que dibujas corresponde a un término producto simplificado. Tu expresión final optimizada es simplemente la “Suma de Productos” (un OR sobre los resultados de esos grupos).

Las reglas de agrupamiento son estrictas pero sencillas. Seguirlas mecánicamente garantiza un resultado mínimo.

Cubre cada ‘1’: todo ‘1’ del mapa debe pertenecer al menos a un grupo. Ningún ‘1’ puede quedar sin agrupar.
Solo potencias de dos: los grupos deben contener exactamente $2^k$ celdas: 1, 2, 4, 8 o 16. No se puede formar un grupo de 3, 5 o 6. Una región de seis 1s debe cubrirse mediante grupos solapados de 4 y 2.
Maximiza el tamaño del grupo: los grupos más grandes eliminan más variables. Un grupo de 2 elimina 1 variable; uno de 4 elimina 2; uno de 8 elimina 3. Busca siempre el mayor grupo posible primero.
Se permite el solapamiento: un mismo ‘1’ puede pertenecer a varios grupos. Usa el solapamiento de forma agresiva para crear grupos más grandes.
Solo forma rectangular: los grupos deben formar rectángulos (incluidos los cuadrados). Formas en L, en T o diagonales no son válidas.
El mapa se envuelve: la columna más a la izquierda es adyacente a la más a la derecha. La fila superior es adyacente a la inferior. Imagina el mapa como un toro: las cuatro esquinas son mutuamente adyacentes.

Profundizando: el K-map de 4 variables

Abordemos un escenario realista. Supongamos que estamos diseñando un trozo concreto de lógica para una CONTROL_UNIT que debe activar una señal cuando una entrada de 4 bits cumple condiciones específicas. Nuestra función es $F(A,B,C,D) = \Sigma m(0, 2, 5, 7, 8, 10, 13, 15)$ .

La notación $\Sigma m$ es solo abreviatura de “la salida está en HIGH cuando la entrada binaria es igual a estos valores decimales”. Primero rellenamos la cuadrícula de 16 celdas.

	$CD=00$	$CD=01$	$CD=11$	$CD=10$
$AB=00$	1 ( $m_0$ )	0	0	1 ( $m_2$ )
$AB=01$	0	1 ( $m_5$ )	1 ( $m_7$ )	0
$AB=11$	0	1 ( $m_{13}$ )	1 ( $m_{15}$ )	0
$AB=10$	1 ( $m_8$ )	0	0	1 ( $m_{10}$ )

Ahora buscamos patrones.

Grupo 1: las cuatro esquinas

Mira los ‘1’ en $m_0, m_2, m_8$ y $m_{10}$ . Como el mapa se envuelve tanto horizontal como verticalmente, ¡las cuatro esquinas son en realidad adyacentes! Forman un único grupo de cuatro.

Variable A: cambia de 0 a 1. (Descartar)
Variable B: permanece en 0. (Mantener $\overline{B}$ )
Variable C: cambia de 0 a 1. (Descartar)
Variable D: permanece en 0. (Mantener $\overline{D}$ )
Resultado: $\overline{B}\overline{D}$

Grupo 2: el bloque central

Tenemos un cuadrado 2x2 perfecto en el centro en $m_5, m_7, m_{13}$ y $m_{15}$ .

Variable A: cambia de 0 a 1. (Descartar)
Variable B: permanece en 1. (Mantener $B$ )
Variable C: cambia de 0 a 1. (Descartar)
Variable D: permanece en 1. (Mantener $D$ )
Resultado: $BD$

Todos los ‘1’ están cubiertos. Nuestra expresión simplificada final es:

F = \overline{B}\overline{D} + BD

Esta es la definición booleana de una puerta XNOR: un lío de ocho puertas AND de 4 entradas se reduce a un único componente.

Diagrama del componente puerta XNOR

Explora el circuito XNOR simplificado

Error común: por qué el código Gray es innegociable

Un error frecuente es dibujar K-maps usando el orden binario estándar: 00, 01, 10, 11. No lo hagas.

Si usas binario estándar, rompes el principio de adyacencia. Mira el salto de 01 a 10. Ambos bits cambian ( $0 \to 1$ y $1 \to 0$ ). Si tienes ‘1’ en esas dos celdas adyacentes, no puedes simplificarlas porque está cambiando más de una variable. La secuencia de código Gray (00, 01, 11, 10) asegura que cada paso en el mapa representa un cambio en exactamente una variable. Esa es la “magia” que permite que las matemáticas funcionen de forma visual. Sin código Gray, el K-map es solo una tabla confusa; con él, es una calculadora.

Verificación con el OSCILLOSCOPE_8CH

Uno de los momentos más satisfactorios de la ingeniería digital es demostrar que tu circuito “pequeño” hace exactamente lo mismo que el “grande”. En digisim.io puedes hacerlo en tiempo real.

Construye la fuerza bruta: usa ocho puertas AND y una OR enorme para representar los mintérminos originales.
Construye la versión optimizada: coloca debajo una sola puerta XNOR (o el equivalente con dos AND y una OR).
Sincroniza las entradas: conecta los mismos cuatro componentes INPUT_SWITCH a ambos circuitos.
Analiza: conecta la salida del circuito de fuerza bruta al canal 1 de un OSCILLOSCOPE_8CH y la salida optimizada al canal 2.

A medida que alternas los interruptores por las 16 combinaciones, las formas de onda en el OSCILLOSCOPE_8CH serán idénticas. Sin embargo, si miras el retardo de propagación ( $t_{pd}$ ), notarás que el circuito optimizado responde significativamente más rápido. En un proyecto de CPU de alta velocidad, esos nanosegundos son la diferencia entre un reloj de 1 MHz y uno de 10 MHz.

Aplicaciones en el mundo real: más allá del aula

Los K-maps no son solo para aprobar exámenes; son pan de cada día en la descripción de hardware.

1. Lógica de control de la ALU

En una CPU típica de 8 bits, la ALU (Unidad Aritmético-Lógica) necesita saber si debe sumar, restar o realizar una AND bit a bit en función de un “opcode”. Ese opcode puede tener 4 bits. Los ingenieros usan K-maps para diseñar la lógica decodificadora que toma ese opcode de 4 bits y activa las líneas de control específicas para el ADDER_8BIT o el COMPARATOR_8BIT. Al minimizar esa lógica reducen el tiempo de “decodificación de instrucción”, un cuello de botella crítico en el rendimiento de la CPU.

2. Máquinas de estados finitos (FSM)

Ya sea un controlador de semáforos o un manejador de protocolos complejos, las FSM se apoyan en lógica de “próximo estado”. Esa lógica observa el estado actual (almacenado en un REGISTER) y las entradas actuales para decidir cuál será el próximo estado. Esas tablas de verdad se vuelven enormes rápidamente. Los K-maps permiten a los diseñadores encontrar la forma más eficiente de enrutar esas señales, ahorrando a menudo decenas de puertas en la implementación final.

Diagrama del componente ALU

Errores comunes

Errores frecuentes que evitar:

Entradas flotantes: cada entrada de cada puerta AND debe estar conectada a algo. Una entrada flotante puede comportarse de forma predecible en un simulador, pero en hardware real recoge ruido.
Olvidar el “envoltorio”: revisa las esquinas y los bordes. Algunas de las simplificaciones más elegantes salen de agrupar las cuatro esquinas o las filas superior e inferior.
Grupos redundantes: una vez cubiertos todos los 1, para. Añadir un grupo extra “porque queda bonito” mete puertas innecesarias y derrota el propósito del K-map.

El poder de las condiciones don’t care

En muchos diseños reales, ciertas combinaciones de entrada nunca pueden ocurrir. Por ejemplo, un sistema BCD (Decimal Codificado en Binario) usa 4 bits para representar los dígitos 0-9, así que las combinaciones de 1010 a 1111 nunca aparecen. En un K-map, esas entradas imposibles se marcan con una $X$ (“don’t care”) en lugar de 0 o 1.

La clave: puedes tratar cada $X$ como 0 o 1, lo que te convenga para formar un grupo mayor. Como esas entradas nunca ocurren en la práctica, no importa lo que el circuito produzca para ellas.

Ejemplo: supón que una función de 4 variables tiene 1s en las celdas 0, 2, 8, 10 y don’t cares en las celdas 1 y 3. Sin los don’t cares, los cuatro 1 (esquinas) se agrupan en $\overline{B}\overline{D}$ . Pero tratando las celdas 1 y 3 como 1, puedes formar un grupo mayor de 4 en la fila superior ( $\overline{A}\overline{B}$ ) además del grupo original de las esquinas, lo que potencialmente da una expresión total más simple. Las condiciones don’t care suelen reducir el conteo final de puertas en un 20-30% en diseños reales.

Da el siguiente paso

Este artículo forma parte de la serie Boolean Algebra Fundamentals. Lectura relacionada:

Dominando el álgebra de Boole — las identidades algebraicas detrás del agrupamiento en K-maps.
Dominando la Suma de Productos (SOP) — la forma canónica que producen los K-maps.
Más allá de la SOP: Producto de Sumas — la minimización dual.
Las leyes de De Morgan — las reglas de transformación para convertir entre formas.

El mapa de Karnaugh convierte una tarea algebraica compleja en un rompecabezas visual. Para funciones de hasta 4 variables produce de forma fiable expresiones SOP (o POS) mínimas. Para 5–6 variables, los K-maps siguen siendo usables pero engorrosos; los métodos algorítmicos como Quine–McCluskey toman el relevo.

Construye los circuitos de fuerza bruta y optimizado del ejemplo trabajado, y observa cómo se alinean las formas de onda en el osciloscopio. Empieza un circuito nuevo para verificarlo.