提问人：Gus 提问时间：5/8/2011 更新时间：5/13/2011 访问量：1743
Python 的布尔函数优化器包
Boolean function optimizer package for Python
问：
我想以表格形式定义一个布尔函数（有 n 个输入和 m 个输出）。我想找到一个实现该函数的最佳布尔表达式。这里的最优意味着，在硬件中实现它需要尽可能少的门（可能每个门都有不同的成本）
我确信 VHDL/Verilog 合成器经常进行这种优化，我基本上出于同样的原因需要它。有某种卡诺求解器吗？或者，是否可以将问题指定为经典优化问题（SAT，整数规划）？我想在 Python 中实现它，所以我主要在寻找一个已经可以做到这一点的包。
答：
5赞
Andy
5/13/2011
#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
对于多个输出，最简单的策略是单独实现每个输出。它们之间可能存在一些重复的术语，可以很容易地共享;构建逻辑以最大化共享更加困难。
评论