Quine-mccluskey

Minimización por el método de QUINE-McCLUSKEY
Se tienen dos formas de desarrollar el método de Quine-McCluskey: con una combinación binaria y una combinación decimal. Ambas formas se desarrollarán mediante dos ejemplos, respectivamente.

Combinación BINARIA.
Sea la función: F(A, B, C, D) = Σ m (1, 3, 4, 5, 7, 9, 10, 11, 15) La TABLA 1 presenta la lista de los minitérminos, expresados en formabinaria e indica el número de UNOS que estos contienen:

TABLA 1
mi
1 3 4 5 7 9 10 11 15

A B C D # de UNOS
0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 2 1 2 3 2 2 3 4

En la TABLA 2, se agrupan los minitérminos con el mismo número de UNOS.

TABLA 2
# de UNOS mi 1 2 3 4
1 4 3 5 9 10 7 11 15

A B C D
0 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 11 1 0 1 1 1 0 1 1 1
√ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √

De la TABLA 2, se combinan los términos que tienen un solo UNO con los que tienen dos UNOS, los que tienen dos UNOS con los que tienen tres UNOS y así sucesivamente. Dos términos se podrán combinar siempre y cuando exista un solo cambio entre ellos; es decir, cuando el lugar en que estén colocados los UNOS coincidan. Por ejemplo, lostérminos 1 y 3 se combinan debido a lo siguiente: ABCD + ABCD = ABD(C + C) = ABXD 0 0 01 0 0 11 00X1

O sea que entre los términos 1 y 3 se eliminó la variable C. Haciendo lo mismo con los demás términos, se obtiene la TABLA 3.

TABLA 3
NIVEL DE AGRUPACIÓN COMBINACIÓN

A 0 0 X 0 0 X 0 1 1 X 1

B 0 X 0 1 X 0 1 0 0 1 X

C X 0 0 0 1 1 X X 1 1 1

D 1 1 1 X 1 1 1 1 X 1 1
√ √ √

1-2

2-33-4

1-3 1-5 1-9 4-5 3-7 3-11 5-7 9-11 10-11 7-15 11-15

*e
√ √ √ √ √ √

*d
√ √

Los términos que en su fila tienen √, son los que se combinaron. Los términos con *, son los que no pudieron combinarse; es decir, aquellos que en su fila no tienen √. A estos términos se les denomina IMPLICANTES PRIMOS. Para la TABLA 4, se combinan los niveles de agrupación 1-2 con 2-3 y 2-3 con 3-4,tomando en cuenta que coincidan tanto las x como los UNOS.

TABLA 4
NIVEL DE AGRUPACIÓN COMBINACIÓN

A 0 X x

B x 0 x

C x x 1

D 1 1 1

1-2-3 2-3-4

1-3-5-7 1-3-9-11 3-7-11-15

*c *b *a

Como ya se indicó, los implicantes primos son términos que no se combinan con ningún otro, por tanto pueden formar parte de la función reducida. Para determinar cuáles de los implicantes primosforman parte de la función reducida, se hace la siguiente tabla, llamada de implicantes primos.

TABLA 5. Implicantes primos
* mi
1 3
√ √ √ (√) √ √ √ √ √ √ √

4

5

7
√

9
(√) √

10

11
√ √

15
(√) √

a b √ c √ d e a b √ c d
√

* * * *

√ √

√ (√) √ √ √ √ √ √ √ √ √ √

√

√

√

√

√

Obsérvese que en la tabla anterior, se encerraron entre paréntesis las √que se encontraron solas en una columna y su fila se proyectó en la parte inferior de la tabla. Si en los cuatro penúltimos renglones se llenan todas las columnas (última fila), entonces se ha llegado a la solución mínima. Nótese que c no tuvo ninguna √ sola dentro de sus columnas, lo que significa que este implicante primo está contenido en los demás; es decir, no forma parte de la funciónreducida. Por tanto, la función reducida es: F(A, B, C, D) = a + b + d + e Donde: a = XX11 = CD b = X0X1 = BD d = 101X = ABC e = 010X = ABC Finalmente, la función reducida es: F(A, B, C, D) = CD + BD + ABC + ABC

Combinación DECIMAL
Retomando el problema anterior: F(A, B, C, D) = Σ m (1, 3, 4, 5, 7, 9, 10, 11, 15) La TABLA 1 de la combinación decimal es idéntica a la combinación binaria. En la TABLA2 se agrupan los minitérminos por su número de UNOS:

TABLA 2
# de UNOS

1 2 3 4

mi 1 4 3 5 9 10 7 11 15

√ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √

sustraendo

minuendo

sustraendo

minuendo

sustraendo minuendo

Las TABLAS 3 y 4 se obtienen aplicando las siguientes reglas:

REGLA 1: REGLA 2: REGLA 3:

La diferencia entre dos minitérminos de dos niveles contiguos, debe...