simplificacióndefunciones(4)

Simplificación de funciones (4)

Algoritmo de Quine – McCluskey ANTERIOR INDICE

El empleo del mapa de Karnaugh es conveniente cuando la función a minimizar no contiene más de cinco o seis variables. En estos casos, empleamos un procedimiento sistemático, llamado el algoritmo de Quine–McCluskey, el cual produce una expresión normalizada y simplificada. El algoritmo debe obedecer a un conjunto de pasos que se verán a través de un ejemplo.

Ejemplo

Simplificar la función de Boole usando el algoritmo de Quine-McCluskey.

1. Enumerar en una tabla todos los mintérminos en forma binaria, organizados según el número de unos que contenga. La aplicación de este paso se muestra en la tabla 2.5.1.

1. Tabla 2.5.1. Mintérminos agrupados según la cantidad de unos
1. Entre los grupos adyacentes buscar los mintérminos que sólo difieren en un bit en la misma posición, para hallar los primeros implicantes primos.
2. La metodología consiste en comparar el primer mintérmino con el resto de los términos del segundo grupo. Así, los términos del segundo grupo se comparan con los mintérminos del grupo siguiente. De la forma anterior, se procede con los demás mintérminos de los demás grupos. Los mintérminos utilizados se les pone una marca (√ ) con el fin de ir diferenciando los términos utilizados y la variable apareada en el proceso se reemplaza con un guión para denotar la eliminación de la variable. Los términos no marcados en la tabla son los primeros implicantes primos (PI_X). Los mintérminos utilizados se les pone una marca (√ ) con el fin de ir diferenciando los términos utilizados y la variable apareada en el proceso anterior se reemplaza con un guión para denotar la eliminación de la variable.

1. Tabla 2.5.2. Implicantes primos de la función F₁
1. Construir una tabla que enumere los implicantes primos y los mintérminos contenidos por cada implicante primo. La letra X en la tabla 2.5.3 indica el mintérmino contenido en cada implicado por fila. Por ejemplo, en la tabla se observa en el primer renglón los mintérminos 2, 3, 6 y 7 para el primer implicante primo. El resto de la tabla se construye de forma similar.

1. Tabla 2.5.3. Selección de implicantes primos esenciales
1. En la tabla se seleccionan las columnas de los mintérminos que contengan solamente una cruz. En este ejemplo, hay dos mintérminos cuyas columnas tienen una sola cruz: 6 y 15. Es decir, la selección del primer implicado PI₁ (A’·C) garantiza que el término mínimo 6 está incluido en la función. De la misma forma, el término mínimo 7 está cubierto por el primer implicado PI₇ (A'·B·C·D). Los primeros implicados que cubren los mintérminos con una sola cruz, se llaman primeros implicados esenciales (en la tabla se encuentran marcados con un asterisco) y son indispensables en la construcción de la función.
2. Seleccionar en cada columna los mintérminos que estén cubiertos por los primeros implicados esenciales. Por ejemplo, el primer implicado esencial * PI₁ (A’·C) cubre los mintérminos 2, 3, 6 y 7. De la misma forma, el primer implicado esencial *PI₇ (A'·B·C·D) cubre los mintérminos 7 y 15. Hasta el momento la selección de primeros implicados cubre los mintérminos 2, 3, 6, 7 y 15 excepto 1, 8, 9 y 10. Estos términos mínimos deben ser seleccionados por medio de otros primeros implicados esenciales. En la tabla 2.5., la selección de los primeros implicados PI₃ y PI₆ garantiza el cubrimiento de los términos mínimos 1, 8, 9 y 10. En la tabla 2.5.4. se muestra el proceso de selección.

Tabla 2.5.4. Selección de primeros implicados esenciales

La función simplificada se obtiene de la suma de los primeros implicados hallados:

F= PI₁ + PI₃ +PI₆ + PI₇

F= (0-1-) + (-001) + (10-0) + (-111)

F = A'·C + B’·C’·D + A·B’·D’ + B·C·D

Ing. Naur Avila Estrada