skip to main content
10.1145/1228784.1228889acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

An efficient cost-based canonical form for Boolean matching

Published: 11 March 2007 Publication History

Abstract

In this paper, we present new canonical forms for P, NP and NPN equivalence relations on boolean functions. The canonical forms are based on the minimization of a cost function. With respect to previous approaches based on cost minimization, our function allows the minimization algorithm to explore a reduced solution space. This reduction is obtained by partitioning the columns of the boolean function through an equivalence relation. NP and NPN canonical forms are obtained by means of a preprocessing step of negligible computational overhead.

References

[1]
Afshin Abdollahi and Massoud Pedram. A new canonical form for fast boolean matching in logic synthesis and verification. In DAC'05: Proceedings of the 42nd annual conference on Design automation, pages 379--384, New York, NY, USA, 2005. ACM Press.
[2]
K. Beauchamp. Applications of Walsh and Related Functions. Academic Press, 1984.
[3]
Luca Benini and Giovanni De Micheli. A survey of boolean matching techniques for library binding. ACM Trans. Des. Autom. Electron. Syst., 2(3):193--226, 1997.
[4]
Jerry R. Burch and David E. Long. Efficient boolean function matching. In ICCAD '92: Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, pages 408--411, Los Alamitos, CA, USA, 1992. IEEE Computer Society Press.
[5]
Jovanka Ciric and Carl Sechen. Efficient canonical form for boolean matching of complex functions in large libraries. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 22(5):535--544, May 2003.
[6]
Janett Mohnke, Paul Molitor, and Sharad Malik. Limits of using signatures for permutation independent boolean comparison. In ASP-DAC '95: Proceedings of the 1995 conference on Asia Pacific design automation (CD-ROM), page 74, New York, NY, USA, 1995. ACM Press.

Index Terms

  1. An efficient cost-based canonical form for Boolean matching

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI
    March 2007
    626 pages
    ISBN:9781595936059
    DOI:10.1145/1228784
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 11 March 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. boolean matching
    2. logic sinthesys
    3. technology mapping

    Qualifiers

    • Article

    Conference

    GLSVLSI07
    Sponsor:
    GLSVLSI07: Great Lakes Symposium on VLSI 2007
    March 11 - 13, 2007
    Stresa-Lago Maggiore, Italy

    Acceptance Rates

    Overall Acceptance Rate 312 of 1,156 submissions, 27%

    Upcoming Conference

    GLSVLSI '25
    Great Lakes Symposium on VLSI 2025
    June 30 - July 2, 2025
    New Orleans , LA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 111
      Total Downloads
    • Downloads (Last 12 months)0
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media