Exact Minimization of Free BDDs and Its Application to Pass-Transistor Logic Optimization (Special Section on VLSI Design and CAD Algorithms)

スポンサーリンク

概要

• 論文の詳細を見る

• In several design methods for Pass-transistor Logic (PTL) circuits, Boolean functions are expressed as OBDDs in decomposed form and then the component OBDDs are directly mapped to PTL cells. The total size of OBDDs (number of nodes) corresponds to the circuit size. In this paper, we investigate a method for PTL synthesis based on exact minimization of Free BDDs (FBDDs). FBDDs are well-studied extension of OBDDs with free variable ordering on each path. We present statistics showing that more than 56% of 616126 NPN-equivalence classes of 5-variable Boolean functions have minimum FBDDs with less size than their OBDDs. This result can be used for PTL synthesis as libraries. We also applied the exact minimization algorithm of FBDDs to the minimization of subcircuits in the synthesis for MCNC benchmarks and found up to 5% size reduction.

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

著者

• Takagi K

  Nagoya Univ. Nagoya‐shi Jpn

• Takagi Kazuyoshi

  Department Of Surgery Kurume University School Of Medicine

• HATAKEDA Hiroshi

  Graduate School of Information Science, Nara Institute of Science and Technology

• KIMURA Shinji

  Graduate School of Information Science, Nara Institute of Science and Technology

• WATANABE Katsumasa

  Graduate School of Information Science, Nara Institute of Science and Technology

• Kimura Shinji

  Graduate School Of Information Production And Systems Waseda University

• Kimura S

  Waseda Univ. Kitakyushu‐shi Jpn

• WATANABE Kaoru

  The author is with Osaka Electro-Communication University

• Hatakeda Hiroshi

  Graduate School Of Information Science Nara Institute Of Science And Technology:(present Address) Da

• Watanabe Katsumasa

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Watanabe K

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Kohara Shunitsu

  Department Of Computer Science Waseda University

• Takagi Kazuyoshi

  Department Of Applied Chemistry Faculty Of Life Sciences Ritsumeikan University

• Kimura Shinji

  Graduate School Of Engineering Nagoya University

関連論文

• Exact Minimization of Free BDDs and Its Application to Pass-Transistor Logic Optimization (Special Section on VLSI Design and CAD Algorithms)
• Hardware Synthesis from C Programs with Estimation of Bit Length of Variables (Special Section on VLSI Design and CAD Algorithms)
• Timing Verification of Sequential Logic Circuits Based on Controlled Multi-Clock Path Analysis (Special Section on VLSI Design and CAD Algorithms)
• Purification and Characterization of Aromatic Amine Dehydrogenase from Alcaligenes xylosoxidans
• Electrochemical Control of Hydrogenase Action of Desulfovibrio vulgaris (Hildenborough)
• Quinone-Mediated Bioelectrochemical Reduction of NAD(P)+ Catalyzed by Flavoproteins
• N-Terminal Region of Chitinase I of Bacillus circulans KA-304 Contained New Chitin-Biding Domain
• Automated Passive-Transmission-Line Routing Tool for Single-Flux-Quantum Circuits Based on A* Algorithm
• A Method of Sequential Circuit Synthesis Using One-Hot Encoding for Single-Flux-Quantum Digital Circuits(Superconducting Electronics)
• Logic Synthesis Method for Dual-Rail RSFQ Digital Circuits Using Root-Shared Binary Decision Diagrams(VLSI Design Technology and CAD)
• Selective Low-Care Coding : A Means for Test Data Compression in Circuits with Multiple Scan Chains(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
• A Scheduling Problem in Multihop Networks
• The p-Collection Problem in a Flow Network with Lower Bounds (Special Section on Discrete Mathematics and Its Applications)
• Aortic Valve Replacement after Esophagectomy with Substernal Gastric Tube Reconstruction
• Infection management in a patient with a left ventricular assist device : a case report of long-term cefazolin sodium hydrate administration
• Dysfunction of an ATS valve in the aortic position : the first reported case caused by pannus formation
• Does Off-Pump Coronary Artery Bypass Grafting Really Preserve Renal Function?
• Floating-Point Euclidean Norm Computing Circuit
• Digit-Recurrence Algorithm for Computing Reciprocal Square-Root(Regular Section)
• A Hardware Algorithm for Integer Division Using the SD2 Representation(VLSI Design Technology and CAD)
• The Optimal Architecture Design of Two-Dimension Matrix Multiplication Jumping Systolic Array
• Automated Passive-Transmission-Line Routing Tool for Single-Flux-Quantum Circuits Based on A^* Algorithm
• A Clock Scheduling Algorithm for High-Throughput RSFQ Digital Circuits
• Fine-Grained Power Gating Based on the Controlling Value of Logic Elements
• Fine-grained power gating based on the controlling value of logic gates (VLSI設計技術)
• Fine-grained power gating based on the controlling value of logic gates (システムLSI設計技術)
• Finite Input-Memory Automaton Based Checker Synthesis of System Verilog Assertions for FPGA Prototyping
• _
• Covering Problems in the p-Collection Problems
• The Problem of where to Locate p-Sinks in a Flow Network: Complexity Approach
• Realization Problems of a Tree with a Transmission Number Sequence (Special Section on the 6th Karuizawa Workshop on Circuits and Systems)
• Issue Mechanism for Embedded Simultaneous Multithreading Processor
• Multi-Cycle Path Detection Based on Propositional Satisfiability with CNF Simplification Using Adaptive Variable Insertion (Special Section on VLSI Design and CAD Algorithms)
• 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)
• A CMOS Rail-to-Rail Current Conveyer and Its Applications to Current-Mode Filters(Special Section on Papers Selected from ITC-CSCC 2002)
• A CMOS Rail-to-Rail Current Conveyor
• Look Up Table Compaction Based on Folding of Logic Functions(Special Section on VLSI Design and CAD Algorithms)
• Class A CMOS Current Conveyors
• A Clock-Feedthrough Compensated Switched-Current Memory Cell
• Robust Quantum Algorithms Computing OR with ε-Biased Oracles(Quantum Computing,Foundations of Computer Science)
• A Built-in Reseeding Technique for LFSR-Based Test Pattern Generation(Timing Verification and Test Generation)(VLSI Design and CAD Algorithms)
• A Built-in Reseeding Technique for LFSR-Based Test Pattern Generation
• RAY-SPACE CODING USING SINUSOIDAL STRUCTURE IN CIRCULAR CAMERA ARRANGEMENT(International Workshop on Advanced Image Technology 2006)
• Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
• A Selective Scan Chain Reconfiguration through Run-Length Coding for Test Data Compression and Scan Power Reduction(Test)(VLSI Design and CAD Algorithms)
• A Hybrid Dictionary Test Data Compression for Multiscan-Based Designs(Test)(VLSI Design and CAD Algorithms)
• Unified Dual-Radix Architecture for Scalable Montgomery Multiplications in GF(P) and GF(2^n)
• Optimizing Controlling-Value-Based Power Gating with Gate Count and Switching Activity
• N-Terminal Region of Chitinase I of Bacillus circulans KA-304 Contained New Chitin-Biding Domain
• Coverage Estimation Using Transition Perturbation for Symbolic Model Checking in Hardware Verification(Simulation and Verification,VLSI Design and CAD Algorithms)
• Structural Coverage of Traversed Transitions for Symbolic Model Checking
• Structural Coverage of Traversed Transitions for Symbolic Model Checking
• Structural Coverage of Traversed Transitions for Symbolic Model Checking
• Structural Coverage of Traversed Transitions for Symbolic Model Checking
• An Efficient and Effective Algorithm for Online Task Placement with I/O Communications in Partially Reconfigurable FPGAs(System Level Design,VLSI Design and CAD Algorithms)
• Quantum versus Classical Pushdown Automata in Exact Computation (特集:量子計算と量子情報)
• Power Optimization of Sequential Circuits Using Switching Activity Based Clock Gating
• Layout-Driven Skewed Clock Tree Synthesis for Superconducting SFQ Circuits
• Automatic Generation of Java-Based, Database-Independent Query API
• Automatic Generation of Java-Based, Database-Independent Query API
• Checker circuit generation for System Verilog Assertions in prototyping verification (システムLSI設計技術)
• Efficient Hybrid Grid Synthesis Method Based on Genetic Algorithm for Power/Ground Network Optimization with Dynamic Signal Consideration
• Automatic Multi-Stage Clock Gating Optimization Using ILP Formulation
• Multi-Operand Adder Synthesis Targeting FPGAs
• Gum chewing enhances early recovery of bowel function following transperitoneal abdominal aortic surgery
• On Gate Level Power Optimization of Combinational Circuits Using Pseudo Power Gating
• Write Control Method for Nonvolatile Flip-Flops Based on State Transition Analysis
• Sensitive Enzymatic Method for the Quantification of Theanine, a Principal Umami Component of Commercial Tea Beverages
• An Exact Approach for GPC-Based Compressor Tree Synthesis
• Dual-Stage Pseudo Power Gating with Advanced Clustering Algorithm for Gate Level Power Optimization
• Anomalous Origin of the Right Coronary Artery: Report of a Case
• Domain Structure and Function of α-1,3-Glucanase from Bacillus circulans KA-304, an Enzyme Essential for Degrading Basidiomycete Cell Walls

もっと見る 閉じる

スポンサーリンク