 Open Access
 Total Downloads : 142
 Authors : Tarlochan Singh, Chakshu Goel
 Paper ID : IJERTV5IS030162
 Volume & Issue : Volume 05, Issue 03 (March 2016)
 DOI : http://dx.doi.org/10.17577/IJERTV5IS030162
 Published (First Online): 12032016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Optimal Approach to Design 4bit Reversible Power Efficient Comparator
Tarlochan Singh PG Student, Dept. of ECE,
Shaheed Bhagat Singh State Technical Campus, Ferozepur (152001), India
Chakshu Goel Assistant Professor, Dept. of ECE,
Shaheed Bhagat Singh State Technical Campus, Ferozepur (152001), India
Abstract: – Reversible logic enamored great attention in digital design so as to decrease the power consumption of the circuit. Low power and compact sized comparators are more efficient and most important for the future computing technologies, low power CMOS, quantum computing, nanotechnology and optical computing. This paper presents two new gates for the compact and low power design of reversible comparator, namely, TCG and CCG. In this approach TCG lonely acts as a single bit comparator with low quantum cost. Proposed design of the reversible comparator can be implemented for multiple number of bits, here the design is implemented up to four bit comparison. In addition, the primary parameters power, numbers of gates, quantum cost, garbage outputs, ancillary input and delay of the reversible 1bit, 2bit and 4bit comparator have been presented and compared with the existing designs.
Keywords: – Reversible gate, Reversible comparator, Quantum cost, ancillary input, garbage output.

INTRODUCTION
A generalpurpose computer is logically irreversible and ineluctably generates heat. There are number of intermediate bits in the circuit that are used to compute the final results. And when intermediate bit(s) is/are erased during any computation, then information loss occurs which causes energy dissipation in computing system that was demonstrated by R. Landauer in the year 1960. According to Landauers [1] principle, for each bit of information is erased a computer must dissipate at least kTIn2 of energy (about 3Ã—1023 J at room temperature) where k = 1.3806505Ã—1023 m2kg2K1 is Boltzmann constant and T is the temperature at process. Gordon. E. Moore [2] in 1965 predicted that the number of transistors onto a chip gets double after every two years. According to him as the number of components on the chip increases, heat and information loss also increases rapidly. Hence power dissipation has become a crucial issue in the integrated circuits. C. Bennett [3] in 1980 revealed that the reversible logic circuits would not loose kTIn2 joules of energy as outputs can be recovered from inputs. Bennett showed that the computations that are performed on classical machine can be performed on reversible machine with the same efficiency with less power dissipation. The reversible logic is achieved when there is one to one function between input and output. Main aim of the reversible operation is to recover lost/erased bit(s) during any computation from outputs, results in zero power dissipation in the circuit if Quantum cost, Garbage output, delay and number of gates are kept low.
A digital comparator circuit is that which compares two or more binary numbers. This circuit is widely used in the field of communication, microprocessors and sorting of signals.

BASIC DEFINITIONS
IN THIS SECTION WE WILL DEFINE SOME IMPORTANT BASIC PARAMETERS THAT WILL HELP US LOT TO DESIGN OUR PROPOSED WORK.

Reversible logic gate
A reversible logic gate is an minput and moutput gate that has unique output recovery pattern from input since every single input is connected to every single output through logic operations. In other words, reversible logic gates are the operations in which the number of inputs are equal to the number of outputs and there is one to one function between input and output vectors [4]. There is one more condition holds for the reversible gate is that fan out and feedback paths not permitted. These gates are expressed in the mÃ—m (m by m) form. World's most common reversible gate is NOT gate which is 1Ã—1 gate. Feynman gate is called Controlled NOT (CNOT) which is a 2 Ã— 2 reversible gate. There are many 3 Ã— 3 reversible gates such as Toffoli (TG), Peres (PG) and Fredkin gate.

Quantum cost
Quantum cost of circuit designed with reversible logic gates depends upon the elementary quantum gates which defines all inputoutput states of that particular gate [5]. Elementary quantum gates are inherently reversible and these act upon q bits rather than the logic original values. The present state of a qbit for 2 logic states can be expressed as q = 0 + 1, where 0 and 1 are logic 0 and 1 state, respectively, and and are the complex numbers such that 2 + 2 = 1. The most used elementary quantum gate is the NOT gate (where only single qbit is reversed), the CNOT gate (the second qbit is inverted if the single control qbit is high or 1), the controlledV gate.

Garbage output
When operating with reversible gates the circuits may have some useless outputs called Garbage outputs. Although these outputs are not used in the circuit but play very important role for the complete operation of the circuit to maintain reversibility. Its value should be kept low as possible so that the garbage can be reduced [6].

Delay
Delay from one input line to any output line is calculated as the maximum number of gates in the path. This explanation is based on the two assumptions [6] that each gate carry out the computation in one unit time. This means that every gate in the given circuit will take the same amount of time for internal logic operations and all inputs to the circuit are known before the computation begins. So delay is calculated as the sum of delays through the path of each gate that causes maximum delay. By this definition before any calculation each operation and internal structure of the individual gate are known.

Various reversible logic gates
Here we present some basic reversible logic gates that are employed to design our proposed comparator circuit. As we said earlier an minput, moutput gate is reversible if there is one to one function among them.
Let Im and Om be the input and output vectors to represent an M Ã— M reversible gate, where
Im = (I1, I2, I3Im), Om = (O1, O2, O3Om).

Feynman Gate (FG): Feynman gate is 2Ã—2 reversible CNOT (Controlled NOT) gate. It is widely used as fanout purposes. Quantum cost for Feynman gate is 2.The total logical calculations for this gate is T= 1. Feynman gate block diagram is shown in figure 1 [7].
Input and output vectors for FG are:
Im = (A, B),
Om = (P=A, Q=AB).
Fig. 1. Block diagram of Feynman Gate (FG).

Peres Gate (PG): Peres gate is a 3Ã—3 reversible gate whose quantum cost is 4 [8]. Due to its low quantum cost, it is used in various reversible circuits. It is also used as half adder, and a twoinput AND gate. The total logical calculations for Peres gate are T= 2+1.

The input and output vectors for PG are:
Im = (A, B, C),
Om= (P=A, Q=AB, R= ABC).
Fig. 2. Block diagram of Peres Gate (PG).


EXISTING WORK
The design of the reversible comparator in [9] performs comparison of bits one by one between two numbers which used further different comparing cells that perform the operation of comparing the nth bit of a number A with the corresponding bit of the second number B. In this approach, a single bit comparator was designed using TG, FG and a NOT gate. Another different type of prefix groupingbased reversible binary comparator has been shown in [10]. In the approach described in [11], the author used five reversible gates to design single bit reversibl comparator from these two are NG, two FG and a single NLG gate. Here the NLG gate used whose quantum cost is 2 by virtue total quantum cost of the 1bit comparator circuit becomes 26. Then they have proposed 4bit reversible comparator circuit which results in 13 units of delay, 23 garbage outputs and total quantum cost of 301 with 53 reversible gates [13]. Furthermore in the design approach [12], here a singlebit comparator is designed using a single ZRQC module which was derived from ZRQG reversible gate with quantum cost of 7, single unit delay and single garbage output. Moreover the design of fourbit reversible comparator was obtained with complex 8bit quantum cost comparator [13]. The resulting reversible comparator consists of 32 reversible gates, delay of 15 units, 18 garbage outputs, and a quantum cost of 90 [12]. In reference to this, the author designed 4bit reversible comparator circuit with the use of four ZRQC cells, six PGs and six FGs turn out be total of 16 reversible gates and total quantum cost of 50 units. The previous efficient design of a singlebit comparator has two ancillary inputs and single garbage output utilizing 7 units of quantum cost and that of a fourbit reversible comparator, delivers 50 units of quantum cost. Moreover, the quantum cost, delay and number of garbage outputs of these design are not compact. Finally, different design epitomes have different types of advantages and pitfalls. However, most of them are not compact in terms of number of gates, garbage outputs, quantum cost, delay, power and some of them are generalized to perform the particular task while others are not.

PROPOSED DESIGN
In this section we present a design of the reversible 4bit comparator using our two new reversible gates with other existing reversible gates.

Proposed TCG gate: TCG is 4Ã—4 reversible logic gate as shown in figure 3.Its input and output vectors are defined as
Im = (A, B, C, D),
Om= (P=A', Q=A'BC, R= AB'AC, S= (ABD)').
Corresponding truth table for this gate is described in TABLE I according to input variations. This reversible gate can implement all Boolean functions as described. When inputs B and D both are equal to 1 then output P=A' (NOT of A), R= AC (AND operation), S=AB (XOR operation) and When inputs
Fig. 3. Block Representation of the reversible TCG. TABLE I. Truth table for reeversible TCG gate.
Inputs
Outputs
A
B D
C
P
Q
R
S
0
0
0
0
1
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
1
1
0
1
0
0
1
1
1
1
0
0
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
1
0
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
1
0
0
1
0
0
1
0
1
1
0
1
0
1
1
1
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
1
1
0
0
1
1
1
1
1
1
1
0
1
1
0
C and D both are 0, this Gate works as one bit comparator as output P = A' (NOT of A), Q = A'B (A is less than B), R = AB' (A is greater than B) and S = (AB)' (A is equal to B). Quantum cost of TCG gate is 6.

Proposed CCG gate: CCG is new 3Ã—3 reversible gate is shown in figure 4. CCG gate has inputoutput vectors as follows:
Input B=1 then output R= A+B (OR operation) and Q= (AC)' implements comparator's equal to function. When input A=1 then it implements two functions, first is EXCHANGE function since input C is exchanged to Q and second is AND operation at output R since R=AB. Its quantum cost is 4 and corresponding truth table is given in TABLE II. In this proposed work CCG gate is used to find number is equal or greater than the other one.

Proposed single bit reversible comparator: In the proposed work, single bit caomparator circuit is designed using single TCG gate as shown in figure 5. From the TABLE III, it is apparent that AGB( A>B) = AB', ALB( A<B) = A'B and AEB( A=B) = (AB)'. When inputs C and D=0 on TCG gate it behaves as both single bit camparator and MSB comparator which is further used in this approach.
Fig. 5. TCG gate as single bit reversible comparator.
TABLE III. Truth table for single bit reversible comparator.
Inputs
Outputs
A
B
A>B
A<B
A=B
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
Im = (A, B, C),
Om= (P=A', Q= (AC)', R=A'CAB).
Now we see how CCG works with different inputs to implement Boolean functions. First is NOT gate always on output P. When
Fig. 4. Block Representation of the reversible CCG. TABLE II. Truth table for reversible CCG gate.

Proposed two and four bits reversible comparator: To perform comparison between two or more bits first we have to design two more circuits namely SBLT (single bit less than) and SBGE (single bit greater or equal) comparator circuits. These circuits are shown in figure this and this respectively. The SBGE circuit is made with a CCG gate and two peres gates since their quantum cost is lower than the other gates. The SBLT is designed using two Feynman gates as it results in the ALB = (AGBAEB)'. Figure 7 represents the block diagram of this circuit which can be easily put into the design of two and four bit reversible comparator circuits.
Now we see how 2bit and 4bit comparator circuits are designed using these basic cells. As shown in figure, A 2bit reverible comparator circuit is implemented using TCG
Inputs
Outputs
A
B
C
P
Q
R
0
0
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
0
1
1
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
0
1
1
1
1
0
1
1
Fig.6 Proposed design of the single bit reversible Greater or Equal to comparator (SBGE).
Fig. 7 Block diagram of the proposed SBGE.
Fig.8 Proposed design of the single bit reversible less than comparator.
Fig. 9 Block diagram if the SBLT comparator.
followed by one SBGE followed by one SBLT and a four bit reversible comparator circuit is implemented using one TCG followed by three SBGE followed by one SBLT comparator cells.
In the 2bit reversible comparator circuit the most significant bits are fed on inputs A and B to the TCG gate and other inputs stay to zero. This will result in output as shown below
Im = (A=A2, B=B2, C=0, D=0), Om= (P=G1, Q=G2, R=P2, S=Q2)
The outputs P and Q are not required in this design so these are named as G1 and G2 respectively, the garbage outputs. The outputs here derived, P2 and Q2 describes whether the MSB bits are greater or equal to each other. If the bit A2 is greater than B2 then P2 signal will be high and if these bits are equal to each other, then Q2 signal at output of TCG will be high. These outputs will give idea that further processing of bits is needed or not. This means that if one bit from these is greater than the other then further calculation of intermediate bits are not needed to save time and result will be immediately displayed as A is greater than B (AGB signal will be high).
If it's not so then further calculation of intermediate bits are needed. This has been done using single bit greater or equal to comparator (SBGE). In this block remaining bits are compared in the form greater or equal to each other. This happens once in 2bit comparator and three times in the 4bit comparator, this means for nbit comparator there are (n1) SBGE blocks have to be employed. If Q1 signal from last SBGE cell is high then single bit less than comparator generates AEB. If the output from this block is neither equal nor greater means both P1 and Q1 signal are low then ALB signal at the output from single bit less then comparator (SBLT) cell will be high which follows:
ALB = (AGBAEB)'
Fig. 10 Proposed design of the reversible 2bit camparator.
Fig. 11 Proposed design of the 4bit reversible comparator.
Fig. 12 Simulation waveform of the proposed single bit reversible comparator.
Fig. 13 Simulation waveform of the proposed 2bit reversible comparator.
Fig. 14 Simulation waveform of the proposed 4bit reversible comparator.


SIMULATION AND COMPARISON
Simulation of the proposed design is done using Verilog Module in Xilinx ise project navigator (P.68d) software on laptop having IntelÂ® quad core (TM) i3 processor inside(TM) with 2.40 GHz clock speed and 4 GB of RAM. The simulation results for the 1, 2 and 4 bit reversible comparator circuits are shown in the figures 12, 13 and 14 respectively. Simulation results for all comparator circuit shows that the proposed design gives rectifying results for all the input combinations.
TABLES IV and V shows that the comparison between the various approaches that were used to design compact and power efficient reversible comparators with the proposed design in terms of Quantum cost (QC), number of gates (NOG), Delay, garbage output (GO) and ancillary input (AI). All results show that the proposed design for the reversible comparator circuit is better in performance, compact and power efficient than the existing designs.
TABLE IV. COMPARISON BETWEEN DIFFERENT 2BIT REVERSIBLE COMPARATOR DESIGNS.
Design
QC
NOG
Delay
GO
AI
Existing design [13]
45
16
8
9
11
Existing design [12]
25
8
6
8
9
Existing design [10]
28
6
10
6
9
Proposed design
21
6
3
5
5
TABLE V. COMPARISON BETWEEN DIFFERENT 4BIT REVERSIBLE COMPARATOR DESIGNS.
Design
QC
NOG
Delay
GO
AI
Existing design [13]
90
32
15
18
21
Existing design [12]
50
16
11
17
20
Existing design [10]
56
14
14
16
18
Proposed design
47
12
6
13
14

COMPARISON
This paper has presented the different design methodologies to design compact reversible comparator circuit up to 4bits comparison with less power, garbage output, quantum cost, delay, number of gates and ancillary inputs. The results compared in this design became possible only with the proposed new gates due to its low quantum cost. Further this approach can be used to design reversible comparator circuits up to nbit comparison due to its hierarchical model.
REFERENCES

R.Landauer, Irreversibility and Heat Generation in the Computational Process, IBMJournal of Research and Development,5, pp.183191, 1961.

Gordon. E. Moore, Cramming more components onto integated circuits Electronics, J. Electron., Volume 38, Number 8, April 19,1965.

Bennett C. H., Logical reversibility of Computation, IBM J. Research and Development,pp.525532,1973.

Synthesis of fulladder circuit using reversible logic. 17th Int. Conference on VLSI Design, 2004, pp. 757760.

Biswas, A.K., Hasan, M.M., Chowdhury, A.R., Babu, H.M.H.:Efficient approaches for designing reversible binary coded decimal adders, Microelectronics J., 2008, 39, (12), pp. 16931703.

Nielsen, M., Chuang, I.: Quantum computation and quantum information (Cambridge Univ. Press, 2000).

Feynman, R.P.: Quantum mechanical computers, Opt. News, 1985, 11, (2), pp. 1120.

Peres, A.: Reversible logic and quantum computers, Phys. Rev., 1985, 32, (6), pp. 32663276.

AlRabadi, A.N.: Closed system quantum logic network implementation of the Viterbi algorithm, Facta Universitatis Elec. Energ., 2009, 22, (1), pp. 133.

Vudadha, C., Phaneendra, P.S., Sreehari, V., Ahmed, S.E., Muthukrishnan, N.M., Srinivas and M.B.: Design of prefixbased optimal reversible comparator. IEEE Computer Society Annual Symp. on VLSI, 2012, pp 201206.

Ni, L., Guan, Z., Dai, X., Li, W.j.: Using new designed NLG gate for the realization of fourbit reversible numerical comparator. In: International Conference on Educational and Network Technology, pp. 254258.

Rigui Zhou, Manqun Zhang, Qian Wu, YanCheng Li, Optimization Approaches for Designing a Novel 4Bit Reversible Comparator, Int. J. of Theoretical Physics, 52, pp. 559575, 2013.

Nagamani, A., Jayashree, H., Bhagyalakshmi, H.R.: Novel low power comparator design using reversible logic gates, Indian J. Comp. Sci. Engg. 2(4), 566574.

Thapliyal, H., Ranganathan, N., Ferreira, R.: Design of a comparator tree based on reversible logic. In:IEEE International Conference on Nanotechnology Joint Symposium, pp. 11131116.

T. Toffoli, Reversible Computing. Technical Memo MIT/LCS/TM 151, MIT Lab. for Computer Science, 1980.