Title :
Exact minimization of fixed polarity Reed-Muller expressions for incompletely specified functions
Author :
Debnath, Debatosh ; Sasao, Tsutomu
Author_Institution :
Dept. of Comput. Sci. & Electron., Kyushu Inst. of Technol., Iizuka, Japan
Abstract :
This paper presents an exact minimization algorithm for fixed polarity Reed-Muller expressions (FPRMs) for incompletely specified functions. For an n-variable function with /spl alpha/ unspecified minterms there are 2/sup n+/spl alpha// distinct FPRMs. A minimum FPRM is one with the fewest products. The minimization algorithm is based on the multi-terminal binary decision diagrams. Experimental results for a set of functions are shown. The algorithm can be extended to obtain exact minimum Kronecker expressions for incompletely specified functions.
Keywords :
Reed-Muller codes; binary decision diagrams; minimisation of switching nets; switching functions; Kronecker expressions; exact minimization algorithm; fixed polarity Reed-Muller expressions; incompletely specified functions; multi-terminal binary decision diagrams; n-variable function; unspecified minterms; Boolean functions; Circuit testing; Computer science; Data structures; Heuristic algorithms; Minimization methods; Paper technology; Polynomials; Search methods; Switching circuits;
Conference_Titel :
Design Automation Conference, 2000. Proceedings of the ASP-DAC 2000. Asia and South Pacific
Conference_Location :
Yokohama, Japan
Print_ISBN :
0-7803-5973-9
DOI :
10.1109/ASPDAC.2000.835105
