research-article

Fast OFDD-Based Minimization of Fixed Polarity Reed-Muller Expressions

Authors:

Rolf Drechsler,

Michael Theobald,

Bernd BeckerAuthors Info & Claims

IEEE Transactions on Computers, Volume 45, Issue 11

Pages 1294 - 1299

https://doi.org/10.1109/12.544485

Published: 01 November 1996 Publication History

Abstract

We present methods to minimize fixed polarity Reed-Muller expressions (FPRMs), i.e., two-level fixed polarity AND/EXOR canonical representations of Boolean functions, using ordered functional decision diagrams (OFDDs). We investigate the close relation between both representations and use efficient algorithms on OFDDs for exact and heuristic minimization of FPRMs. In contrast to previously published methods, our algorithm can also handle circuits with several outputs. Experimental results on large benchmarks are given to show the efficiency of our approach.

References

[1]

B. Becker and R. Drechsler, "Synthesis for Testability: Circuits Derived from Ordered Kronecker Functional Decision Diagrams," Proc. European Design and Test Conf., p. 592, Mar. 1995.

Digital Library

[2]

B. Becker R. Drechsler and M. Theobald, "On the Implementation of a Package for Efficient Representation and Manipulation of Functional Decision Diagrams," Proc. IFIP WG 10.5 Workshop Applications of the Reed-Muller Expansion in Circuit Design, Hamburg, pp. 162-169, Sept. 1993.

[3]

R.K. Brayton G.D. Hachtel C. McMullen and A.L. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984.

Digital Library

[4]

S.D. Brown R.J. Francis J. Rose and Z.G. Vranesic, Field-Programmable Gate Arrays. Kluwer Academic Publisher, 1992.

Digital Library

[5]

R.E. Bryant, "Graph-Based Algorithms for Boolean Function Manipulation," IEEE Trans. Computers, vol. 35, no. 8, pp. 677-691, Aug. 1986.

Digital Library

[6]

O. Coudert H. Fraisse and J.-C. Madre, "A Breakthrough in Two-Level Logic Minimization," Proc. Int'l Workshop Logic Synthesis, p. P2b, May 1993.

[7]

R. Drechsler and B. Becker, "Rapid Prototyping of Fully Testable MultiLevel AND/EXOR Networks," IFIP WG 10.5 Workshop Applications of the Reed-Muller Expansion in Circuit Design, Hamburg, pp. 126-133, Sept 1993.

[8]

R. Drechsler A. Sarabi M. Theobald B. Becker and M.A. Perkowski, "Efficient Representation and Manipulation of Switching Functions Based on Ordered Kronecker Functional Decision Diagrams," Proc. Design Automation Conf., pp. 415-419, June 1994.

Digital Library

[9]

U. Kebschull and W. Rosenstiel, "Efficient Graph-Based Computation and Manipulation of Functional Decision Diagrams," Proc. European Conf. Design Automation, pp. 278-282, Mar. 1993.

[10]

U. Kebschull E. Schubert and W. Rosenstiel, "Multilevel Logic Synthesis Based on Functional Decision Diagrams," Proc. European Conf. Design Automation, pp. 43-47, Mar. 1992.

[11]

S. Minato, "Zero-Suppressed BDDs for Set Manipulation in Combinational Problems," Proc. Design Automation Conf., pp. 272-277, June 1993.

Digital Library

[12]

G. Papakonstantinou, "Minimization of Modulo-2 Sum of Products," IEEE Trans. Computers, vol. 28, no. 8, pp. 163-167, Feb. 1979.

Digital Library

[13]

M.A. Perkowski and M. Chrzanowska-Jeske, "An Exact Algorithm to Minimize Mixed-Radix Exclusive Sums of Products for Incompletely Specified Boolean Functions," Proc. Int'l Symp. Circ. and Systems, pp. 1,652-1,655, May 1990.

[14]

M.A. Perkowski L. Csanky A. Sarabi and I. Schäfer, "Fast Minimization of Mixed-Polarity AND/XOR Canonical Networks," Proc. Int'l Conf. Computer Design, pp. 33-36, Oct. 1992.

Digital Library

[15]

S.M. Reddy, "Easily Testable Realizations for Logic Functions," IEEE Trans. Computers, vol. 21, no. 11, pp. 1,183-1,188, Nov. 1972.

[16]

U. Rollwage, "The Complexity of Mod-2 Sum PLAs for Symmetric Functions," Proc. IFIP WG 10.5 Workshop Applications of the Reed-Muller Expansion in Circuit Design, Hamburg, pp. 6-12, Sept. 1993.

[17]

A. Sarabi and M.A. Perkowski, "Fast Exact and Quasi-Minimal Minimization of Highly Testable Fixed-Polarity AND/XOR Canonical Networks," Proc. Design Automation Conf., pp. 30-35 June 1992.

Digital Library

[18]

A. Sarabi and M.A. Perkowski, "Design for Testability Properties of AND/XOR Networks," Proc. IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design, Hamburg, pp. 147-153, Sept. 1993.

[19]

T. Sasao, "EXMIN2: A Simplification Algorithm for Exclusive-OR-Sum-of Products Expressions for Multiple-Valued-Input Two-Valued-Output Functions," IEEE Trans. Computer-Aided Design, vol. 12, pp. 621-632, May 1993.

Digital Library

[20]

T. Sasao, Logic Synthesis and Optimization. Kluwer Academic Publisher, 1993.

Digital Library

[21]

T. Sasao and P. Besslich, "On the Complexity of Mod-2 Sum PLAs," IEEE Trans. Computers, vol. 39, no. 2, pp. 262-266, Feb. 1990.

Digital Library

[22]

J. Saul, "Logic Synthesis for Arithmetic Circuits Using the Reed-Muller Representation," Proc. European Conf. Design Automation, pp. 109-113, Mar. 1992.

[23]

I. Schäfer and M.A. Perkowski, "Multiple-Valued Input Generalized Reed-Muller Forms," Proc. Int'l Symp. MultiValued Logic, pp. 40-48, May 1991.

[24]

D. Sieling and I. Wegener, "Reduction of BDDs in Linear Time," Information Processing Letters, vol. 48, pp. 139-144, Nov. 1993.

Digital Library

[25]

C.C. Tsai and M. Marek-Sadowska, "Efficient Minimization Algorithms for Fixed Polarity AND/XOR Canonical Networks," Proc. Great Lakes Symp. VLSI pp. 76-79, Feb. 1993.

[26]

C.C. Tsai and M. Marek-Sadowska, "Boolean Matching Using Generalized Reed-Muller Forms," Proc. Design Automation Conf., pp. 339-344, June 1994.

Digital Library

Cited By

Zhou YHe ZJiang JLiu JHe JWang TXiao LWang X(2023)Fast Area Optimization Approach for XNOR/OR-based Fixed Polarity Reed-Muller Logic Circuits based on Multi-strategy Wolf Pack AlgorithmACM Transactions on Design Automation of Electronic Systems10.1145/358781828:3(1-16)Online publication date: 18-Apr-2023
https://dl.acm.org/doi/10.1145/3587818
Huang XFang KFang LChen QLai ZWei L(2019)Bi-Kronecker Functional Decision DiagramsProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33012867(2867-2875)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33012867
Lin CJha N(2014)RMDDSACM Journal on Emerging Technologies in Computing Systems10.1145/256492310:2(1-25)Online publication date: 6-Mar-2014
https://dl.acm.org/doi/10.1145/2564923
Show More Cited By

Index Terms

Fast OFDD-Based Minimization of Fixed Polarity Reed-Muller Expressions
1. Hardware
  1. Integrated circuits
    1. Logic circuits
  2. Very large scale integration design
2. Mathematics of computing
  1. Mathematical software

Recommendations

Minimization for ternary fixed polarity Reed–Muller expressions based on ternary quantum shuffled frog leaping algorithm
Abstract
Logic minimization is one of the most crucial steps in combinational logic synthesis. The minimization for ternary fixed polarity Reed–Muller (FPRM) expressions aims to find a polarity that produces a ternary FPRM expression with as ...
Highlights
- A ternary quantum rotation gate (TQRG) is proposed to update and optimize the worst frog encoded by qutrits.
Delay optimization for ternary fixed polarity Reed–Muller circuits based on multilevel adaptive quantum genetic algorithm
Abstract
Delay optimization has now emerged as an important optimization goal in logic synthesis. The delay optimization for ternary fixed polarity Reed–Muller (FPRM) circuits aims to find a ternary FPRM circuit with a minimum delay. Because the delay ...
Easily Testable Realizations for Generalized Reed-Muller Expressions

This paper presents a design method of easily testable AND-EXOR networks. It is an improvement of Reddy and Saluja-Reddy's methods, and has the following features: 1) The network uses generalized Reed-Muller expressions (GRMs) instead of Positive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 45, Issue 11

November 1996

129 pages

ISSN:0018-9340

Editor:
Jane W. S. Liu
Univ. of Illinois, Urbana

Issue’s Table of Contents

Copyright © Copyright © 1996 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 November 1996

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou YHe ZJiang JLiu JHe JWang TXiao LWang X(2023)Fast Area Optimization Approach for XNOR/OR-based Fixed Polarity Reed-Muller Logic Circuits based on Multi-strategy Wolf Pack AlgorithmACM Transactions on Design Automation of Electronic Systems10.1145/358781828:3(1-16)Online publication date: 18-Apr-2023
https://dl.acm.org/doi/10.1145/3587818
Huang XFang KFang LChen QLai ZWei L(2019)Bi-Kronecker Functional Decision DiagramsProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33012867(2867-2875)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33012867
Lin CJha N(2014)RMDDSACM Journal on Emerging Technologies in Computing Systems10.1145/256492310:2(1-25)Online publication date: 6-Mar-2014
https://dl.acm.org/doi/10.1145/2564923
Drechsler RGünther WHöreth S(2002)Minimization of word-level decision diagramsIntegration, the VLSI Journal10.1016/S0167-9260(02)00047-033:1(39-70)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1016/S0167-9260%2802%2900047-0
Debnath DSasao TYoshida K(2000)Exact minimization of fixed polarity Reed-Muller expressions for incompletely specified functionsProceedings of the 2000 Asia and South Pacific Design Automation Conference10.1145/368434.368622(247-252)Online publication date: 28-Jan-2000
https://dl.acm.org/doi/10.1145/368434.368622

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents