Logic synthesis for switching lattices

Mustafa Altun, Marc D. Riedel

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


This paper studies the implementation of Boolean functions by lattices of four-terminal switches. Each switch is controlled by a Boolean literal. If the literal takes the value 1, the corresponding switch is connected to its four neighbors; else it is not connected. A Boolean function is implemented in terms of connectivity across the lattice: it evaluates to 1 iff there exists a connected path between two opposing edges of the lattice. The paper addresses the following synthesis problem: how should one assign literals to switches in a lattice in order to implement a given target Boolean function? The goal is to minimize the lattice size, measured in terms of the number of switches. An efficient algorithm for this task is presented-one that does not exhaustively enumerate paths but rather exploits the concept of Boolean function duality. The algorithm produces lattices with a size that grows linearly with the number of products of the target Boolean function in ISOP form. It runs in time that grows polynomially. Synthesis trials are performed on standard benchmark circuits. The synthesis results are compared to a lower-bound calculation on the lattice size.

Original languageEnglish (US)
Article number6311385
Pages (from-to)1588-1600
Number of pages13
JournalIEEE Transactions on Computers
Issue number11
StatePublished - 2012

Bibliographical note

Funding Information:
The authors would like to thank Ivo Rosenberg for his contributions. A preliminary version of this paper appeared in [1]. This work is supported by US National Science Foundation (NSF) CAREER award #0845650.


  • Boolean functions
  • lattices
  • nanowire crossbar arrays
  • switching circuits


Dive into the research topics of 'Logic synthesis for switching lattices'. Together they form a unique fingerprint.

Cite this