Majority Logic Synthesis Based on Nauty Algorithm - Field-Coupled Nanocomputing: Paradigms, Progress, and Perspectives - page 109

Majority Logic Synthesis
Based on Nauty Algorithm

Peng Wang 1 , Mohammed Niamat 1 , and Srinivasa Vemuru 2( & )

1

Department of Electrical Engineering and Computer Science,
University of Toledo, Toledo, OH 43606, USA
[e-mail],
[e-mail]

2

Department of Electrical and Computer Engineering and Computer Science,
Ohio Northern University, Ada, OH 45810, USA
[e-mail]

Abstract. Quantum-dot Cellular Automata (QCA) based on majority logic is a
promising technology for implementation of future integrated circuits.
However, the current majority logic synthesis approaches based on three-fea-
sible networks often lead to inefficient QCA circuit implementations. In this
work, four-feasible networks are used as the starting point; therefore each node
in the network can accommodate one extra variable. Using the Nauty algo-
rithm, 222 standard functions along with their majority gate mapping are
identified for Boolean logic functions with up to four-variables. In addition, all
redundancies in the synthesized results are eliminated to reduce the size of the
QCA circuit implementations. The proposed method leads to an average
reduction of 7.94 % in terms of levels of logic and 8.13 % in terms of gates for
the 24 Microelectronics Center of North Carolina (MCNC) benchmarks as
compared to other methods.

Keywords: Majority logic synthesis Quantum-dot cellular automata

(QCA) Nauty algorithm

1 Introduction

The feature size of the Complementary Metal Oxide Semiconductor (CMOS) com-
ponents has been continuously reducing for the past five decades. However, this trend
encounters serious difficulties as the fundamental physical limits of CMOS are quickly
approached [ 1 ]. Fortunately, many new nanoscale devices have been developed, such
as Quantum-dot Cellular Automata (QCA) [ 2 - 5 ], Single Electron Tunneling (SET)
[ 6 , 7 ] and Tunneling Phase Logic (TPL) [ 8 ]. While a lot of effort has already been put
into understanding and developing new nanoscale devices, research efforts on logic
synthesis techniques are also needed to fully utilize the potential of these new
technologies.
CMOS technology uses NAND, NOR, NOT, and other functions as the basic
logic units, whereas these new technologies are based on either majority or minority
logic. For example, QCA uses majority logic, SET uses both majority and minority