Combinational equivalence checking for threshold logic circuits

Tejaswi Gowda, Sarma Vrudhula, Goran Konjevod

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationGLSVLSI'07
Subtitle of host publicationProceedings of the 2007 ACM Great Lakes Symposium on VLSI
Number of pages6
StatePublished - 2007
Event17th Great Lakes Symposium on VLSI, GLSVLSI'07 - Stresa-Lago Maggiore, Italy
Duration: Mar 11 2007Mar 13 2007

Publication series

NameProceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI


Other17th Great Lakes Symposium on VLSI, GLSVLSI'07
CityStresa-Lago Maggiore


  • EDA
  • Equivalence checking
  • Nano devices
  • Threshold logic

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Combinational equivalence checking for threshold logic circuits'. Together they form a unique fingerprint.

Cite this