Método de Quine-McCluskey

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de marzo de 2021; las comprobaciones requieren 23 ediciones .

El método Quine – McCluskey es un  método tabular para minimizar funciones booleanas propuesto por Willard Quine y mejorado por Edward McCluskey . Es un intento de deshacerse de las deficiencias del método de Quine .

Algoritmo de minimización

  1. Los términos (conjuntivos en el caso de SDNF y disyuntivos en el caso de SKNF ) sobre los que se define la función de álgebra lógica (FAL) se escriben como sus equivalentes binarios;
  2. Estos equivalentes se dividen en grupos, cada grupo incluye equivalentes con igual número de unos (ceros);
  3. Se realiza una comparación por pares de equivalentes (términos) en grupos vecinos para formar términos de rango inferior;
  4. Se compila una tabla en la que los encabezados de las filas son los términos iniciales y los encabezados de las columnas son los términos de los rangos inferiores;
  5. Se colocan etiquetas que reflejan la absorción de términos de rangos superiores (términos iniciales) y luego se realiza la minimización según el método de Quine .

Características

La especificidad del método de Quine-McCluskey en comparación con el método de Quine es reducir el número de comparaciones por pares para su pegado. La reducción se logra debido a la división inicial de los términos en grupos con igual número de unos (ceros). Esto permite excluir comparaciones que obviamente no dan pegado.

Aunque es más práctico que los mapas de Karnaugh cuando se trata de más de cuatro variables, el método de Quine-McCluskey también tiene limitaciones de alcance, ya que el tiempo de ejecución del método crece exponencialmente con el aumento de los datos de entrada. Se puede demostrar que para una función de n variables el límite superior del número de implicantes principales es 3 n / n . Si n = 32 puede haber más de 6,5 * 10 15 . Véase también problema de transcomputación .

Las funciones con una gran cantidad de variables deben minimizarse con una heurística potencialmente subóptima . Hoy en día, el algoritmo heurístico de minimización de espresso es el estándar mundial de facto [1] .

Ejemplo

Paso 1: encontrar los implicantes principales

Sea dada la función usando la siguiente tabla de verdad :

#
0 0 0 0 0 0
una 0 0 0 una 0
2 0 0 una 0 0
3 0 0 una una 0
cuatro 0 una 0 0 una
5 0 una 0 una 0
6 0 una una 0 0
7 0 una una una 0
#
ocho una 0 0 0 una
9 una 0 0 una una
diez una 0 una 0 una
once una 0 una una una
12 una una 0 0 una
13 una una 0 una 0
catorce una una una 0 una
quince una una una una una

Uno puede escribir fácilmente SDNF simplemente sumando los minitérminos (ignorando los términos definidos de manera incompleta ), donde la función toma el valor 1.

Para optimizar, escribimos los minitérminos, incluidos los que corresponden a estados indiferentes, en la siguiente tabla:

Cantidad: 1 término mínimo representación binaria
una M4 0100
M8 1000
2 M9 1001
M10 1010
M12 1100
3 M11 1011
M14 1110
cuatro M15 1111

Ahora puede comenzar a combinar minterms entre sí, es decir, realizar la operación de pegado. Si dos minitérminos difieren solo en un carácter que está en la misma posición en ambos, reemplazamos este carácter por “-”, lo que significa que este carácter no nos importa. Los términos que no pueden combinarse más se indican con "*". Al pasar a implicantes de segundo rango, interpretamos "-" como el tercer valor. Por ejemplo: -110 y -100 o -11- se pueden combinar, pero no -110 y 011-. (Sugerencia: compare "-" primero).

Cantidad "1" Minitérminos | Implicantes de nivel 1 | Implicantes de nivel 2 ---------------------------|------------- ------- ----|------------------------------------- 1 m4 0100 | m(4,12) -100* | m(8,9,10,11) 10--* m8 1000 | m(8,9) 100- | m(8,10,12,14) 1--0* ------------------------------| m(8,10) 10-0 |-------------------------------------- 2m9 1001 | m(8,12) 1-00 | m(10,11,14,15) 1-1-* m10 1010 |-----------------------| m12 1100 | m(9,11) 10-1 | ------------------------------| m(10,11) 101- | 3m11 1011 | m(10,14) 1-10 | m14 1110 | m(12,14) 11-0 | ---------------------------|------------- ------- ----| 4m15 1111 | m(11,15) 1-11 | | m(14,15) 111- |

Paso 2: tabla de implicantes primos

Cuando ya no es posible realizar más combinaciones, construimos una tabla de implicantes primos. Aquí tomamos en cuenta solo aquellas salidas de la función que importan, es decir, no prestamos atención a estados incompletamente definidos.

cuatro ocho 9 diez once 12 catorce quince
m(4,12) X X -100
m(8,9,10,11) X X X X diez--
m(8,10,12,14) X X X X 1--0
m(10,11,14,15) X X X X 1-1-

El principio de selección implicante es el mismo que en el método de Quine . Los implicantes simples que son núcleos se muestran en negrita. En este ejemplo, los núcleos no cubren todos los minitérminos, en cuyo caso se puede realizar un procedimiento adicional de simplificación de tablas (consulte el método de Petrik ). Obtenemos la siguiente opción:

Notas

  1. ↑ VP Nelson ea, Diseño y análisis de circuitos digitales , Prentice Hall, 1995, pág. 234

Enlaces