Блог

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

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

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

Одним из алгоритмов оптимизации логики является Куайн-Маккласки. Существует реализация на 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
  

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