Metodo de Quine McCluskey

Método de minimización de Quine

El método de Quine-McCluskey una función booleana. Básicamente este método tiene dos ventajas sobre el mapa de Karnaugh. La primera es que se trata de un métodouna función mínima que depende patrones que el método de mapa de Karnaugh, limitado en la práctica a cinco o seis variables. En general el método Qmintérminos de la función para determinar todas las combinaciones de mintérminos adyacentes lógicamente.

Paso 1: Enumerar en una columna todos los su representación binaria. Separarbinaria. Esta partición facilitara la identificación de los mintérminos adyacentes lógicamente que para serlo, dos mintérminos deben diferir exactamente en una literal y, por tanto, la representación binaria de un mintérminotro.

Paso 2: Realizar una búsqueda vecinos e incluirlos en una columna de implicantes de (término ya incluido. La representación binaria de cada nuevo implicante tiene un guion en la posición de la variable eliminada. Este procedimiento se repite para cada columna, cambiando los implicantes de (netc., hasta que no se puedan unir representara un implicante primo de la función, pues no queda cubierto por un implicante mayor. El resultado final es una lista de implicantes primos de la

Paso 3: Construir una tabla de implicantes primos que enumere los mintérminos en sentido horizontal y los implicantes primos en sentido vertical, escribiendo una entradacierto implicante primo (fila) cubra un mintérmino (columna).

Paso 4: Seleccionar un númeromintérminos de la función de conmutación.

En el siguiente ejemplo se describen cada uno de los pasos.

Ejemplo: Minimizar la siguiente función utilizando el método de Quine

f(A,B,C,D) = ∑m(2,3,4,5,7,8,10,13,15)

Paso 1: Debemos representar los continuación.

Instituto Tecnológico de Culiacán

Electrónica Digital II

Héctor Manuel Monroy Garc

Método de minimización de Quine-McCluskey

McCluskey (Q-M) es un método de tabular para la minimización de una función booleana. Básicamente este método tiene dos ventajas sobre el mapa de Karnaugh. La primera es que se trata de un método directo y sistemático para determinar

que depende menos de la habilidad del diseñador para reconocer patrones que el método de mapa de Karnaugh, limitado en la práctica a cinco o seis variables. En general el método Q-M realiza una búsqueda lineal ordenada sobre los mintérminos de la función para determinar todas las combinaciones de mintérminos

Enumerar en una columna todos los mintérminos de la función por minimizar, en su representación binaria. Separar los grupos según el número de unos en su representación

Esta partición facilitara la identificación de los mintérminos adyacentes lógicamente que para serlo, dos mintérminos deben diferir exactamente en una literal y, por

binaria de un mintérmino debe tener un bit 1 menos o má

Paso 2: Realizar una búsqueda exhaustiva de los mintérminos adyacentes entre grupos vecinos e incluirlos en una columna de implicantes de (n-1) variables, marcando cada

ido. La representación binaria de cada nuevo implicante tiene un guion en la posición de la variable eliminada. Este procedimiento se repite para cada columna, cambiando los implicantes de (n-1) variables para obtener implicantes de (n

hasta que no se puedan unir más implicantes. Cualquier término representara un implicante primo de la función, pues no queda cubierto por un implicante mayor. El resultado final es una lista de implicantes primos de la función de conmutación.

Paso 3: Construir una tabla de implicantes primos que enumere los mintérminos en sentido horizontal y los implicantes primos en sentido vertical, escribiendo una entradacierto implicante primo (fila) cubra un mintérmino (columna).

número mínimo de implicantes primos que cubran a todos los mintérminos de la función de conmutación.

En el siguiente ejemplo se describen cada uno de los pasos.

inimizar la siguiente función utilizando el método de Quine-McCluskey

m(2,3,4,5,7,8,10,13,15)

ebemos representar los mintérminos en su forma binaria, la cual se muestra a



Héctor Manuel Monroy García

es un método de tabular para la minimización de una función booleana. Básicamente este método tiene dos ventajas sobre el mapa de

directo y sistemático para determinar menos de la habilidad del diseñador para reconocer

patrones que el método de mapa de Karnaugh, limitado en la práctica a cinco o seis ueda lineal ordenada sobre los

mintérminos de la función para determinar todas las combinaciones de mintérminos

de la función por minimizar, en de unos en su representación

Esta partición facilitara la identificación de los mintérminos adyacentes lógicamente que para serlo, dos mintérminos deben diferir exactamente en una literal y, por

o debe tener un bit 1 menos o más que el

adyacentes entre grupos 1) variables, marcando cada

ido. La representación binaria de cada nuevo implicante tiene un guion en la posición de la variable eliminada. Este procedimiento se repite para cada columna,

1) variables para obtener implicantes de (n-2) variables, no eliminado

representara un implicante primo de la función, pues no queda cubierto por un implicante de conmutación.

Paso 3: Construir una tabla de implicantes primos que enumere los mintérminos en sentido horizontal y los implicantes primos en sentido vertical, escribiendo una entrada × cuando

mínimo de implicantes primos que cubran a todos los

McCluskey.

en su forma binaria, la cual se muestra a

En la tabla 2 agrupamos los mintérminos

Tabla 2

Paso 2: Realizamos la búsqueda exhaustiva de los vecinos e incluirlos en una nueva lista, marcando conque recordar que para que un sola literal, por ejemplo: el mintérminoque solo difieren en la literal D. Lcolumna colocando un “ - “ en lugar de la literal que difiere.términos que son adyacentes.

Mintérminos A B C

2 0 0 1

4 0 1 0

8 1 0 0

3 0 0 1

5 0 1 0

10 1 0 1

7 0 1 1

13 1 1 0

15 1 1 1




Grupo 1 (un solo uno)

Grupo 4 (cuatro unos)

Grupo 3 (tres unos)

Grupo 2 (dos unos)

Mintérminos A B C D

2 0 0 1 0

3 0 0 1 1

4 0 1 0 0

5 0 1 0 1

7 0 1 1 1

8 1 0 0 0

10 1 0 1 0

13 1 1 0 1

15 1 1 1 1

mintérminos según el número de unos en su representación.

mos la búsqueda exhaustiva de los mintérminos adyacentes entre grupos vecinos e incluirlos en una nueva lista, marcando con • cada mintérmino ya incluido.

ara que un mintérmino sea adyacente con otro, solo deben diferir en una mintérmino 2 (0010) es adyacente al mintérmino

teral D. Los mintérminos adyacentes los anotamos en una nueva “ en lugar de la literal que difiere. La tabla 3 muestra los

C D

1 0

0 0

0 0

1 1

0 1

1 0

1 1

0 1

1 1




mero de unos en su representación.

adyacentes entre grupos ya incluido. Hay

otro, solo deben diferir en una mintérmino 3 (0011) ya

adyacentes los anotamos en una nueva La tabla 3 muestra los

Tabla 3

Se puede observar que no es necesario comparar cada uno de los son adyacentes los que se encuentran en grupos vdel grupo dos, los del grupo tres con los grupos

Ahora realizamos la búsqueda exhaustiva en los resulta evidente porque es importante marcar las vacomo antes, podemos combinar dos términos única literal, solo podríamos combinar los términos a los cuales les(un guión en la misma posición

La tabla 4 nos muestra que solo son adyacentes los mintérminos 5,13 y 7, 15 también son adyacentes pero como ya están contenidos en el mintérmino anterior, no es necesario anotarlos.

Una forma conveniente de verificar loses realizar la siguiente prueba de entrada: restamos los números de los mintérminos para verificar que hemos omitido las variables adecuadas. Por ejemplo, la entrada (2,10 de la segunda columna de mintérminos indica que debemos eliminar la variable con peso 10 – 2 = 8. En este ejemplo los posibles pesos son 8, 4, 2, 1.

Para la entrada de la tercera columna de

7 – 5 = 2

15 – 13 = 2 13

Mintérminos A

2 0

4 0

8 1

3 0

5 0

10 1

7 0

13 1

15 1




Se puede observar que no es necesario comparar cada uno de los mintérminosson adyacentes los que se encuentran en grupos vecinos, es decir, los del grupo uno con los del grupo dos, los del grupo tres con los grupos dos y cuatro, etc.

Ahora realizamos la búsqueda exhaustiva en los mintérminos de la segunda columna, aquí resulta evidente porque es importante marcar las variables que han sido eliminadas,

podemos combinar dos términos de la segunda columna solo si difieren en una única literal, solo podríamos combinar los términos a los cuales les falta la misma literal

posición).

que solo son adyacentes los mintérminos 5,7 y 13,5, se observa que 5,13 y 7, 15 también son adyacentes pero como ya están contenidos en el

anterior, no es necesario anotarlos.

Una forma conveniente de verificar los errores en las listas de los mintérminos adyacentes es realizar la siguiente prueba de entrada: restamos los números de los mintérminos para verificar que hemos omitido las variables adecuadas. Por ejemplo, la entrada (2,10

de mintérminos indica que debemos eliminar la variable con peso . En este ejemplo los posibles pesos son 8, 4, 2, 1.

entrada de la tercera columna de mintérminos (5, 7, 13 ,15 -1-1):

5 = 2 15 – 7 = 8

13 = 2 13 – 5 = 8

A B C D Mintérminos A B C D

0 0 1 0 • 2,3 0 0 1 -

0 1 0 0 • 2,10 - 0 1 0

1 0 0 0 • 4,5 0 1 0 -

8,10 1 0 - 0

0 0 1 1 •

0 1 0 1 • 3,7 0 - 1 1

1 0 1 0 • 5,7 0 1 - 1

5,13 - 1 0 1

0 1 1 1 •

1 1 0 1 • 7,15 - 1 1 1

13,15 1 1 - 1

1 1 1 1 •




mintérminos ya que solo ecinos, es decir, los del grupo uno con los

de la segunda columna, aquí s que han sido eliminadas, ya que

de la segunda columna solo si difieren en una falta la misma literal

5,7 y 13,5, se observa que 5,13 y 7, 15 también son adyacentes pero como ya están contenidos en el

errores en las listas de los mintérminos adyacentes es realizar la siguiente prueba de entrada: restamos los números de los mintérminos para verificar que hemos omitido las variables adecuadas. Por ejemplo, la entrada (2,10 - 0 1 0)

de mintérminos indica que debemos eliminar la variable con peso

Tabla 4

Como ya no se pueden combinartoda la tabla son implicantes (PI)

Paso 3: Formar la tabla de implicantes implicantes primos necesarios par

En las filas colocamos los mintérminoscolocamos una × en los mintérminos

Tabla 5

Se observa que los mintérminosun solo implicante primo PI1 , PIPI4 , PI5 , que entonces son implicantes primos esenciales al elegir estos tres implicantes los marcamos en la tabla con una

Mintérminos A B C D

2 0 0 1 0 •

4 0 1 0 0 •

8 1 0 0 0 •

3 0 0 1 1 •

5 0 1 0 1 •

10 1 0 1 0 •

7 0 1 1 1 •

13 1 1 0 1 •

15 1 1 1 1 •

×× PI1

PI2

PI3

×× PI4

×× PI5

PI6




e pueden combinar otros términos, por tanto los términos no marcados en (PI) primos y los llamamos PI1 … PI6 .

Paso 3: Formar la tabla de implicantes primos para determinar el mínimo núimplicantes primos necesarios para realizar la función.

mintérminos y en las columnas los implicantes primosmintérminos que cubre cada implicante primo. Ver tabla 5.

mintérminos 4,8,13,15 (marcados por ©) quedan cubiertos cada uno por , PI4 , PI5 por tanto debemos elegir los implicantes primos PI

implicantes primos esenciales (indicados con ×× )al elegir estos tres implicantes primos también hemos cubierto a los mintérminos

con una • sobre los números de los mintérminos.

Mintérminos A B C D Mintérminos A

2,3 0 0 1 - PI2 5,7,13,15 -

2,10 - 0 1 0 PI3 5,13,7,15 -

4,5 0 1 0 - PI4

8,10 1 0 - 0 PI5

3,7 0 - 1 1 PI6

5,7 0 1 - 1 •

5,13 - 1 0 1 •

7,15 - 1 1 1 •

13,15 1 1 - 1 •

• • •

2 3 4 5 7 8 10 13 15

× × © ©

× ×

×

© ×

© ×

× ×




, por tanto los términos no marcados en

mos para determinar el mínimo número de

y en las columnas los implicantes primos, además que cubre cada implicante primo. Ver tabla 5.

(marcados por ©) quedan cubiertos cada uno por debemos elegir los implicantes primos PI1,

). Observe que mintérminos 5,7 y 10,

B C D

1 - 1 PI1

1 - 1

El problema siguiente es seleccionar el menor esenciales) adicionales necesarios para cubrir los formando una tabla reducida de implicante

Observe que la tabla solo contiene los implicantes primos restantes para su inclusión en la cubierta.

Observe que la mejor forma de cubrir los implicantes primos es elegir PIrestantes indican que hemos generado una cubierta completa.

Por tanto, una realización mínima de la func

f(A,B,C,D) = PI1 + PI2 + PI4 +

= -1-1 + 001- +010

= ��

Comprobación minimizando la función mediante mapas de

f




El problema siguiente es seleccionar el menor número de implicantes primos (no adicionales necesarios para cubrir los mintérminos 2 y 3. Realizamos esto

formando una tabla reducida de implicantes primos, misma que se muestra a continuación.

Observe que la tabla solo contiene los mintérminos que faltan por cubrir y los candidatos a implicantes primos restantes para su inclusión en la cubierta.

rve que la mejor forma de cubrir los mintérminos 2 y 3 con el menor número de PI2 (lo marcamos con ××) y las marcas sobre los

restantes indican que hemos generado una cubierta completa.

ínima de la función original seria:

+ PI5

+010- + 10-0

��

la función mediante mapas de Karnaugh

= ��

• •

2 3

×× PI2 × ×

PI3 ×

PI6 ×

CD

AB 00 01 11 10

00 1 1

01 1 1 1

11 1 1

10 1 1




de implicantes primos (no 2 y 3. Realizamos esto

s primos, misma que se muestra a continuación.

que faltan por cubrir y los candidatos a

2 y 3 con el menor número de (lo marcamos con ××) y las marcas sobre los mintérminos

Análisis y Diseño de Circuitos Lógicos Digitales

Víctor P. Nelson

H. Troy Nagle

Bill D. Carrol

J. David Irwin

Prentice Hall México 1996

Paginas: 189, 211




BIBLIOGRAFÍA

lisis y Diseño de Circuitos Lógicos Digitales




Metodo de Quine McCluskey

Documents

Transcript of Metodo de Quine McCluskey