An Algorithm for Generating Generic BDDs (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク

概要

• 論文の詳細を見る

• Binary Decision Diagrams(BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs(OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs(GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees(PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.

• 社団法人電子情報通信学会の論文
• 2000-12-25

著者

• Ochi Hiroyuki

  The Faculty Of Information Sciences Hiroshima City University

• KATAYAMA Tetsushi

  the Faculty of Information Sciences, Hiroshima City University

• TSUDA Takao

  the Faculty of Information Sciences, Hiroshima City University

• Tsuda Takao

  The Faculty Of Information Sciences Hiroshima City University

• Katayama Tetsushi

  The Faculty Of Information Sciences Hiroshima City University:(present Address) Rohm Co. Ltd.

関連論文

• Datapath-Layout-Driven Design for Low-Power FPGA Implementation (特集:電子システムの設計技術と設計自動化)
• ASAver.1: An FPGA-Based Education Board for Computer Architecture/System Design
• A Zero-Suppressed BDD Package with Pruning and Its Application to GRM Minimization (Special Section on VLSI Design and CAD Algorithms)
• An Algorithm for Generating Generic BDDs (Special Section on VLSI Design and CAD Algorithms)
• An Exact Minimization of AND-EXOR Expressions Using Encoded MRCF (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク