Article

Free access

A new viewpoint on two-level logic minimization

Authors:

Olivier Coudert,

Jean Christophe Madre,

Henri FraisseAuthors Info & Claims

DAC '93: Proceedings of the 30th international Design Automation Conference

Pages 625 - 630

https://doi.org/10.1145/157485.165071

Published: 01 July 1993 Publication History

PDF eReader

References

[1]

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

Digital Library

Google Scholar

[2]

R. K. Brayton, P. C. McGeer, J. Sanghavi, "A New Exact and Heuristic Minimizer for Two-Level Logj'c Synthesis',in Proc. of Int'l Symposia on In}ormat*'on Sciences, Fukuoka, Japan, July 1992.

Google Scholar

[3]

R. E. Bryant, "Graph-based Algorithms for Boolean Functions Manipulation", in IEEE Trans. on Computers, Vol C-35, 1986.

Digital Library

Google Scholar

[4]

O. Coudert, J. C. Madre, "A New Method to Com- ~ute Prime and Essential Prime Implicants of Boolean unctions", in Advanced research in VLSI and Parallel S_ystems, T. Knight and J. Savage Editors, The MIT Press, pp. 113-128, March 1992.

Google Scholar

[5]

O. Coudert, J. C. M~dre, "Implicit and Incremental Computation of Primes and Essential Primes of Boolean functions", in Proc. of the 29th DAC, Anaheim, CA, June 1992.

Digital Library

Google Scholar

[6]

O. Coudert, J. (3. Madre, "A New Viewpoint on Two- Level Logic Minimization", Bull research report N~ 92026, November 1992.

Google Scholar

[7]

O. Coudert, J. C. Madre, "Towards a Symbolic Logic Minimization Algorithm", in Proc. of VLSI Design'93, Bombay, India, January 1993.

Google Scholar

[8]

R. B. Cutler, S. Muroga, "Useless Prime Implicants of Incompletely Specified Multiple-Output Switching Functions~, in Int~l Journal of Computer and Information Sciences, Vol. 9, No. 4, 1980.

Google Scholar

[9]

S. J. Hong, S. Muroga, "Absolute Minimization of Completely Specified Switching Functions" in IEEE Trans. on Computers, Vol 40, pp. 53-65, 1991'.

Digital Library

Google Scholar

[10]

E. J. Jr. McCluskey, "Minimization of Boolean Functions", in Bell System Technical Journal, Vol 35, pp. 1417-1444, 1959.

Google Scholar

[11]

P. C. McGeer, J. Sanghavi, R. K. Brayton, "Minimization of Logic Functions using Essential Signature Sets", in Proc. of VLSI Design'93, Bombay, india, January 1993.

Google Scholar

[12]

W. V. O. Quine, "The Problem of Simplifying Truth Functions", in American Mathematical Monthly, Vol 59, pp. 521-531, 1952.

Crossref

Google Scholar

[13]

R. L. Rudell, Multiple-Valued Logic Minimization for PLA Synthesis, UCB technical report M86/65, 1986.

Google Scholar

[14]

R. L. Rudell, A. L. Sangiovanni-Vincentelli, "Multiple Valued Minimization for PLA Optimization", in IEEE Trans. on CAD, Vol 6, No 5, pp. 727-750, September 1987.

Digital Library

Google Scholar

[15]

G. M. Swamy, P. McGeer, R. K. Brayton, "A Fully Quine-McCluskey Procedure using BDD's", UCB technical report #UCB/ERL M92/127, November 1992. Also submitted to IWLS'93 and DAC'93.

Google Scholar

[16]

S. Yang, Logic Synthesis and Optimization Benchmarks User Guide, Microelectronics Center of North Carolina, January 1991.

Google Scholar

Cited By

View all

Lin CTam KKo CYen HWei SChen YWang C(2020)A Dynamic Expansion Order Algorithm for the SAT-based Minimization2020 IEEE 33rd International System-on-Chip Conference (SOCC)10.1109/SOCC49529.2020.9524758(271-276)Online publication date: 8-Sep-2020
https://doi.org/10.1109/SOCC49529.2020.9524758
Lee TWu CLin CChen YWang C(2018)Logic optimization with considering boolean relations2018 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2018.8342109(761-766)Online publication date: Mar-2018
https://doi.org/10.23919/DATE.2018.8342109
Khatri SShenoy NGiomi JKhouja A(2016)Logic SynthesisElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-4(27-55)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-4
Show More Cited By

Index Terms

A new viewpoint on two-level logic minimization

Recommendations

Two-level ℓ₁minimization for compressed sensing

Compressed sensing using 1 minimization has been widely and successfully applied. To further enhance the sparsity, a non-convex and piecewise linear penalty is proposed. This penalty gives two different weights according to the order of the absolute ...
New Restricted Isometry Property Analysis for $\ell_1-\ell_2$ Minimization Methods

The $\ell_1-\ell_2$ regularization is a popular nonconvex yet Lipschitz continuous metric, which has been widely used in signal and image processing. The theory for the $\ell_1-\ell_2$ minimization method shows that it has superior sparse recovery ...
Type-2 Fuzzy Logic System and Level Set
SKG '07: Proceedings of the Third International Conference on Semantics, Knowledge and Grid

The basic theory of a type-2 Fuzzy Logic Systems (FLSs) is presented, an efficient and simplified method to convert a type-2 fuzzy to a crisp result in a type-2 FLS is proposed, which is a straightforward way for the liberation of computation complexity,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '93: Proceedings of the 30th international Design Automation Conference

July 1993

768 pages

ISBN:0897915771

DOI:10.1145/157485

Chairman:
Alfred E. Dunlop
AT&T Bell Labs., Murray Hill, NJ

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: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC93

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC93: The 30th ACM/IEEE Design Automation Conference

June 14 - 18, 1993

Texas, Dallas, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

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

32
Total Citations
View Citations
430
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lin CTam KKo CYen HWei SChen YWang C(2020)A Dynamic Expansion Order Algorithm for the SAT-based Minimization2020 IEEE 33rd International System-on-Chip Conference (SOCC)10.1109/SOCC49529.2020.9524758(271-276)Online publication date: 8-Sep-2020
https://doi.org/10.1109/SOCC49529.2020.9524758
Lee TWu CLin CChen YWang C(2018)Logic optimization with considering boolean relations2018 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE.2018.8342109(761-766)Online publication date: Mar-2018
https://doi.org/10.23919/DATE.2018.8342109
Khatri SShenoy NGiomi JKhouja A(2016)Logic SynthesisElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-4(27-55)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-4
Wiśniewski RStefanowicz ŁBazydło GWęgrzyn M(2015)Application of Hypergraphs in the Prime Implicants Selection ProcessIFAC-PapersOnLine10.1016/j.ifacol.2015.07.05148:4(302-305)Online publication date: 2015
https://doi.org/10.1016/j.ifacol.2015.07.051
Iwane HHiguchi HAnai H(2013)An Effective Implementation of a Special Quantifier Elimination for a Sign Definite Condition by Logical Formula SimplificationProceedings of the 15th International Workshop on Computer Algebra in Scientific Computing - Volume 813610.1007/978-3-319-02297-0_17(194-208)Online publication date: 9-Sep-2013
https://dl.acm.org/doi/10.1007/978-3-319-02297-0_17
Domis DTrapp M(2009)Component-Based Abstraction in Fault Tree AnalysisProceedings of the 28th International Conference on Computer Safety, Reliability, and Security10.1007/978-3-642-04468-7_24(297-310)Online publication date: 3-Sep-2009
https://dl.acm.org/doi/10.1007/978-3-642-04468-7_24
Minato SArimura H(2007)Frequent Closed Item Set Mining Based on Zero-suppressed BDDsTransactions of the Japanese Society for Artificial Intelligence10.1527/tjsai.22.16522(165-172)Online publication date: 2007
https://doi.org/10.1527/tjsai.22.165
Minato SArimura H(2007)Frequent Pattern Mining and Knowledge Indexing Based on Zero-Suppressed BDDsKnowledge Discovery in Inductive Databases10.1007/978-3-540-75549-4_10(152-169)Online publication date: 2007
https://doi.org/10.1007/978-3-540-75549-4_10
Minato SArimura H(2006)Frequent pattern mining and knowledge indexing based on zero-suppressed BDDsProceedings of the 5th international conference on Knowledge discovery in inductive databases10.5555/1777194.1777206(152-169)Online publication date: 18-Sep-2006
https://dl.acm.org/doi/10.5555/1777194.1777206
Bernd Wurth (2006)Functional Multiple-Output Decomposition: Theory and an Implicit Algorithm32nd Design Automation Conference10.1109/DAC.1995.250063(54-59)Online publication date: Dec-2006
https://doi.org/10.1109/DAC.1995.250063
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

Two-level ℓ₁minimization for compressed sensing

New Restricted Isometry Property Analysis for $\ell_1-\ell_2$ Minimization Methods

Type-2 Fuzzy Logic System and Level Set