Quantum Cellular Automata (QCA) is a nanotechnology that has recently been recognized as one of the top six emerging technologies with potential applications in future computers (Wilson et al., 2002) (Islamshah et al., 2000). It has gained significant popularity in recent years. This is mainly due to rising interest in creating computing devices and implementing any logical function with that. The basic building block of QCA circuit is majority gate; hence, efficiently constructing QCA circuits using majority gates has attracted a lot of attentions (Zhang et al., 2005a). Several studies have reported that QCA can be used to design general purpose computational and memory circuits (Berzon and Fountain, 1998). QCA is expected to achieve high device density, very high clock frequency and extremely low power consumption (Islamshah et al., 2000).
In recent years the development of integrated circuits has been essentially based on scaling down that is, increasing the element density on the wafer. Scaling down of complementary metal oxide semiconductor CMOS circuits, however, has its limits. Above a certain element density various physical phenomena, including quantum effects, conspire to make transistor operation difficult if not impossible. If a new technology is to be created for devices of nanometer scale, new design principles are necessary. One promising approach is to move to a transistor-less cellular architecture based on interacting quantum dots, quantum-dot cellular automata QCA (Amlani et al., 1999; Lent et al., 1993a).
At this time, it is unclear whether or not this technology will replace such a firmly embedded technology as CMOS, but investigations into modeling and design have demonstrated that QCA has many powerful features some of which are not available in CMOS (Tougaw and Lent, 1994; Porod, 1997). Although many fabrication challenges have still to be overcome (Islamshah et al., 2000), the simple design nature of QCA makes it attractive for investigation of new circuit topologies (Vetteth et al., 2002). QCA topologies are not simple translations of standard circuit layouts; new ideas for translating standard logic units into QCA are needed.
One of the interesting features of QCA is that there is no fixed connection strategy and hence, it should be possible to apply optimization algorithms such as genetic algorithms to minimize the number of cells in a design. In (Bonyadi et al., 2007) a logic optimization method is introduced and hardware saving using genetic algorithm is performed.
As it mentioned, the basic building block of QCA circuit is majority gate,
hence, efficiently constructing QCA circuits using majority gates has attracted
a lot of attentions (Zhang et al., 2004, 2005a). Related study goes back
to 1960s (Akers, 1962). In implementation of any logical function with majority,
instead of using Boolean logic operators (AND, OR and their complements), majority
logic represents and manipulates digital functions on the basis of majority
decision (Oya et al., 2003). Traditional logic reduction methods such
as Karnaugh maps (K-maps) always produce simplified expressions in the two standard
forms: Sum of Products (SOP) or Product of Sums (POS). Moreover, we will encounter
difficulties in converting these two forms into majority expressions due to
the complexity of multilevel majority gates. In CMOS/silicon design, the logic
circuits are usually implemented using AND and OR gates based on SOP or POS
formats. However, since QCA logic is based on a majority gate primitive, it
is critical that an efficient technique be established for designing with this
primitive (Zhang et al., 2004).
In this study, we propose another possible design for majority gates resulting in a novel scheme for QCA cells, to facilitate simplifying logical functions. By applying this form of majority gate, we can simplify logical functions and achieve improved results. For example a 1-bit QCA adder is constructed only with three gates (two different forms of majority gates and only one inverter). In comparison to other existing implementation this method has demonstrated interesting results. Beside, some Boolean functions are expressed as examples and it has been shown, how our reduction method by applying new proposed item, decreases gate counts and levels. We will show and discuss that using of the proposed items can be efficient in designing majority gate based circuits. Furthermore, we will discuss the construction of primitive components for circuit designing in QCA technology such as QCA wire, majority gate and inverter using this novel form of quantum cell.
MATERIALS AND METHODS
Quantum cells: Quantum Cellular Automata is a new device architecture which is amenable to the nanometer scale (Lent and Tougaw, 1993). The principle of quantum cellular automata was first proposed by Lent et al. (1993a). In order to implement a system that encodes information in the form of electron position it becomes necessary to construct a vessel in which an electron can be trapped and counted as there or not there. A quantum dot does just this by establishing a region of low potential surrounded by a ring of high potential. In other Words, QCA stores logic states not as voltage levels, but based on the position of individual electrons (Tougaw and Lent, 1994).
In ordinary form, QCA technology is based on the interaction of bi-stable QCA
cells constructed from four quantum dots. A schematic of a basic cell is shown
in Fig. 1a. The cell is charged with two free electrons, which
are able to tunnel between adjacent dots. These electrons tend to occupy antipodal
sites as a result of their mutual electrostatic repulsion. Thus, there exist
two equivalent energetically minimal arrangements of the two electrons in the
QCA cell, as shown in Fig. 1b and c. These
two arrangements are denoted as cell polarization. Binary information is encoded
in the charge configuration of the QCA cell to represent logic 1 and 0 (Zhang
et al., 2004).
Basic QCA cell and binary encoding. (a) Schematic of the
basic cell constructed from four quantum dots. Coulomb repulsion causes
the electrons to occupy antipodal sites within the cell. These two bit states
result in cell polarizations of (b) P = +1 (Binary 1) and (c) P = -1(Binary
As mentioned earlier, Coulomb repulsion causes the electrons to occupy antipodal
sites, the ground state charge distribution may have the electrons aligned along
either of the two diagonal axes shown in Fig. 1b and
c. In (Tougaw and Lent, 1994) the cell polarization has been defined, a
quantity which measures the extent to which the charge distribution is aligned
along one of these axes. The polarization is defined by Eq. 1.
Where, ρi denotes the electronic charge at dot i. With respect
to this equation, electrons exactly localized on sites two and four will result
in P = +1, while electrons on sites one and three yield P = -1. In next section,
we use similar expression for our approach presentation. In (Tougaw and Lent,
1994), the standard cell parameters have been discussed. And a simple model
of the standard quantum cell has been employed, representing the quantum dots
as sites and ignoring any degrees of freedom internal to the dot. Moreover,
a second-quantized Hubbard-type Hamiltonian in the basis of two-particle site
kits for this model has been used. Finally, a function for calculating cell-cell
response has been expressed, because for using of cellular automata type architectures,
the state of a cell must be strongly influenced by the states of neighboring
The concept of a QCA cell is generic in that it can be implemented in several
different ways and there have been proposals for: semiconductor Implementation,
molecular implementation and magnetic implementation. Each of these implementations
has certain advantages and disadvantages.
Micro-sized QCA devices have been fabricated with metal cells which operate at 50 mK (Orlov et al., 1997) (i.e., cryogenic). In terms of feature size, a QCA cell of few nanometers has been fabricated through a molecular implementation by a self-assembly process. The study in Orlov et al. (1997) reported an experimental demonstration of a metal QCA cell; such a device consists of four metal dots connected with tunnel junctions and capacitors. Experiments have confirmed that switching of a single electron in a double-dot cell can control the position of a single electron in another double-dot cell.
Different devices and circuits have been proposed for QCA implementation. These include a carry look-ahead adder, a barrel shifter, microprocessors and Field-Programmable Gate Arrays (FPGAs) (Vetteth et al., 2002; Frost et al., 2002; Niemier et al., 2002; Walus et al., 2003).
Moreover, one of the important features in the QCA architecture is clocking scheme. Signal propagation is accomplished along serial timing zones using the one-dimensional (1-D) technique of Lent and Tougaw (1997). This 1-D arrangement results from the four phases required for correctly operating the QCA cells. A trapezoid clocking scheme has been proposed in (Niemier and Kogge, 2001) to provide feedback paths, while generating processing-in-wire capabilities of QCA designs. As shown in Lent and Tougaw (1997), QCA has many desirable features for processing; clocking and timing can be adjusted as functions of the cells in a Cartesian layout with low power (power gain has been demonstrated by clocking of the cells), high density and regularity.
Nanoelectronic Circuits based on three-input majority gates and inverters:
Any QCA circuit can be efficiently built using only majority gates and inverters.
As shown in Fig. 2a, an ordinary QCA gate implementing the
majority function is as follows.
Assuming the inputs are A, B and C, the logic function of a majority gate is
shown in Eq. 2.
Beside, truth table of a three-input majority gate is shown in Table
1. As illustrated in Fig. 2a and b each
QCA majority gate in normal form requires only five QCA cells. And every QCA
inverter gate can be implemented by 11 quantum cells. Unlike conventional CMOS,
in which the inverter is the simplest block, its gate-level implementation consumes
a considerable area in QCA.
Primitive components. (a) A QCA majority gate. The states
of the center and right cells are always the same as the state of the majority
of the three input neighbors and (b) A QCA inverter. The signal comes in
from the left, splits into two parallel wires and is inverted at the point
|| Truth table of a three-input majority gate
The binary wire and inverter chain act as interconnect in the QCA. As it is
shown in Eq. 3a and b, for generating
an AND gate or an OR gate with majority we can fix the polarization of one input
to a constant logic 0 or logic 1. Hence, QCA circuit is based on majority gate-based
circuits instead of AND/OR/Inverter gate-based circuits (Zhang et al.,
2005; Gergel et al., 2003).
Other important component in QCA designing is wire. In a QCA wire, the binary
signal propagates from input to output because of the electrostatic interactions
between cells. Since the polarization of each cell tends to align with that
of its neighbors, a linear arrangement of standard cells can be used to transmit
binary information from one point to another. In this wire, all of free cells
align in the same direction as the driving cell (input cell), so the information
contained in the state of the input is transmitted down the wire. Beside, the
distance between dots and between cells is a key parameter giving Coulomb effect
in QCA application in conventional form (Lent et al., 1993b) (Fig.
|| QCA wire. The binary signal propagates from input to output
because of the electrostatic interactions between cells
|| Truth table of a five-input majority gate based on sum of
Moreover in a QCA wire, all of the computational power is provided by
the Coulomb interaction between cells and there is no electrical current flow
between cells and hence no power dissipation.
Five-input majority gate and novel design for QCA cell: A five pins
majority gate must have five inputs and one output. A truth table of a five-input
majority gate based on sum of inputs is shown in Table 2.
In ordinary form of QCA cells, a cell can take effect from three around sides
(bottom, up and left) and out the result function from another side (right).
Hence this form of cell is proper for three-input majority implementation, but
for a five-input majority gate we need a different design of cells, that can
affect from five sides and transmit its polarization from another side. Hence
we need to have a new structure in QCA cells including five inputs and one output.
A new scheme for QCA cells is presented here. In the proposed design a QCA cell
is a structure comprised of eight quantum-dots arranged in a cube pattern as
shown in Fig. 4. We propose this structure for compatibility
with five pins majority gate.
As mentioned, QCA uses the positions of electrons in quantum dots to represent
binary values 0 and 1. In the proposed design, we have the same conditions.
Figure 5 shows a QCA cell with eight quantum dots. Four electrons
occupy each cell. Each electron is free to tunnel between dots within one cell,
but cannot leave the cell. The four electrons within each cell repel each other
to diagonally opposite corners of the cell. This leaves only two stable states
for each cell. These two states are used to represent logic values.
As shown in Fig. 5, in present design we determine every
corner and thus every quantum dot with a number, which is between one up to
eight. The occupation of dots in the corners with numbers one, three, six and
eight represent logic 1, as shown in Fig. 5a. In this case,
the QCA cell is said to be polarized to +1.
Three cube QCA cell. Schematic of a novel QCA cell comprised
of eight quantum dots. Coulomb repulsion causes the electrons to occupy
antipodal sites within the cell
Binary encoding. The four electrons within each cell repel
each other to diagonally opposite corners of the cell. This leaves only
two stable states for each cell. (a) P = +1(Binary 1) and (b) P = -1(Binary
In Fig. 5b, similarly,the
occupation of two, four, five and seven dots represents logic 0. In this case,
the QCA cell is said to be polarized to -1.
Like ordinary form of QCA cells, in proposed form of QCA cells, an equation
for cell polarization can be defined as follows:
In Eq. 4, ρi denotes the electronic charge
at site i. The charge on each site can be calculated by finding the expectation
value of the number operator in the ground state. In this equation, electrons
completely localized on sites one, three, six and eight polarization result
in binary one (P = +1) and while electrons on sites two, four, five and seven
yield binary zero (P = -1). Beside, polarization can get a value between these
two complete polarization magnitudes. This kind of QCA cells has a similar treatment
to ordinary QCA cells. Hence, we can generalize all of the problems and questions
around that, to new QCA cell form.
|| QCA wire. The binary signal propagates from input to output
because of the electrostatic interactions between cells
In this new form of QCA cell, moreover we can have primitive components for
designing every function only with QCA cells. These components are QCA wire,
majority and inverter gates. These components in our approach can be explained
QCA wires: With respect to new design of QCA cells, QCA wires can be
represented as shown in Fig. 6. Adjacent QCA cells interact
in an attempt to settle to a ground state determined by the current state of
the inputs. Since the polarization of each cell tends to align with that of
its neighbors. This is most clear in the case of the QCA wire (Fig.
6). The polarization of the input cell is propagated down the wire, as a
result of the system attempting to settle to a ground state. Any cells along
the wire that are anti-polarized to the input would be at a higher energy level
and would soon settle to the correct ground state.
QCA inverter: Two standard cells in a diagonal orientation are geometrically
similar to two rotated cells in a horizontal orientation. For this reason, standard
cells in a diagonal orientation tend to align in opposite polarization directions
as in the inverter chain (Tougaw and Lent, 1994). Computation with QCA is accomplished
by designing QCA layouts, which exhibit the desired interaction of states. Consider
the arrangements in Fig. 7, demonstrating the QCA implementation
of an inverter. Similarly to ordinary QCA inverter, in this form we have 11
Five-input majority gate: Majority is a voter. In a new structure, a
majority gate can be implemented as shown in Fig. 8a. Polarization
of input cells are fixed and middle cell and out cell are free. Inputs from
five around cells affect on the middle cell and it determines polarization of
the output cell. This structure makes majority decision. The majority voting
logic function can be expressed in terms of fundamental Boolean operator as
QCA Inverter. The signal comes in from the left, splits into
two parallel wires and is inverted at the point of convergence. An inverter
gate can be implemented using 11 new proposed QCA cells
Majority gate (a) the states of the center and out cells
are always the same as the state of the majority of the five input neighbors
and (b) schematic symbol for the majority gate
A schematic symbol of a five pins majority gate is shown in Fig.
8b. We can implement a three-input AND gate and also a three-input OR gate
using this majority gate. These functions are shown in Eq. 6a
ONE BIT QCA FULL ADDER
Here, we will apply the proposed majority construction to design QCA full adder.
First, we present other implementations and then our design is presented.
|| One-bit QCA Adder with eight gates implemented in (Tougaw
and Lent, 1994). Five, three-input majority gate and three inverter gates
A 1-bit full adder is defined as follows: Inputs: Operand bits (A, B) and carry bit is shown as C. Outputs: Sum bit and carry out.
A QCA adder with eight gates: In a classic design in (Tougaw and Lent, 1994), a full adder with five, three-input majority gates and three inverters has been implemented. We can simplify this design and reduce one majority gate simply, for example we can replace M(A, B, ) with only . Thus, an easier form for this QCA adder can be implemented using four majority gates and three inverters.
It must be notified that in the following designs, a single bit full adder
is implemented using only inverter and majority gates, whereas in order to implement
the sum function based on AND and OR gates, the number of gates involved will
be increased (Fig. 9).
A QCA adder with five gates: In (Zhang et al., 2004) a method
for majority logic reduction for QCA circuits has been presented and another
form of QCA adder is expressed. The design is shown in Fig. 10
there are three majority gates and two inverters. Beside, this design has been
used in (Heumpil and Swartzlander, 2007), recently.
Layout of this full adder has four clocking zone. This layout is designed by
QCAdesigner and shown in Fig. 11. We successfully verified
the operation of FA using QCAdesigner simulator. Simulation results for this
full adder shown in Fig. 12. The first three curves represent
the input waveforms, here exhaustively tested. The next two represent the outputs
Sum and Cout or carry output. Notice that each time the Clock 0 goes low the
output cells get latched to some value P = -1 or P = 1. The first time the outputs
are latched they fall to a random polarization (in this case Sum = 1 and Cout
= 1) NOT determined by the inputs because the inputs have not had a chance to
propagate through the circuit yet.
|| One-bit QCA Adder with five gates implemented Zhang et
al. (2004). Three, three-input majority gates and two inverters
|| Layout of a one-bit QCA full adder. The different shades
of gray represent connections to the different clock phases
Therefore, the correct output is delayed
by one clock cycle with respect to the input.
A method for reducing the number of majority gates required for computing three
variable Boolean functions is developed to facilitate the conversion of sum-of-products
expression into QCA majority logic (Zhang et al., 2004). Thirteen standard
functions are introduced to represent all three variable Boolean functions and
the simplified majority expressions corresponding to these standard functions
||QCA designer simulation results for the full-adder shown above.
There is a one cycle delay between the time the inputs are set and when
the outputs reflect the addition of those particular inputs
One-bit QCA Adder with only three gates implemented using
our proposed method. One, five-input majority gate, one three-input majority
gate and one inverter
In this study a novel method for using these standard functions has been described
to convert the sum-of-products expression to majority logic. By applying this
method a considerable gate counts reduction will be achieved as illustrated
in Table 3.
A QCA adder only with three gates: In proposed design, we simplify the
QCA adder complexity and reduce the number of both majority gates and inverters.
In design the one bit full adder comprises only two majority gates and one inverter
||Comparison of QCA Adders. By applying the proposed method
a considerable gate counts reduction will be achieved
Beside, a new module is provided for simulating proposed QCA cell structures based on existing QCADesigner (Linux version) and verified proposed full adder QCA circuit. We have similar results, in simulating proposed circuit.
As noted above, proposed method represents a considerable reduction in gate
counts compared to the other existing methods (Tougaw and Lent, 1994; Zhang
et al., 2004) and retains the simple clocking scheme. This reduction
is shown in Table 3.
As is mentioned, the proposed item is very useful in circuit designing. In
so many cases the standard Boolean function can be simplified and we are able
to convert the Sum of Products expression to five- and three-input majority
based design. In the following some examples are demonstrated, in which some
three variables Boolean functions realized with Sum of Products are implemented
using the five- and three- input majority gates. These examples are presented
by Zhang et al. (2004), Zhi et al. (2006) and we compare their
approach to ours.
|| Majority expression of some three variable Boolean functions.
The proposed item in this paper can be very efficient in majority and inverter
gate counts reduction
|| Optimization results and comparison. Our method gains advantages
in designing Boolean circuits
These examples are shown in Table 4. In (Zhi et al.,
2006) a logic optimization method for majority gate based Nanoelectronic circuits
using a novel mapping and sharing scheme is proposed to achieve simple synthesized
circuits and high synthesis speed. In Zhi et al. (2006) they have tried
to optimize the previous work presented by Zhang et al. (2005b) and the
presented method has a considerable improvement in comparison to those works.
It is obvious from Table 4 the proposed item in this study
can be very efficient in majority and inverter gate counts reduction. We compared
our approach to the method presented by Zhang et al. (2004) and Zhi et
al. (2006) and in this comparison we achieve some considerable and efficient
improvements. These important results illustrated in Table 5.
The reduction is in the number of circuit levels, majority gate counts and inverter
The method gains advantages designing Boolean circuits. In the first function
level counts reduced 50% as in shown in Table 5.
In addition, we replace two three-input majority gate with a five-input majority gate and hence gate counts is reduced. In the second function, the number of levels are not changed but inverter counts has a good reduction. Also, the number of majority gates has been reduced. In our approach we have used both five-input majority gates and three-input majority gates simultaneously. In the second function, in comparison to previous design number of inverters has a considerable reduction. And thus, gate counts has a good reduction.
RESULTS AND DISCUSSION
In this study, a novel scheme for QCA cell has been introduced to construct
a five-input majority gate in order to make efficient QCA majority logic design.
Furthermore, we have introduced a new strategy for simplifying Boolean functions
based on five-input majority gate. The study has had a direct application to
the design of logic functions in QCA where the logic primitives are three- and
five-input majority gates. As a case study, the proposed technique is used to
develop a 1-bit QCA adder that is constructed with only two majority gates and
one inverter. The QCA adder has been compared with another existing implementation
of QCA adders. Also, some examples illustrates that our method has considerable
influence on circuits simplifying as our proposed item reduces the level counts
and the number of majority and inverter. It is expected that the new scheme
for QCA cells and the new form of majority gate and the reduction method presented
in this study produces significant improvement in majority gate based Nanoelectronic
circuits and reduces chip area and increases speed for many future QCA architectures.
For a fast design in QCA, complexity constraints are very critical issues and the design needs to use architectural techniques to boost the speed considering these limitations. This study presents a new design for QCA 1-bit full-adder with lesser complexity than the previous designs. In proposed design the one bit full adder comprises only two majority gates and one inverter. Moreover, a logic optimization and reduction strategy based on a new proposed scheme of majority gates has been presented. This strategy achieves considerable reduction in level and gate counts in Nano structure circuits design. The layouts and functionality checks are done using QCADesigner and those designs are compared according to the complexity.