QUINEMcCLUKEYS

Tabla de Implicantes Primos

Tabla de Implicantes Primos

Contexto

Parte de los circuitos electrónicos se estructuran bajo diseño digital donde se ven involucradas distintas herramientas y métodos para análisis y simplificación. Tienen amplia área de aplicación desde dispositivos personales hasta sistemas militares robustos, y cada día toman más impulso en el sector industrial.

Las estrategias para simplificar expresiones booleanas más utilizadas son:

Álgebra de Boole (A-B)

Mapas de Karnaugh (M-K)

Método de Quine McCluskey (Q-M)

Cada una se utiliza en situaciones propias o a dominio del diseñador

Un método ampliamente utilizado cuando se tiene mayor cantidad de variables es Quine-McCluskey (Q-M), cuyos autores son Willard Van Orman Quine y Edward J. McCluskey. Es un algoritmo sistemático que cubre las limitaciones de los métodos gráficos (m-k y t-v), por tanto, es útil para simplificar funciones lógicas de niveles más complejos

Definición del método

También llamado método tabular, se utiliza para reducir ecuaciones Booleanas. El método se divide en dos partes: encontrar los implicantes primos y obtener las ecuaciones a partir de la tabla de implicantes primos.

Es un método tabulador para ser programado en un computador, y que se representan los implicantes primos en forma binaria.

Método de Quine.McCluskey, al igual que los mapas de Karnaugh, tiene un componente heurístico cuando se trata de completar la cubierta, o conjunto de implicantes primos necesarios para terminar de cubrir los minitérminos de una función y que no son cubiertos por los implicantes primos esenciales.

El método Q-M, es la estrategia que mejor se ajusta con cantidades de variables mayores de 5. Se basa en asignar un número decimal a cada término canónico, normalmente minitérminos e ir obteniendo de manera sistemática las adyacencias de órdenes crecientes, hasta llegar a las de mayor orden posible que se incluyan en la función, estas reciben el nombre de primos implicantes

Conceptos claves

Implicante primo esencial

Implicante primo

Implicante

Implicante que no se puede combinar para formar otro subcubo No contiene literales repetidos No contiene una variable y su complemento No contiene redundante, si se descarta un literal implicante el resto no se’r implicante Si X e Y son implicantes primos de F, entonces: X no cubre a Y, y viceversa

Elemento individual del on-set o grupo de estos elementos que puede combinar para formar un subcubo

Un implicante primo es esencial si el es el único que cubre un elemento on-set o minitérmino va a participar de todas las posibilidades de cobertura on-set.

Algoritmos Q-M para encontrar implicantes primos

A grandes rasgos consiste en:

Formar columnas con los minitérminos de la función.

Formar siguientes columnas de acuerdo a:

Revisar primer elemento de la columna con todos los siguientes: si se encuentra un término que difiere de una variable, se le anota en la nueva columna omitiendo el literal correspondiente; se marcan los términos en la columna actual. Se repite para todos los elementos.

Repetir el paso anterior hasta que no pueda formar más columnas.

Después se pueden encontrar los implicantes primos esenciales usando la tabla de implicantes primos.

Explicación del proceso

Ejemplo

Obtención de la ecuación final

Marcado de la tabla

Dibujo de la tabla

1. Se dibuja una tabla, en las columnas se acomodan los mintérminos. 2. Acomodar en los renglones los términos de la última columna y de las columnasanteriores que no fueron marcados. 3. Se coloca una X en donde cruzan los términos con los mintérminos.

Tabla de Implicantes Primos

4. Se agrupan verticalmente las X 5. Las X que quedan solas son las que marcan cuál término pasará a ser parte de la ecuación final. Esta X eliminará a las que se encuentran en su mismo renglón y se deben marcar los mintérminos involucrados.

6. Si al final quedan mintérminos sin marcar, se tomará un término que los involucre, tomando el mismo criterio que en mapas de Karnaugh: agrupar el mayor número de mintérminos en el menor número de grupos posibles. 7. Los guiones representan a las variables que se eliminan, los 1 a las variables y los 0 a las variables negadas, formando cada una de las partes de la ecuación final.

A B C D

Ecuación

(0,1,4,5,8,9,12,13) (0,2,8,10) (5,7,13,15)

_ _ 0 _ _ 0 _ 0 _ 1 _ 1

C' B' D' B D

Ecuación final: C’ + B’ D’ + B D