IEICE TRANSACTIONS on Fundamentals
Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.12 pp.3332-3341
- Publication Date
- 2005/12/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietfec/e88-a.12.3332
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
- Logic Synthesis
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Debatosh DEBNATH, Tsutomu SASAO, "Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs" in IEICE TRANSACTIONS on Fundamentals,
vol. E88-A, no. 12, pp. 3332-3341, December 2005, doi: 10.1093/ietfec/e88-a.12.3332.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.12.3332/_p
Copy
@ARTICLE{e88-a_12_3332,
author={Debatosh DEBNATH, Tsutomu SASAO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs},
year={2005},
volume={E88-A},
number={12},
pages={3332-3341},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e88-a.12.3332},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 3332
EP - 3341
AU - Debatosh DEBNATH
AU - Tsutomu SASAO
PY - 2005
DO - 10.1093/ietfec/e88-a.12.3332
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2005
AB - 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.
ER -
English
