On Properties of Kleene TDDs(Special Issue on Test and Diagnosis of VLSI)

スポンサーリンク

概要

• 論文の詳細を見る

• Three types of ternary decision diagrams(TDDs)are considered:AND_TDDs, EXOR_TDDs, and Kleene_TDDs. Kleene_TDDs are useful for logic simulation in the presence of unknown inputs. Let N(BDD:f), N(AND_TDD:f), and N(EXOR_TDD:f)be the number of non-terminal nodes in the BDD, the AND_TDD, and the EXOR_TDD for f, respectively. Let N(Kleene_TDD:F)be the number of non-terminal nodes in the Kleene_TDD for F, where F is the regular ternary function corresponding to f. Then N(BDD:f)≦N(TDD:f). For parity functions, N(BDD:f)=N(AND_TDD:f)=N(EXOR_TDD:f)=N(Kleene_TDD:F). For unate functions, N(BDD:f)=N(AND_TDD:f). The sizes of Kleene_TDDs are O(3^n/n), and O(n^3)for arbitrary functions, and symmetric functions, respectively. There exist a 2n-variable function, where Kleene_TDDs require O(n)nodes with the best order, while O(3^n)nodes in the worst order.

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

著者

• SASAO Tsutomu

  Department of Computer Science and Electronics, Kyushu Institute of Technology

• MATSUURA Munehiro

  Department of Computer Science and Electronics, Kyushu Institute of Technology

• IGUCHI Yukihiro

  Department of Computer Science, Meiji University

• Sasao T

  Department Of Computer Science And Electronics Kyushu Institute Of Technology

• Sasao Tsutomu

  The Department Of Computer Science And Electronics Kyushu Institute Of Technology

• Iguchi Y

  Department Of Computer Science Meiji University

• MATSUURA Munehiro

  Kyushu Institute of Technology

• IGUCHI Yukihiro

  the Department of Computer Science, Meiji University

• MATSUURA Munehiro

  the 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)
• Generalized Reed-Muller Expressions: Complexity and an Exact Minimization Algorithm (Special Section on VLSI Design and CAD Algorithms)
• Shared Multi-Terminal Binary Decision Diagrams for Multiple-Output Functions (Special Section on VLSI Design and CAD Algorithms)
• A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams
• Heuristics to Minimize Multiple-Valued Decision Diagrams (Special Section on VLSI Design and CAD Algorithms)
• 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)
• 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)
• Minimization of AND-OR-EXOR Three-Level Networks with AND Gate Sharing (Special Issue on Synthesis and Verification of Hardware Design)
• A Design Method of a Regular Expression Matching Circuit Based on Decomposed Automaton
• A Memory-Based Programmable Logic Device Using Look-Up Table Cascade with Synchronous Static Random Access Memories
• On the Numbers of Products in Prefix SOPs for Interval Functions

もっと見る 閉じる

スポンサーリンク