Método de Quine McCluskey

 

Método de Quine McCluskey

El Método de Quine McCluskey se utiliza para reducir ecuaciones booleanas. El método se divide en dos partes: encontrar los implicantes primos y obtener las ecuaciones a partir de la tabla de implicantes primos.}

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 variable 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.

PROCEDIMIENTO.

Paso 1. Encontrar implicantes primos

Se toman los mintérminos de la tabla de verdad, y se convierten a su equivalente en binario. Σm(0,1,2,3,5,7,9,11,12,13,15) Fig. 1.

Fig. 1. Tabla de verdad tomada junto con los valores obtenidos al aplicar el método.

Paso 2. Una vez obtenidos los datos, se deben de ordenar los valores de menor a mayor los números que tienen muchos 1, como se observa en la Fig. 2.

Fig. 2. Datos ordenados para la obtención y la reducción de los datos para conseguir a tabla reducida completamente.

Paso 3. Se comparan los mintérminos que sólo tienen una diferencia en sus bits, formando la columna de la Fig. 3. En esta columna se escriben los mintérminos comparados y el nuevo término, donde se marcará con un guión ( _ ) esa diferencia. Cada término que pase a la siguiente columna deberá marcarse con una (ü).

Fig. 3. Comparación de los mintérminos que tienen diferencia de bits, aplicándola en los pasos 3, 4 y 5.

Paso 4. El paso 3 se repetirá hasta que ya no sea posible formar nuevas columnas.

Paso 5. Si en alguna de las columnas se repiten elementos, se toma solamente uno para formar la Fig. 4.

Fig. 4. Datos obtenidos y reducidos en su totalidad para la obtención de los valores y configurar la tabla de implicantes primos.

Paso 6. Tabla de Implicantes primos.

Para obtener la tabla y la solución de la ecuación, hay que seguir un distinto procedimiento para poder obtener los resultados en la tabla de implicantes primos.

 

·         Se dibuja una tabla, en las columnas se acomodan los mintérminos.

·         Acomodar en los renglones los términos de la última columna y de las columnas anteriores que no fueron marcados.

·         Se coloca una X en donde cruzan los términos con los mintérminos.

·         Se agrupan verticalmente las X

·         Las X que quedan solas son las que marcan cuál término pasará a ser parte de la ecuación final. Esta X eliminará a las que se encuentran en su mismo renglón y se deben marcar los mintérminos involucrados.

·         Si al final quedan mintérminos sin marcar, se tomará un término que los involucre, tomando el mismo criterio que en mapas de Karnaugh: agrupar el mayor número de mintérminos en el menor número de grupos posibles.

·         Los guiones representan a las variables que se eliminan, los 1 a las variables y los 0 a las variables negadas, formando cada una de las partes de la ecuación final.

 

 

Sin embargo, existe una forma mas especificada para poder acomodar la tabla para obtener las posibles incógnitas que formaran y estructuran la ecuación booleana. Para ello la estructuraremos la tabla como se observa en la Fig. 5.

Acomodando solamente los elementos que obtuvieron la palomita de los pasos números 3,4 y 5 para tomar solamente esos resultados y acomodarlos como se muestra en la Fig. 5.

Finalmente al obtener los valores de la tabla de implicantes primos, podemos agrupar los resultados como la suma de productos obtenidos.

Con ello obtuvimos las Implicantes primarios esenciales extraídos que son:

Y ahora si podemos armar nuestra  Expresión booleana mínima:

Que si las sustituimos con letras que conocemos más formalmente para la ecuación, nos quedaría como sigue:

Ecuación Final:  

Ecuación Final: