
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs
Debatosh DEBNATH Tsutomu SASAO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E88A
No.12
pp.33323341 Publication Date: 2005/12/01
Online ISSN: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms) Category: Logic Synthesis Keyword: ANDEXOR, ReedMuller expression, FPRM, exact minimization, incompletely specified function,
Full Text: PDF(549.7KB) >>Buy this Article
Summary:
Fixed polarity ReedMuller 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 nvariable function with α 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 integervalued 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 integervalued functions, which are then efficiently manipulated by using multiterminal 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.

