Abstract: Quantum-dot Cellular Automata (QCA) which was proposed as a transistor-less paradigm is looked at as a compeer to the Field Effect Transistor (FET). Mapping of the existing technology to this new quantum dot paradigm necessitates bringing in the QCA structures that can perform all the logic operations that are executed in the current technology. Many QCA structures that perform all logic operations were proposed. QCA is exploited in this paper to implement Boolean expressions using Shannon's theorem, a method which breaks down a large function into smaller function. The layouts are simulated using QCA Designer Tool.
INTRODUCTION
Field effect transistors are being used since 1970s in High levels of integration. The speed and size of the electronic devices are improved drastically. This trend of reduction in transistor size follows Moore's law, which predicts that the number of transistors fabricated on a chip double every 18 months. The reduction in size of FET is possible due to reduction in the gate length. FET encounters effects such as heat dissipation when it reaches a size of 0.1 micrometers. According to the micro electronics industries the FETs are expected to reach this by the early 2010s. New paradigms are proposed in research fields to maintain the reduction in size and growth in device density. One such paradigm was proposed by Bose and Johnson (2004) is QCA. Quantum dots are used to perform the computations in QCA. QCA Effectively performs all the Boolean computations that are performed in CMOS.
QCA MODEL
A Quantum-Dot Cellular Automata cell consists of four quantum dots in a square array coupled with tunnel junctions as shown in Fig. 1. The potential barriers of the tunnel junctions are controlled (raised or lowered) by an applied local electric field mentioned that two extra electrons placed in two of the quantum dots get arranged in the diagonal dots due to coulomb interactions. These diagonal arrangements are considered the ground states and they have minimum energy when compared to any other arrangements.
| Fig. 1: | QCA cell polarization used to encode binary information |
The polarization (P) of the cell depends on the neighboring cells. (Amlani et al., 1998) stated that electrons can tunnel through the junction only when these potential barriers are low and are latched when the potential barriers are high. The lowering and rising of the potential barriers is controlled by external electrodes. The cell with the raised potential barrier act as an input to the cell with lowered potential barriers.
The polarization can also be defined from the expectation value of t he charge on each quantum dot as:
| (1) |
The expectation value of charge on Quantum Dot (QD) is '0' in the absence of electron. If the electrons are present in 1 and 3 diagonal quantum dots, the polarization is:
| (2) |
| Fig. 2(a-b): | Polarization of cells for (a) Classical and (b) Quantum computing |
If the electrons are in 2 and 4 diagonal dots, the polarization is:
| (3) |
In classical computing, P has only two values -1 and +1. But for quantum computing, P can vary continuously from -1 to +1. The polarization of the cells used for classical and quantum computing are shown in Fig. 2a and b, respectively.
This polarization is not same as the usual dipole polarization of a continuous medium. It represents the degree to which of the possible directions, the alignment occurs. The cells with complete polarization have minimum energy and are said to be in ground state. A QCA system will be in the ground state if the polarization of all the cells is same (Goser et al., 2004). Energy of the system increases if two neighboring cells have opposite polarization. This energy which is greater than the ground state energy is called the Kink energy and is calculated by the electrostatic interactions between the quantum dots in neighboring cells (Toth and Lent, 2001). The electrostatic interactions between the quantum dots in neighboring cells ‘i’ and ‘j’ is given by:
| (4) |
Kink energy is given by the difference of the electrostatic energy when the cells have opposite polarization and same polarization.
| (5) |
By considering the kink energy between cells, polarization and tunneling energy of an electron (gamma), the Hamiltonian of a cell 'i' can be written as Eq. 6:
| (6) |
Summation is over all cells which effect the polarization of cells 'i'.
By the time independent Schrodinger equation, we can find the stationary states of the cell in the environment described by this Hamiltonian:
HiΨ = EiΨ |
CLOCKING IN QCA
The polarization of a cell is fixed electrostatically to use it as an input (Taskin and Hong, 2008). After allowing the system to relax and reach its ground state, polarization of the output cell is sensed to read the outputs (Snider et al., 1998). For a QCA Cell to settle down to ground state, four steps are followed.
Lowering the barriers: Potential barriers of the tunnel junction are lowered so that the electron can easily tunnel from one dot to the other.
Removing the older input: The lowered potential barriers are maintained to be low. The polarization of a cell in this stage is '0'. This stage removes the effect of the previous input on the cell.
Applying new input: By applying a new input, the potential barriers are raised. The QCA cell becomes polarized according to the state of the input cell. In this state the actual computation occurs.
Raising the barriers: Finally, the potential barriers are raised and are high enough to suppress any electron tunneling and the states are fixed. Now the cell has the polarization of the input cell and can be used as input to next cell.
| Fig. 3: | Four phases of a clock |
| Fig. 4: | QCA cells in a linear arrangement acting as a wire |
| Fig. 5: | QCA inverter |
This process of raising and lowering of the potential barriers to change the polarization of a cell and allowing it to settle in the ground state is called clocking and the four consecutive steps mentioned above are named release, relax, switch and hold phases, respectively. Any two successive phases has a phase difference of π/4. All the four phases are shown in Fig. 3.
LOGIC DEVICES IN QCA
Designing of QCA architectures that find correct implementation of Boolean equations similar to that of CMOS is important for mapping the CMOS logic on to QCA. Such architectures which serve as logic gates for the new paradigm are discussed here (Choi et al., 2007). QCA wire, inverter, fan-out and majority gate are explained in this section.
QCA wire: Cells connected in a line act as a wire (Fig. 4). The polarization of the input cell (leftmost cell in Fig. 4) is fixed to one stable state. This polarization is shifted from left cell to the right cell. State of the output cell is checked to verify the operation.
QCA inverter: If a QCA Wire is displaced by 45° from the input cell, it acts as an inverter as shown in Fig. 5a.
| Fig. 6(a-c): | (a) Majority gate, (b) Majority gate as OR gate and (c) Majority gate as AND gate |
To improve the strength of the signal, the input is split into two lines and brought back to a cell that is displaced by 45° from the two lines as in Fig. 5b. This 45° displaced wire has the polarization opposite to that of the input cell.
Majority gate: In the majority gate, three input cells vote on the polarization of the center cell and the majority wins. Cell arrangement of a majority gate resembles a cross and is shown in Fig. 6a. Majority gate is the Universal gate in QCA paradigm. By fixing the polarization of one of the input cells to +1 or -1 we can make majority gate act as AND gate or OR gate. Using of QCA cells as AND and OR gate by fixing the polarization of a single cell is shown in Fig. 6a, b, respectively.
By using these logic devices, we can implement any Boolean expression in QCA paradigm.
SHANNON’S EXPANSION THEOREM
In CMOS design we deal with functions of many variables. Shannon's expansion is a method which breaks down these large functions into smaller functions. Boolean logic functions (F) can be expanded in terms of Boolean variables (A). We consider a function:
| • | F (Sum) = A'B'C+A'BC'+AB'C'+ABC (Full Adder) |
Split the above function (F (Sum)) into two smaller functions:
| • | F = A (B'.C'+B.C)+A'(B'.C+B.C') |
In multiplexer logics we can represent the above equation as in Fig. 7. The larger functions (B'.C'+B.C) and (B'.C+B.C') can further be split into smaller functions. The complement implementation of the function F (Sum) in multiplexer logic is shown in the Fig. 8.
Similarly Carry function that implements F (Carry) = AB+BC+CA can also be included to the circuit. Shannon’s expansion is implemented using the QCA architectures and is shown in Fig. 9.
| Fig. 7: | Multiplexer implementation |
SIMULATION AND RESULTS
Figure 10 shows the simulation result of the function F (sum). The equation is expanded using Shannon's Theorem is implemented using Quantum Cellular Automata (QCA). QCA Designer Tool is used to simulate the layout results.
| Fig. 8: | Complement Shannon’s expansion for function F (Sum) |
| Fig. 9: | Implementation of the function F(Sum) using Shannon’s expansion theorem |
| Fig. 10: | Simulation of F(sum)using Shannon's expansion theorem in QCA |
The results have a delay of 1/4th units for one clock cycle used. Total delay is equal to quarter the number of clock cycles used.
CONCLUSION
Implementation of a simple full adder using Shannon's theorem is explained in this paper. Similarly any Boolean function can be expanded using Shannon's theorem and implemented in QCA. Expanded equations can be used in Logic Modules in FPGA chips.