Dominando Mapas de Karnaugh de 5 y 6 Variables para Diseño Lógico Eficiente

A medida que la lógica combinacional crece, el tamaño del mapa de Karnaugh se expande. Saber cuándo un mapa de 5 o 6 variables es apropiado —y cómo interpretar y agrupar sus celdas— puede reducir drásticamente el uso lógico en diseños FPGA y ASIC.

Altera (ahora parte de Intel) examinó miles de diseños de clientes para entender tamaños típicos de fan-in. La distribución resultante fue casi plana de dos a seis entradas, con un pico claro en cinco. En la práctica, la mayoría de circuitos usan no más de seis entradas, y el diseño promedio encaja cómodamente dentro de cinco.

Los propios datos de Altera, extraídos de su biblioteca de diseños de clientes, respaldan el valor de la heterogeneidad. Al examinar conos lógicos, mapearlos a nodos basados en LUT y ordenarlos por el número de entradas óptimo en cada nodo, Altera encontró que la distribución de fan-ins era casi plana entre dos y seis entradas, con un buen pico en cinco.

A continuación se muestra un mapa de Karnaugh clásico de cinco variables.

Mapa K de Cinco Variables (Mapa de Reflexión)

El estilo de reflexión antiguo etiqueta la parte superior (y, para un mapa de 6 variables, el lado) del mapa con código Gray completo. El código Gray se refleja alrededor del centro del mapa —una convención encontrada en muchos textos clásicos. Un diseño más nuevo y preferido se muestra a continuación.

Versión Superpuesta del Mapa-K

El mapa superpuesto consiste en dos sub-mapas idénticos de 4 celdas, distinguidos solo por el bit más significativo de la dirección de 3 bits a través de la parte superior. La numeración difiere del mapa de reflexión: si se ignora el dígito más significativo, la secuencia 00, 01, 11, 10 aparece en ambos sub-mapas. La secuencia de ocho bits no es código Gray, pero el sufijo de dos bits 01, 10 lo es.

Apliquemos el mapa de cinco variables a un problema real: diseñar un circuito que acepte una entrada binaria de 5 bits (A = MSB, B, C, D, E) y genere HIGH lógico siempre que el número binario sea primo.

Los números primos dentro del rango de 5 bits son (1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Marque un 1 en cada celda correspondiente, luego agrupe los unos. Termine escribiendo la expresión simplificada.

En el mapa de reflexión, el grupo de 4 celdas A'B'E abarca dos pares reflejados, mientras que el grupo de 2 celdas AB'DE aparece como par reflejado. Al usar el mapa superpuesto, busque imágenes espejo a través de las dos mitades.

Out = A'B'E + B'C'E + A'C DE + A'C D'E + ABCE + AB'DE + A'B'C'D

Abajo está la versión superpuesta de la misma expresión.

Comparando los dos mapas, algunas celdas se desplazan porque el esquema de direccionamiento difiere. Superponiendo una mitad sobre la otra revelan grupos superpuestos que guían la simplificación. Por ejemplo, el grupo de 4 celdas A'B'E cubre el patrón ABCDE = 00xx1, significando A, B y E fijos en 0,0,1 respectivamente mientras C y D varían.

Sigue un ejemplo de mapa de Karnaugh de seis variables. Apilando mentalmente los cuatro sub-mapas, podemos identificar un grupo de 4 celdas que implementa Out = C'F'.

Para ilustrar el mapa de 6 variables, considere un comparador de magnitud de 3 bits que produce tres salidas: igual, mayor-que, y menor-que. El comparador toma dos entradas de 3 bits A₂A₁A₀ y B₂B₁B₀. Por simplicidad, resolveremos solo la salida A > B.

Mapa K de 6 Variables

El mapa superpuesto abajo asiste en simplificar la lógica para la salida A > B de un comparador de 3 bits. El código de dirección binaria a lo largo de la parte superior y el lado izquierdo no es un código Gray completo de 3 bits, pero los códigos de 2 bits de cada uno de los cuatro sub-mapas son Gray.

Donde ABC excede XYZ, se traza un 1. El mapa se llena según corresponda.

El agrupamiento sigue estas directrices:

• Un grupo de 16 celdas
• Dos grupos de 8 celdas
• Cuatro grupos de 4 celdas

El grupo de 16 celdas AX' ocupa el sub-mapa inferior derecho. Dos grupos de 8 celdas se forman superponiendo patrones idénticos de 4 celdas de los sub-mapas superior e inferior. Cuatro grupos de 4 celdas aparecen en el mapa; cada uno produce un término de producto. La reducción final Suma-de-Productos contiene siete términos.

Contando los 1s, hay 28 unos. Antes de reducción, el SOP contendría 28 términos de producto de seis entradas cada uno. El mapa-K colapsa esto a siete términos de producto de cuatro o menos entradas —una simplificación dramática.

El diagrama de cableado se omite, pero aquí está la lista de partes para un comparador de magnitud de 3 bits (A > B) usando componentes de familia lógica 4-TTL:

• 1 × 7410 triple compuerta NAND de 3 entradas (AX', ABY', BX'Y')
• 2 × 7420 dual compuerta NAND de 4 entradas (ABCZ', ACY'Z', BCX'Z', CX'Y'Z')
• 1 × 7430 compuerta NAND de 8 entradas (para la salida final de 7 términos)

Repaso

• Álgebra booleana, mapas de Karnaugh y CAD son herramientas esenciales para simplificación lógica.
• Una solución de coste mínimo usa las menos compuertas con las menos entradas.
• Diagramas de Venn ayudan a visualizar expresiones booleanas antes de traducirlas a mapas-K.
• Las celdas de mapa-K se organizan en código Gray, revelando redundancias que permiten simplificación.
• Expresiones Suma-de-Productos (SOP) se implementan típicamente como compuertas AND alimentando una sola OR.
• SOP puede realizarse con lógica NAND-NAND reemplazando ANDs y ORs con NANDs.
• Producto-de-Sumas (POS) es menos común pero puede implementarse con compuertas OR alimentando una sola AND, basada en los 0s del mapa (maxterminos).