Logic synthesis for networks of four-terminal switches.

Loading...

View/Download File

Altun_umn_0130E_12700.pdf (1.46 MB)

Persistent link to this item

https://hdl.handle.net/11299/127424

Statistics

View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Logic synthesis for networks of four-terminal switches.

Authors

Altun, Mustafa

Published Date

2012-05

Publisher

Type

Thesis or Dissertation

Abstract

We develop a synthesis method to implement Boolean functions with lattices of four-terminal switches. Each switch is controlled by a Boolean literal. We address the synthesis problem of how best to assign literals to switches in a lattice in order to implement a given target Boolean function, with the goal of minimizing the lattice size, measured in terms of the number of switches. We present an efficient algorithm for this task. The algorithm has polynomial time complexity. It produces lattices with a size that grows linearly with the number of products of the target Boolean function. We evaluate our synthesis method on standard benchmark circuits and compare the results to a lower-bound calculation on the lattice size. Although not tied to any particular technology, we comment that our synthesis results are applicable to emerging technologies such as nanowire crossbar arrays and magnetic switch-based structures. We address the problem of implementing Boolean functions with lattices of four-terminal switches in the presence of defects. We assume that such defects occur probabilistically. Our approach is predicated on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly. A significant tangent for this work is its mathematical contribution: lattice-based implementations present a novel view of the properties of Boolean function duality. We study the applicability of these properties to the famous problem of testing whether two monotone Boolean functions in irredundant sum-of-products form are dual. This is one of the few problems in circuit complexity whose precise tractability status is unknown.

Keywords

Defect tolerance

Emerging technologies

Four terminal switch

Lattice duality

Electrical/Computer Engineering

Description

University of Minnesota Ph.D. dissertation. May 2012. Major:Electrical/Computer Engineering. Advisor: Marc D. Riedel. 1 computer file (PDF): ix, 98 pages.

Related to

Replaces

License

Collections

Dissertations

Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Altun, Mustafa. (2012). Logic synthesis for networks of four-terminal switches.. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/127424.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.