ROBDD complexity analysis for XOR/XNOR min-terms
ROBDD complexity analysis for XOR/XNOR min-terms
复制标题
DOI：
10.1080/00207210701828770
复制
发表时间：
2008-01-01
影响因子：
1.3
通讯作者：
Assi, A.
中科院分区：
文献类型：
--
作者：
Prasady, P. W. C.;Singh, A. K.;Assi, A.
本文讨论了具有 XOR/XNOR 最小项的布尔函数的降序二元决策图 (ROBDD) 的复杂性。知道变量的数量和仅包含 XOR/XNOR 最小项的布尔函数的乘积项的数量，我们可以预测其 ROBDD 表示中的节点数量，而无需构建二元决策图 (BDD)。这一预测的数学模型已经开发出来。该模型可用于查找给定数量的变量的最大节点数。理论和实验结果强调了这种方法的效率。实验结果表明，即使无法使用布尔定律或任何其他简化方法来简化 XOR/XNOR 最小项，从而获得更好的最小项表示，ROBDD 仍将使用 ROBDD 约简规则执行简化。分析了不同表示方法所需的内存，该分析表明 ROBDD 是存储和表示布尔函数中大量 XOR/XNOR 最小项的内存高效结构。
This paper discusses the complexity of reduced ordered binary decision diagrams (ROBDDs) for Boolean functions with XOR/XNOR min-terms. Knowing the number of variables and the number of product terms of Boolean function containing only XOR/XNOR min-terms, one can predict the number of nodes in its ROBDD representation without building the binary decision diagram (BDD). A mathematical model for this prediction has been developed. This model can be used to find the maximum number of nodes for a given number of variables. Theoretical and experimental results are reported to underline the efficiency of this approach. The experimental results show that even though the XOR/XNOR min-terms cannot be simplified using Boolean laws or any other simplification method leading to a better min-term representation, the ROBDD will perform the simplification using the ROBDD reduction rules. The required memory is analysed for different methods of representation, and this analysis showed that ROBDDs are memory efficient structures to store and represent large numbers of XOR/XNOR min-terms in Boolean functions.