IEICE TRANSACTIONS on Fundamentals
Generalized Reed-Muller Expressions: Complexity and an Exact Minimization Algorithm
Summary :
A generalized Reed-Muller expression (GRM) is obtained by negating some of the literals in a positive polarity Reed-Muller expression (PPRM). There are at most 2(n2)^(n-1) different GRMs for an n-variable function. A minimum GRM is one with the fewest products. This paper presents certain properties and an exact minimization algorithm for GRMs. The minimization algorithm uses binary decision diagrams. Up to five variables, all the representative functions of NP-equivalence classes were generated and minimized. Tables compare the number of products necessary to represent four-and five-variable functions for four classes of expressions: PPRMs, FPRMs, GRMs and SOPs. GRMs require, on the average, fewer products than sum-of-products expressions (SOPs), and have easily testable realizations.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.12 pp.2123-2130
- Publication Date
- 1996/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
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
Tsutomu SASAO, Debatosh DEBNATH, "Generalized Reed-Muller Expressions: Complexity and an Exact Minimization Algorithm" in IEICE TRANSACTIONS on Fundamentals,
vol. E79-A, no. 12, pp. 2123-2130, December 1996, doi: .
Abstract: A generalized Reed-Muller expression (GRM) is obtained by negating some of the literals in a positive polarity Reed-Muller expression (PPRM). There are at most 2(n2)^(n-1) different GRMs for an n-variable function. A minimum GRM is one with the fewest products. This paper presents certain properties and an exact minimization algorithm for GRMs. The minimization algorithm uses binary decision diagrams. Up to five variables, all the representative functions of NP-equivalence classes were generated and minimized. Tables compare the number of products necessary to represent four-and five-variable functions for four classes of expressions: PPRMs, FPRMs, GRMs and SOPs. GRMs require, on the average, fewer products than sum-of-products expressions (SOPs), and have easily testable realizations.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_12_2123/_p
Copy
@ARTICLE{e79-a_12_2123,
author={Tsutomu SASAO, Debatosh DEBNATH, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized Reed-Muller Expressions: Complexity and an Exact Minimization Algorithm},
year={1996},
volume={E79-A},
number={12},
pages={2123-2130},
abstract={A generalized Reed-Muller expression (GRM) is obtained by negating some of the literals in a positive polarity Reed-Muller expression (PPRM). There are at most 2(n2)^(n-1) different GRMs for an n-variable function. A minimum GRM is one with the fewest products. This paper presents certain properties and an exact minimization algorithm for GRMs. The minimization algorithm uses binary decision diagrams. Up to five variables, all the representative functions of NP-equivalence classes were generated and minimized. Tables compare the number of products necessary to represent four-and five-variable functions for four classes of expressions: PPRMs, FPRMs, GRMs and SOPs. GRMs require, on the average, fewer products than sum-of-products expressions (SOPs), and have easily testable realizations.},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - Generalized Reed-Muller Expressions: Complexity and an Exact Minimization Algorithm
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2123
EP - 2130
AU - Tsutomu SASAO
AU - Debatosh DEBNATH
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1996
AB - A generalized Reed-Muller expression (GRM) is obtained by negating some of the literals in a positive polarity Reed-Muller expression (PPRM). There are at most 2(n2)^(n-1) different GRMs for an n-variable function. A minimum GRM is one with the fewest products. This paper presents certain properties and an exact minimization algorithm for GRMs. The minimization algorithm uses binary decision diagrams. Up to five variables, all the representative functions of NP-equivalence classes were generated and minimized. Tables compare the number of products necessary to represent four-and five-variable functions for four classes of expressions: PPRMs, FPRMs, GRMs and SOPs. GRMs require, on the average, fewer products than sum-of-products expressions (SOPs), and have easily testable realizations.
ER -
English
