Research on Efficient Manipulation of Boolean Functions Using Shared Binary Decision Diagrams and Its Application to Computer Aided Logic Design

点击翻译按钮获取中文摘要

We have carried out researches on efficient representation and manipulation of Boolean functions, and applied them to computer aided logic design.1. Efficient Representation and Manipulation of Boolean FunctionsWe have carried out researches on the efficient representation of Boolean functions using Shared Binary Decision Diagrams (SBDDs). For efficient manipulation of SBDDS, we have proposed attributed edges. We have developed a vector algorithm for manipulating SBDDs. We have also investigated variables ordering methods for minimizing SBDDs.2. Computer Aided Logic Design Using Shared Binary Decision DiagramsWe have applied Boolean function manipulation to fault diagnosis and timing verification of logic circuits. On fault diagnosis, we have developed efficient fault simulation methods for multiple faults and novel methods of generating compact test sets. On timing verification, we have developed methods for simulating logic circuits with nondeterministic delays.3. Formal Verification of Logic Design Using Shared Binary Decision DiagramsWe have proposed a method to represent state transition diagrams using SBDDs. Based on the method, we have developed a formal verification algorithm on branching time regular temporal logic, and implemented a formal verification system for sequential machines.4. Computational Complexity of Boolean Function ManipulationWe have clarified the class of functions efficiently expressed by BDDs. We have also developed a paranelization methods for manipulating BDDs and clarified the computational complexity.5. Systems for Computer Aided Logic DesignWe have developed a package software so as to make it easy to manipulate SBDDs on tools for computer aided logic design.