Algebra de Boole (3)

Simplificación de funciones booleanas

En el artículo anterior vimos dos métodos de simplificación de funciones booleanas.

Los mapas de Karnaugh son métodos gráficos, fáciles de usar pero limitados a cinco variables como mucho, y difíciles de programar.

El algoritmo de Quine-McCluskey, por otra parte, es más laborioso de aplicar sobre el papel, pero es mucho más fácil de programar, y una vez hecho, no hay límite al número de variables de entrada, salvo la memoria disponible y la capacidad del ordenador.

En este artículo implementaremos este algoritmo en C++, lo que nos será muy útil en siguientes artículos, no solo para crear circuitos lógicos, sino que veremos que se puede aplicar también a la programación de microcontroladores.

Estructuras de datos

Con el fin de optimizar el programa haremos uso de varias estructuras de datos de la biblioteca estándar STL de C++, porque no siempre es necesario reinventar la rueda.

Como aún no hemos incluido en la página la documentación de STL, recomendamos acudir a la página cppreference.com, que ya dispone de una referencia muy completa al respecto.

Estructura vector

Un vector STL es una plantilla para una estructura dinámica que permite almacenar objetos del mismo tipo, estructura o clase. Se comportan igual que un array, los elementos se almacenan en posiciones de memoria consecutivas y se puede acceder a ellos mediante un índice, usando el operador [].

Entre los métodos de que dispone, tenemos size, que nos devuelve el número de elementos, y nos resultará útil en bucles, al igual que los iteradores begin y end.

La misma estructura puede usarse para crear pilas, ya que dispone de los métodos push_back y pop_back.

#include <vector>

std::vector<int> iVector = { 2, 4, 7, 12, 23 };

Estructura list

Una list es una plantilla para una estructura de lista enlazada. No permite el acceso aleatorio, como sí sucede en los vectores.

Entre los métodos de que dispone, usaremos push_back para añadir elementos al final de la lista, y el método sort para ordenar la lista.

Para recorrer la lista usaremos los iteradores begin y end.

#include <list>

std::list<int> iLista;
iLista.push_back(34);

Estructura map

La estructura map es una plantilla para construir contenedores asociativos. Un contenedor asociativo funciona de forma parecida a un array, pero los índices pueden ser de cualquier tipo. Aunque en este programa los índices serán de tipo entero, usar un mapa tiene la ventaja de que los índices que no hayamos añadido no existirán en la estructura.

Por ejemplo, si insertamos elementos para los índices 2, 5, 7 y 9, el mapa no contendrá valores para los índices 0, 1, 3, 4, 6 y 8.

Usaremos el operador operator[], que permite tanto acceder a la referencia a un elemento como insertar elementos nuevos.

Para averiguar si un elemento existe o no usaremos el método find.

También disponemos de los iteradores begin y end.

#include <map>

std::map siMapa;
siMapa["Manzana"] = 10;
siMapa["Naranja"] = 2;

Funciones algorithm

Los algoritmos STL incluyen tareas que se pueden aplicar sobre los contenedores. En nuestro caso usaremos el algoritmo sort para ordenar vectores.

Cuando se trate de vectores de elementos de tipos fundamentales no será necesario añadir métodos, constructores ni operadores, pero cuando los elementos sean estructuras o clases, sí tendremos que hacerlo.

Concretamente, necesitaremos implementar para la estructura o clase un constructor copia y sobrecargar el operador de asignación, ya que el algoritmo sort los usará internamente.

Además, deberemos definir un método estático de comparación que devuelva un booleano y admita dos parámetros que sean referencias a objetos de la estructura o clase.

Para ordenar un vector se debe usar la función sort con tres parámetros. El primero es el iterador del inicio del rango a ordenar, normalmente begin. El segundo será el iterador del final del rango a ordenar, generalmente end y el tercero será la función de comparación que hemos definido.

Para tipos fundamentales se pueden omitir todos los parámetros si queremos ordenar todo el vector de menor a mayor.

#include <algorithm>
#include <vector>

std::vector<int> iVector = { 32, 2, 43, 1, 4, 6, 2};
std::sort(iVector.begin(), iVector.end());

Clase minterm

El algoritmo de Quine-McCluskey empieza determinando el número de entradas y eligiendo los minterms que definen la función y los redundantes (aquellos que agrupan combinaciones de entradas que no se pueden presentar). Después los ordenaremos por número de bits de valor uno que contienen.

Empezaremos definiendo una clase para almacenar y manipular un único minterm.

Para esta clase de objetos solo nos interesa almacenar su valor y contar los bits con valor uno.

class minterm {
public:
    // Constructor
    minterm(long int v=0);
    // Interfaz
    int Valor() { return valor; }
    int BitsActivos() { return nBitsActivos; }
    bool operator<(minterm &m) { return valor<m.Valor(); }
    bool operator==(minterm &m) { return valor==m.Valor(); }
private:
    long int valor;     /**< Valor del minterm 64 bits */
    int nBitsActivos;   /**< Número de bits con valor 1 */
};

minterm::minterm(long int v) : valor(v), nBitsActivos(0) {
    int m = valor;

    while(m) {
        if(m & 1) nBitsActivos++;
        m >>= 1;
    }
}

En nuestro programa crearemos dos vectores de minterms, uno m para almacenar los minterms que componen la función y otro r para almacenar los minterms redundantes. Por ejemplo, para la función g del codificador de siete segmentos tendremos:

    int noBits = 4;
    std::vector<minterm> m = {2,3,4,5,6,8,9};
    std::vector<minterm> r = {10,11,12,13,14,15};

Como ya dijimos, noBits es un valor importante en el algoritmo, y contiene el número de variables de entrada, que es lo que define el tamaño en bits de cada minterm.

Sería buena idea verificar que todos los minterms se pueden codificar con el número de entradas indicadas. Esto lo haremos en la versión GUI, que permitirá introducir los datos de la función al usuario. Otra alternativa es calcular el número de bits de entrada en función del minterm con el valor más alto.

Clase implicante

Un implicante es una combinación de minterms.

Inicialmente los implicantes son los minterms que componen la función, incluyendo los redundantes. Posteriormente obtendremos nuevos implicantes como resultado de combinar parejas de implicantes existentes. Y la condición para que dos implicantes se puedan combinar es que solo se diferencien en el valor de un bit.

En cada implicante nos interesa almacenar tanto la lista de minterms que lo componen como los valores de los bits que lo definen.

Para la lista de minterns que componen un implicante usaremos una estructura list de objetos de la clase minterm. Para los bits usaremos una cadena vector de caracteres. Esto es necesario ya que cada bit puede tener tres valores: 0, 1 o -.

En la primera fase del algoritmo crearemos una lista de implicantes a partir de los minterms que definen la función y de los redundantes. Todos los implicantes tendrán inicialmente un único minterm. Para ello usaremos el primer constructor, que toma como parámetro el valor de un minterm. Este constructor guarda el minterm y calcula el valor inicial del vector de bits.

Probablemente se podría haber prescindido de la clase minterm, ya que un minterm no deja de ser un implicante, pero considero que es más claro usar clases diferentes para cada objeto, y el código queda más limpio.

En fases sucesivas usaremos un segundo constructor que crea un nuevo implicante a partir de dos implicantes. De nuevo se crea la lista de minterms a partir de los de los dos implicantes de entrada. Opcionalmente se puede ordenar la lista de implicantes, pero no es necesario.

Para esta clase será necesario sobrecargar el operador de comparación operator==. Este operador compara dos implicantes y nos dice si son el mismo. Para ello es necesario comparar los bits de cada uno o la lista de minterms que lo componen. Como hemos usado una cadena para almacenar los bits, lo más simple es usar el operador de comparación de la clase vector.

También sobrecargamos el operador de sustracción operator-. Restar dos implicantes nos dará la cuenta de los bits diferentes entre ellos. Recordemos que solo es posible combinar dos implicantes si solo difieren en el valor de un bit.

A pesar de que intentaremos combinar implicantes con una diferencia de un bit activo, eso no implica que siempre se puedan combinar

El resto de métodos son el interfaz para acceder a los datos de la clase.

class implicante {
public:
    // Constructor a partir de un minter v
    implicante(minterm m=0) : marca(false), usado(false) {
        int mask = 1;
        lminterms.push_back(m.Valor());
        for(int i=0; i<tam; i++) {
            bits.insert(0, 1, (m.Valor() & mask) ? '1' :'0');
            mask <<= 1;
        }
    }
    // Constructor a partir de dos implicantes i1 e i2
    implicante(implicante &i1, implicante &i2 ) : marca(false), usado(false) {
        for(minterm n : i1.lminterms) lminterms.push_back(n);
        for(minterm n : i2.lminterms) lminterms.push_back(n);
        //lminterms.sort(); // Opcional, no necesario
        for(int i=0; i<tam; i++) {
            bits.push_back((i1.bits[i] == i2.bits[i]) ? i1.bits[i] :'-');
        }
        i1.usado = i2.usado = true;
    }
    static void SetTam(int t) { tam = t; }
    bool operator==(implicante &i) {
        return bits ==i.bits;
    }
    // Calcula el número de bits diferentes en dos implicantes
    int operator-(implicante &i2) {
        int d = 0;
        for(int i=0; i<tam; i++) {
            if(bits[i] != i2.bits[i]) d++;
        }
        return d;
    }
    // Interfaz
    std::string &Bit() { return bits; }
    int Tam() const { return tam; }
    std::list<minterm> &Minterm() { return lminterms; }
    bool Marca() const { return marca; }
    bool Usado() const { return usado; }
    void Marcar(bool m = true ) { marca = m; }
private:
    static int tam; // Tamaño del implicante = número de entradas
    std::string bits; // bits del implicante
    std::list<minterm> lminterms; // Lista de minterms que componen el implicante
    bool marca; // true si el implicante ha sido usado en una combinación
    bool usado; // variable auxiliar
};

Para el valor del número de entradas, que se almacena en el miembro tam hemos usado un entero estático. Esto es una optimización, ya que todos los implicantes de una función tienen el mismo número de bits, usar un objeto estático usa un único objeto para todos ellos. Por la misma razón también se ha declarado el método SetTam como estático.

Usar datos miembro estáticos implica que se ha de definir su valor. La implementación de esta clase incluye esa definición.

int implicante::tam=0;

Primera fase del algoritmo

Almacenaremos los implicantes en un array de dos dimensiones, usando un vector de vectores de la clase implicante.

El primer vector contendrá los implicantes sin ningún bit con valor 1, el segundo los implicantes con un bit con valor 1, etc.

En principio necesitaremos un vector más que el número de entradas de la función, aunque alguno de los vectores puede estar vacío.

En la primera fase del algoritmo intentaremos combinar los implicantes de grupos con un número de bits de valor uno que difieran en una unidad. Es decir, los implicantes sin bits uno con los que tengan un bit uno, los de un bit uno con los de dos, etc.

Esto es porque sabemos que dos implicantes que difieran en más de un bit con valor 1 no se podrán combinar, y tampoco se podrán combinar dos implicantes con el mismo número de bits con valor 1.

Para ello crearemos un vector de vectores de implicantes, al que llamaremos grupo. En el primer índice indicaremos el número de bits a uno de los implicantes que contiene. Así, en grupo[0] almacenaremos los implicantes sin ningún bit a uno, en grupo[1] los implicantes con un bit a uno, etc. Esto implica que puede haber un máximo de nº entradas + 1 grupos.

Para iniciar los vectores añadiremos cada implicante inicial, a partir de los minterms necesarios y redundantes al grupo correspondiente en función del número de bits a uno que contenga.

    int noBits = 4;
    std::vector<minterm> m = {2,3,4,5,6,8,9};
    std::vector<minterm> r = {10,11,12,13,14,15};
    vector<vector<implicante>> grupo;

    implicante::SetTam(noBits);

    grupo.resize(noBits+1); // Crear los grupos

    for(size_t i=0; i<m.size(); i++) {
        grupo[m[i].BitsActivos()].push_back(implicante(m[i]));
    };
    for(size_t i=0; i<r.size(); i++) {
        grupo[r[i].BitsActivos()].push_back(implicante(r[i]));
    };

Una vez creados los grupos, intentaremos combinar cada pareja de implicantes:

El bucle exterior se repite tantas veces como sea necesario hasta que no se puedan combinar más implicantes. Esto se hace en el bucle do..while, la condición será verdadera si se han combinado dos implicantes en una de las iteraciones.

Esta condición es relativamente simple:

• Ninguno de los implicantes ha sido marcado como usado previtamente en una combinación de implicantes.
• La diferencia de bits entre los dos implicantes debe ser 1.

Si estas dos condiciones se cumplen creamos un nuevo implicante combinándolos. El constructor que crea este nuevo implicante marcará los dos implicantes de entrada como usados.

El nuevo implicante siempre tendrá el mismo número de bits con valor 1 que el implicante de entrada con menos bits a 1.

Es decir, si combinamos un implicante con n bits a 1 con otro con n+1 bits a uno, el resultado tendrá n bits a 1.

Por ejemplo:

Implecante 1: 1010 (dos bits a 1)
Implecante 2: 1110  (tres bits a 1)
Resultado: 1-10 (dos bits a 1)

Puede suceder que el nuevo implicante ya estuviese en la lista de implicantes, en ese caso lo ignoraremos.

Por ejemplo, en la función que estamos simplificando, en un momento combinaremos los minterms (2,6), (10,14), (2,10) y (6,14):

Implicante 2,6: 0-10
Implicante 10,14: 1-10
Implicante 2,10: -010
Implicante 6,14: -110

Vemos que tanto el primero y segundo se pueden combinar y el tercero y cuarto también, ya que solo difieren en un bit:

Implicante 2,6,10,14: --10
Implicante 2,10, 6, 14: --10

Pero ambos producen el mismo implicante como resultado, ya que combinan los mismos minterms.

De modo que verificaremos si el nuevo implicante está ya en el grupo que le corresponde según el número de bits uno que tiene. Si no es así, lo añadimos. Además, si en el bucle interior se añade algún implicante nuevo, significa que el bucle exterior debe repertirse de nuevo.

Una vez completada la verificación del los dos grupos, los implicantes usados se marcan como marcados. Los implicantes marcados no se volverán a usar en la creación de nuevos implicantes.

    // Combinar grupos
    implicante imp;
    bool contiene;
    bool repetir;
    do {
        repetir = false;
        int nbit=0;
        // Combinar grupo de nbit con grupo de nbit+1
        while(nbit < noBits) {
            size_t s1 = grupo[nbit].size();
            size_t s2 = grupo[nbit+1].size();
            if(s1 && s2) { // Si alguno de los vectores no contiene elementos, no ejecutaremos el bucle
                for(size_t i=0; i<s1; i++) {
                    for(size_t j=0; j<s2; j++) {
                        if(!grupo[nbit][i].Marca() && !grupo[nbit+1][j].Marca() && grupo[nbit][i]-grupo[nbit+1][j] == 1) {
                            imp = implicante(grupo[nbit][i], grupo[nbit+1][j]);
                            contiene=false;
                            for(size_t k=0; k<grupo[nbit].size() && !contiene; k++) contiene |= grupo[nbit][k] == imp;
                            if(!contiene) {
                                grupo[nbit].push_back(imp);
                               repetir = true;
                            }
                        }
                    }
                }
            }
            nbit++;
        }
        // Marcar los implicantes usados
        for(nbit=0; nbit<=nBits; nbit++) {
            size_t s1 = grupo[nbit].size();
            for(size_t i=0; i<s1; i++)
                if(grupo[nbit][i].Usado()) grupo[nbit][i].Marcar();
        }
    } while(repetir);

Cuando se complete esta fase, los implicantes que no estén marcados serán determinantes primos, y se usarán como datos de entrada en la siguiente fase.

En nuestro ejemplo, los implicantes primos son:

Determinantes primos:
2,6,10,14: --10
2,3,10,11: -01-
4,6,12,14_ -1-0
4,5,12,13_ -10-
8,9,10,11,12,13,14,15: 1---
15: 1111

Clase implicanteprimo

Nuestra última clase es implicanteprimo, que usaremos para crear un vector con los determinantes primos entre los que tendremos que seleccionar aquellos que determinen la fórmula final simplificada.

Cada elemento de ese vector debe contener una estructura que almacene la presencia de cada uno de los minterms en cada implicante. Esto lo haremos con una estructura map, en el que el índice será el valor del minterm y el contenido un booleano que indique si está o no presente. Aunque podríamos usar como índice objetos de la clase minterm, es más simple usar el valor del minterm, que es un entero.

Además mantiene un puntero al implicante, para poder consultar los bits, los minterms y el número de entradas.

Un valor booleano para indicar si el implicante es esencial o no.

Los valores nMinterms y nOperaciones se usan para ordenar la tabla de determinantes primos, lo que será necesario para seleccionar los determinantes primos esenciales. nMinterms es el número de minterms necesarios que contiene el implicante. Cuantos más contenga, más prioridad le daremos para seleccionarlo como esencial. nOperaciones es el número de operadores lógicos que hay que aplicar al determinante. Por ejemplo, un '1', requiere una operación lógica, un '0', requiere dos, ya que hay que invertir el valor de la entrada, y un '-' no requiere ninguna. Por ejemplo, los bits "01--1", requiere cuatro operaciones: ~I₁·I₂·I₅. Entre dos implicantes con el mismo número de minterms, elegiremos con prioridad el que requiera menos operaciones.

Tenemos el constructor principal, que crea un elemento primo a partir de un puntero a un implicante y la lista de minterms necesarios. El constructor inicializa el mapa de minterms necesarios presentes en el implicante (excluyendo los redundantes). También actualiza los valores de nMinterms y de nOperaciones.

Tenemos que definir el constructor copia y el operador de asignación para poder usar el algoritmo sort, ya que los usa internamente para ordenar vectores.

En algún momento del algoritmo necesitaremos contar cuántas veces aparece cada minterm entre todos los implicantes primos. Si un minterm aparece solo en uno de los implicantes primos, ese implicante será esencial. El método AjustaCuenta se encargará de esa tarea. Recibe como parámetro una referencia a un mapa con la cuenta de cada minterm y lo actuializa con el implicante actual.

El método Contiene devuelve un valor true si el implicante contiene el minterm que se ha pasado como parámetro.

Cada vez que seleccionemos un determinante primo como esencial, tendremos que eliminar los minterms que contiene del resto de determinantes primos, de modo que solo queden aquellos minterms que aún no formen parte de ningún determinante primo esencial. El método EliminarMinterms se encarga de esa tarea. Recibe como parámetro una referencia a un determinante primo, y elimina del determinante actual los minterms que contiene el parámetro. Adicionalmente ajusta los valores de nMinterms.

El método Comparar se usará para ordenar la tabla de implicantes primos. Recibe dos parámetros de tipo implicanteprimo y retornará true si el primer parámetro contiene más minterms que el segundo, o, a igual número de minterms si el primero requiere menos operaciones que el segundo.

El resto de métodos forman parte del interfaz, o se usan para mostrar por pantalla ciertos contenidos.

class implicanteprimo {
public:
    // Constructor
    implicanteprimo(implicante *i, std::vector<minterm> &m);
    // Constructor copia, necesario para aplicar el algoritmo sort
    implicanteprimo(const implicanteprimo &t);
    // Operador de asignación, necesario para aplicar el algoritmo sort
    implicanteprimo &operator=(const implicanteprimo &t);
    // Función estática de comparación usada para ordenar vectores de implicantes primos
    static bool Comparar(implicanteprimo &a, implicanteprimo &b);
    // Incrementa los elementos del mapa 'cuenta' con los minterms de este implicante implicanteprimo
    void AjustaCuenta(std::map<int,int> &cuenta);
    // Elimina los minterms de este implicante presentes en el parámetro t
    void EliminarMinterms(implicanteprimo &t);
    // Devuelve true si el implicante contiene el minterm del parámetro
    bool Contiene(int m) const;
    // Interfaz
    bool Esencial() { return esencial; }
    void MarcaEsencial() { esencial = true; }
    int NMinterms() const { return nMinterms; }
    int NOperaciones() const { return nOperaciones; }
    std::map<int,bool> &Presente() { return presente; }
    implicante *Imp() { return imp; }
private:
    implicante *imp; // Puntero al implicante dentro del vector de implicantes
    std::map<int,bool> presente; // Indica si el implicante primo contiene o no los minterms necesarios
    bool esencial; // Implicante primo marcado como esencial
    int nMinterms; // Usado para ordenar, número de minterms que contiene el implicante
    int nOperaciones; // Usado para ordenar, número de operaciones del implicante primo
};

Segunda fase del algoritmo

La segunda fase consiste en seleccionar de la lista de implicantes primos aquellos que resulten esenciales para obtener una función simplificada. No tiene por qué existir una única simplificación para una función determinada, de modo que tendremos que elegir algún criterio para elegir una entre todas las posibles soluciones.

Lo primero que haremos es crear una tablaFinal con los implicantes primos:

    vector<primo> tablaFinal;
    map<int,int> cuenta; // Cuenta de presencia de minterms en determinantes primos.
    bool terminado=false;
    size_t i, j;

    // Construir tabla final:
    for(int i=0; i<=noBits; i++) {
        size_t t=grupo[i].size();
        for(size_t j=0; j<t; j++) {
            if(!grupo[i][j].Marca()) {
                tablaFinal.push_back(implicanteprimo(&grupo[i][j], m));
            }
        }
    }

El contenido de esta tabla contiene la siguiente información:

Tabla
                        2  3  4  5  6  8  9
-01-(MI:  2- OP: 3) =>  X  X
--10(MI:  2- OP: 3) =>  X           X
-10-(MI:  2- OP: 3) =>        X  X
-1-0(MI:  2- OP: 3) =>        X     X
1---(MI:  2- OP: 1) =>                 X  X
1111(MI:  0- OP: 4) =>

Para cada implicante disponemos de los datos de mintersm no redundantes que contiene, el número de operaciones que requiere, y los minterms presentes. Por ejemplo, para el implicante '-01' contiene dos minterms no redundantes, el 2 y el 3, y necesita tres operaciones. El '1111' no contiene minterms no redundantes, y por lo tanto no puede ser elegido como esencial.

Anidaremos dos bucles do..while. El más exterior se repetirá hasta que hayamos seleccionado todos los determinantes esenciales necesarios.

El segundo bucle seleccionará los determinantes que contengan algún minterm que no esté presente en ningún otro determinante, si es que existen.

Si se encuentra algún determinante que cumpla esa condición se marcará como esencial y se eliminarán los minterms que contiene del resto de determinantes primos.

Cabe la posibilidad que después de hacer esto, alguno de los determinantes restantes contenga algún minterm en exclusividad, por lo que repetiremos el proceso hasta que no se encuentre ninguno.

En nuestro ejemplo, para la primera iteración de este bucle, obtenemos la siguiente tabla:

2 :> 2
3 :> 1
4 :> 2
5 :> 1
6 :> 2
8 :> 1
9 :> 1

Que nos indica que los minterms 3, 5, 8 y 9 solo aparecen en un implicante, de modo que debemos elegir esos implicantes como esenciales, que son: '-01-', -10-' y '1---'.

Es posible que los determinantes marcados como esenciales sean suficientes para obtener la función simplificada. Deberemos asegurarnos de que quedan implicantes no esenciales con minterms sin usar. Por ello, antes de seguir, verificaremos si hemos terminado.

De no ser así, llegados a este punto, los determinantes que queden en la tabla sin marcar como esenciales no podrán ser seleccionados usando ese criterio.

En nuestro ejemplo, en la segunda iteración, si se eliminan los minterms correspondientes a esos implicantes esenciales, la tabla queda:

2 :> 0
3 :> 0
4 :> 0
5 :> 0
6 :> 2
8 :> 0
9 :> 0

Es decir, ya solo queda un minterm por codificar, pero aparece en dos implicantes,

Esto significa que el bucle interior ya no puede determinar un implicante esencial con el criterio indicado, así que pasamos al bucle exterior.

De modo que entre los restantes elegiremos aquel que contenga más minterms, y en caso de empate, el que requiera menos operaciones lógicas.

Para ello primer ordenaremos la tabla usando ese criterio, mediante el algoritmo sort.

Con la tabla ordenada, seleccionaremos el primer determinante como esencial, eliminaremos los minterms de ese determinante de todos los de la tabla.

De nuevo, verificamos si hemos terminado de seleccionar implicantes, y de no ser así, repetimos el bucle desde el principio.

Volviendo al ejemplo, ahora se ordenan los implicantes de mayor a menor por el número de minterms que contienen y en caso de coincidencia, de menor a mayor por el número de operaciones. Esto nos deja:

Tabla
                2  3  4  5  6  8  9
--10( 1- 3) =>              X
-1-0( 1- 3) =>              X
// El resto no contienen minterms no redundantes

Elegiremos el primer implicante como esencial, aunque en este caso es indiferente elegir uno u otro. Con esto quedan seleccionados todos los implicantes esenciales. Si no fuese así, repetiremos todo el proceso.

El código para seleccionar todos los implicantes esenciales es:

    // Seleccionar determinantes esenciales:
    // Los que contengan en exclusividad uno de los minterms.
    do {
        do {
            repetir = false;
            for(size_t x=0; x<m.size(); x++) cuenta[m[x].Valor()] = 0;
            for(size_t i=0; i<tablaFinal.size(); i++) {
                if(!tablaFinal[i].Esencial()) tablaFinal[i].AjustaCuenta(cuenta);
            }
            // Buscar los determinantes con minters con cuenta igual a 1 (Si los hay)
            for(size_t x=0; x<m.size(); x++)
                if(cuenta[m[x].Valor()] == 1) { // Guarda bits:
                    repetir = true;
                    i=0;
                    while(!tablaFinal[i].Contiene(m[x].Valor()) && i<tablaFinal.size()) i++;
                    tablaFinal[i].MarcaEsencial();
                    for(j=0; j<tablaFinal.size(); j++) {
                        if(i != j) tablaFinal[j].EliminarMinterms(tablaFinal[i]);
                    }
                    tablaFinal[i].EliminarMinterms(tablaFinal[i]);
                }
        } while(repetir);
        terminado = true;
        for(j=0; terminado && j<tablaFinal.size(); j++) {
            if(!tablaFinal[j].Esencial() && tablaFinal[j].NMinterms()) terminado = false;
        }
        if(!terminado) {
            // Seleccionar determinantes prioritariamente por número de minterms, de mayor a menor
            // y por número de bits de menor a mayor (los ceros cuentan por 2)
            std::sort(tablaFinal.begin(), tablaFinal.end(), implicanteprimo::Comparar);

            // Seleccionamos el primero como esencial:
            for(j=1; j<tablaFinal.size(); j++) {
                tablaFinal[j].EliminarMinterms(tablaFinal[0]);
            }
            tablaFinal[0].EliminarMinterms(tablaFinal[0]);
            tablaFinal[0].MarcaEsencial();
            // Optimización para evitar otra iteración:
            terminado = true;
            for(j=0; terminado && j<tablaFinal.size(); j++) {
                if(!tablaFinal[j].Esencial() && tablaFinal[j].NMinterms()) terminado = false;
            }
        }
    } while(!terminado);

Al finalizar esta fase, en la tabla de implicantes primos tendremos marcados como esenciales aquellos necesarios para obtener la función simplificada.

Tercera fase del algoritmo

Cada bit del vector de char bit de los implicantes primos esenciales corresponde a una variable de entrada. El bit 0 será la primera entrada, el 1 la segunda, etc.

Y a cada conjunto de bits le corresponde una función AND de sus variables. Si el valor del bit es '1', la variable aparecerá tal cual, si es '0', aparecerá negada y si es '-', no aparecerá.

En esta última fase del algoritmo procesaremos los bits de los implicantes primos esenciales y daremos la función de salida, que será la suma (opeación OR), de cada uno de los implicantes.

    cout << "Resultado" << endl;
    bool primero=true;
    cout << "S = ";
    for(size_t i=0; i<tablaFinal.size(); i++) {
        if(tablaFinal[i].Esencial()) {
            if(!primero) std::cout << "+ ";
            else primero=false;
            for(int j=tablaFinal[i].Imp()->Tam()-1; j>=0; j--) {
                if(tablaFinal[i].Imp()->Bit()[j] == '1') std::cout << "I" << noBits-j << " ";
                if(tablaFinal[i].Imp()->Bit()[j] == '0') std::cout << "I" << noBits-j << "' ";
            }
        }
    }
    std::cout << endl;

Por ejemplo, para nuestro ejemplo, los implicantes primos esenciales elegidos generan esta función:

S = I1' I2 + I4 + I2 I3' + I2' I3

Ejemplo 1

Este primer programa de ejemplo simplifica funciones en modo consola. Los minterms están iniciados en el código, por lo que habrá que recompilar el programa para cada función. Se comparte a modo de ilustración, ya que no hay ningún mecanismo de validación de entradas ni interfaz de usuario.

Nombre	Fichero	Fecha	Tamaño	Contador	Descarga
Ejemplo 1	Quine-McCluskey.zip	2024-07-29	5991 bytes	226

Ejemplo 2

El segundo ejemplo es una aplicación GUI que hace uso de la librería wxWidgets, y que permite la entrada de datos de la función a simplificar y resulta más fácil de usar.

El sistema para introducir minterms cuando las variables de entrada son más de siete no es adecuado, ya que hay demasiadas combinaciones de minterms y el control (widget) utilizado para marcar los minters tiene es poco amigable en estos casos.

Nombre	Fichero	Fecha	Tamaño	Contador	Descarga
Ejemplo 2	wx-Quine-McCluskey.zip	2024-07-29	23995 bytes	234

Ejemplo 3

Este ejemplo es una nueva versión del ejemplo2.

Debido a que el orden de las variables de entrada en un minterm es de derecha a izquierda, la introducción de datos y el resultado de la simplificación resulta confuso. Esta nueva versión permite etiquetar cada variable de entrada.

Nombre	Fichero	Fecha	Tamaño	Contador	Descarga
Ejemplo3	wx-Quine-McCluskey2.zip	2024-09-28	23593 bytes	174