Basic Research on High-Speed Boolean Function Manipulator

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

We have carried out basic research on high-speed manipulation of Boolean functions based on binary decision diagrams.1.Algorithms and Complexity of Manipulating Binary Decision DiagramsWe have propsed highly parallel algorithms for reduction and Booleam operations, which are basic Boolean function manipulation based on binary decision diagrams (BDDs), and clarified their computational complexity. On the expressive power of BDDs, we have defined the class of Boolean functions expressible by polynomial size BDDs and compared it with the classes based on Turing machines. We have also studied on the size of BDDs representing threshold functions.2.High-Speed Boolean Function ManipulatorWe have propsed and experimented a method using secondary memory to manipulate very large shared BDDs (SBDDs) which cannot be stored in the main memory. Breadth-first manipulation of SBDDs is adopted in this method. We have also developed a parallel method to manipulate SBDDs on content sddressable memories (CAMs). It seems that very high parallelism can be realized using CAMs.3.Computer Aided Logic Design Based on Boolean ProcessingWe have applied Boolean function manipulation based on SBDDs to computer aided logic design, First, we proposed a method to generate compace test sequences for scan-based seaquential circuits. The second one is the application to the several state assignment methods for asynchronous sequential circuits. As an application for the problems not in the field of logic design, we have proposed some methods to solve combinatorial problems using Boolean processing.