Пакет оптимизатора булевых функций для Python

Question

Я бы хотел определить булеву функцию (с n входами и m выходами) в табличной форме. Я хотел бы найти оптимальное логическое выражение, которое реализует функцию. Оптимальный в данном случае означает, что для его реализации в аппаратном обеспечении потребуется как можно меньше шлюзов (при этом, возможно, каждый шлюз имеет разные затраты)

Я уверен, что синтезаторы VHDL / Verilog часто проводят эту оптимизацию, и в основном она мне нужна по той же причине. Есть какой-то решатель Карно? В качестве альтернативы, можно ли определить проблему как классическую задачу оптимизации (SAT, целочисленное программирование)? Я хотел бы реализовать это на Python, поэтому я в первую очередь ищу пакет, который уже делает это.

Answer 1

Алгоритмы поиска оптимального решения имеют экспоненциальную сложность, поэтому обычно доступные инструменты ищут хорошую реализацию, а не оптимальную реализацию.Я не уверен, насколько строги ваши требования или насколько велики ваши функции.

Один алгоритм оптимизации логики - Quine-McCluskey .Существует реализация Python .Однако это относится только к одному выходному случаю.

$ ./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

Для нескольких выходов простейшая стратегия - реализовать каждый отдельно.Между ними могут быть дублированные термины, которые можно легко разделить;структурировать логику для максимизации общего доступа сложнее.