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

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

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


python optimization boolean-logic hardware
person Gus    schedule 07.05.2011    source источник

Ответы (1)


arrow_upward
5
arrow_downward

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

Одним из алгоритмов оптимизации логики является 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

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

person Andy    schedule 12.05.2011