Efficient Manipulation of Boolean Functions with OBDDs

Abstract:

One of the main problems in chip design is the huge number of possible combinations of individual chip elements, leading to a combinatorial explosion as chips become more and more complex. New key results in theoretical computer science and in the design of data structures and efficient algorithms can be applied fruitfully here. The use and application of ordered binary decision digrams (OBDDs) has led to dramatic performance improvements in many computer-aided design projects. The talk provides an introduction to this interdisciplinary research area with an emphasis in computer-aided circuit design and verification.