Algoritmo de Quine-McCluskey

Maurice Karnaugh

Edward J. McCluskey, ingeniero eléctrico y profesor, durante el periodo entre 1955 y 1959 trabajaba en los laboratorios Bell. Desarrolló el algoritmo Quine-McCluskey como trabajo de doctorado en el MIT.

El segundo método para simplificar funciones booleanas que veremos es el del algoritmo de Quine-McCluskey. Es algo más laborioso que el de los mapas de Karnaugh, pero tiene dos ventajas importantes:

  1. No está limitado por el número de variables de entrada. Aunque la complejidad aumenta con cada variable que se añada.
  2. Es fácilmente programable, con lo que cualquier complejidad derivada del número de variables o de posibles errores queda minimizada.

Primera etapa

Partiremos de la forma canónica de la función, o de su tabla de verdad. El primer paso consiste en obtener la expresión en minterms.

Volvamos a las tablas de verdad del ejemplo del codificador BCD a 7 segmentos:

 a  b  c  d   A  B  C  D  E  F  G 
00001111110
00010110000
00101101101
00111111001
01000110011
01011011011
01101011111
01111110000
10001111111
10011111011
1010XXXXXXX
1011XXXXXXX
1100XXXXXXX
1101XXXXXXX
1110XXXXXXX
1111XXXXXXX

Esto nos proporciona las siguientes expresiones en mimterms, donde los valores entre paréntesis que siguen a la letra 'm' son los términos minterms de la función, y los que siguen a la letra 'r', los términos redundantes, o sea, los marcados con 'X' en la tabla de verdad:

A = m(0,2,3,5,6,7,8,9) r(10,11,12,13,14,15)

B = m(0,1,2,3,4,7,8,9) r(10,11,12,13,14,15)

C = m(0,1,3,4,5,6,7,8,9) r(10,11,12,13,14,15)

D = m(0,2,3,5,6,8,9) r(10,11,12,13,14,15)

E = m(0,2,3,6,8) r(10,11,12,13,14,15)

F = m(0,4,5,6,8,9) r(10,11,12,13,14,15)

G = m(2,3,4,5,6,8,9) r(10,11,12,13,14,15)

Aplicaremos el algoritmo de Quine-McCluskey a la función G.

Trasladamos a una tabla los minterms de la función, incluyendo los redundantes, y los ordenamos por el número de unos que contienen:

Función G
mbitsprimo
1
20010 
40100 
81000 
2
30011 
50101 
60110 
91001 
101010 
121100 
3
111011 
131101 
141110 
4
151111 

A cada uno de los elementos de esta tabla lo llamaremos implicante.

Ahora, intentaremos combinar los implicantes de cada grupo con el siguiente, en este caso, los del grupo con un uno con los del grupo con dos unos, los de dos con los de tres, y los de tres con los de cuatro. Para poder combinar dos implicantes, sus representaciones binarias sólo pueden variar en un bit. Los implicantes resultantes de la combinación se añaden a la tabla, sustituyendo el bit que cambia por un '-'.

Los implicantes que no se puedan combinar se denominan implicantes primos, y se marcan con un '*'.

Función G
mbitsprimo
1
2,3001- 
2,60-10 
2,10-010 
4,5010- 
4,601-0 
4,12-100 
8,9100- 
8,1010-0 
8,121-00- 
2
3,11-011 
5,13-101 
6,14-110 
9,1110-1 
9,131-01 
10,11101- 
10,141-10 
12,13110- 
12,1411-0 
3
11,151-11 
13,1511-1 
14,15111- 

El proceso se repite con cada conjunto de grupos de implicantes obtenido. En cada iteración obtenemos, al menos, un grupo menos, hasta que sólo se obtiene un grupo, o ninguno, si todos los implicantes resultan ser primos.

A veces sucede que al combinar dos parejas distintas de implicantes obtenemos el mismo resultado. En ese caso, ninguno de los cuatro implicantes será primo, pero sólo añadiremos uno de los resultados.

Por ejemplo, en el caso anterior, al combinar las parejas (2,3) con (10,11) obtenemos el mismo implicante que al combinar (2,10) con (3,11). Sólo añadiremos una vez el implicante resultante (2,3,10,11), pero consideraremos que ninguno de los implicantes originales es candidato a implicante primo.

Para la siguiente iteración, los implicantes son:

Función G
mbitsprimo
1
2,3,10,11-01-*
2,6,10,14--10*
4,5,12,13-10-*
4,6,12,14-1-0*
8,9,10,1110-- 
8,9,12,131-0- 
8,10,12,141--0- 
2
9,11,13,151--1 
10,11,14,151-1- 
12,13,14,1511-- 

La siguiente iteración es la última:

Función G
mbitsprimo
1
8,9,10,11,12,13,14,151---*

Entre todos estos implicantes, los únicos que no se pueden combinar con otros, los implicantes primos, son los siguientes:

Función G
mbitsprimo
2,3,10,11-01-*
2,6,10,14--10*
4,5,12,13-10-*
4,6,12,14-1-0*
8,9,10,11,12,13,14,151---*

Con esto hemos terminado la primera etapa del algoritmo.

Segunda etapa

A partir de la tabla de implicantes obtendremos una nueva tabla, llamada tabla de elección. Para formar esta tabla usaremos los implicantes primos.

En esta nueva tabla se incluye una 'X' para cada minterm, excluyendo los redundantes, que compone cada uno de los implicantes primos:

Funcion G
bin2345689Esencial
-01-XX     E
--10X   X   
-10-  XX   E
-1-0  X X   
1---     XXE

En esta tabla marcaremos los implicantes primos que contengan minterms que no estén presentes en otros implicantes primos. Llamaremos a esos implicantes primos, implicantes primos esenciales. Por ejemplo, el minterm '3' sólo está presente en el primer implicante primo, por lo tanto, ese implicante es esencial. Del mismo modo, el minterm '5' sólo está presente en el tercero, y el '8' y el '9', en el quinto.

Todos los minterms presentes en los otros dos implicantes primos también están presentes en otros implicantes primos, y por lo tanto, no son esenciales.

Puede suceder, como en este caso, que eligiendo sólo los implicantes primos esenciales no tengamos todos los minterms que componen la función. En este caso nos falta el '6'. Para el siguiente paso marcaremos todos los minterms presentes en implicantes primos esenciales:

Funcion G
bin2345689Esencial
-01-XX     E
--10X   X   
-10-  XX   E
-1-0  X X   
1---     XXE

Para completar esta etapa, deberemos elegir los implicantes primos no esenciales necesarios para que el conjunto final incluya todos los minterms de la función. Ahora no hay un criterio claro para seleccionar implicantes. En el programa que he hecho para acompañar a este artículo se eligen primero los que más 'X' tengan, y si (como en este caso) todos tienen el mismo número de 'X' sin marcar, se elige uno al azar.

Cada vez que elijamos uno, lo marcaremos como esencial, y marcaremos las 'X' que contenga en el resto de los implicantes.

Funcion G
bin2345689Esencial
-01-XX     E
--10X   X  e
-10-  XX   E
-1-0  X X   
1---     XXE

En nuestro ejemplo no quedan 'X' sin marcar, por lo tanto, este proceso ha terminado.

Tercera etapa

El último paso es obtener la fórmula. Para ello usaremos las combinaciones binarias de los implicantes primos esenciales. Cada uno determina un término en minterm reducido, que se debe combinar mediante funciones OR con el resto. Cada bit corresponde a una variable. Las variables correspondientes a bits con un '-' se eliminan de la expresión, las que correspondan a un '1' se incluyen directamente, y las que correspondan con un '0', se incluyen negadas.

De este modo, "-01-" corresponde con b'·c. Y la función G:

G = b'·c + c·d' + b·c' + b·d' + a