Novel Methods for Efficient Realization of Logic Functions Using Switching Lattices

Levent Aksoy*, Mustafa Altun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Two-dimensional switching lattices including four-terminal switches are introduced as alternative structures to realize logic functions, aiming to outperform the designs consisting of one-dimensional two-terminal switches. Exact and approximate algorithms have been proposed for the problem of finding a switching lattice which implements a given logic function and has the minimum size, i.e., a minimum number of switches. In this article, we present an approximate algorithm, called janus, that explores the search space in a dichotomic search manner. It iteratively checks if the target function can be realized using a given lattice candidate, which is formalized as a satisfiability (SAT) problem. As the lattice size and the number of literals and products in the given target function increase, the size of a SAT problem grows dramatically, increasing the run-time of a SAT solver. To handle the instances that janus cannot cope with, we introduce a divide and conquer method called medea. It partitions the target function into smaller sub-functions, finds the realizations of these sub-functions on switching lattices using janus, and explores alternative realizations of these sub-functions which may reduce the size of the final lattice. Moreover, we describe the realization of multiple functions in a single lattice. Experimental results show that janus can find better solutions than the existing approximate algorithms, even than the exact algorithm which cannot determine a minimum solution in a given time limit. On the other hand, medea can find better solutions on relatively large size instances using a little computational effort when compared to the previously proposed algorithms. Moreover, on instances that the existing methods cannot handle, medea can easily find a solution which is significantly better than the available solutions.

Original languageEnglish
Article number8889423
Pages (from-to)427-440
Number of pages14
JournalIEEE Transactions on Computers
Issue number3
Publication statusPublished - 1 Mar 2020

Bibliographical note

Publisher Copyright:
© 1968-2012 IEEE.


This work is part of a project that has received funding from the European Union’s H2020 research and innovation programme under the Marie Sk»odowska-Curie grant agreement No 691178, and supported by the TUBITAK-Career project #113E760 and TUBITAK-NSF project #218E068. The authors would like to thank Luca Frontini for providing the sub-functions of logic functions used in this article which are obtained using the decomposition algorithm mentioned in [16].

FundersFunder number
Horizon 2020 Framework Programme113E760, 691178


    • Binary search
    • emerging technologies
    • four-terminal switch
    • logic synthesis
    • satisfiability
    • switching lattice


    Dive into the research topics of 'Novel Methods for Efficient Realization of Logic Functions Using Switching Lattices'. Together they form a unique fingerprint.

    Cite this