Método Quine-McCluskey

Como ya lo vimos anteriormente los mapas de karnaugh son un método sencillo y eficaz para la simplificación de funciones de pocas variables sin embargo cuando lo implementamos en funciones de más de 6 variables nos resulta muy laborioso y desborda la capacidad de agrupación visual, debido a esto surge el método Quine-McCluskey el cual no presenta las limitaciones del método de karnaugh y que nos permite su programación y uso en un sistema informático.

COMPARACIÓN

Mapas de Karnaugh
1.- Técnica basada en agrupamientos.
2.- Enfocada a trabajarse manualmente.
3.- La expresión resultante es la suma mínima de primos implicados.
4.- implican los casos verdaderos de la funció

Método de Quine-McCluskey
1.- Es un algoritmo para ser implementado computacionalmente.
2.- Tiene 2 etapas:
             1.- Se obtienen los primos implicantes.
             2.- Se encuentra la suma mínima de primos implicantes.

El método Quine-McClusky consiste en obtener las adyacencias de órdenes crecientes, hasta llegar a las de mayor orden posible, que son los ya estudiados implicantes primos. para ello se parte de las adyacencias de orden cero o términos canónicos de la función, posteriormente con este método y de forma sistemática se obtienen todas las adyacencias de primer orden y así hasta obtener todos los de mayor orden posible, en pocas palabras esquemáticamente este método consiste en agrupar los vectores de entrada que activan la función (dan resultado 1 para ella) en clases diferenciadas por el número de variables cuyo valor sea 1 y calcular todas las posibilidades de simplificación entre vectores de 2 clases sucesivas, eligiendo las que son más eficientes.

Este método al igual que el de Karnaugh y el algebraico utiliza el siguiente teorema del álgebra booleana

Teorema que se obtiene de aplicar las leyes distributiva e inversa.

El método lo dividiremos cuatro pasos:

1. a) Se obtiene la representación binaria de cada uno de los mintérminos dados. Es importante que todos los números se representen con la misma cantidad de dígitos, la cantidad de dígitos que se debe utilizar está dada por el míntermino de mayor a valor. La cantidad de dígitos representa la cantidad de variables que tiene la función. Por ejemplo, para la función: F(a,b,c,d) = m(4,5,7,8,9,11)

2. b) Una vez que se tiene la representación binaria se agrupan los minterminos según la cantidad de unos que tengan para esto nos vamos a utilizar una tabla. Por ejemplo vemos que los minterminos m(4) y m(8) solo tienen un uno, m(5) y m(9) tienen dos unos, etc. En la tabla que se muestra a continuación podemos ver los mintérminos de la función f ya agrupados:

3. c) El siguiente paso consiste en comparar los términos de cada grupo con cada uno de los términos del grupo inmediato siguiente (los que tengan un uno con los que tengan dos unos, etc.), si la representación binaria de los elementos difiere únicamente en un dígito entonces agrupamos estos términos en otra tabla, y en el lugar del dígito diferente se coloca un guion. Esto se hace para cada elemento de cada grupo con cada elemento del grupo siguiente. Por ejemplo

   Al comparar 4 con 5 vemos que solo difieren en el último dígito

   

   Por lo tanto, sustituimos este con un guion y lo anexamos a la otra tabla. Tras repetir este proceso con todos los elementos de todos los grupos se obtiene la siguiente tabla.

   

   Repetimos este proceso con la nueva tabla obtenida hasta que ya no se puedan agrupar más términos. Vemos que para nuestro ejemplo ya no se pueden realizar más agrupaciones.

   NOTA: Es importante marcar todos los elementos que han sido agrupados en cada iteración. Por ejemplo, de la tabla uno se marcan los siguientes elementos.

   
   Todo elemento que no esté marcado al finalizar el proceso de comparación es un implicante primo y se debe de tomar en cuenta para la última etapa.

4. d) Finalmente vamos a construir una tabla en la cuál vamos a colocar en una columna los términos de cada uno de los implicantes primos ya en términos de las variables booleanas. en otra las agrupaciones formadas (cada una con su término correspondiente y, por último, una columna por cada míntermino de la función. Para nuestro ejemplo la tabla se vería así

   

   Por último, marcamos todos los minterminos que formen parte de una agrupación con una x. Todo término que sea único, esto es, que tenga solo una x en la columna se considera un implicante primo esencial y se incluye en el resultado final.

   

   La función minimizada es: