Lógica combinacional: minimización y riesgos
La expresión más corta no siempre es la mejor: puede dejar caer la salida durante unos nanosegundos cuando no debería. Minimizar bien es encontrar la mínima y saber cuándo agregarle un término.
01De la tabla de verdad a la expresión mínima
Las compuertas, el álgebra de Boole y el paso de una tabla de verdad a un circuito están desarrollados en la página de lógica combinacional de la tecnicatura. Esta unidad parte de ahí y se hace la pregunta de ingeniería: entre todos los circuitos que implementan la misma función, ¿cuál es el mejor?
Leída directamente de la tabla, cualquier función queda como suma de productos canónica: un término AND por cada fila que vale 1, con las cuatro variables. Es correcta y casi siempre innecesariamente cara. Minimizarla reduce tres cosas a la vez: la cantidad de compuertas (el costo y el área en un chip), la cantidad de entradas por compuerta, y la profundidad del circuito, que es lo que decide cuán rápido responde.
02El mapa de Karnaugh
El mapa de Karnaugh reordena la tabla de verdad en una grilla donde dos celdas vecinas difieren en una sola variable. Para lograrlo, filas y columnas se numeran en código Gray —00, 01, 11, 10— y los bordes opuestos también son vecinos: el mapa es, en realidad, un toro. Dos unos vecinos se pueden agrupar porque la variable que cambia entre ellos no importa: \( AB + A\overline B = A \).
| Regla | Por qué |
|---|---|
| Los grupos tienen 1, 2, 4, 8 o 16 celdas | Cada duplicación elimina exactamente una variable |
| Los grupos son rectángulos, y pueden cruzar los bordes | Los bordes opuestos difieren en una sola variable |
| Conviene el grupo más grande posible | Más celdas, menos literales en el término |
| Los grupos se pueden superponer | Un 1 cubierto dos veces no cambia la función (\( X + X = X \)) |
| Los indiferentes (X) se usan solo si agrandan un grupo | No hace falta cubrirlos |
Cada grupo que no está contenido en otro más grande es un implicante primo. Los que cubren algún 1 que ningún otro cubre son esenciales y van sí o sí; el resto se elige para completar la cobertura con la menor cantidad de términos.
03Quine-McCluskey: el mismo método, para una computadora
El mapa funciona a ojo hasta cinco o seis variables; después se vuelve imposible de ver. El método de Quine-McCluskey hace lo mismo de manera tabular: combina de a pares los términos que difieren en un bit, repite hasta que no se pueda combinar más, y lo que queda sin combinar son los implicantes primos. Después resuelve un problema de cobertura: elegir el menor conjunto de primos que cubra todos los unos.
Esa segunda etapa es un problema de cobertura de conjuntos, y crece de manera explosiva con la cantidad de variables. Por eso las herramientas reales de síntesis —desde ESPRESSO, en los años ochenta, hasta las que hoy compilan para una FPGA— usan heurísticas que encuentran soluciones muy buenas sin garantizar la óptima. El laboratorio de esta página aplica Quine-McCluskey completo, que con cuatro variables se resuelve de manera exacta.
Tocá cada celda para pasarla de 0 a 1, de 1 a indiferente (X) y de vuelta a 0, o elegí un ejemplo. El laboratorio encuentra los implicantes primos con Quine-McCluskey, elige la cobertura mínima, la dibuja sobre el mapa y avisa si queda algún riesgo estático.
04Riesgos: cuando la expresión mínima falla
El álgebra de Boole supone que las señales cambian de manera instantánea. Las compuertas reales tardan: un inversor 74HC del orden de 10 ns. Si una misma variable llega a una compuerta OR por dos caminos con distinto retardo —uno directo y otro a través de un inversor—, durante esos nanosegundos los dos términos que la usan pueden valer 0 a la vez, y la salida, que debía quedarse en 1, cae un instante. Eso es un riesgo estático de 1, y el pulso espurio que produce se llama glitch.
En el mapa, el riesgo se ve a simple vista: aparece cuando dos unos vecinos quedan cubiertos por grupos distintos sin ningún grupo que los contenga a los dos. En un circuito combinacional que alimenta a otro combinacional el glitch suele no importar; en uno que maneja el reloj o el reset de un flip-flop, o una línea de habilitación, puede provocar una falla intermitente muy difícil de encontrar. Por eso el diseño sincrónico —el tema de la unidad siguiente— toma las salidas recién cuando ya se asentaron.
05Retardo y camino crítico
La salida de un circuito combinacional queda válida recién cuando la señal recorrió el camino más lento, el camino crítico. Minimizar compuertas y minimizar retardo no siempre van juntos, y el caso que lo muestra mejor es el sumador.
| Sumador de n bits | Cómo propaga el acarreo | Retardo | Compuertas |
|---|---|---|---|
| De acarreo en cascada (ripple carry) | Cada etapa espera el acarreo de la anterior | Crece como \( n \) | Pocas |
| De acarreo anticipado (carry lookahead) | Calcula todos los acarreos en paralelo con términos de generación y propagación | Crece como \( \log n \) | Muchas más |
Un sumador de 64 bits en cascada necesitaría del orden de 128 retardos de compuerta; uno de acarreo anticipado, unos pocos niveles. Todo procesador moderno paga en área para ganar en velocidad justo ahí.
06Dónde aparece en la electrónica
| Caso | Qué se usa de esta unidad |
|---|---|
| Decodificador de siete segmentos | Indiferentes: los códigos BCD que no existen simplifican cada segmento |
| Síntesis para FPGA | La herramienta minimiza sola, y después mapea el resultado en tablas de búsqueda |
| Lógica de habilitación de memorias | Un glitch en la selección de chip puede escribir un dato donde no debía |
| ALU de un microprocesador | Acarreo anticipado para no perder velocidad en la suma |
07En el laboratorio
Minimizar los siete segmentos de un decodificador BCD usando los indiferentes. Armar uno de ellos con compuertas 74HC y verificarlo con los diez dígitos.
Armar \( \overline{B}D + BC \) con compuertas reales, dejar \( C = D = 1 \), conmutar \( B \) con un generador y buscar con el osciloscopio el pulso espurio en la salida. Agregar \( CD \) y comprobar que desaparece.
Resolver por tabulación la mayoría de cuatro variables y comparar los implicantes primos con los que encuentra el laboratorio.
08Errores frecuentes
- Numerar el mapa en binario común. Con 00, 01, 10, 11 las celdas vecinas no difieren en un solo bit y los grupos dejan de ser válidos.
- Olvidar que los bordes son vecinos. Las cuatro esquinas de un mapa de cuatro variables forman un grupo.
- Hacer grupos de tres o de seis. Solo potencias de dos.
- Cubrir los indiferentes como si fueran unos. Se usan si ayudan; no hace falta cubrirlos.
- Creer que la mínima es siempre la mejor. Puede tener riesgos que una con un término más no tiene.
09Autoevaluación
¿Por qué el mapa de Karnaugh se numera en código Gray?
Para que dos celdas vecinas difieran en una sola variable, que es lo que permite agruparlas.
¿Qué es un implicante primo esencial?
Un implicante primo que cubre al menos un 1 que ningún otro primo cubre; tiene que estar en toda expresión mínima.
¿Qué hace un indiferente en el mapa?
Puede tomarse como 1 si agranda un grupo, o ignorarse si no: la especificación no exige ningún valor en esa combinación.
¿Cuándo hay un riesgo estático de 1?
Cuando dos unos vecinos quedan en grupos distintos sin ningún grupo que los cubra a los dos: al cambiar la variable que los separa, la salida puede caer un instante.
¿Por qué un sumador de acarreo anticipado es más rápido?
Porque calcula los acarreos en paralelo en vez de esperar que cada etapa le pase el suyo a la siguiente.
10Para ampliar
- M. Morris Mano y Michael D. Ciletti. Digital Design. 6.ª ed., Pearson, 2018. Mapas de Karnaugh, Quine-McCluskey y bloques combinacionales, con el enfoque clásico de los cursos de técnicas digitales.
- John F. Wakerly. Digital Design: Principles and Practices. 5.ª ed., Pearson, 2018. El tratamiento más cuidadoso de los riesgos y de los retardos reales de las familias lógicas.
- Robert K. Brayton y otros. Logic Minimization Algorithms for VLSI Synthesis. Kluwer, 1984. El libro de ESPRESSO: cómo minimiza un programa cuando las variables son demasiadas para Quine-McCluskey.