An algorithm for generating generic BDDs
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 orle of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node tu 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 far 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 OBDDs 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.
binary decision diagram combinational synthesis logic function switching theory pass-transistor logic