We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the com...
详细信息
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of booleanfunctions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The second main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven parity-FBDD.
We present a data structure for boolean manipulation-the Mod-2-OBDDs-that considerably extends ESOPs (EXOR-sum-of-products) as well as OBDDs (ordered binary decision diagrams). There are booleanfunctions of practical...
详细信息
We present a data structure for boolean manipulation-the Mod-2-OBDDs-that considerably extends ESOPs (EXOR-sum-of-products) as well as OBDDs (ordered binary decision diagrams). There are booleanfunctions of practical interest which have exponential size optimal ESOPs (even multilevel EXOR-expressions) and/or OBDDs that can be represented by (low degree) polynomial size Mod-2-OBDDs. We show that boolean manipulation tasks such as apply operation, quantification, composition can be performed with Mod-2-OBDDs at least as efficient as with OBDDs. Indeed, since the size of a minimal Mod-2-OBDD-representation of a boolean function is;in general, smaller (sometimes even exponentially smaller) than the size of an optimal OBDD-representation, the increase in efficiency is considerable. Moreover, EXOR-operations as well as complementations can be performed in constant time O(1). However, the price of constant time EXOR-apply operations is the canonicity of the Mod-2-OBDD-representation. In order to allow in spite of this fact efficient analysis of Mod-2-OBDDs we present a fast probabilistic equivalence test with one-sided error probability for Mod-2-OBDDs (and, hence, for ESOPs) which performs only linear many arithmetic operations.
Ordered binary decision diagrams (OBDDs) play an important role as data structure for booleanfunctions. They are used, e.g., in the logical synthesis process, for verification and test pattern generation, and as part...
详细信息
Ordered binary decision diagrams (OBDDs) play an important role as data structure for booleanfunctions. They are used, e.g., in the logical synthesis process, for verification and test pattern generation, and as part of CAD tools. For a given ordering of the variables and a given boolean function f the reduced OBDD, i.e. the OBDD of minimal size, is unique (up to isomorphisms) and can be computed from any OBDD G for f of size \G\ in time O(\G\ log \G\). A new reduction algorithm which works in optimal linear time O(\G\) is presented.
暂无评论