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

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

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

Ответы

Ответ 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

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