IBDDs: an efficient functional representation for digital circuits
Jawahar Jain, Magdy S. Abadir, James R. Bitner et al. · 2003
A central issue in the solution of many computer aided design problems is finding a concise representation for circuit designs and their functional specifications. Ordered binary decision diagrams (OBDDs) have recently emerged as a popular representation for various CAD applications such as design verification, synthesis, testing, modeling and simulation. Unfortunately, there is no efficient OBDD representation for many circuits, even in some cases for circuits which perform such apparently simple functions as multiplication. The authors present a new BDD representation scheme, called indexed BDDs (IBDDs), and show that it allows polynomial representations of functions which provably require exponential space using OBDDs. The key idea in IBDDs is to allow multiple occurrences of the input variables, subject to ordering constraints. The authors give an algorithm for verifying the equivalence of two IBDDs and a heuristic for constructing IBDDs for arbitrary combinational circuits.>
Cited by 34 works. doi:10.1109/edac.1992.205973
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- Computer arithmetic: Principles, architecture, and design
- The complexity of equivalence and containment for free single variable program schemes
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Proving circuit correctness using formal comparison between expected and extracted behaviour
- Proving circuit correctness using formal comparison between expected and extracted behaviour
- Probabilistic design verification
- Boolean satisfiability and equivalence checking using general binary decision diagrams
- Efficient Verification Of Multiplier And Other Difficult Functions Using IBDDs