logo标签列表

布尔表达式简化

booleanboolean-logicboolean-expressioncircuit
3
我正在尝试简化一个具有39个输入和约500到800百万个项（即那么多的与/或非语句）的布尔表达式。
不需要完美简化，但最好能得到一个好的结果。
我知道K-maps、Quine-McCluskey和Espresso算法。然而，根据我所了解的，这些机制在简化这样大小的电路时需要太长的时间。
我需要在24小时内尽可能地简化这个表达式。
在谷歌搜索后，我发现很难找到任何尝试简化这样巨大机器的资源！是否有任何资源或库可以在24小时内至少尝试简化到一定程度？
“Terms”是什么意思？“AND”连接词呢？平均一个术语中有多少个39个变量？哪种缩减被认为是“好”的？看到一些典型术语的小样本会有所帮助。 - Axel Kemper
出于好奇，使用您对术语的特定定义，39个输入可能有多少个唯一的术语？听起来可能会有很多重复。 - 500 - Internal Server Error
2个回答
5
一种贪心启发式算法“Simplify”在稍早的书中被描述，该书为：

Robert K. Brayton，Gary D. Hachtel，C. McMullen，Alberto Sangiovanni-Vincentelli VLSI综合逻辑最小化算法

你可以在此处找到该章节。
“Simplify”基于“unate范式”。以分治的方式，它递归地应用“Shannon”的展开定理将函数分割成较小的子函数。这个启发式规则是首先按最多变量分割，即分离最多项的变量。
第二种方法是使用图分割工具（如METIS）将项分割成独立（或至少松散相关）的子集。但我不知道这是否已经成功地用于逻辑综合任务。我的最爱搜索引擎持怀疑态度，并没有返回任何结果。
一种基于二元决策图的更近期的算法在此处发表：

Olivier Coudert：Doing Two-Level Logic Minimization 100 Times Faster

该论文列出了与您手头任务类似的非常多项的示例。
另一种相关的简化技术“BDD Sweeping”在A Study of Sweeping Algorithms in the Context of Model Checking中被描述。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接