python - Python 的 bool 函数优化器包

Question

我想以表格形式定义一个 bool 函数(具有 n 个输入和 m 个输出)。我想找到一个实现该功能的最佳 bool 表达式。这里的最优意味着，在硬件中实现它需要尽可能少的门(可能每个门都有不同的成本)

我确信 VHDL/Verilog 合成器经常进行这种优化，出于同样的原因，我基本上也需要它。有某种卡诺求解器吗？或者，是否可以将问题指定为经典优化问题(SAT，整数规划)？我想用 Python 实现它，所以我主要是在寻找一个已经可以做到这一点的包。

Answer 1

寻找最佳解决方案的算法具有指数级的复杂性，因此通常可用的工具会寻找良好的实现而不是最佳实现。我不确定您的要求有多严格，或者您的功能有多大。

逻辑优化的一种算法是Quine-McCluskey .有一个 python implementation .但是，这仅涵盖单个输出情况。

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

对于多个输出，最简单的策略是分别实现每个输出。它们之间可能有一些重复的术语，可以很容易地共享；构建最大化共享的逻辑更加困难。