Paquete optimizador de funciones booleanas para Python

Question

Me gustaría definir una función booleana (con n entradas y m salidas) en forma tabular. Me gustaría encontrar una expresión booleana óptima que implemente la función. Óptimo aquí significa que implementarlo en hardware requeriría la menor cantidad posible de puertas (con tal vez cada puerta tenga costos diferentes)

Estoy seguro de que los sintetizadores VHDL/Verilog hacen esta optimización con frecuencia, y básicamente la necesito por el mismo motivo . ¿Hay algún tipo de solucionador de Karnaugh? Alternativamente, ¿es posible especificar el problema como un problema clásico de optimización (SAT, programación entera)? Me gustaría implementarlo en Python, así que estoy buscando principalmente un paquete que ya lo haga.

Answer 1

Los algoritmos para encontrar la solución óptima tienen una complejidad exponencial, por lo que, en general, las herramientas disponibles buscan una buena implementación en lugar de la implementación óptima. No estoy seguro de cuán estrictos son sus requisitos o cuán grandes son sus funciones.

Un algoritmo para la optimización lógica es Quine-McCluskey. Hay un python implementation. Sin embargo, eso solo cubre el caso de salida única.

$ ./qm.py -o 1,2,3 
1X X1 
$ ./qm.py -o 1,2 
10 01 
$ ./qm.py -o 0,15 
1111 0000 
$ ./qm.py -o 0,8,15 
1111 X000 

Para salidas múltiples, la estrategia más simple es implementar cada una por separado. Puede haber algunos términos duplicados entre ellos que puedan compartirse fácilmente; estructurar la lógica para maximizar el intercambio es más difícil.