Método tabular de Quine-McCluskey
En el capítulo anterior, discutimos el método K-map, que es un método conveniente para minimizar funciones booleanas hasta 5 variables. Pero es difícil simplificar las funciones booleanas que tienen más de 5 variables usando este método.
El método tabular de Quine-McClukey es un método tabular basado en el concepto de implicantes primos. Lo sabemosprime implicant es un término de producto (o suma), que no se puede reducir más combinándolo con cualquier otro término de producto (o suma) de la función booleana dada.
Este método tabular es útil para obtener los principales implicados utilizando repetidamente la siguiente identidad booleana.
xy + xy '= x (y + y') = x.1 = x
Procedimiento del método tabular de Quine-McCluskey
Siga estos pasos para simplificar las funciones booleanas utilizando el método tabular de Quine-McClukey.
Step 1 - Organizar los términos mínimos dados en un ascending ordery hacer los grupos en función del número de unos presentes en sus representaciones binarias. Entonces, habráat most ‘n+1’ groups si hay 'n' variables booleanas en una función booleana o 'n' bits en el equivalente binario de términos mínimos.
Step 2 - Compare los términos mínimos presentes en successive groups. Si hay un cambio en la posición de un solo bit, entonces tome el par de esos dos términos mínimos. Coloque este símbolo '_' en la posición de bit diferente y mantenga los bits restantes como están.
Step 3 - Repita el paso 2 con los términos recién formados hasta obtener todos prime implicants.
Step 4 - Formular el prime implicant table. Consiste en un conjunto de filas y columnas. Los implicantes primos se pueden colocar en filas y los términos mínimos se pueden colocar en columnas. Coloque '1' en las celdas correspondientes a los términos mínimos que se cubren en cada implicante principal.
Step 5- Encontrar los implicantes primos esenciales observando cada columna. Si el término mínimo está cubierto solo por un implicante principal, entonces esessential prime implicant. Los implicantes primos esenciales formarán parte de la función booleana simplificada.
Step 6- Reducir la tabla de implicantes primos eliminando la fila de cada implicante primo esencial y las columnas correspondientes a los términos mínimos que se cubren en ese implicante primo esencial. Repita el paso 5 para la tabla de implicantes primos reducidos. Detenga este proceso cuando terminen todos los términos mínimos de la función booleana dada.
Ejemplo
Nos deja simplify la siguiente función booleana, $ f \ left (W, X, Y, Z \ right) = \ sum m \ left (2,6,8,9,10,11,14,15 \ right) $ usando Quine-McClukey método tabular.
La función booleana dada está en sum of min termsformar. Tiene 4 variables W, X, Y y Z. Los términos mínimos dados son 2, 6, 8, 9, 10, 11, 14 y 15. El orden ascendente de estos términos mínimos se basa en el número de unos presentes en su equivalente binario es 2, 8, 6, 9, 10, 11, 14 y 15. La siguiente tabla muestra estosmin terms and their equivalent binary representaciones.
| Nombre del grupo | Términos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GA1 | 2 | 0 | 0 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | |
| GA2 | 6 | 0 | 1 | 1 | 0 |
| 9 | 1 | 0 | 0 | 1 | |
| 10 | 1 | 0 | 1 | 0 | |
| 11 | 1 | 0 | 1 | 1 | |
| 14 | 1 | 1 | 1 | 0 | |
| GA4 | 15 | 1 | 1 | 1 | 1 |
Los términos mínimos dados se organizan en 4 grupos según el número de unos presentes en sus equivalentes binarios. La siguiente tabla muestra los posiblesmerging of min terms de grupos adyacentes.
| Nombre del grupo | Términos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6 | 0 | - | 1 | 0 |
| 2,10 | - | 0 | 1 | 0 | |
| 8,9 | 1 | 0 | 0 | - | |
| 8,10 | 1 | 0 | - | 0 | |
| GB2 | 6,14 | - | 1 | 1 | 0 |
| 9,11 | 1 | 0 | - | 1 | |
| 10,11 | 1 | 0 | 1 | - | |
| 10,14 | 1 | - | 1 | 0 | |
| 11,15 | 1 | - | 1 | 1 | |
| 14,15 | 1 | 1 | 1 | - |
Se fusionan los términos mínimos, que se diferencian en sólo un bit de los grupos adyacentes. Ese bit diferente se representa con este símbolo, '-'. En este caso, hay tres grupos y cada grupo contiene combinaciones de dos términos mínimos. La siguiente tabla muestra los posiblesmerging of min term pairs de grupos adyacentes.
| Nombre del grupo | Términos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GB1 | 2,6,10,14 | - | - | 1 | 0 |
| 2,10,6,14 | - | - | 1 | 0 | |
| 8,9,10,11 | 1 | 0 | - | - | |
| 8,10,9,11 | 1 | 0 | - | - | |
| GB2 | 10,11,14,15 | 1 | - | 1 | - |
| 10,14,11,15 | 1 | - | 1 | - |
Se fusionan los grupos sucesivos de pares de términos mínimos, que se diferencian sólo en la posición de un bit. Ese bit diferente se representa con este símbolo, '-'. En este caso, hay dos grupos y cada grupo contiene combinaciones de cuatro términos mínimos. Aquí, estas combinaciones de términos de 4 minutos están disponibles en dos filas. Entonces, podemos eliminar las filas repetidas. La tabla reducida después de eliminar las filas redundantes se muestra a continuación.
| Nombre del grupo | Términos mínimos | W | X | Y | Z |
|---|---|---|---|---|---|
| GC1 | 2,6,10,14 | - | - | 1 | 0 |
| 8,9,10,11 | 1 | 0 | - | - | |
| GC2 | 10,11,14,15 | 1 | - | 1 | - |
No es posible una fusión adicional de las combinaciones de términos mínimos de grupos adyacentes, ya que se diferencian en más de una posición de un bit. Hay tres filas en la tabla anterior. Entonces, cada fila dará un implicante principal. Por lo tanto, losprime implicants son YZ ', WX' y WY.
los prime implicant table se muestra a continuación.
| Términos mínimos / Implicantes principales | 2 | 6 | 8 | 9 | 10 | 11 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|
| YZ’ | 1 | 1 | 1 | 1 | ||||
| WX’ | 1 | 1 | 1 | 1 | ||||
| WY | 1 | 1 | 1 | 1 |
Los implicantes principales se colocan en filas y los términos mínimos en columnas. Los 1 se colocan en las celdas comunes de las filas de implicantes primos y las correspondientes columnas de término mínimo.
Los términos mínimos 2 y 6 están cubiertos solo por un implicante principal YZ’. Entonces, es unessential prime implicant. Esto será parte de la función booleana simplificada. Ahora, elimine esta fila de implicantes primos y las columnas de término mínimo correspondientes. La tabla de implicantes primos reducidos se muestra a continuación.
| Términos mínimos / Implicantes principales | 8 | 9 | 11 | 15 |
|---|---|---|---|---|
| WX’ | 1 | 1 | 1 | |
| WY | 1 | 1 |
Los términos mínimos 8 y 9 están cubiertos solo por un implicante principal WX’. Entonces, es unessential prime implicant. Esto será parte de la función booleana simplificada. Ahora, elimine esta fila de implicantes primos y las columnas de término mínimo correspondientes. La tabla de implicantes primos reducidos se muestra a continuación.
| Términos mínimos / Implicantes principales | 15 |
|---|---|
| WY | 1 |
El término mínimo 15 está cubierto solo por un implicante principal WY. Entonces, es unessential prime implicant. Esto será parte de la función booleana simplificada.
En este problema de ejemplo, obtuvimos tres implicantes primos y los tres son esenciales. Por lo tanto, lossimplified Boolean function es
f(W,X,Y,Z) = YZ’ + WX’ + WY.