Article

Free access

Fast OFDD based minimization of fixed polarity Reed-Muller expressions

Authors:

Rolf Drechsler,

Bernd Becker,

Michael TheobaldAuthors Info & Claims

EURO-DAC '94: Proceedings of the conference on European design automation

Pages 2 - 7

Published: 23 September 1994 Publication History

PDF eReader

References

[1]

B. Becker and R. Drechsler. On the computational power of functional decision diagrams. SO. Workrhop iiber Komplezithtstheorie, Datenrtruktunn und efiziente Algorithmen, Berlin, 1993.

Google Scholar

[2]

B. Becker and R. Drechsler. Testability of circuits do rived from functional decision diagrams. In European Conf. on Design Automation, page 667, 1994.

Google Scholar

[3]

R.K. Brayton, G.D. Hachtel, C. McMullen, and AL Sangiovanni-VincenteIIi. Logic Minimization Algorithmr for VLSI Syntherir. Kluwer Academic Pub lishers, 1984.

Digital Library

Google Scholar

[4]

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

Digital Library

Google Scholar

[5]

R.E. Bryant. Graph - based aIgorithms for Boolean fuuction manipulation. IEEE &no. on Comp., 8:677-691, 1986.

Digital Library

Google Scholar

[6]

O. Coudert, H. Fraiese, and J.-C. Madre. A breakthrough in two-level logic minimization. In Int'l Workrhop on Logic Sgnth., page P2b, 1993.

Google Scholar

[7]

R. Drechsler, A. Sarabi, M. Theobald, B. Becker, and M.A. Perkowski. Efficient representation and manip ulation of switching functions based on ordered kronecker functional decision diagrams. In Design Automation Conf., pages 415-419, 1994.

Digital Library

Google Scholar

[8]

U. Kebschull and W. Rosenstiel. Efficient graph-based computation and manipulation of functional decision diagrams. In European Conf. on Design Automation, pages 278-282, 1993.

Crossref

Google Scholar

[9]

U. Kebschull, E. Schubert, and W. Roeenstiel. Multilevel logic synthesis based on functional decision diagrams. In European Conf. on Design Automation, pages 43-47, 1992.

Crossref

Google Scholar

[10]

S. Minato. Zero-suppressed BDDe for set manipulation in combinational problems. In Derign Automation Conf., pages 272-277, 1993.

Digital Library

Google Scholar

[11]

M.A. Perkowski and M. Chrzanowska-Jeske. An exact algorithm to minimize mixed-radix exclusive sums of products for incompletely specified boolean functions. In Int'l Sgmp. Circ. and Syrtemr, pages 1652-1655, 1990.

Google Scholar

[12]

M.A. Perkowski, L. Csansky, A. Sarabi, and I. Schkfer. Fast minimization of mixed-polarity andfxor canonicaI networks. In Int'l Conf. on Comp. De+, pages 33-36, 1992.

Crossref

Google Scholar

[13]

S.M. Reddy. Easily testable realizations for logic functions. In IEEE Dunraction on Computers, volume c-21, pages 1183-1188, 1972.

Google Scholar

[14]

A. Sarabi and MA. Perkowski. Fast exact and quasiminimal minimization of highly testable fixed-polarity and/xor canonical networks. In Derign Automation Conf., pages 3Q-35, 1992.

Digital Library

Google Scholar

[15]

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

Digital Library

Google Scholar

[16]

T. Sasao and Ph. Besslich. On the complexity of mod- 2 sum PLAs. IEEE !l%anr. on Comp., 39:262-266, 1990.

Digital Library

Google Scholar

[17]

J. Saul. Logic synthesis for arithmetic circuits using the reed-muller representation. In European Conf. on Derign Automation, pages 109-113, 1992.

Crossref

Google Scholar

[18]

I. Sch5fer and M.A. Perkowski. Multiple-valued input generalized reed-muUer forms. In Int'l Sgmp. on multi-valued Logic, pages 40-48, 1991.

Google Scholar

[19]

D. Sieliug and I. Wegener. Reduction of BDDs in linear time. Information Procerring Letters, 48(3):13Q- 144, 11 1993.

Digital Library

Google Scholar

[20]

C.C. Tsai and M. Marek-Sadowska. Boolean matching using generalized Reed-Muller forms. In Derign Automation Conf., pages 33+344, 1994.

Digital Library

Google Scholar

Cited By

View all

Shen SZhang JQin YLi SRoychowdhury J(2009)Synthesizing complementary circuits automaticallyProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687472(381-388)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687472
Lotfi-Kamran PHosseinabady MShojaei HMassoumi MNavabi ZTang T(2005)TED+Proceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120964(567-572)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120964
Aguirre ACoello Coello C(2003)Evolutionary Synthesis of LogicCircuits Using Information TheoryArtificial Intelligence Review10.1023/B:AIRE.0000006603.98023.9720:3-4(445-471)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1023/B%3AAIRE.0000006603.98023.97
Show More Cited By

Index Terms

Fast OFDD based minimization of fixed polarity Reed-Muller expressions
1. Hardware
  1. Hardware test
    1. Design for testability
  2. Very large scale integration design
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

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

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 ...
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.
On Perfect and Reed–Muller Codes over Finite Fields
Abstract
We consider error-correcting codes over a finite field with elements (-ary codes). We study relations between single-error-correcting -ary perfect codes and -ary Reed–Muller codes. For we find parameters of affine Reed–Muller codes of order . We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

EURO-DAC '94: Proceedings of the conference on European design automation

September 1994

697 pages

ISBN:0897916859

Chairman:
Jean Mermet
ECSI Office, Gie`res, France

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 23 September 1994

Check for updates

Qualifiers

Article

Conference

EuroDAC94

Sponsor:

SIGDA

EuroDAC94: European Design Automation Conference

September 19 - 23, 1994

Grenoble, France

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
186
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)5

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shen SZhang JQin YLi SRoychowdhury J(2009)Synthesizing complementary circuits automaticallyProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687472(381-388)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687472
Lotfi-Kamran PHosseinabady MShojaei HMassoumi MNavabi ZTang T(2005)TED+Proceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1120964(567-572)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1120964
Aguirre ACoello Coello C(2003)Evolutionary Synthesis of LogicCircuits Using Information TheoryArtificial Intelligence Review10.1023/B:AIRE.0000006603.98023.9720:3-4(445-471)Online publication date: 1-Dec-2003
https://dl.acm.org/doi/10.1023/B%3AAIRE.0000006603.98023.97
Schmiedle FDrechsler NGroße DDrechsler R(2002)Heuristic Learning Based on Genetic ProgrammingGenetic Programming and Evolvable Machines10.1023/A:10209889259233:4(363-388)Online publication date: 1-Dec-2002
https://dl.acm.org/doi/10.1023/A%3A1020988925923
Drechsler R(2002)Verifying integrity of decision diagramsIntegration, the VLSI Journal10.1016/S0167-9260(02)00042-132:1-3(61-75)Online publication date: 1-Nov-2002
https://dl.acm.org/doi/10.1016/S0167-9260%2802%2900042-1
Miller JJob DVassilev V(2000)Principles in the Evolutionary Design of Digital Circuits—Part IGenetic Programming and Evolvable Machines10.1023/A:10100163133731:1-2(7-35)Online publication date: 1-Apr-2000
https://dl.acm.org/doi/10.1023/A%3A1010016313373
Drechsler RHengster HSchäfer HHartmann JBecker B(1999)Testability of 2-Level AND/EXOR CircuitsJournal of Electronic Testing: Theory and Applications10.1023/A:100830600288214:3(219-225)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1023/A%3A1008306002882
Drechsler RBecker BJahnke A(1998)On Variable Ordering and Decomposition Type Choice in OKFDDsIEEE Transactions on Computers10.1109/12.73768547:12(1398-1403)Online publication date: 1-Dec-1998
https://dl.acm.org/doi/10.1109/12.737685
Drechsler RHengster HSchafer HHartmann JBecker B(1997)Testability of 2-level AND/EXOR circuitsProceedings of the 1997 European conference on Design and Test10.5555/787260.787722Online publication date: 17-Mar-1997
https://dl.acm.org/doi/10.5555/787260.787722
Becker BDrechsler R(1997)Decision Diagrams in Synthesis - Algorithms, Applications and ExtensionsProceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications10.5555/523974.834854Online publication date: 4-Jan-1997
https://dl.acm.org/doi/10.5555/523974.834854
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

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

Minimization for ternary fixed polarity Reed–Muller expressions based on ternary quantum shuffled frog leaping algorithm

On Perfect and Reed–Muller Codes over Finite Fields