Aprende › Tema 5

Método de Quine-McCluskey paso a paso

Lectura de 7 min · Equipo bitGateLab

El mapa de Karnaugh es rápido para cuatro variables, pero depende de tu vista y deja de ser práctico con cinco o más. El método de Quine-McCluskey hace el mismo trabajo con tablas y reglas mecánicas: no requiere intuición, siempre encuentra todos los implicantes primos y es la base de los programas que simplifican funciones lógicas. Aquí vas a entender sus dos etapas, a identificar los implicantes primos esenciales y a resolver un ejemplo completo de cuatro variables.

Vocabulario: implicantes y primos

• Un implicante de F es un término producto que, cuando vale 1, garantiza que F vale 1. Cada minitérmino de F es un implicante, y también lo es cualquier grupo válido de un mapa de Karnaugh.
• Un implicante primo es un implicante que no se puede agrandar más; si le quitas una variable, cubre algún renglón donde F vale 0. Equivale a un grupo máximo del mapa.
• Un implicante primo esencial es un primo que cubre al menos un minitérmino que ningún otro primo cubre. Tiene que aparecer en cualquier solución mínima.

El método tiene dos etapas: primero encuentra todos los implicantes primos combinando términos; después elige el menor conjunto de primos que cubra todos los minitérminos.

Etapa 1: combinar términos

Cada término se escribe en binario, y la posición de una variable eliminada se marca con un guion. Por ejemplo, con variables A, B, C, D, el término 0-11 significa ACD (B fue eliminada).

1. Agrupa los minitérminos según la cantidad de unos que tiene su código binario.
2. Compara cada término de un grupo con cada término del grupo siguiente. Si difieren en un solo bit, combínalos poniendo un guion en esa posición, y marca los dos originales como usados.
3. Repite con la nueva lista. Solo se combinan términos que tienen los guiones en las mismas posiciones.
4. Cuando ya no se pueda combinar nada, los términos que nunca quedaron marcados son los implicantes primos.

Etapa 2: tabla de implicantes primos

Se arma una tabla con un renglón por cada implicante primo y una columna por cada minitérmino de la función (las condiciones "no importa" no llevan columna). Se marca qué minitérminos cubre cada primo. Luego:

1. Busca columnas con una sola marca. El primo de ese renglón es esencial: selecciónalo y tacha todas las columnas que cubre.
2. Con las columnas que queden, elige el menor número de primos que las cubra. Si dos primos cubren lo mismo, cualquiera sirve; prefiere el de menos literales.

Si dibujas esta función en un mapa de Karnaugh, P1 son las cuatro esquinas, P4 es el bloque central, P2 son las columnas 11 y 10 de las filas 00 y 10 (unidas por el borde) y P3 es la columna 11 completa. El método tabular llega al mismo resultado sin necesidad de ver el mapa.

Condiciones "no importa" y tablas cíclicas

Las condiciones X se incluyen en la etapa 1 como si fueran unos, porque pueden ayudar a formar implicantes más grandes. En la etapa 2 se omiten: no llevan columna, ya que no es obligatorio cubrirlas. Un primo formado solo por X nunca se necesita.

A veces, después de elegir los esenciales, o desde el principio, cada columna tiene al menos dos marcas y no hay forma obvia de decidir. A esa situación se le llama tabla cíclica. Se resuelve probando: eliges un primo, quitas lo que cubre y repites, comparando las soluciones que salgan. Para tablas grandes existe un procedimiento algebraico (el método de Petrick) que enumera todas las coberturas posibles.

Errores comunes

• Combinar términos con guiones en posiciones distintas, como 0-01 con 00-1. No es válido aunque parezcan diferir en un bit.
• Olvidar marcar como usados los dos términos de cada combinación, y luego listar como primo algo que no lo es.
• Poner columnas para las condiciones X en la tabla de cobertura, lo que obliga a cubrirlas sin necesidad.
• Elegir primos que no son esenciales antes que los esenciales. Primero asegura los esenciales; luego decide el resto.
• Escribir mal el término desde el código: en -0-1 la B va negada (vale 0), la D va sin negar (vale 1), y A y C desaparecen.

Pruébalo en el simulador

El simulador simplifica las funciones con este tipo de procedimiento, así que puedes usarlo para revisar cada etapa de tu trabajo a mano.

1. Crea una tabla de verdad de cuatro variables y marca con 1 los minitérminos del ejemplo.
2. Haz las etapas 1 y 2 en papel y escribe tu resultado.
3. Observa la expresión mínima que da la herramienta y su mapa de Karnaugh; identifica qué grupo corresponde a cada implicante primo.
4. Convierte las dos soluciones posibles a circuito en el mismo lienzo y cambia las entradas para confirmar que siempre dan la misma salida.

Ejercicios

1. Encuentra los implicantes primos y la expresión mínima de F(A, B, C, D) = Σm(0, 1, 3, 7, 8, 9, 11, 15).
   Respuesta

   Primos: -00- (BC), -0-1 (BD) y --11 (CD). La columna 0 solo la cubre BC, y la 7 solo la cubre CD: ambos son esenciales y juntos cubren todo. F = BC + CD. El primo BD sobra.

2. Resuelve F(A, B, C) = Σm(0, 1, 2, 5, 6, 7). ¿Hay primos esenciales?
   Respuesta

   Los pares son 00-, 0-0, -01, -10, 1-1 y 11-, y ninguno se combina en cuarteto: son seis primos. Cada minitérmino lo cubren exactamente dos, así que no hay esenciales (tabla cíclica). Dos soluciones mínimas: AB + BC + AC, o AC + BC + AB.

3. Simplifica F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15).
   Respuesta

   Incluyendo las X en la etapa 1 salen cuatro primos: -0-1 (BD), -01- (BC), --11 (CD) y 1--1 (AD). En la tabla, sin columnas para 1, 10 y 15: el 2 solo lo cubre BC, el 7 solo CD y el 13 solo AD. Los tres son esenciales y cubren también 3, 9 y 11. F = BC + CD + AD.

4. ¿Por qué no se compara el grupo con un uno contra el grupo con tres unos en la etapa 1?
   Respuesta

   Porque dos códigos con uno y tres unos difieren al menos en dos bits, y para combinarse deben diferir exactamente en uno.