有没有多级逻辑最小化的算法?

Is there an algorithm for multi-level logic minimization?

提问人:Nathan Comer 提问时间:11/6/2022 最后编辑:Nathan Comer 更新时间:11/7/2022 访问量:253

问:

我需要一种算法,当给定任意数量的布尔表达式时,具有任意数量的变量,可以进行多级逻辑最小化以给出一组布尔函数。

维基百科简要提到了多层次表示并举了一个例子,但没有解释如何做到这一点,我在其他任何地方也找不到它。

编辑:澄清一下,它需要在具有多个输出的系统上工作,合并部分输出的布尔表达式,以最大程度地减少所需的逻辑门的数量。

维基百科给出了以下示例:

F1 = AB + AC + AD

F2 = A`B + A`C + A`E

功能等效的多级表示可以是:

P = B + C

F1 = AP + AD

F2 = A`P + A`E

这减少了重用 B + C 所需的逻辑门数量。

我正在寻找一种算法,可以用任意数量的输入和输出来做到这一点,并以尽可能少的逻辑门数生成功能等效的多级表示。如果我的任何术语被关闭,我们深表歉意。

算法 布尔逻辑 最小化

评论

0赞 Axel Kemper 11/6/2022
你看过这个相关帖子吗?
0赞 Spektre 11/6/2022
你的意思是像 Karnaugh Maps 这样的东西吗?
0赞 Sebastian 11/6/2022
有趣的是:Nvidia 现在成功地使用强化学习来创建改进的 64 位加法器和类似电路,击败了现有的方法和启发式算法:developer.nvidia.com/blog/...... sci.utah.edu/publications/Roy2021a/......人们会认为,加法器电路是在 92 年的进位前瞻加法器 (en.wikipedia.org/wiki/Carry-lookahead_adder)
1赞 greybeard 11/7/2022
(@Sebastian我在 1980 年代靠编程 IC 设计工具赚取了报酬。
1赞 alias 11/9/2022
我相信浓缩咖啡可以处理这些问题。请参见:en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer

答:

0赞 Y.T. 11/6/2022 #1

我相信你想要的是 Quine-McCluskey 算法,它具有指数级的复杂性。这个想法是生成一个真值表并组合最小项。链接的维基百科清楚地解释了该算法的工作原理。

评论

0赞 Nathan Comer 11/7/2022
据我了解,Quine-McCluskey 算法采用一个布尔函数并将其最小化。我需要的是适用于任意数量的布尔函数的东西(以便整个系统具有多个输出)。我已经编辑了这个问题来澄清。谢谢。
0赞 Y.T. 11/7/2022
如果您有多个布尔函数,则可以多次运行 Quine-McCluskey 算法。
0赞 Nathan Comer 11/7/2022
所以这个想法是通过 Quine-McCluskey 算法运行所有函数并寻找共享部分?在简化了维基百科的例子之后,我们可以看到两个函数都包含子字符串“B + C”,这正是我们需要提取到另一个函数的逻辑。但是,Quine-McCluskey算法是否会给出函数的可重用部分不是两个简化函数的相同子字符串的结果?如果是这样,我们将如何看到这些函数共享一些我们可以提取的逻辑?如果没有,我们应该能够扫描两个简化函数以查找共享子字符串。
0赞 Y.T. 11/8/2022
@NathanComer 那么你的问题比我想象的要难。