Analytic approaches to the collapse operation and equivalence verification of threshold logic circuits
- 7 November 2016
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the 35th International Conference on Computer-Aided Design
Abstract
Threshold logic circuits gain increasing attention due to their feasible realization with emerging technologies and strong bind to neural network applications. In this paper, for logic synthesis we formulate the fundamental operation of collapsing threshold logic gates, not addressed by prior efforts. A necessary and sufficient condition of collapsibility is obtained for linear combination of two threshold logic gates, and an analytic approach is proposed for fast circuit transformation. On the other hand, for equivalence verification we propose a linear time translation from threshold logic circuits to pseudo-Boolean constraints, in contrast to prior exponential translation costs. Experimental results demonstrate the effectiveness of circuit transformation by the collapse operation and the memory efficiency of equivalence verification by our pseudo-Boolean translation.Keywords
This publication has 18 references indexed in Scilit:
- A million spiking-neuron integrated circuit with a scalable communication network and interfaceScience, 2014
- Spintronic Threshold Logic Array (STLA)—A compact, low leakage, non-volatile gate array architectureJournal of Parallel and Distributed Computing, 2014
- Improved Threshold Logic Synthesis Using Implicant-Implicit AlgorithmsACM Journal on Emerging Technologies in Computing Systems, 2014
- An efficient heuristic to identify threshold logic functionsACM Journal on Emerging Technologies in Computing Systems, 2012
- SAT-based equivalence checking of threshold logic designs for nanotechnologiesPublished by Association for Computing Machinery (ACM) ,2008
- Synthesis of threshold logic circuits using tree matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Synthesis and optimization of threshold logic networks with application to nanotechnologiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- VLSI implementations of threshold logic- a comprehensive surveyIEEE Transactions on Neural Networks, 2003
- Equivalence checking of combinational circuits using Boolean expression diagramsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999
- On the Complexity of Derivation in Propositional CalculusPublished by Springer Science and Business Media LLC ,1983