A Simple and Effective Heuristic Method for Threshold Logic Identification

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 2018-05, Vol.37 (5), p.1023-1036
• Main Authors: Neutzling, Augusto, Martins, Mayler G. A., Callegaro, Vinicius, Reis, Andre I., Ribas, Renato P.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Digital circuit; Heuristic algorithms; Integrated circuit reliability; linear separable function; Logic functions; Logic gates; threshold functions; threshold logic gate; threshold logic identification
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/TCAD.2017.2729403

In this paper, a straightforward and effective method to identify threshold logic function (TLF) is presented. Threshold logic is a promising alternative to conventional Boolean logic due to its suitability for emerging technologies, like memristors, quantum-dot cellular automata, resonant tunneling device, and spintronic devices. Identification and synthesis of TLF are essential tasks in a design flow based on such a logic strategy. The proposed method relies on irredundant sum-of-products Boolean function description form and exploits both ordering of variables and system of inequalities to assign the variable weights and the function threshold value. This is the first heuristic algorithm able to identify all threshold functions with up to six variables, being also more effective than other heuristic methods for functions with a larger number of variables. For functions obtained from {k} -cuts of benchmark circuits, experimental results demonstrated effectiveness near to 100% when compared to exact methods, even when the number of function variables increases. The execution time of the proposed approach is similar to related heuristic methods, being faster than integer linear programming-based algorithms.