Mtodo de Quine- Mtodo de Quine-McCluskey

McCluskey Mapa de Karnaugh til slo hasta N=6

Difcil ver implicantes para N superior
Prof. Mario Medina Mtodo de Quine-McCluskey
Mtodo tabular y grfico para encontrar
[email protected]
implicantes
Aplicable a N grande
Fcil de implementar en un computador

Basado en el teorema AB + AB = A
Basado en agrupacin de trminos producto
Mario Medina

Agrupando trminos producto Grupos de trminos producto

Sea la funcin Grupo 0 0 0000 Dos trminos pueden
F(a, b, c, d) = m(0, 1, 2, 5, 6, 7, 8, 9, 10, 14) Grupo 1 1 0001 combinarse si difieren
2 0010 en slo una variable
Agrupar trminos producto de acuerdo al
8 1000 Combinar trminos de
nmero de bits en 1 de cada uno de ellos
Grupo 2 5 0101 grupos adyacentes
Comparar todos los trminos producto de a dos
6 0110 Grupo 0 y Grupo 1
en dos buscando trminos que se puedan 9 1001 Grupo 1 y Grupo 2
combinar y variables que se puedan eliminar 10 1010 Los trminos
Grupo 3 7 0111 combinados se marcan
14 1110 como tales

Combinando trminos (I) Combinando trminos (II)

Grupo 0 0 0000 0, 1 000- 0, 1 000-
Grupo 1 1 0001 0, 2 00-0 0, 2 00-0 Los trminos combinados
2 0010 0, 8 -000 0, 8 -000 obtenidos anteriormente
8 1000 1, 5 0-01 1, 5 0-01 tambin se dividen en
Grupo 2 5 0101 1, 9 -001 1, 9 -001 grupos de acuerdo al
6 0110 2, 6 0-10 2, 6 0-10 nmero de 1s
9 1001 2,10 -010 2,10 -010 Grupos adyacentes se
10 1010 8, 9 100- 8, 9 100- combinan entre s slo si
Grupo 3 7 0111 8,10 10-0 8,10 10-0 difieren en 1 variable y
14 1110 5, 7 01-1 5, 7 01-1 tienen guiones en la
6, 7 011- 6, 7 011- misma columna
6,14 -110 6,14 -110
10,14 1-10 10,14 1-10

2014 Mario Medina C. 1

 Combinando trminos (III) Combinando trminos (IV)
0, 1 000-
0, 2 00-0
0,1,8,9 -00-
0, 8 -000 0,2,8,10 -0-0 1, 5 0-01 acd
1, 5 0-01 0,8,1,9 -00-
5, 7 01-1 abd
1, 9 -001 0,8,2,10 -0-0
2, 6 0-10 2,6,10,14 --10 6, 7 011- abc
2,10 -010
2,10,6,14 --10
8, 9 100- 0,1,8,9 -00- bc
8,10 10-0
5, 7 01-1 El proceso termina cuando 0,2,8,10 -0-0 bd
6, 7 011- ya no se puede seguir
6,14 -110 combinando trminos 2,6,10,14 --10 cd
10,14 1-10

Implicantes primos Grfico de implicantes primos

Trminos no marcados al final del proceso son los Crculo indica minitrminos que aparecen
implicantes primos slo en un implicante
F = ACD + ABD + ABC + BC + BD + CD Esos son implicantes primos esenciales
Pero, la funcin no es mnima!
Puede contener trminos redundantes
Cules implicantes primos son esenciales?
Segunda etapa de mtodo de Quine-McCluskey
Mtodo grfico

Grfico de implicantes primos Grfico de implicantes primos

Tachar todos los minitrminos cubiertos por
Implicante primo esencial bc cubre
los implicantes primos esenciales
minitrminos 0, 1, 8, 9
Agregar implicantes primos que cubran el resto
Implicante primo esencial cd cubre
minitrminos 2, 6, 10, 14
Quedan los minitrminos 5 y 7
Implicante primo abd cubre ambos
minitrminos

2014 Mario Medina C. 2

 Ejemplo sin I. P. Esenciales Ejemplo sin I. P. Esenciales
F(a, b, c) = m(0, 1, 2, 5, 6, 7) No hay implicantes primos esenciales
F(a, b, c) = ab + bc + ac = ac + bc + ab
0 000 0,1 00-
1 001 0,2 0-0 Son todos
2 010 1,5 -01 implicantes primos
no esenciales!
5 101 2,6 -10
6 110 5,7 1-1
7 111 6,7 11-

Ejemplo sin I. P. Esenciales Mtodo de Petrick

Caso anterior equivalente a Mtodo sistemtico para encontrar todas
las soluciones de suma de productos para
un grfico de implicantes primos
Reducir el grfico de I. P. eliminando filas y
columnas de los implicantes primos esenciales
Rotular las filas del grfico reducido como
productos P1, P2, etc.
Formar una funcin lgica P que sea 1 cuando
todas las columnas estn cubiertas
Aplicar teoremas del lgebra Booleana!

Mtodo de Petrick Mtodo de Petrick

Tabla anterior con las filas rotuladas P = (P1 + P2)(P1 + P3)(P2 + P4)(P3 + P5)(P4 + P6)(P5 + P6)
Convirtiendo la expresin anterior de
producto de sumas a suma de productos, da
(P1 + P2) P = P1 P4 P5 + P1 P2 P5 P6 + P2 P3 P4 P5 + P1 P3 P4 P6 + P2 P3 P6
(P1 + P3) Cada trmino representa una combinacin de
implicantes primos que cubre todos los
minitrminos
Escoger una que tenga el nmero mnimo de literales
P2 P3 P6 = AC + BC + AB
P1 P4 P5 = AB + BC + AC

2014 Mario Medina C. 3

 Funciones con trminos Ejemplo con trminos
redundantes redundantes
Trminos redundantes se incluyen en la F(A, B, C, D) = m(2, 3, 7, 9, 11, 13) + d(1, 10, 15)
primera etapa del mtodo BD

Generacin de implicantes primos BC

CD
Trminos redundantes no se incluyen en la AD

etapa del grfico

Proceso de simplificacin asigna valores a los
trminos redundantes

Ejemplo con trminos

redundantes Ejercicios: Quine-McCluskey
Tres ltimas filas son implicantes esenciales Utilice el mtodo de Quine-McCluskey para
F(A, B, C, D) = BC + CD + AD minimizar la funcin f(a, b, c, d, e) = m(0, 2,
d10 y d15 valen 1, d1 vale 0
3, 7, 11, 13, 14, 15, 16, 23, 28, 29, 30, 31)
Utilice el mtodo de Quine-McCluskey para
BD minimizar la funcin f(a, b, c, d) = m(0, 2, 6,
BC
8, 9, 10, 12) + d(5, 7, 14)
CD
AD

Mtodo de Quine-McCluskey Mtodo de Quine-McCluskey

Nmero de patrones de n bits con q bits en 1 El mtodo de Quine-McCluskey comienza
0 1 2 3 4 5 6 7 comparando patrones de 2 en 2
1 1 1
Nmero de variables en la funcin

Para n = 3, son 15 comparaciones mx.

2 1 2 1 Este es un tringulo de Pascal!
Para n = 4, son 56 comparaciones mx.
3 1 3 3 1
Para n = 5, son 210 comparaciones mx.
4 1 4 6 4 1
Se puede demostrar que el nmero de
5 1 5 10 10 5 1
implicantes primos es como mximo 3n/n
6 1 6 15 20 15 6 1
Quine-McCluskey es inviable para n grande
7 1 7 21 35 35 21 7 1

2014 Mario Medina C. 4