Representations of Multiple-Output Functions Using Binary Decision Diagrams for Characteristic Functions (Special Section on VLSI Design and CAD Algorithms)
スポンサーリンク
概要
- 論文の詳細を見る
This paper proposes a method to construct smaller binary decision diagrams for characteristic functions (BDDs for CFs). A BDD for CF represents an n-input m-output function, and evaluates all the outputs in O(n+m) time. We derive an upper bound on the number of nodes of the BDD for CF of n-bit adders (adrn). We also compare complexities of BDDs for CFs with those of shared binary decision diagrams (SBDDs) and multi-terminal binary decision diagrams (MTBDDs). Our experimental results show: 1) BDDs for CFs are usually much smaller than MTBDDs; 2) for adrn and for some benchmark circuits, BDDs for CFs are the smallest among the three types of BDDs; and 3) the proposed method often produces smaller BDDs for CFs than an existing method.
- 社団法人電子情報通信学会の論文
- 1999-11-25
著者
-
SASAO Tsutomu
Department of Computer Science and Electronics, Kyushu Institute of Technology
-
Sasao T
Department Of Computer Science And Electronics Kyushu Institute Of Technology
-
Sasao Tsutomu
Department Of Computer Science And Electronics Kyushu Institute Of Technology
-
HASAN BABU
Department of Computer Science and Electronics, Kyushu Institute of Technology
-
Hasan Babu
Department Of Computer Science And Electronics Kyushu Institute Of Technology
関連論文
- A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams
- Compact Numerical Function Generators Based on Quadratic Approximation : Architecture and Synthesis Method(Circuit Synthesis,VLSI Design and CAD Algorithms)
- A Parallel Branching Program Machine for Sequential Circuits: Implementation and Evaluation
- Bi-Partition of Shared Binary Decision Diagrams(Special Section on VLSI Design and CAD Algorithms)
- Time-Division Multiplexing Realizations of Multiple-Output Functions Based on Shared Multi-Terminal Multiple-Valued Decision Diagrams (Special Issue on Multiple-Valued Logic and Its Applications)
- Design Method for Numerical Function Generators Using Recursive Segmentation and EVBDDs(Logic Synthesis and Verification,VLSI Design and CAD Algorithms)
- Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs(Logic Synthesis, VLSI Design and CAD Algorithms)
- A New Equivalence Relation of Logic Functions and Its Application in the Design of AND-OR-EXOR Networks(Discrete Mathematics and Its Applications)
- BDD Representation for Incompletely Specified Multiple-Output Logic Functions and Its Applications to the Design of LUT Cascades(Logic Synthesis and Verification,VLSI Design and CAD Algorithms)
- A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams
- A Quaternary Decision Diagram Machine : Optimization of Its Code
- Efficient Computation of Canonical Form under Variable Permutation and Negation for Boolean Matching in Large Libraries(Logic Synthesis,VLSI Design and CAD Algorithms)
- A Parallel Branching Program Machine for Sequential Circuits : Implementation and Evaluation
- A Memory-Based Programmable Logic Device Using a Look-Up Table Cascade with Synchronous SRAMs
- A Realization of Multiple-Output Functions by a Look-Up Table Ring(Logic Synthesis)(VLSI Design and CAD Algorithms)
- Design Methods of Radix Converters Using Arithmetic Decompositions(Computer Components)
- A Design of AES Encryption Circuit with 128-bit Keys Using Look-Up Table Ring on FPGA(Computer Components)
- Area-Time Complexities of Multi-Valued Decision Diagrams(Discrete Mathematics and Its Applications)
- On Properties of Kleene TDDs(Special Issue on Test and Diagnosis of VLSI)
- Representations of Multiple-Output Functions Using Binary Decision Diagrams for Characteristic Functions (Special Section on VLSI Design and CAD Algorithms)
- Compact Representations of Logic Functions Using Heterogeneous MDDs(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
- A PC-Based Logic Simulator Using a Look-Up Table Cascade Emulator(Simulation and Verification,VLSI Design and CAD Algorithms)
- A Design Algorithm for Sequential Circuits Using LUT Rings(Logic Synthesis, VLSI Design and CAD Algorithms)
- Fast Boolean Matching under Permutation by Efficient Computation of Canonical Form(Logic Synthesis)(VLSI Design and CAD Algorithms)
- Output Phase Optimization for AND-OR-EXOR PLAs with Decoders and Its Application to Design of Adders(Digital Circuits and Computer Arithmetic, Recent Advances in Circuits and Systems-Part 1)
- A Design Method of a Regular Expression Matching Circuit Based on Decomposed Automaton
- A Virus Scanning Engine Using an MPU and an IGU Based on Row-Shift Decomposition
- On the Numbers of Products in Prefix SOPs for Interval Functions
- On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems