Algoritmo Quine–McCluskey
El
Algoritmo Quine–McCluskey es un método de simplificación de
funciones booleanas desarrollado por Willard Van Orman Quine y Edward J. McCluskey. Es funcionalmente idéntico a la utilización del Mapa de karnaugh,
pero su forma tabular lo hace más eficiente para su implementación en
lenguajes computacionales, y provee un método determinístico de
conseguir la mínima expresión de una función booleana.
Pasos
El método consta de dos pasos:
- Encontrar todos los implicantes primos de la función.
- Usar esos implicantes en una tabla de implicantes primos para encontrar los implicantes primos esenciales, los cuales son necesarios y suficientes para generar la función.
Complejidad
Aunque es más práctico que el mapa de Karnaugh, cuando se trata de
trabajar con más de cuatro variables, el tiempo de resolución del
algoritmo Quine-McCluskey crece de forma exponencial con el aumento del número de variables. Se puede demostrar que para una función de
n variables el límite superior del número de implicantes primos es 3
n/
n. Si
n = 32 habrá más de 6.5 * 10
15 implicantes primos. Funciones con un número grande de variables tienen que ser minimizadas con otros métodos heuristicos
Ejemplo
Paso 1: Encontrando implicantes primos
Minimizando una función arbitraria:
|
A |
B |
C |
D |
f |
m0 |
0 |
0 |
0 |
0 |
0 |
m1 |
0 |
0 |
0 |
1 |
0 |
m² |
0 |
0 |
1 |
0 |
0 |
m³ |
0 |
0 |
1 |
1 |
0 |
m4 |
0 |
1 |
0 |
0 |
1 |
m5 |
0 |
1 |
0 |
1 |
0 |
m6 |
0 |
1 |
1 |
0 |
0 |
m7 |
0 |
1 |
1 |
1 |
0 |
m8 |
1 |
0 |
0 |
0 |
1 |
m9 |
1 |
0 |
0 |
1 |
X |
m10 |
1 |
0 |
1 |
0 |
1 |
m11 |
1 |
0 |
1 |
1 |
1 |
m12 |
1 |
1 |
0 |
0 |
1 |
m13 |
1 |
1 |
0 |
1 |
0 |
m14 |
1 |
1 |
1 |
0 |
X |
m15 |
1 |
1 |
1 |
1 |
1 |
Uno fácilmente puede formar la expresion canomica suma de productos de esta tabla, simplemente sumando miniterminos (dejando fuera las redundancias) donde la función se evalúa con 1:
Por supuesto, esta expresión no es mínima. Para optimizarla, primero
son colocados todos los minitérminos evaluados en la función como 1 en
una tabla Las redundancias también son agregadas a la tabla, estas pueden combinarse con los minitérminos:
N. de 1s |
Minterm |
Representación binaria |
1 |
m4
m8 |
0100
1000 |
2 |
m9
m10
m12 |
1001
1010
1100 |
3 |
m11
m14 |
1011
1110 |
4 |
m15 |
1111 |
En este punto, uno puede empezar a combinar los minitérminos entre
sí. Si dos minitérminos sólo varían en un solo dígito, ese dígito debe
reemplazarse por un guion "-" indicando que ese bit no importa. Los
términos que ya no pueden combinarse más son marcados con "*". Cuando
van de tamaño 2 a 4, tratamos '-' como un valor de bit
Ejemplo: -110 y -100 o -11- pueden ser combinados, pero no -110 y 011-.
(Consejo: agrupar los '-' primero.)
Número de 1s Minterm Bin | Implicantes de tamaño 2 | Implicantes de tamaño 4
--------------------------------|-------------------------|------------------------
1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--*
m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0*
--------------------------------| m(8,10) 10-0 |------------------------
2 m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-*
m10 1010 |-------------------------|
m12 1100 | m(9,11) 10-1 |
--------------------------------| m(10,11) 101- |
3 m11 1011 | m(10,14) 1-10 |
m14 1110 | m(12,14) 11-0 |
--------------------------------|-------------------------|
4 m15 1111 | m(11,15) 1-11 |
| m(14,15) 111- |
Paso 2: tabla de implicantes primos
Los términos marcados con "*" ya no pueden combinarse más, en este
punto ya tenemos la tabla de implicantes primos. En el costado van los
implicantes primos recientemente generados, y en la parte superior los
minitérminos utilizados. Los minitérminos correspondientes a las
redundancias son omitidos en este paso, no se colocan en la parte
superior.
|
4 |
8 |
10 |
11 |
12 |
15 |
|
|
X |
|
|
|
X |
|
- |
1 |
0 |
0 |
|
|
X |
X |
X |
|
|
1 |
0 |
- |
- |
|
|
X |
X |
|
X |
|
1 |
- |
- |
0 |
|
|
|
X |
X |
|
X |
1 |
- |
1 |
- |
En esta tabla vemos los minitérminos que "cubre" cada implicante
primo. Ninguno de los implicantes de esta tabla está incluido dentro de
otro (esto queda garantizado en el paso uno), pero si puede estar
"cubierto" por dos o más implicantes. Es el caso de
que está cubierto por
y
o
que está cubierto por
y
.
Por este motivo, cada uno de estos dos implicantes sólo son
esenciales en ausencia del otro. Un proceso adicional simple para
reducir estos implicantes es prueba y error, pero un proceso más
sistemático es el metodo de pretrick. En el caso que estamos analizando, los dos implicantes primos
y
no llegan a incluir todos los minitérminos por lo que podemos combinar
estos implicantes con cada uno de los implicantes no esenciales para
conseguir dos funciones mínimas:
Las dos son equivalentes a esta función original: