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.E88-A   No.12   pp.3332-3341
Publication Date: 2005/12/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.12.3332
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Logic Synthesis
Keyword: 
AND-EXOR,  Reed-Muller expression,  FPRM,  exact minimization,  incompletely specified function,  

Full Text: PDF(549.7KB)
>>Buy this Article


Summary: 
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 α unspecified minterms there are 2n 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.