Generalized Reed-Muller Expressions: Complexity and an Exact Minimization Algorithm (Special Section on VLSI Design and CAD Algorithms)
スポンサーリンク
概要
- 論文の詳細を見る
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>>-l 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, a11 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.
- 社団法人電子情報通信学会の論文
- 1996-12-25
著者
-
Sasao Tsutomu
The Department Of Computer Science And Electronics Kyushu Institute Of Technology
-
DEBNATH Debatosh
the Department of Computer Science and Electronics, Kyushu Institute of Technology
-
Debnath Debatosh
The Department Of Computer Science And Electronics Kyushu Institute Of Technology
-
SASAO Tsutomu
the Department of Computer Science and Electronics, Kyushu Institute of Technology
関連論文
- Generalized Reed-Muller Expressions: Complexity and an Exact Minimization Algorithm (Special Section on VLSI Design and CAD Algorithms)
- Shared Multi-Terminal Binary Decision Diagrams for Multiple-Output Functions (Special Section on VLSI Design and CAD Algorithms)
- Heuristics to Minimize Multiple-Valued Decision Diagrams (Special Section on VLSI Design and CAD Algorithms)
- A Design of AES Encryption Circuit with 128-bit Keys Using Look-Up Table Ring on FPGA(Computer Components)
- On Properties of Kleene TDDs(Special Issue on Test and Diagnosis of VLSI)
- Minimization of AND-OR-EXOR Three-Level Networks with AND Gate Sharing (Special Issue on Synthesis and Verification of Hardware Design)