Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
スポンサーリンク
概要
- 論文の詳細を見る
An Ordered Binary Decision Diagram(OBDD) is a directed acyclic graph representing a Boolean function. The size of OBDDs largely depends on the variable ordering. In this paper, we show the size of the OBDD representing the i-th bit of the output of n-bit/n-bit integer division is Ω(2^<(n-i)/8>)for any variable ordering. We also show that ∨-OBDDs, ∧-OBDDs and 【◯!+】-OBDDs representing integer division has the same lower bounds on the size. We develop new methods for proving lower bounds on the size of ∨-OBDDs, ∧-OBDDs and 【◯!+】-OBDDs.
- 社団法人電子情報通信学会の論文
- 1998-08-25
著者
-
Horiyama Takashi
Graduate School Of Engineering Kyoto University
-
Yajima Shuzo
Faculty Of Engineering Kyoto University
-
Yajima Shuzo
Faculty Of Informatics Kansai University
関連論文
- New Graph Calculi for Planar Non-3-Colorable Graphs
- Computational Power of Nondeterministic Ordered Binary Decision Diagrams and Their Subclasses (Special Section on Discrete Mathematics and Its Applications)
- Formal Design Verification of Combinational Circuits Specified by Recurrence Equations (Special Issue on Synthesis and Verification of Hardware Design)
- Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
- Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
- Computational Complexity of Manipulating Binary Decision Diagrams
- On Parallel Computation Time of Unification for Restricted Terms
- On the Computational Power of Binary Decision Diagrams
- Hardware Algorithms and Logic Design Automation : An Overview and Progress Report
- Area-Time Efficient Evaluation of Elementary Functions
- Power Optimization of Sequential Circuits Using Switching Activity Based Clock Gating
- Exponential Lower Bounds on the Size of Variants of OBDD Representing Integer Division
- Compaction of Test Sets for Combinatinal Circuits Based on Symbolic Fault Simulation (Special Issue on Synthesis and Verification of Hardware Design)
- Automatic Multi-Stage Clock Gating Optimization Using ILP Formulation