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

Combinational equivalence checking for threshold logic circuits

Published: 11 March 2007 Publication History

Abstract

Threshold logic is gaining prominence as an alternative to Boolean logic. The main reason for this trend is the availability of devices that implement these circuits efficiently (current mode, differential mode circuits), as well as the promise they hold for the future nanoalldevices (RTDs, SETs, QCAs and other nano devices). This has generated renewed interest in the design automation community to design efficient CAD tools for threshold logic. Recently a lot of work has been done to synthesize threshold logic circuits. So far there has been no efficient method to verify the synthesized circuits. In this work we address the problem of combinational equivalence checking for threshold circuits. We propose a new algorithm, to obtain compact functional representation of threshold elements. We give the proof of correctness, and analyze its runtime complexity. We use this polynomial time algorithm to develop a new methodology to verify threshold circuits. We report the result of our experiments, comparing the proposed methodology to the naive approach. We get up to 189X improvement in the run time (23X on average), and could verify circuits that the naive approach could not.

References

[1]
M. Avedillo and J. Quintana. A Threshold Logic Synthesis Tool for RTD Circuits. In Euromicro Symposium on Digital System Design, 2004.
[2]
V. Beiu et al. VLSI implementations of threshold logic-a comprehensive survey. In IEEE Transactions on Neural Networks, volume 14, 2003.
[3]
Y. Beiu et al. Differential Implementations of Threshold Logic Gates. In Proceedings of the IEEE.
[4]
S. Bobba and I. Hajj. Current-Mode Threshold Logic Gates. In Proc. of ICCD, 2000.
[5]
D. Brand. Verification of Large Synthesized Designs. In Proc. ICCAD, 1993.
[6]
R. E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. In IEEE Transactions on Computers, volume 35, 1986.
[7]
M. Dertouzos. Threshold Logic : A Synthesis Approach. The MIT Press, 1965.
[8]
G. D. Hachtel and F. Somenzi. Logic Synthesis and Verification Algorithms. Boston: KAP, 1996.
[9]
H. Hulgaard et al. Equivalence Checking of Combinational Circuits using Boolean Expression Diagrams. In IEEE Transactions on CAD, July 1999.
[10]
J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.
[11]
Z. Kohavi. Switching and Finite Automata Theory. New York: McGraw-Hill Book Company, 1970.
[12]
A. Kuehlmann and F. Krohm. Equivalence Checking Using Cuts and Heaps. In Proc. of DAC, 1997.
[13]
A. Kuehlmann and C. A. van Eijk. Logic Synthesis and Verification, chapter Combinational and Sequential Equivalence Checking. KAP, 2001.
[14]
W. Kunz and D. Pradhan. Recursive Learning: A New Implication Technique for Efficient Solution to CAD Problems-- Test, Verification and Optimization. In IEEE Transactions on CAD, 1994.
[15]
S. Muroga. Threshold Logic and Its Applications. New York: WILEY-INTERSCIENCE, 1971.
[16]
S. K. Shukla and I. R. Bahar. Nano, Quantum and Molecular Computing. KAP, Norwell, MA, USA, 2004.
[17]
P. F. Williams, H. Hulgaard, and H. R. Andersen. Boolean Expression Diagram Tool - Version 2.5.
[18]
L. Zhang. Threshold Logic Network Synthesis Suite. Master's thesis, Delft University of Technology, 2005.
[19]
R. Zhang et al. Threshold Network Synthesis and Optimization and Its Application to Nanotechnologies. In IEEE Transactions on CAD, January 2005.

Cited By

View all
  • (2021)Constraint Solving for Synthesis and Verification of Threshold Logic CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.301544140:5(904-917)Online publication date: May-2021
  • (2019)Optimization of Threshold Logic Networks with Node Merging and Wire ReplacementACM Transactions on Design Automation of Electronic Systems10.1145/335874824:6(1-18)Online publication date: 14-Oct-2019
  • (2019)Majority Logic: Prime Implicants and n-Input Majority Term Equivalence2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID)10.1109/VLSID.2019.00098(464-469)Online publication date: Jan-2019
  • Show More Cited By

Index Terms

  1. Combinational equivalence checking for threshold logic circuits

    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. EDA
    2. equivalence checking
    3. nano devices
    4. threshold logic

    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

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Constraint Solving for Synthesis and Verification of Threshold Logic CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2020.301544140:5(904-917)Online publication date: May-2021
    • (2019)Optimization of Threshold Logic Networks with Node Merging and Wire ReplacementACM Transactions on Design Automation of Electronic Systems10.1145/335874824:6(1-18)Online publication date: 14-Oct-2019
    • (2019)Majority Logic: Prime Implicants and n-Input Majority Term Equivalence2019 32nd International Conference on VLSI Design and 2019 18th International Conference on Embedded Systems (VLSID)10.1109/VLSID.2019.00098(464-469)Online publication date: Jan-2019
    • (2019)Equivalence Checking and Compaction of n-input Majority Terms Using Implicants of MajorityJournal of Electronic Testing10.1007/s10836-019-05831-xOnline publication date: 30-Nov-2019
    • (2018)Identifying a Probabilistic Boolean Threshold Network From SamplesIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2017.264803929:4(869-881)Online publication date: Apr-2018
    • (2018)Reconfigurable arithmetic logic unit designed with threshold logic gatesIET Circuits, Devices & Systems10.1049/iet-cds.2018.004613:1(21-30)Online publication date: 24-May-2018
    • (2017)In&Out: Restructuring for threshold logic network optimization2017 18th International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2017.7918351(413-418)Online publication date: Mar-2017
    • (2015)Synthesis for Width Minimization in the Single-Electron Transistor ArrayIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2014.238633123:12(2862-2875)Online publication date: Dec-2015
    • (2015)Comparative power-delay performance analysis of threshold logic technologies5th International Conference on Energy Aware Computing Systems & Applications10.1109/ICEAC.2015.7352166(1-4)Online publication date: Mar-2015
    • (2014)Rewiring for threshold logic circuit minimizationProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2616754(1-6)Online publication date: 24-Mar-2014
    • Show More Cited By

    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