Efficient algorithmic circuit verification using indexed BDDs
James R. Bitner, Jawahar Jain, Magdy S. Abadir et al. · 2002
The Indexed Binary Decision Diagram (IBDD), a Boolean function representation scheme, provides a compact representation for functions whose OBDD representation is intractably large. In this paper, we present more efficient algorithms for satisfiability testing and equivalence checking of IBDDs. Efficient verification of Booth multipliers, as well as practical strategies for polynomial time verification of some classes of unsigned array multipliers, are demonstrated experimentally. Our results show that the verification of many instances of functions whose analysis is intractable using OBDDs, such as multipliers and the hidden-weighted-bit function, can be done efficiently using IBDDs.>
Cited by 13 works. doi:10.1109/ftcs.1994.315633
Authors
References
- Graph-Based Algorithms for Boolean Function Manipulation
- A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Using BDDs to verify multipliers
- Boolean satisfiability and equivalence checking using general binary decision diagrams
- Extended BDD's: trading off canonicity for structure in verification algorithms
- IBDDs: an efficient functional representation for digital circuits
- Efficient Verification Of Multiplier And Other Difficult Functions Using IBDDs
- Boolean satisfiability and equivalence checking using general Binary Decision Diagrams