Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs(Logic Synthesis, <Special Section>VLSI Design and CAD Algorithms)

スポンサーリンク

概要

• 論文の詳細を見る

• Fixed polarity Reed-Muller expressions (FPRMs) exhibit several useful properties that make them suitable for many practical applications. This paper presents an exact minimization algorithm for FPRMs for incompletely specified functions. For an n-variable function with a unspecified minterms there are 2^<n+α> distinct FPRMs, and a minimum FPRM is one with the fewest product terms. To find a minimum FPRM the algorithm requires to determine an assignment of the incompletely specified minterms. This is accomplished by using the concept of integer-valued functions in conjunction with an extended truth vector and a weight vector. The vectors help formulate the problem as an assignment of the variables of integer-valued functions, which are then efficiently manipulated by using multi-terminal binary decision diagrams for finding an assignment of the unspecified minterms. The effectiveness of the algorithm is demonstrated through experimental results for code converters, adders, and randomly generated functions.

• 社団法人電子情報通信学会の論文
• 2005-12-01

著者

• SASAO Tsutomu

  Department of Computer Science and Electronics, Kyushu Institute of Technology

• Debnath Debatosh

  Oakland Univ. Michigan Usa

• Debnath Debatosh

  Department Of Computer Science And Engineering Oakland University

• Sasao Tsutomu

  Kyushu Inst. Of Technol. Iizuka‐shi Jpn

• Sasao Tsutomu

  Department Of Computer Science And Electronics Kyushu Institute Of Technology

• Debnath Debatosh

  Department Of Computer Science And Electronics Faculty Of Computer Science And Systems Engineering K

関連論文

• 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)
• Optimization of Pseudo-Kronecker Expressions Using Multiple-Place Decision Diagrams (Special Issue on Multiple-Valued Logic)
• 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 Memory-Based Programmable Logic Device Using Look-Up Table Cascade with Synchronous Static Random Access Memories
• Programmable Architectures and Design Methods for Two-Variable Numeric Function Generators
• Programmable Architectures and Design Methods for Two-Variable Numeric Function Generators
• 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
• Programmable Architectures and Design Methods for Two-Variable Numeric Function Generators
• On Optimizations of Edge-Valued MDDs for Fast Analysis of Multi-State Systems

もっと見る 閉じる

スポンサーリンク