Article

Free access

Exact minimization of fixed polarity Reed-Muller expressions for incompletely specified functions

Authors:

Debatosh Debnath,

Tsutomu SasaoAuthors Info & Claims

ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation Conference

Pages 247 - 252

https://doi.org/10.1145/368434.368622

Published: 28 January 2000 Publication History

PDF eReader

References

[1]

G. Bioul, M. Davio, and J.-P. Deschamps, "Minimization of ring-sum expansions of Boolean functions," Philips Res. Repts., Vol. 28, pp. 17-36, 1973.

Google Scholar

[2]

R. E. Bryant, "Graph-based algorithms for Boolean function manipulation," IEEE Trans. Comput., Vol. C-35, No. 8, pp. 677-691, Aug. 1986.

Digital Library

Google Scholar

[3]

C.-H. Chang and B. J. Falkowski, "Flexible optimization of fixed polarity Reed-Muller expansions for multiple output completely and incompletely specified Boolean functions," Proc. Asia and South Pacific Design Automation Conference, pp. 335-340, Sept. 1995.

Digital Library

Google Scholar

[4]

C.-H. Chang and B. J. Falkowski, "Adaptive exact optimisation of minimally testable FPRM expansions," IEE Proceedings-Computers and Digital Techniques, Vol. 145, No. 6, pp. 385-394, Nov. 1998.

Crossref

Google Scholar

[5]

E. M. Clarke, K. L. McMillan, X. Zhao, M. Fujita, and J. Yang, "Spectral transforms for large Boolean functions with applications to technology mapping," Proc. Design Automation Conference, pp. 54-60, June 1993.

Digital Library

Google Scholar

[6]

M. Davio, J.-P. Deschamps, and A. Thayse, Discrete and Switching Functions, McGraw-Hill International, 1978.

Google Scholar

[7]

R. Drechsler, M. Theobald, and B. Becker, "Fast OFDD- based minimization of fixed polarity Reed-Muller expressions," IEEE Trans. Comput., Vol. C-45, No. 11, pp. 1294-1299, Nov. 1996.

Digital Library

Google Scholar

[8]

D. H. Green, "Reed-Muller expansions of incompletely specified functions," IEE Proceedings, Vol. 134, Pt. E, No. 5, pp. 228-236, Sept. 1987.

Google Scholar

[9]

S. L. Hurst, D. M. Miller, and J. C. Muzio, Spectral Techniques in Digital Logic, Academic Press Inc., 1985.

Digital Library

Google Scholar

[10]

U. Kebschull and W. Rosenstiel, "Efficient graph-based computation and manipulation of functional decision diagrams," Proc. European Conference on Design Automation, pp. 278-282, Mar. 1993.

Google Scholar

[11]

B. W. Kernighan and D. M. Ritchie, The C Programming Language, Second Edition, Prentice-Hall, 1988.

Digital Library

Google Scholar

[12]

P. K. Lui and J. C. Muzio, "Boolean matrix transforms for the minimization of modulo-2 canonical expressions," IEEE Trans. Comput., Vol. C-41, No. 3, pp. 342-347, Mar. 1992.

Digital Library

Google Scholar

[13]

L. McKenzie, A. E. A. Almaini, J. F. Miller, and P. Thomson, "Optimisation of Reed-Muller logic functions," International Journal of Electronics, Vol. 75, No. 3, pp. 451- 466, Sept. 1993.

Crossref

Google Scholar

[14]

A. Sarabi and M. A. Perkowski, "Fast exact and quasiminimal minimization of highly testable fixed polarity AND/XOR canonical networks," Proc. Design Automation Conference, pp. 30-35, June 1992.

Digital Library

Google Scholar

[15]

T. Sasao, "AND-EXOR expressions and their optimization," in T. Sasao, ed., Logic Synthesis and Optimization, Kluwer Academic Publishers, 1993.

Digital Library

Google Scholar

[16]

T. Sasao, "Representations of logic functions using EXOR operators," in T. Sasao and M. Fujita, eds., Representations of Discrete Functions, Kluwer Academic Publishers, 1996.

Google Scholar

[17]

T. Sasao and F. Izuhara, "Exact minimization of FPRMs using multi-terminal EXOR TDDs," in T. Sasao and M. Fujita, eds., Representations of Discrete Functions, Kluwer Academic Publishers, 1996.

Google Scholar

[18]

T. Sasao, Switching Theory for Logic Synthesis, Kluwer Academic Publishers, 1999.

Digital Library

Google Scholar

[19]

F. Somenzi, CUDD: CU Decision Diagram Package, Release 2.3.0, University of Colorado at Boulder, 1998 (http://vlsi.colorado.edu/~fabio/).

Google Scholar

[20]

A. Tran, "Graphical method for the conversion of minterms to Reed-Muller coefficients and the minimization of exclusive-OR switching functions," IEE Proceedings, Vol. 134, Pt. E, No. 2, pp. 93-99, Mar. 1987.

Google Scholar

[21]

C. Tsai and M. Marek-Sadowska, "Minimisation of fixed-polarity AND/XOR canonical networks," IEE Proceedings-Computers and Digital Techniques, Vol. 141, No. 6, pp. 369-374, Nov. 1994.

Crossref

Google Scholar

[22]

C. Tsai and M. Marek-Sadowska, "Generalized Reed- Muller forms as a tool to detect symmetries," IEEE Trans. Comput., Vol. 45, No. 1, pp. 33-40, Jan. 1996.

Digital Library

Google Scholar

[23]

C. Tsai and M. Marek-Sadowska, "Multilevel logic synthesis for arithmetic functions," Proc. 33rd Design Automation Conference, pp. 242-247, June 1996.

Digital Library

Google Scholar

[24]

C. Tsai and M. Marek-Sadowska, "Boolean functions classification via fixed polarity Reed-Muller forms," IEEE Trans. Comput., Vol. C-46, No. 2, pp. 173-186, Feb. 1997.

Digital Library

Google Scholar

[25]

D. Varma and E. A. Trachtenberg, "Computation of Reed-Muller expansions of incompletely specified Boolean functions from reduced representations," IEE Proceedings-E, Vol. 138, No. 2, pp. 85-92, Mar. 1991.

Google Scholar

[26]

A. Zakrevskij, "Minimizing polynomial implementation of weakly specified logic functions and systems," Proc. 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 157-166, Sept. 1997.

Google Scholar

[27]

I. I. Zhegalkin, "The technique of calculation of statements in symbolic logic," Mathe. Sbornik, Vol. 34, pp. 9-28, 1927 (in Russian).

Google Scholar

[28]

Z. Zilic and Z. G. Vranesic, "A multiple-valued Reed- Muller transform for incompletely specified functions," IEEE Trans. Comput., Vol. C-44, No. 8, pp. 1012-1020, Aug. 1995.

Digital Library

Google Scholar

Cited By

View all

He ZXiao LRuan LGu FHuo ZQin GZhu MZhang LLiu RWang X(2017)A Power and Area Optimization Approach of Mixed Polarity Reed-Muller Expression for Incompletely Specified Boolean FunctionsJournal of Computer Science and Technology10.1007/s11390-017-1723-132:2(297-311)Online publication date: 13-Mar-2017
https://doi.org/10.1007/s11390-017-1723-1
Kamal TKhan M(2008)An application specific integrated circuit for optimization of fixed polarity reed-muller expressions2008 International Conference on Electrical and Computer Engineering10.1109/ICECE.2008.4769303(721-726)Online publication date: Dec-2008
https://doi.org/10.1109/ICECE.2008.4769303

Recommendations

A Multiple-Valued Reed-Muller Transform for Incompletely Specified Functions

This paper considers the Reed-Muller transform for incompletely specified multiple-valued logic functions, which is obtained as the finite field polynomial representation. A new algorithm for dealing with single-variable functions is presented. It is ...
Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs

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-...
Boolean Functions Classification via Fixed Polarity Reed-Muller Forms

In this paper, we present a new method to characterize completely specified Boolean functions. The central theme of the classification is the functional equivalence (a.k.a. Boolean matching). Two Boolean functions are equivalent if there exists input ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation Conference

January 2000

691 pages

ISBN:0780359747

DOI:10.1145/368434

Chairman:
Kenji Yoshida
Toshiba Corp., Kawasaki, Japan

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 January 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ASP-DAC00

Sponsor:

IEICE
IPSJ
SIGDA
IEEE-CAS

ASP-DAC00: Asia and South Pacific Design Automation Conference 2000

Yokohama, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
354
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

He ZXiao LRuan LGu FHuo ZQin GZhu MZhang LLiu RWang X(2017)A Power and Area Optimization Approach of Mixed Polarity Reed-Muller Expression for Incompletely Specified Boolean FunctionsJournal of Computer Science and Technology10.1007/s11390-017-1723-132:2(297-311)Online publication date: 13-Mar-2017
https://doi.org/10.1007/s11390-017-1723-1
Kamal TKhan M(2008)An application specific integrated circuit for optimization of fixed polarity reed-muller expressions2008 International Conference on Electrical and Computer Engineering10.1109/ICECE.2008.4769303(721-726)Online publication date: Dec-2008
https://doi.org/10.1109/ICECE.2008.4769303

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

Recommendations

A Multiple-Valued Reed-Muller Transform for Incompletely Specified Functions

Exact Minimization of FPRMs for Incompletely Specified Functions by Using MTBDDs

Boolean Functions Classification via Fixed Polarity Reed-Muller Forms