A Comprehensive Technique for Majority/Minority Logic Synthesis with Applications in Nanotechnology

by Peng Wang

Institution: University of Toledo
Department: Electrical Engineering
Degree: PhD
Year: 2014
Keywords: Electrical Engineering
Record ID: 2044968
Full text PDF: http://rave.ohiolink.edu/etdc/view?acc_num=toledo1387934672


In the past few decades, the semiconductor industry has been able to keep up with Moore’s Law by scaling down the feature size of Complementary Metal-Oxide Semiconductor (CMOS) components. However, attempts at further scaling down the feature sizes face many hurdles due to the fundamental physical limits of CMOS technology. For example, as gate lengths are reduced below 10 nm, quantum effects are likely to dominate the performance of the device, resulting in increased gate leakage current, capacitive coupling, electro-migration failures, doping fluctuations and increased difficulties in lithography. Alternative technologies such as Quantum-dot Cellular Automata (QCA), Single Electron Tunneling (SET) and Tunneling Phase Logic (TPL) are being considered as possible replacements for CMOS. Unlike CMOS technology which uses “NAND/NOR/NOT” gates to implement circuits, QCA uses majority logic, SET uses both majority and minority logic, and TPL uses minority logic. In this work, QCA technology and its majority logic basis are used to explain the proposed method. Research in majority logic synthesis started decades ago. Reduced-unitized-tables, K-maps, and Shannon’s decomposition principles were employed for majority logic synthesis. However, these methods were only appropriate for small networks since they were used to solve the problem manually. A recent majority logic synthesis method, which uses geometric interpretation of Boolean functions, lead to thirteen standard functions. However, these functions are capable of solving only three-variable problems. More practical methods, which can deal with Boolean logic functions with any number of variables, have also been proposed. The main idea of these synthesis methods is to first decompose the Boolean logic network to three-feasible networks (each node in a three-feasible network contains three or fewer inputs), and then convert each node to a corresponding majority expression. However, these methods cannot take full advantage of all the three inputs of a majority gate, thus they are not efficient enough to obtain optimal majority expressions.In this work, we develop new decomposition methods to obtain four-feasible networks in which each node can accommodate one extra variable and lead to simpler synthesized results. We propose the concepts of primitives and standard functions for four-variable problems based on graph theory, which can be applied to majority logic synthesis. Also, an efficient algorithm to find the minimal majority gate mapping, along with a Majority expression Look-Up Table (MLUT) is developed. All redundancies in the synthesized results are removed, thus reducing the size of the circuit. From the optimal majority network, the minority network can easily be obtained by applying the De Morgan’s theorem. In summary, a comprehensive majority/minority logic synthesis technique is proposed that results in fewer majority gates and fewer levels than previous methods. For the 40 MCNC benchmark circuits considered, the proposed technique, on an average, reduces the…