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 determinista 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. Si n = 32 habrá más de 6.5 * 10¹⁵ implicantes primos. Funciones con un número grande de variables tienen que ser minimizadas con otros métodos heurísticos.

Ejemplo

Paso 1: Encontrar implicantes primos

Minimizando una función arbitraria:

$f\left(A,B,C,D\right)=\sum m\left(4,8,10,11,12,15\right)+\sum d\left(9,14\right)\,$
	A	B	C	D	f
m0	0	0	0	0	0
m1	0	0	0	1	0
m2	0	0	1	0	0
m3	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 expresión canónica suma de productos de esta tabla, simplemente sumando minitérminos (dejando fuera las redundancias) donde la función se evalúa con 1:

${\begin{matrix}f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'CD'+AB'CD+ABC'D'+ABCD\end{matrix}}$

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 solo 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
$m\left(4,12\right)*$	X				X		-	1	0	0
$m\left(8,9,10,11\right)$		X	X	X			1	0	-	-
$m\left(8,10,12,14\right)$		X	X		X		1	-	-	0
$m\left(10,11,14,15\right)*$			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 $m\left(8,9,10,11\right)$ que está cubierto por $m\left(8,10,12,14\right)$ y $m\left(10,11,14,15\right)$ o $m\left(8,10,12,14\right)$ que está cubierto por $m\left(8,9,10,11\right)$ y $m\left(4,12\right)$ .

Por este motivo, cada uno de estos dos implicantes solo 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 método de Petrick. En el caso que estamos analizando, los dos implicantes primos $m\left(4,12\right)$ y $m\left(10,11,14,15\right)$ 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:

${\begin{matrix}f_{A,B,C,D}=BC'D'+AB'+AC\end{matrix}}$

${\begin{matrix}f_{A,B,C,D}=BC'D'+AD'+AC\end{matrix}}$

Las dos son equivalentes a esta función original dándole:

${\begin{matrix}f_{A,B,C,D}=A'BC'D'+AB'C'D'+AB'C'D+AB'CD'+AB'CD+ABC'D'+ABCD'+ABCD\end{matrix}}$

Véase también

Enlaces externos

Implementación del algoritmo de Quine-McCluskey con búsqueda de todas las soluciones, by Frédéric Carpon.
All about Quine-McClusky, artículo de Jack Crenshaw comparando el método de Quine-McCluskey con los mapas de Karnaugh.
Lectura del algoritmo de Quine–McCluskey.
Java applet.
Implementación Python
Quinessence, an open source implementation written in Free Pascal.
QCA an open source, R based implementation used in the social sciences, by Adrian Duşa
Un ejemplo totalmente trabajado y explicado: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
[1], Applet donde se implementa paso a paso el algoritmo de Quine-McCluskey.
[2] Implementación del método Quine-McCluskey. Consola de dominio público SourceForge.net.
[3] Archivado el 13 de abril de 2017 en Wayback Machine. Tutorial del método de Quine-McCluskey (pdf).
Una excelente fuente donde se detallan todos los pasos: Olivier Coudert "Two-level logic minimization: an overview" INTEGRATION, the VLSI journal, 17-2, pp. 97–140, October 1994 Archivado el 10 de mayo de 2020 en Wayback Machine.
The Boolean Bot: Una implementación en JavaScript para la web: http://booleanbot.com/
ElTamiz: Documento en español con una detalladísima definición del algoritmo Quine-McCluskey completo, incluso el método de Petrik, proponiendo, además, mejoras a ciertos pasos del algoritmo: https://eltamiz.com/elcedazo/wp-content/uploads/2023/01/El-algoritmo-de-Quine-McClusky-por-Macluskey-2023.pdf

Datos: Q621409

	A	B	C	D	f
m0	0	0	0	0	0
m1	0	0	0	1	0
m2	0	0	1	0	0
m3	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

	A	B	C	D	f
m0	0	0	0	0	0
m1	0	0	0	1	0
m2	0	0	1	0	0
m3	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

	A	B	C	D	f
m0	0	0	0	0	0
m1	0	0	0	1	0
m2	0	0	1	0	0
m3	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