Mapa de Karnaugh

En el ejemplo anterior, las cuatro variables de entrada se pueden combinar de 16 maneras diferentes, por lo que la tabla de verdad tiene 16 filas y el mapa de Karnaugh tiene 16 posiciones. Por lo tanto, el mapa de Karnaugh está organizado en una cuadrícula de 4  ×  4.

Los índices de fila y columna (mostrados en la parte superior y en el lado izquierdo del mapa de Karnaugh) están ordenados según el código Gray, en lugar de seguir un orden numérico binario. El código Gray garantiza que solo una variable cambie entre cada par de celdas adyacentes. Cada celda del mapa de Karnaugh completo contiene un dígito binario que representa el resultado de la función para esa combinación de entradas.

Una vez construido el mapa de Karnaugh, se utiliza para encontrar una de las formas más simples posibles —una forma canónica— para la información de la tabla de verdad. Los 1 adyacentes en el mapa de Karnaugh representan oportunidades para simplificar la expresión. Los minterms («términos mínimos») para la expresión final se encuentran rodeando grupos de 1 en el mapa. Los grupos de minterms deben ser rectangulares y tener un área que sea potencia de dos (es decir, 1,  2,  4,  8...). Los rectángulos de minterms deben ser lo más grandes posible sin contener ningún 0. Los grupos pueden superponerse para aumentar su tamaño. Las agrupaciones óptimas en el ejemplo siguiente están marcadas con líneas verdes, rojas y azules, y los grupos rojo y verde se superponen. El grupo rojo es un cuadrado de 2  ×  2, el grupo verde es un rectángulo de 4  ×  1, y el área de superposición se indica en marrón.

Las celdas suelen representarse mediante una abreviatura que describe el valor lógico de las entradas que abarcan. Por ejemplo, AD significaría una celda que cubre el área de 2x2 donde A y D son verdaderas, es decir, las celdas numeradas 13, 9, 15 y 11 en el diagrama anterior. Por otro lado, A D significaría las celdas donde A es verdadera y D es falsa (es decir, D es verdadera).

La cuadrícula está conectada toroidalmente , lo que significa que los grupos rectangulares pueden extenderse a través de los bordes (ver imagen). Las celdas del extremo derecho son en realidad "adyacentes" a las del extremo izquierdo, en el sentido de que los valores de entrada correspondientes difieren solo en un bit; de manera similar, lo mismo ocurre con las celdas de la parte superior e inferior. Por lo tanto, AD puede ser un término válido: incluye las celdas 12 y 8 en la parte superior y se extiende hasta la parte inferior para incluir las celdas 10 y 14, al igual que BD , que incluye las cuatro esquinas.

Una vez construido el mapa de Karnaugh y vinculados los 1 adyacentes mediante cajas rectangulares y cuadradas, se pueden hallar los minitérminos algebraicos examinando qué variables permanecen iguales dentro de cada caja.

Para el grupo rojo:

• A es la misma y es igual a 1 en toda la caja, por lo tanto, debe incluirse en la representación algebraica del minitérmino rojo.
• B no mantiene el mismo estado (pasa de 1 a 0) y, por lo tanto, debe excluirse.
• C no cambia. Siempre es 0, por lo que su complemento, NOT-C, debe incluirse. Por lo tanto, C debe incluirse.
• D cambia, por lo que queda excluido.

Por lo tanto, el primer minterm en la expresión booleana de suma de productos es A C .

Para el grupo verde, A y B mantienen el mismo estado, mientras que C y D cambian. B es 0 y debe negarse antes de poder incluirse. Por lo tanto, el segundo término es AB . Cabe señalar que es aceptable que el grupo verde se solape con el rojo.

De la misma manera, la agrupación azul da el término BC D .

Las soluciones de cada grupo se combinan: la forma normal del circuito es${\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}}$.

Así, el mapa de Karnaugh ha guiado una simplificación de

${\displaystyle {\begin{aligned}f(A,B,C,D)={}&{\overline {A}}BC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}C{\overline {D}}+{}\\&A{\overline {B}}CD+AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABC{\overline {D}}\\={}&A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}\end{aligned}}}$

También habría sido posible obtener esta simplificación aplicando cuidadosamente los axiomas del álgebra booleana , pero el tiempo que lleva hacerlo crece exponencialmente con el número de términos.

La inversa de una función se resuelve de la misma manera, agrupando los 0 en su lugar. ^{[ nb 1 ]}

Los tres términos para cubrir la inversa se muestran con recuadros grises con bordes de diferentes colores:

• marrón : A B
• oro : A C
• azul : BCD

Esto produce el inverso:

${\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}$

Mediante el uso de las leyes de De Morgan , se puede determinar el producto de sumas :

${\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {BCD}}\right)\\&=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)\end{aligned}}}$

Los mapas de Karnaugh también facilitan la minimización de funciones cuyas tablas de verdad incluyen condiciones de " indiferencia ". Una condición de "indiferencia" es una combinación de entradas cuyo resultado no le importa al diseñador. Por lo tanto, estas condiciones pueden incluirse o excluirse de cualquier grupo rectangular, según cuál lo haga más grande. Generalmente se indican en el mapa con un guion o una X.

El ejemplo de la derecha es idéntico al anterior, pero con el valor de f (1,1,1,1) reemplazado por un "no importa". Esto permite que el término rojo se expanda completamente hacia abajo y, por lo tanto, elimina por completo el término verde.

Esto da como resultado la nueva ecuación mínima:

${\displaystyle f(A,B,C,D)=A+BC{\overline {D}}}$

Nótese que el primer término es simplemente A , no AC . En este caso, la opción "no importa " ha omitido un término (el rectángulo verde); simplificado otro (el rojo); y eliminado el riesgo de carrera (eliminando el término amarillo como se muestra en la siguiente sección sobre riesgos de carrera).

El caso inverso se simplifica de la siguiente manera:

${\displaystyle {\overline {f(A,B,C,D)}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}D}$

Mediante el uso de las leyes de De Morgan , se puede determinar el producto de sumas :

${\displaystyle {\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+{\overline {A}}\,D}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {{\overline {A}}\,D}}\right)\\&=\left(A+B\right)\left(A+C\right)\left(A+{\overline {D}}\right)\end{aligned}}}$

Los mapas de Karnaugh son útiles para detectar y eliminar condiciones de carrera . Los riesgos de carrera son muy fáciles de identificar con un mapa de Karnaugh, ya que una condición de carrera puede existir al moverse entre cualquier par de regiones adyacentes, pero disjuntas, circunscritas en el mapa. Sin embargo, debido a la naturaleza de la codificación Gray, el término "adyacente" tiene una definición especial, explicada anteriormente: de hecho, nos movemos sobre un toroide, en lugar de un rectángulo, rodeando la parte superior, inferior y los lados.

• En el ejemplo anterior , existe una posible condición de carrera cuando C y D son 0, A es 1 y B cambia de 1 a 0 (pasando del estado azul al verde). En este caso, la salida se define para que permanezca sin cambios en 1, pero como esta transición no está contemplada en un término específico de la ecuación, existe la posibilidad de un fallo (una transición momentánea de la salida a 0).
• En el mismo ejemplo, existe un segundo posible fallo más difícil de detectar: ​​cuando D es 0 y A y B son ambos 1, y C cambia de 1 a 0 (pasando del estado azul al rojo). En este caso, el fallo se repite desde la parte superior del mapa hasta la inferior.

Que se produzcan fallos depende de la naturaleza física de la implementación, y que debamos preocuparnos por ello depende de la aplicación. En la lógica síncrona, basta con que la lógica alcance el valor deseado a tiempo para cumplir con el plazo establecido. En nuestro ejemplo, no consideramos la lógica síncrona.

En nuestro caso, un término adicional de${\displaystyle A{\overline {D}}}$Esto eliminaría el riesgo potencial de carrera, estableciendo un puente entre los estados de salida verde y azul o los estados de salida azul y rojo: esto se muestra como la región amarilla (que se extiende desde la parte inferior hasta la parte superior de la mitad derecha) en el diagrama adyacente.

El término es redundante en términos de la lógica estática del sistema, pero este tipo de términos redundantes, o de consenso , suelen ser necesarios para garantizar un rendimiento dinámico sin condiciones de carrera.

De manera similar, un término adicional de${\displaystyle {\overline {A}}D}$debe agregarse al inverso para eliminar otro posible riesgo de carrera. La aplicación de las leyes de De Morgan crea otra expresión de producto de sumas para f , pero con un nuevo factor de${\displaystyle \left(A+{\overline {D}}\right)}$.

 A continuación se muestran todos los posibles mapas de Karnaugh de 2 × 2 con 2 variables  . Junto a cada uno se enumeran los minitérminos en función de${\textstyle \sum m()}$y la ecuación mínima libre de riesgo de carrera ( ver sección anterior ). Un minterm se define como una expresión que da la forma más mínima de expresión de las variables mapeadas. Se pueden formar todos los bloques interconectados horizontales y verticales posibles. Estos bloques deben ser del tamaño de potencias de 2 (1, 2, 4, 8, 16, 32, ...). Estas expresiones crean un mapeo lógico mínimo de las expresiones de variables lógicas mínimas para las expresiones binarias que se van a mapear. Aquí están todos los bloques con un campo.

Un bloque puede extenderse por la parte inferior, superior, izquierda o derecha del gráfico. Incluso puede sobrepasar el borde del gráfico para minimizar las variables. Esto se debe a que cada variable lógica corresponde a cada columna vertical y fila horizontal. La visualización del mapa de Karnaugh puede considerarse cilíndrica. Los campos en los bordes izquierdo y derecho son adyacentes, al igual que los de la parte superior e inferior. Los mapas de Karnaugh para cuatro variables deben representarse como una rosquilla o un toroide. Las cuatro esquinas del cuadrado dibujado por el mapa de Karnaugh son adyacentes. Se necesitan mapas aún más complejos para cinco variables o más.

• 
  Σ m (0); K = 0
• 
  Σ m (1); K = A ′ B ′
• 
  Σ m (2); K = AB ′
• 
  Σ m (3); K = A ′ B
• 
  Σ m (4); K = AB
• 
  Σ m (1,2); K = B ′
• 
  Σ m (1,3); K = A ′
• 
  Σ m (1,4); K = A ′ B ′ + AB
• 
  Σ m (2,3); K = AB ′ + A ′ B
• 
  Σ m (2,4); K = A
• 
  Σ m (3,4); K = B
• 
  Σ m (1,2,3); K = A' + B ′
• 
  Σ m (1,2,4); K = A + B ′
• 
  Σ m (1,3,4); K = A ′ + B
• 
  Σ m (2,3,4); K = A + B
• 
  Σ m (1,2,3,4); K = 1