Minimización de mútiples expresiones booleanas

[cacharreo]

¿Conocéis alguna metodología (algorítmica, heurística,...) o, incluso mejor, un programa/aplicación que sea capaz de minimizar/reducir/simplificar de forma óptima y en un tiempo razonable un conjunto dado de expresiones booleanas? No hablo de Karnaugh, Petrick, Quine-McCluskey u otras variaciones que cuando se trabaja en sistemas con, p.e., 12 dimensiones/variables serían una pesadilla y, aparte, solo operan sobre una única expresión. Tampoco hablo de buscar a mano posibles cambios de variables o grupos comunes de implicantes primos y temo que la estrategia de ir buscando óptimos locales quede muy lejos de ser óptima.

El problema sería: Dadas N expresiones booleanas de M variables del tipo:
E1=ABC...Z
E2=C+D+F+I
E3=!(J+K)
...
En=BC...!P!Q...!Z
obtenerlas de forma que, por ejemplo, la implementación con puertas lógicas fuera mínima tanto en cuanto a número de puertas como en cuanto a número de niveles.

Me consta que es un problema NP-complejo (NP-hard) pero pregunto por si conocierais que exista alguna solución aproximativa práctica razonablemente aceptable.

Edito: Se me olvidó comentar que he oído hablar de los avances de Brayton pero no he sido capaz de encontrar nada concreto.

[explorer]

Pero... ¿Cómo se relacionan las expresiones entre sí? Algoritmos como el Algorithm::QuineMcCluskey sirve para funciones compuestas de varias expresiones, pero cuyo resultado son siempre 0 o 1.

Más información...

[wilco2009]

Has probado a escribirlo en verilog y compilarlo con quartus o vivado?

[cacharreo]

Gracias por las respuestas a ambos. Temí que me quedaría más solo que la una en esto.

Pero... ¿Cómo se relacionan las expresiones entre sí?

Comparten las variables aunque no necesariamente todas. Llevándolo al terreno de la electrónica son funciones lógicas (o de conmutación completamente especificadas/circuitos combinacionales) basadas en el mismo conjunto finito de entradas aunque las salidas son diferentes (pueden coincidir para ciertos vectores de entrada pero las funciones en sí no son idénticas).

Algoritmos como el Algorithm::QuineMcCluskey sirve para funciones compuestas de varias expresiones, pero cuyo resultado son siempre 0 o 1.

En efecto, todas son expresiones booleanas por lo que su resultado es siempre 0 ó 1 pero en los casos que me interesan cada expresión (función) es independiente y aunque cada una comparta variables con el resto, no incluye ninguna de las otras (en sentido estricto no serían funciones compuestas).

Por poner un ejemplo trivial (que desgraciadamente son casi los únicos que se leen en Internet),
E1=AB+C+!D
E2=AB+!C (ó, en su forma canónica/expandida/normalizada, E2=AB+!C+0*D)

puede escribirse como,
E3=AB
E1=E3+C+!D
E2=E3+!C

En su primera forma trasladando las ecuaciones al ámbito electrónico, implican el uso de dos puertas AND de doble entrada, dos puertas OR de triple entrada y dos puertas NOT. En su segunda forma, una puerta AND de doble entrada, dos puertas OR de triple entrada y dos puertas NOT por lo que se ahorra una puerta AND de doble entrada manteniendo el número de niveles (ó etapas). Este ejemplo podría no ser el ideal u óptimo pero creo que deja entrever qué busco (que es evitar el método algebraico y la dependencia de una "idea feliz").

[cacharreo]

Has probado a escribirlo en verilog y compilarlo con quartus o vivado?

Sinceramente no lo he probado pero, aunque salvo descuido o error siempre implemento estos diseños en su forma óptima, por lo que he visto estas optimizaciones (ISE, Vivado, Quartus,...) al sintetizar diseños de los ejemplos son del tipo de las que he mencionado (variaciones de Quine-McCluskey).

[explorer]

En Perl he hecho pruebas. Por ejemplo:

$perl -MAlgorithm::QuineMcCluskey -E '$q = Algorithm::QuineMcCluskey->new(width => 4, columnstring => "1011101110111111"  ); print $q->all_solutions '
(AB) + (C) + (D')

Pero el tema está en que son varias funciones. Logic::TruthTable sí que permite definir un problema con varias funciones, y ofrecer una reducción, pero el ejemplo que muestras ya de por sí está muy reducido y estas bibliotecas no me dan ninguna respuesta que me digo que sirven para lo que quieres.

¿No tienes un ejemplo más complejo?

[cacharreo]

Muchas gracias por el intento.

Ciertamente el ejemplo era trivial pero, más que nada, para que se comprendiera el objetivo.

La solución que ofrece el algoritmo es obviamente la expresión/ecuación/función E1. El resultado debe ofrecer E1, E2 y quizás alguna (sub)función más (p.e. E3) en sus formas reducidas (reducción de las 2 expresiones a la vez, no de cada una de forma independiente).

¿No tienes un ejemplo más complejo?

Claro que sí, un ejemplo práctico real. Un conjunto de 13 variables (de la A a la M) y 4 funciones en su forma bruta (al menos sin una optimización previa intencional). No las he normalizado porque creo que así se verán mejor.

Código: Seleccionar todo

E1 = B + !E + F + !G + !H + !I + !J + !K + !L
E2 = C + F + !G + !H + !I + !J + !K + !L
E3 = C + !D + !E + !F + !G + !H + !I + !J + K + !L
E4 = A + D + E + !F + !G + H + I + !J + !K + L + M

Una vez reducidas el resultado deberían ser 4 funciones reducidas y, si se aplica, un número indeterminado de subfunciones.

[explorer]

13 variables son 2^13 combinaciones, o sea 8192.

Al final me sale como resultado

F0 => (ADEF'G'HIJ'K'LM) + (BE'FG'H'I'J'K'L') + (CD'E'F'G'H'I'J'KL') + (CFG'H'I'J'K'L')

[cacharreo]

Muchas gracias por el intento.

F0 => (ADEF'G'HIJ'K'LM) + (BE'FG'H'I'J'K'L') + (CD'E'F'G'H'I'J'KL') + (CFG'H'I'J'K'L')

Curiosamente este F0 es la suma de las 4 expresiones en el orden E4, E1, E3 y E2 después de haber cambiado sumas por productos en cada una de ellas (variando su resultado porque ni se aplican las leyes de De Morgan para dicho cambio) pero, en definitiva, no hay ninguna minimización como resultado de añadir subfunciones que sean comunes a dos o más expresiones, subfunciones que a simple vista se ve que existen.