Logic synthesis for switching lattices

Mustafa Altun, Marc D. Riedel

Research output: Contribution to journalArticle

28 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 - Oct 16 2012


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

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

  • Cite this