Algoritmo de Quine-McCluskey
El algoritmo Quine-McCluskey (QMC), también conocido como el método de los implicantes primos, es un método utilizado para la minimización de valores booleanos funciones que fue desarrollado por Willard V. Quine en 1952 y ampliado por Edward J. McCluskey en 1956. Como principio general, este enfoque ya había sido demostrado por el lógico Hugh McColl en 1878, fue probado por Archie Blake en 1937 y fue redescubierto por Edward W. Samson y Burton E. Mills en 1954 y por Raymond J. Nelson en 1955. También en 1955, Paul W. Abrahams y John G. Nordahl, Albert A. Mullin y Wayne G. Kellner propusieron una variante decimal del método.
El algoritmo de Quine-McCluskey es funcionalmente idéntico al mapeo de Karnaugh, pero la forma tabular lo hace más eficiente para su uso en algoritmos informáticos y también ofrece una forma determinista de comprobar que se ha alcanzado la forma mínima de una función booleana. A veces se lo denomina método de tabulación.
El método consta de dos pasos:
- Encontrar a todos los principales implicantes de la función.
- Usa esos primeros implicantes en un Gráfico principal implicado encontrar los principales implicantes esenciales de la función, así como otros principales implicantes que son necesarios para cubrir la función.
Complejidad
Aunque es más práctico que Karnaugh al tratar con más de cuatro variables, el algoritmo Quine-McCluskey también tiene un rango limitado de uso ya que el problema que resuelve es NP-completo. El tiempo de funcionamiento del algoritmo Quine-McCluskey crece exponencialmente con el número de variables. Para una función de n variables el número de principales implicantes puede ser tan grande como 3n/n{displaystyle 3^{n}/{sqrt {n}} por ejemplo, para 32 variables puede haber más de 534 × 1012 Principales implicantes. Las funciones con un gran número de variables deben minimizarse con métodos heurísticos potencialmente no óptimos, de los cuales el minimizador de lógica heurística de Espresso fue el estándar de facto en 1995.
El paso dos del algoritmo equivale a resolver el problema de la cobertura fija; Las instancias NP-hard de este problema pueden ocurrir en este paso del algoritmo.
Ejemplo
Entrada
En este ejemplo, la entrada es una función booleana en cuatro variables, f:{}0,1}4→ → {}0,1}{displaystyle f:{0,1}{4}to {0,1} que evalúa 1{displaystyle 1} sobre los valores 4,8,10,11,12{displaystyle 4,8,10,11,12} y 15{displaystyle 15}, evalúa a un valor desconocido en 9{displaystyle 9} y 14{displaystyle 14}, y a 0{displaystyle 0} en todas partes (donde estos enteros se interpretan en su forma binaria para la entrada a f{displaystyle f} para la succincticidad de la notación). Las entradas que evalúan 1{displaystyle 1} se llaman 'minterms'. Codificamos toda esta información escribiendo
- f()A,B,C,D)=.. m()4,8,10,11,12,15)+d()9,14).{displaystyle f(A,B,C,D)=sum m(4,8,10,11,12,15)+d(9,14).,}
Esta expresión dice que la función de salida f será 1 para los minterms 4,8,10,11,12{displaystyle 4,8,10,11,12} y 15{displaystyle 15} (denotado por el término 'm') y que no nos importa la salida para 9{displaystyle 9} y 14{displaystyle 14} combinaciones (denotadas por el término 'd'). El símbolo de la suma .. {displaystyle sum } denota la suma lógica (lógica O, o disyunción) de todos los términos que se resumen.
Paso 1: encontrar implicantes primos
Did you mean:First, we write the function as a table (where x#39;x#39; stands for don't care):
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
Se puede formar fácilmente la expresión de suma canónica de productos a partir de esta tabla, simplemente sumando los minitérminos (omitiendo los términos indiferentes) donde la función se evalúa como uno:
- fA,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.
que no es mínimo. Entonces, para optimizar, todos los términos mínimos que se evalúan como uno se colocan primero en una tabla de términos mínimos. Los términos que no importan también se agregan a esta tabla (nombres entre paréntesis), por lo que se pueden combinar con minitérminos:
Número
de 1Minterm binario
Representación1 m4 0100 m8 1000 2 (m9) 1001 m10 Graben 19, 1010 m12 1100 3 m11 1011 (m14) 1110 4 m15 1111
En este punto, uno puede comenzar a combinar minitérminos con otros minitérminos. Si dos términos difieren en un solo dígito, ese dígito se puede reemplazar con un guión que indica que el dígito no importa. Los términos que ya no se pueden combinar están marcados con un asterisco (*). Por ejemplo, 1000 y 1001 se pueden combinar para dar 100-, lo que indica que ambos términos mínimos implican que el primer dígito es 1 y los dos siguientes son 0.
Número
de 1Minterm 0-Cube Tamaño 2 Implicantes 1 m4 0100 m(4,12) -100 * m8 1000 m(8,9) 100- — m(8,10) 10-0 — m(8,12) 1-00 2 m9 1001 m(9,11) 10-1 m10 Graben 19, 1010 m(10,11) 101- — m(10,14) 1-10 m12 1100 m(12,14) 11-0 3 m11 1011 m(11,15) 1-11 m14 1110 m(14,15) 111- 4 m15 1111 —
Al pasar del tamaño 2 al tamaño 4, trate - como un tercer valor de bit. Haga coincidir los -'s primero. Los términos representan productos y para combinar dos términos de productos deben tener las mismas variables. Una de las variables debe estar complementada en un término y no complementada en el otro. El resto de variables presentes deben coincidir. Entonces, para hacer coincidir dos términos, los -'s deben alinearse y todos menos uno de los otros dígitos deben ser iguales. Por ejemplo, -110 y -100 se pueden combinar para dar -1-0, al igual que -110 y -010 para dar --10, pero -110 y 011- no pueden dado que - 's no se alinean. -110 corresponde a BCD' mientras
011- corresponde a A'BC y BCD' + A'BC no es equivalente a un término de producto.
Número
de 1Minterm 0-Cube Tamaño 2 Implicantes Tamaño 4 1 m4 0100 m(4,12) -100 * — m8 1000 m(8,9) 100- m(8,9,10,11) 10... * — m(8,10) 10-0 m(8,10,12,14) 1-0 * — m(8,12) 1-00 — 2 m9 1001 m(9,11) 10-1 — m10 Graben 19, 1010 m(10,11) 101- m(10,11,14,15) 1-1- * — m(10,14) 1-10 — m12 1100 m(12,14) 11-0 — 3 m11 1011 m(11,15) 1-11 — m14 1110 m(14,15) 111- — 4 m15 1111 — —
Nota: En este ejemplo, ninguno de los términos de la tabla de implicantes de tamaño 4 se puede combinar más. En general, este proceso debe continuar (tamaños 8, 16, etc.) hasta que no se puedan combinar más términos.
Paso 2: tabla de implicantes primos
Ninguno de los términos se puede combinar más allá de esto, por lo que en este punto construimos una tabla de implicantes primos esenciales. A un lado van los implicantes principales que se acaban de generar (estos son los que se han marcado con un "*" en el paso anterior), y en la parte superior van los minitérminos especificados anteriormente. Los términos de indiferencia no se colocan en la parte superior; se omiten de esta sección porque no son entradas necesarias.
4 8 10 11 12 15 ⇒ A B C D m(4,12) 
⇒ — 1 0 0 m(8,9,10,11) ⇒ 1 0 — — m(8,10,12,14) ⇒ 1 — — 0 m(10,11,14,15) ⇒ 1 — 1 —
Para encontrar los implicantes primos esenciales, buscamos columnas con un solo "✓". Si una columna tiene solo un "✓", esto significa que el minitérmino solo puede estar cubierto por un implicante primo. Este implicante primo es esencial.
Por ejemplo: en la primera columna, con el minitérmino 4, solo hay un "✓". Esto significa que m(4,12) es esencial. Minterm 15 también tiene solo un "✓", por lo que m(10,11,14,15) también es esencial. Ahora todas las columnas con un "✓" están cubiertos.
El segundo implicante primo puede ser 'cubierto' por el tercero y el cuarto, y el tercer implicante primo puede ser 'cubierto' por el segundo y el primero, y ninguno es por lo tanto esencial. Si un implicante primo es esencial entonces, como se esperaría, es necesario incluirlo en la ecuación booleana minimizada. En algunos casos, los implicantes primos esenciales no cubren todos los minitérminos, en cuyo caso se pueden emplear procedimientos adicionales para la reducción de gráficos. El "procedimiento adicional" es prueba y error, pero una forma más sistemática es el método de Petrick. En el ejemplo actual, los implicantes primos esenciales no manejan todos los minitérminos, por lo que, en este caso, los implicantes esenciales se pueden combinar con uno de los dos no esenciales para producir una ecuación:
- fA,B,C,D BC'D + AB' + AC
o
- fA,B,C,D = BC'D + AD' + AC
Ambas ecuaciones finales son funcionalmente equivalentes a la ecuación detallada original:
- fA,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.