www.ietdl.

org
Published in IET Computers & Digital Techniques
Received on 6th April 2013
Revised on 2nd October 2013
Accepted on 28th October 2013
doi: 10.1049/iet-cdt.2013.0066

ISSN 1751-8601

Approach to design a compact reversible low power

binary comparator
Haz Md. Hasan Babu1, Nazir Saleheen2, Lafa Jamal1, Sheikh Muhammad Sarwar1,
Tsutomu Sasao3
1
Department of Computer Science and Engineering, University of Dhaka, Bangladesh
2
Department of Computer Science, University of Memphis, USA
3
Department of Computer Science, Meiji University, 214-8571, Kanagawa, Japan
E-mail: [email protected]

Abstract: Reversible logic has captured signicant attention in recent time as reducing power consumption is the main concern of
digital logic design. It consumes less power by recovering bit loss from its unique inputoutput mapping. In this study, the authors
propose a reversible low power n-bit binary comparator. An algorithm is presented for constructing a compact reversible n-bit
binary comparator circuit. The authors also propose two new reversible gates, namely, Babu-Jamal-Saleheen (BJS) and
Hasan-Lafa-Nazir (HLN) gates, to optimise the comparator. In addition, several theorems on the numbers of gates, garbage
outputs, quantum cost, ancilla input, power, delay and area of the reversible n-bit comparator have been presented. The
simulation results of the proposed comparator show that the circuit works correctly and gives signicantly better performance
than the existing ones. The comparative study shows that, as an example, for a 64-bit comparator, the proposed design
achieves the improvement of 24.4% in terms of number of gates, 19.9% in terms of garbage outputs, 7.7% in terms of
quantum cost, 25.77% in terms of area and 3.43% in terms of power over the existing best one. Area and power analysis also
show that the proposed design is the most compact as well as a low power circuit.

1 Introduction theorems and lemmas, the efciency of reversible logic

synthesis of an n-bit comparator has also been proved in
Reversible logic has proved its distinctive feature of this paper.
recovering bit loss from unique inputoutput mapping, The paper is organised with the following sections: Section 2
where conventional logic has failed to do so. Over the last gives the idea about the reversible gate, garbage output,
few years, reversible logic has been extensively used in quantum cost, delay area and power. Section 3 shows the
numerous technologies such as DNA computing, quantum existing approaches of designing reversible binary
computing and nanotechnology. In conventional logic, comparator. Section 4 introduces the logic synthesis of
information is lost once input cannot be recovered from its reversible n-bit comparator. Section 5 gives the simulation
output pattern or vice versa. In the early 1960s, Landauer [1] results of all the proposed circuits and comparison with
demonstrates that losing bits of information causes loss of other existing researches. Finally, the paper is concluded
energy. It is proved that the loss of each bit of information with Section 6.
loses at least KT ln2 joules of energy, where K is the
Boltzmann constant and T is the temperature at which the
system is operating [1]. Reversible logic has the feature to 2 Basic definitions and literature overview
generate one-to-one correspondence between its input and
output [24]. As a result, no information is lost in In this section, we present the basic idea and denitions of
reversible logic and zero power dissipation would be reversible gate, garbage output, quantum cost, delay area
achieved only if the network consists of reversible gates [5]. and power.
Quantum cost, delay, garbage output and number of gates
used in a reversible design should be kept as minimum as 2.1 Reversible gate
possible [6].
Comparison of two binary numbers nds its wide A reversible gate is an n-input and n-output (denoted by n n)
application in general purpose microprocessors, gate that produces a unique output pattern [7] for each
communication systems, encryption device, sorting possible input pattern. In other words, reversible gates are
networks etc. In this work, we present an n-bit comparator circuits in which the number of outputs is equal to the
which has less number of gates; it also produces less number of inputs and there is a one-to-one correspondence
garbage outputs, quantum cost and delay. With the help of between the vectors of inputs and outputs.

IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139 129
doi: 10.1049/iet-cdt.2013.0066 & The Institution of Engineering and Technology 2014
www.ietdl.org
The simple reversible gate is a NOT gate and it is a 1 1 Here, K is the dielectric constant of metal, L is the maximum
gate. Controlled NOT (CNOT) is a 2 2 reversible gate. interconnect wire length, is the wire resistivity, is the
There are many 3 3 reversible gates such as Toffoli (TG), permitivity, is the least thickness value and n is the no. of
Peres (PG) and Fredkin gate. lines broke for calculation for long lines.

2.2 Garbage output 2.6 Area

Unwanted or unused output of a reversible gate (or circuit) is The area of a logic circuit is the summation of individual area
known as garbage output, that is, the output(s) which is (are) of each gate of the circuit. Suppose, a reversible circuit
needed only to maintain the reversibility is (are) known as consists of n reversible gates and area of those n gates are
garbage output(s). Heavy price is paid off for each garbage a1, a2, , an. Then by using above denition, area (A) of
output [8]. that circuit is

n
2.3 Quantum cost A= ai
i=1
The quantum cost can be derived by substituting the
reversible gates of a circuit by a cascade of elementary Given the above denition the area of a circuit can be
quantum gates [9]. Elementary quantum gates realise calculated easily by obtaining area of each individual gate
quantum circuits that are inherently reversible and using CMOS 45 nm Open Cell Library [12] and Synopsis
manipulate qubits rather than pure logic values. The state of Design Compiler [16].
a qubit for two pure logic states can be expressed as |c =
|0 + |1, where |0 and |1 denote 0 and 1, respectively,
2.7 Power
and and are the complex numbers such that ||2 + ||2 =
1. The most used elementary quantum gates are the NOT The power of a logic circuit is the summation of individual
gate (a single qubit is inverted), the CNOT gate (the target power of each gate of the circuit. Suppose, a reversible
qubit is inverted if the single control qubit is 1), the circuit consists of n reversible gates and individual power of
controlled-V gate (also known as a square root of NOT, those gates are p1, p2, , pn, respectively. Then, the power
since two consecutive V operations are equivalent to an (P) of the circuit is
inversion), and the controlled-V + gate (which performs the
inverse operation of the V gate and thus is also a square

n
root of NOT) [9]. P= pi
i=1

2.4 Various reversible gates

As we can obtain current rating of each gate by using CMOS
In this subsection, we present some reversible gates that are 45 nm Open Cell Library [12], Microwind DSCH 3.5 [13]
used to design our proposed circuit. and voltage is constant across each transistor, we can
Let Iv and Ov be the input and output vector of a 2 2 calculate power requirement of each transistor using the
Feynman gate (FG) [10], respectively, where Iv = (A, B) formula P = V I. Here, P refers to the power, V refers to
and Ov = (P = A, Q = A B). The quantum cost of FG is the voltage and I refers to the current.
one [10].
Let Iv and Ov be the input and output vector of a 3 3 PG [11], 3 Existing works
respectively, where Iv = (A, B, C) and Ov = (P = A, Q =
A B, R = AB C). The quantum cost of PG is four [11]. The existing reversible design [17] of the binary comparator is
a serial architecture that has the latency of O(n). According to
this design approach, the comparator consists of a chain of
2.5 Delay reversible comparison cells that perform the operation of
The delay of a logic circuit is the maximum number of gates comparing the ith bit of the rst number xi with the
in a path from any input line to any output line. This denition corresponding bit of the second number yi. Here, a 1-bit
is based on the following two assumptions [8]: rstly, each comparator cell is designed using reversible TG, FG and
gate performs the computation in one unit time. This means the NOT gate. In this work, the design of reversible
that every gate in the given circuit will take the same comparator has not been generalised for n-bit. Furthermore,
amount of time for internal logic operations. Secondly, all another serial architecture-based design of an existing
inputs to the circuit are known before the computation reversible binary comparator [18, 19] also represents the
begins. In this work, computation time for each gate is latency of O(n). In this design approach, the comparator
obtained using CMOS 45 nm Open Cell Library [12], consists of a chain of reversible comparison cells that
DSCH 3.5 [13] and delay is calculated as the sum of delays perform the comparison between corresponding bits of the
of each gate through the path that causes maximum delay. two numbers. Unlike [17], this design of reversible
This means that the internal structure and each operation of comparator has been generalised for n-bit.
the gate are known before the calculation. Interconnect A different design approach of the reversible binary
delay is playing a signicant role as semiconductor comparator is tree-based [20]. The existing reversible binary
technology is marching towards lower sized chips [14, 15]. tree comparator has a binary tree structure, in which each
The interconnect delay (tid) can be calculated as node consists of a 2-bit reversible binary comparator that
can compare two 2-bit numbers x (xi, xi1) and y (yi, yi1),
to generate 2-bit outputs indicating whether x (xi, xi1) > y
tid = (3.56 K L2 r 1)/(l2 n) (yi, yi1) or x (xi, xi1) < y (yi, yi1). This approach has

130 IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139
& The Institution of Engineering and Technology 2014 doi: 10.1049/iet-cdt.2013.0066
 www.ietdl.org
been further illustrated with the design of 8-bit and 64-bit Table 1 Reversibility of the proposed BJS gate
reversible comparators. This work has not been generalised
A B C D P Q R S
for n-bit. Moreover, to improve the design of [20], another
improved prex grouping-based reversible binary 0 0 0 0 0 0 0 1
comparator is proposed in [21]. 0 0 0 1 0 0 0 0
Another existing approach [22] showed the reversible 0 0 1 0 0 0 1 0
design of 1-bit binary comparator. In this design, 1-bit 0 0 1 1 0 0 1 1
comparator has been designed with many popular reversible 0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 1
gates, but here also, the design has not been generalised for 0 1 1 0 0 1 1 1
n-bit. A sequential and a tree-based comparator have been 0 1 1 1 0 1 1 0
shown in [23]. In this design, several new gates have been 1 0 0 0 1 1 0 0
proposed to design the comparator. However, the design 1 0 0 1 1 1 0 1
1 0 1 0 1 0 0 1
has not been generalised for n-bit. Moreover, the quantum 1 0 1 1 1 0 0 0
cost, delay and number of garbage outputs of this design 1 1 0 0 1 1 1 1
are not compact. Finally, different design paradigms have 1 1 0 1 1 1 1 0
different types of advantages and pitfalls. However, most of 1 1 1 0 1 0 1 0
them are not compact in terms of number of gates, garbage 1 1 1 1 1 0 1 1
outputs, quantum cost, delay, power and area. Some of
them are generalised while others are not.
In this paper, BJS gate is used to design the 1-bit
4 Proposed design of reversible n-bit comparator (shown in Section 4.3) and the MSB
comparator comparator (shown in Section 4.4). Fig. 1b shows the
equivalent quantum realisation of the BJS gate. Here, each
In this section, we propose a compact and improved version of dotted rectangle is equivalent to a 2 2 CNOT gate. Hence,
reversible n-bit comparator. A binary comparator compares the the quantum cost of the BJS gate is six.
magnitude of two binary numbers to determine whether they
are equal or one is greater/less than the other. To construct
4.2 Proposed HLN gate
the optimised n-bit comparator, we propose two new
reversible gates, namely BJS and HLN gate in Sections 4.1 A 3 3 reversible gate is proposed in this subsection which is
and 4.2, respectively. Section 4.3 shows the design of 1-bit named as HLN gate (shown in Fig. 2a). The corresponding
comparator circuit. In order to improve the design, we truth table of the gate is shown in Table 2. The truth table
propose an MSB comparator circuit for comparing the nth bit shows that the inputoutput combinations preserve the
(MSB) of two n-bit numbers described in Section 4.4. Then, one-to-one mapping between them.
a single-bit GE (greater or equal) comparator cell has been The HLN gate can implement all Boolean functions. When
designed to generate greater and equal signal for the C = 1 and C = 0, it implements EX-OR (Q = A B) and
remaining (n 1) bits of two numbers with the previous AND (Q = AB) functions, respectively. When B = 1, it
comparison result of MSB which is described in Section 4.5. implements OR function (R = A + B). When B = 0 and
Moreover, a single-bit LT (less than) comparator cell is C = 0, it depicts NOT function (Q = A). In this paper,
designed to determine the less than signal, which is HLN gate is used to design the single-bit greater or equal
described in Section 4.6. These three circuits are then comparator cell (shown in Section 4.5). Fig. 2b shows the
extensively used to design 2-bit and n-bit reversible binary equivalent quantum realisation of HLN gate. The quantum
comparators which are described in Sections 4.7 and 4.8, cost of the HLN gate is ve.
respectively.

4.1 Proposed BJS gate

In this subsection, a new 4 4 reversible gate, namely BJS

gate, is proposed. The proposed gate is shown in Fig. 1a.
The corresponding truth table of the gate is shown in
Table 1. It can be veried from the truth table that the input
pattern corresponding to a particular output pattern can be Fig. 2 HLN gate
uniquely determined. a Block diagram
The proposed BJS gate can implement all Boolean b Quantum Realisation of proposed HLN gate
functions. When C = 0 and D = 1, the BJS
simultaneously implements Q = A + B, R = AB and S =
A B. When B = 1 and C = 1, the output is Q = A. Table 2 Reversibility of the proposed HLN gate
A B C P Q R

0 0 0 0 1 0
0 0 1 0 0 1
0 1 0 0 0 0
0 1 1 0 1 1
1 0 0 1 0 0
Fig. 1 BJS gate 1 0 1 1 1 0
1 1 0 1 1 1
a Block diagram 1 1 1 1 0 1
b Quantum realisation of proposed BJS gate

IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139 131
doi: 10.1049/iet-cdt.2013.0066 & The Institution of Engineering and Technology 2014
www.ietdl.org
Table 3 Truth table for 1-bit binary comparator
Inputs Outputs

A B ALB AEB AGB

0 0 0 1 0
0 1 1 0 0
1 0 0 0 1
1 1 0 1 0

Fig. 4 GE comparator cell

a Proposed design
Fig. 3 BJS works as b Block diagram of the single-bit GE comparator cell

a 1-bit reversible comparator

b MSB comparator circuit

4.3 Proposed design of 1-bit reversible comparator

circuit

The 1-bit comparator compares two 1-bit binary numbers and

determines the result among ALB (A < B), AEB (A = B) and
Fig. 5 LT comparator cell
AGB (A > B). The truth table of 1-bit comparator is shown
a Proposed design
in Table 3. b Block diagram of single-bit LT comparator cell
From the truth table, it is obvious that ALB = AB, AEB =
(A B) and AGB = AB. The proposed BJS gate can be
used as a 1-bit comparator. The gate takes two 1-bit binary
numbers as inputs A and B and two constant inputs. The 4.6 Proposed design of reversible single-bit less
outputs of the gate produce one garbage output and than comparator cell
three consecutive outputs AGB, ALB and AEB (shown
in Fig. 3a). The circuit described in previous subsection produces two
outputs Pn-1 (AEB) and Qn1 (AGB). If An1 < Bn1, we
can calculate it using the equation, ALB = (AEB AGB).
4.4 Proposed design of reversible MSB
The design of this circuit and its block diagram are shown
comparator circuit
in Figs. 5a and b, respectively. As the circuit requires two
The MSB comparator circuit takes MSB of two binary FGs, the quantum cost of the circuit is two.
numbers An, Bn and sets two constant inputs as 0. It
produces three outputs based on the bits present at the input 4.7 Proposed design of reversible 2-bit comparator
level. ALB (Rn), AGB (Qn) and AEB (Pn) are the three
outputs produced from this circuit. Later on these outputs A reversible 2-bit binary comparator consists of a proposed
are fed into the next level, where (n 1)th bits have also reversible MSB comparator, a single-bit GE comparator and
been compared. This proposed MSB comparator circuit a single-bit LT comparator circuit. The reversible design of
shown in Fig. 3b consists of only one BJS gate which 2-bit binary comparator is shown in Fig. 6a.
produces one garbage output and has the quantum cost of six.
4.8 Proposed design of reversible n-bit
4.5 Proposed design of reversible single-bit comparator
greater or equal comparator cell
The proposed reversible n-bit binary comparator is shown in
In this subsection, the design of a reversible single-bit Fig. 6b which consists of one MSB comparator, (n 1)
comparator cell is shown, which consists of one HLN gate single-bit GE comparators and a single-bit LT comparator
and two PGs. It takes (n 1)th bits of two binary numbers circuit. The algorithm for constructing reversible n-bit
A and B and two more inputs Pn and Qn from previous binary comparator is given in Algorithm 1 (see Fig. 7).
comparison result. Together they work to produce two
outputs AEB (Pn1) and AGB (Qn1) which indicates Theorem 1: A reversible n-bit binary comparator (n 2) can
whether the given numbers A and B are equal to each other be realised with 3n gates; where n is the number of data bits.
or greater than the other. Figs. 4a and b show the proposed
circuit and the block diagram of the reversible single-bit Proof: We prove the above statement by mathematical
greater or equal comparator cell, respectively. induction.

132 IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139
& The Institution of Engineering and Technology 2014 doi: 10.1049/iet-cdt.2013.0066
 www.ietdl.org

Fig. 6 Proposed design of reversible

a Proposed design of reversible 2-bit comparator;
b Proposed design of reversible n-bit comparator;
c Critical path of the reversible n-bit binary comparator

Fig. 7 Reversible n-bit binary comparator, when n 2

IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139 133
doi: 10.1049/iet-cdt.2013.0066 & The Institution of Engineering and Technology 2014
www.ietdl.org
An MSB comparator circuit requires one BJS gate. A Lemma 2: A reversible n-bit comparator requires (42.5n
single-bit GE comparator cell is constructed with one HLN 14.5) m2 area, where n is the number of data bits.
gate and two PGs. A single-bit LT comparator cell requires
two FGs. A 2-bit comparator circuit is constructed with one Proof: An n-bit comparator is constructed with one MSB
MSB comparator circuit, one single-bit GE comparator cell comparator circuit, (n 1) single bit GE comparator cells
and one single-bit LT comparator cell (shown in Fig. 6a). and one single bit LT comparator cell. An MSB comparator
Hence, the total number of gates required to construct 2-bit circuit requires one BJS gate. A single-bit GE comparator
binary comparator (NOG2-bit) is cell is constructed with one HLN gate and two PGs. A
single-bit LT comparator cell requires two FGs. Hence, the
NOG2-bit = NOGMSB + NOGSBGE + NOGSB-LT total number of gates is
= 1 + (1 + 2) + 2
NOG = NOGMSB + (n 1) NOGSB-GE + NOGSB-LT . . .
=6
= 1 BJS + (n 1)(HLN + 2 PG) + 2 FG
=32
(2)
Hence, the statement holds for the base case n = 2.
The areas of BJS gate, HLN gate, PG and FG are 20, 17.5,
Assume that, the statement holds for n = k. Hence, a
12.5 and 7 m2, respectively, (obtained using CMOS 45 nm
reversible k-bit binary comparator can be realised with 3k
Open Cell Library [12] and Algorithm 2 (see Fig. 8).
reversible gates.
Hence, the total area of an n-bit comparator can be
A (k + 1)-bit binary comparator requires one MSB
modelled as follows
comparator circuit, k single-bit GE comparator cell and one
single-bit LT comparator cell. Hence, the total number of
gates required to construct (k + 1)-bit binary comparator A = AMSB + (n 1) ASB-GE + ASB-LT
(NOG(k + 1)-bit) is = {20 + (n 1)(17.5 + 2 12.5) + 7} mm2
NOG(k+1)-bit = NOGMSB + k NOGSB-GE + NOGSB-LT = (42.5n 42.5 + 27) mm2
= 1 + k(1 + 2) + 2 = (42.5n 14.5) mm2
= 3k + 3
= 3(k + 1)
Lemma 3: A reversible n-bit comparator requires (117.76n
32.94) W power, where n is the number of data bits.
Thus, the statement holds for n = k + 1.
Therefore a reversible n-bit binary comparator can be Proof: One MSB comparator circuit, (n 1) single bit GE
realised with 3n reversible gates. comparator cells and one single bit LT comparator cell
are required to realise an n-bit comparator. Hence, the
Lemma 1: A reversible n-bit comparator requires (0.15n total required power can be measured by using following
0.03) ns timing delay, where n is the number of data bits. equation
Proof: The proposed n-bit comparator design has a serial Total power(P) = PMSB + (n 1) PSB-GE
architecture that has latency of O(n). An n-bit comparator
requires one MSB comparator circuit, (n 1) GE + PSB-LT . . . (3)
comparator cells and one single bit LT comparator cell.
Hence, the delay of the comparator circuit is

Total delay(T ) = TMSB + (n 1) TSB-GE + TSB-LT . . . (1)

The critical path for single-bit GE comparator cell contains

one HLN gate and two PGs. The delays of HLN gate and
PG are 0.07 ns and 0.04 ns, respectively, (obtained by
DSCH 3.5 [13]). Hence, the delay of single-bit GE
comparator cell can be calculated as follows

TSB-GE = THLN + 2TPG = (0.07 + 2 0.04) ns = 0.15 ns

Using DSCH 3.5 [13], CMOS 45 nm Open Cell Library [12]

and interconnect delay [14, 15] we obtain the delays of the
MSB and LT modules which are 0.07 and 0.05 ns,
respectively. Using (1), the total delay of an n-bit
comparator can be modelled as follows

T = {0.07 + (n 1) 0.15 + 0.05}ns

= (0.15n 0.15 + 0.12)ns
Fig. 8 Area calculation of reversible n-bit binary comparator,
= (0.15n 0.03)ns when n 2

134 IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139
& The Institution of Engineering and Technology 2014 doi: 10.1049/iet-cdt.2013.0066
 www.ietdl.org
The single-bit GE comparator cell contains one HLN gate and Proof: A 2-bit comparator circuit consists of one MSB
two PGs. The power requirement of HLN gate and PG are comparator, one single-bit GE comparator cell and one
58.88 and 29.44 W, respectively, (obtained by DSCH 3.5 single-bit LT comparator cell. The MSB comparator circuit
[13] and CMOS 45 nm Open Cell Library [12]). Hence, the produces one garbage output and the single-bit GE
power requirement of a single-bit GE comparator cell, comparator cell produces four garbage outputs. The
PSB-GE, can be calculated as follows single-bit LT comparator cell does not produce any garbage
output. Hence, the total number of garbage outputs
PSB-GE = (58.88 + 2 29.44)mW = 117.76 mW produced by a 2-bit comparator is at least

Using DSCH 3.5 [13] and CMOS 45 nm Open Cell Library G2-bit = GMSB + GSB-GE + GSB-LT
[12], we have obtained the power requirement of MSB and
LT modules that are 37.72 and 47.1 W, respectively. =1+4+0
Hence, the total power of an n-bit comparator can be =5
modelled as below according to (3) =423

P = {37.72 + (n 1) 117.76 + 47.1} mW Hence, the statement holds for the base case n = 2.
= (117.76n 117.76 + 84.82) mW
Assume that, the statement holds for n = k. Hence, a
= (117.76n 32.94) mW reversible k-bit binary comparator produces at least 4k 3
garbage outputs.
A (k + 1)-bit binary comparator requires one MSB
Theorem 2: A reversible n-bit binary comparator (n 2) comparator circuit, k single-bit GE comparator cell and one
produces at least 4n 3 garbage outputs, where n is the single-bit LT comparator cell. So, the total number of
number of data bits. garbage outputs produced by the (k + 1)-bit binary

Fig. 9 Simulation result of reversible

a 1-bit comparator
b 2-bit comparator
c 4-bit comparator

IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139 135
doi: 10.1049/iet-cdt.2013.0066 & The Institution of Engineering and Technology 2014
www.ietdl.org
Table 4 Comparative results of the complexities of different Therefore a reversible n-bit binary comparator produces at
reversible n-bit comparators least 4n 3 garbage outputs.
Methods NOG GO QC

proposed circuit 3n 4n 3 13n 5

Theorem 3: A reversible n-bit binary comparator (n 2) can
Rangaraju et al. [18, 19] 7n 4 5n 4 16n 10 be realised with 13n 5 quantum cost; where n is the number
Thaplial et al. [20] 9n 6n 6 18n 9 of data bits.
Vudadha et al. [21] 4n 2 5n 4 14n
Morrison et al. [23] 5n 1 17n 12

NOG, no. of gates; GO, garbage output; QC, quantum cost; , Proof: An MSB comparator circuit requires one BJS gate. A
not mentioned single-bit GE comparator cell is constructed with one HLN
gate and two PGs. A single-bit LT comparator cell requires
two FGs. A 2-bit comparator circuit is constructed with one
Table 5 Comparative results of the complexities of different MSB comparator circuit, one single-bit GE comparator cell
reversible n-bit comparators and one single-bit LT comparator cell. The quantum cost of
BJS gate, HLN gate, PG and FG are six, ve, four and one,
Methods Area, m2 Power, W Delay, ns respectively. Hence, the total quantum cost of the 2-bit
comparator circuit is
proposed circuit 42.5n 12.5 117.76n 0.15n 0.03
32.94
Rangaraju et al. 57.5n 35 182.53n + 0.2n 0.16
[18, 19] 76.55 QC2-bit = QCMSB + QCSB-GE + QCSB-LT
Thaplial et al. [20] 90n 77.5 268.23n 0.23*log2(n) + 0.1
239.2 = 6 + (5 + 4 2) + 2
Vudadha et al. [21] 57.5n 35 122.36n 0.09*log2(n) + 0.2
60.36 = 21
= 13 2 5

comparator (G(k + 1)-bit) is

Hence, the statement holds for the base case n = 2.
G(k+1)-bit = GMSB + k GSB-GE + GSB-LT
Assume that, the statement holds for n = k. Hence, a
=1+k4+0 reversible k-bit binary comparator can be realized with 13k
= 4k + 1 5 quantum cost.
= 4(k + 1) 3 A (k + 1)-bit binary comparator requires one MSB
comparator circuit, k single-bit GE comparator cell and one
Thus, the statement holds for n = k + 1. single-bit LT comparator cell. Hence, the quantum cost of

Table 6 Comparison among proposed and existing reversible 8-bit comparators

Methods NOG GO QC Area, m2 Power, W Delay, ns

proposed circuit 24 29 99 325.5 909.14 1.17

Rangaraju et al. [18, 19] 52 36 118 425 1536.79 1.44
Thaplial et al. [20] 72 42 135 642.5 1906.64 0.79
Al-Rabadi [17] 40 64 321 850 3070.5 1.54
Vudadha et al. [21] 30 36 112 425 918.52 0.47
improvement (%) with respect to Rangaraju et al. [18, 19] 53.8 19.4 16.1 23.41 40.84 18.75
improvement (%) with respect to Thaplial et al. [20] 66.6 30.9 26.7 49.33 52.32 NI
improvement (%) with respect to Al-Rabadi [17] 40 54.7 69.1 61.71 70.39 24.03
improvement (%) with respect to Vudadha et al. [21] 20 19.4 11.6 23.41 1.02 NI

NI, no improvement; NOG, no. of gates; GO, garbage output; QC, quantum cost

Table 7 Comparison among proposed and existing reversible 64-bit comparators

Methods NOG GO QC Area, m2 Power, W Delay, ns

roposed circuit 192 253 827 2705.5 7503.7 9.57

Rangaraju et al. [18, 19] 444 316 1014 3645 11758.47 12.64
Thapliyal et al. [20] 576 378 1143 5682.5 16927.52 1.48
Al-Rabadi [17] 320 512 2505 10055 23704.26 13.19
Vudadha et al. [21] 254 316 896 3645 7770.68 0.74
improvement (%) with respect to Rangaraju et al. [18, 19] 56.8 19.9 18.4 25.77 36.19 24.29
improvement (%) with respect to Thapliyal et al. [20] 66.6 33.1 27.6 52.39 55.67 NI
improvement (%) with respect to Al-Rabadi [17] 40 50.6 66.98 73.09 68.35 27.45
improvement (%) with respect to Vudadha et al. [21] 24.4 19.9 7.7 25.77 3.43 NI

NI, no improvement; NOG, no. of gates; GO, garbage output; QC, quantum cost

136 IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139
& The Institution of Engineering and Technology 2014 doi: 10.1049/iet-cdt.2013.0066
 www.ietdl.org
the (k + 1)-bit binary comparator is (QC(k + 1)-bit) is

Proposed

1659
3323
6651
203
411
827
21
47
99
QC(k+1)-bit = QCMSB + k QCSB-GE + QCSB-LT
= 6 + k(5 + 4 2) + 2

et al. [23]
Morrison

1076
2164
4340
8692
124
260
532
= 13k + 8

22
56
et al. [20]
= 13(k + 1) 5
Thapliyal

Thus, the statement holds for n = k + 1.

1143
2295
4599
9207
135
279
567
27
83
QC

Therefore a reversible n-bit binary comparator can be

realised with 13n 5 quantum cost.
et al. [18, 19]

Theorem 4: A reversible n-bit binary comparator (n 2)

Rangaraju

1014
2038
4086
8182
118
246
502

requires at least three ancilla inputs, where n is the number

22
54

of data bits.

Proof: An n-bit comparator circuit (n 2) consists of one

et al. [21]
Vudadha

MSB comparator, (n 1) single-bit GE comparator cells

1792
3584
7168
112
224
448
896
28
56

and one single-bit LT comparator cell. The MSB

comparator circuit requires two ancilla inputs and the
Table 8 Comparison between existing and proposed comparators in terms of number of gates, garbage outputs and quantum cost

single-bit LT comparator cell requires one ancilla input. The

Proposed

(n 1) single-bit GE comparator cells do not require any

1021
2045
125
253
509
13
29
61
5

ancilla input. Hence, the total number of ancilla inputs

required for an n-bit comparator is at least
et al. [23]
Morrison

Ancilla inputs (AI) = AIMSB + (n 1) AISB-GE + AISB-LT

1279
2559
159
319
639
19
39
79
9

= 2 + (n 1) 0 + 1
=3
et al. [20]
Thapliyal

1530
3066
186
378
762
18
42
90
6
GO

Example: The reversible 3-bit comparator requires one MSB

comparator circuit, two single-bit GE comparator cells and
et al. [18, 19]

one single-bit LT comparator cell. To construct the

Rangaraju

comparator, we require 3 3 = 9 reversible gates which

1276
2556
156
316
636
16
36
76

produce (4 3 3) = 9 garbage outputs. It requires three

6

ancilla inputs. The quantum cost is (13 3 5) = 34, the

required area is (42.5 3 12.5) = 115 m2, the required
power is (117.76 3 32.94) = 320.34 W.
et al. [21]

NOG, no. of gates; GO, garbage output; QC, quantum cost; , not mentioned
Vudadha

1276
2556
156
316
636
16
36
76
6

5 Simulation and comparison

Proposed

1536
192
384
768
12
24
48
96

The simulation of the proposed circuit is done using

6

Microwind DSCH 3.5 [13] and CMOS 45 nm Open Cell

Library [12] software on a computer, which has the Intel(R)
et al. [23]
Morrison

Core(TM) i3 CPU with 2.10 GHz Clock Speed and 2.00 GB

RAM. The simulation results show that the comparators

give correct outputs for all possible combinations of inputs.

The simulation results for 1-bit, 2-bit and 4-bit reversible
et al. [20]

binary comparators are shown in Figs. 9a, b and c,

Thapliyal

1152
2304
4608
144
288
576

respectively, which ensure the correctness of the

18
36
72
NOG

functioning of the proposed comparator.

Tables 4 and 5 show the comparative study of our proposed
et al. [18, 19]

design with existing designs for a reversible n-bit comparator.

Rangaraju

Tables 6 and 7 show the comparative study of our proposed

1788
3580
108
220
444
892
10
24
52

design with the existing designs for reversible 8-bit and

64-bit comparators, respectively. From Tables 6 and 7, we
nd that the proposed design outperforms the existing ones
in terms of number of gates, garbage outputs, quantum
et al. [21]
Vudadha

1022
2046

costs, area, power and delay for 8-bit and 64-bit comparator
126
254
510
14
30
62
6

circuits, respectively.
The performance and comparative study of 2, 4, 8, 16,
32, 64-bit binary comparator designs with respect to
bits

128
256
512
No.

16
32
64
of

number of gates, garbage outputs and quantum cost;

2
4
8

IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139 137
doi: 10.1049/iet-cdt.2013.0066 & The Institution of Engineering and Technology 2014
www.ietdl.org
delay, area and power are shown in Tables 8 and 9,

Proposed

202.58

909.14
1851.22
3735.38

15040.34
30113.62
60260.18
438.1

7503.7
respectively. Table 8 shows that for all of the cases, the
proposed circuit requires less numbers of gates, garbage
outputs and quantum costs than the existing designs
[1821, 23]. The calculation of area, delay and power has

1906.640
et al. [20]
Thapliyal

297.26
833.72

4052.48
8344.16
16927.52
34094.24
68427.68
137094.56
been done according to the process mentioned in Section
2. Although the proposed design has less delay than [17,
18], it produces much delay than [20, 21]. As [20, 21]
both are tree-based design, they require O(log2(n)) delay,
Power, W

whereas the proposed design requires O(n) delay. The

Rangaraju et al.

proposed design outperforms the existing ones in terms of

441.61
806.67
1536.79
2997.03
5917.51
11758.47
23440.39
46804.23
93531.91
area and power also.
[18, 19]

6 Conclusions
This paper has presented the design methodologies of a
et al. [21]
Vudadha

184.36
429.08
918.52

3855.16
7770.68
15601.72

62587.96

compact low power reversible n-bit binary comparator. We

1897.4

31263.8

have proposed an algorithm to design the compact

reversible n-bit comparator. In addition, we have proposed
two reversible gates, namely, BJS and HLN gates. We have
proved the efciency of the proposed design with several
Proposed

155.5
325.5
665.5
1345.5
2705.5
5425.5
70.5

10865.5
21745.5

theorems and lemmas. The required ancilla inputs, for the

proposed circuit, is independent of n (for, n 2). It has also
been shown by comparative analysis that the proposed
circuit has been constructed with the optimum number of
gates (proposed circuit has 3n compared with 7n 4 [18,
et al. [20]
Thapliyal

102.5
282.5
642.5
1362.5
2802.5
5682.5
11442.5
22962.5
46002.5

19], 9n [20] and 4n 2 [21]), garbage outputs (proposed

circuit has 4n 3 compared with 5n 4 [18, 19], 6n 6
[20], 5n 4 [21] and 5n 1 [23]), quantum cost
(proposed circuit has 13n 5 compared with 16n 10
Area, m2

[18, 19], 18n 9 [20], 14n [21] and 17n 12 [23]),

Rangaraju et al.
Table 9 Comparison between existing and proposed comparators in terms of delay, area and power

power (proposed circuit requires 117.76n 32.94

[18, 19]

195
425
885
1805
3645
7325
14 685
29 405
80

compared with 182.53n + 76.55 [18, 19], 268.23n 239.2

[20] and 122.36n 60.36 [21]) and area (proposed circuit
needs 42.5n 14.5 compared with 57.5n 35 [18, 19],
90n 77.5 [20] and 57.5n 35 [21]). Even though the
timing delay of the proposed circuit (0.15n 0.03
et al. [21]

compared with 0.2n 0.16 [18, 19], 0.23 * log2(n) + 0.1 [20]
Vudadha

195
425
885
1805
3645
7325
14 685
29 405
80

and 0.09 * log2(n) + 0.2 [21]) is not as less as the tree-based

designs, considering the optimisation of all the parameters,
the circuit outperforms the existing ones in terms of
scalability and efciency. Simulations of the proposed
Proposed

circuit have shown that it works correctly. Since

0.27
0.57
1.17
2.37
4.77
9.57
19.17
38.37
76.77

comparison of two numbers are useful in many

applications, the comparator circuits can be used in many
operations inside the microprocessor, communication
systems, encryption devices, sorting networks, low power
et al. [20]
Thapliyal

circuits etc. [17, 19, 24].

0.33
0.56
0.79
1.02
1.25
1.48
1.71
1.94
2.17
Delay, ns

7 References
Rangaraju et al.

1 Landauer, R.: Irreversibility and heat generation in the computational

[18, 19]

12.64
25.44
51.04
102.24
0.24
0.64
1.44
3.04
6.24

process, IBM J. Res. Dev., 1961, 5, pp. 183191

2 Perkowski, M., Al-Rabadi, A.N., Kerntopf, P., et al. A general
decomposition for reversible logic. Proc. RM2001, Starkville, 2001,
pp. 119138
3 Perkowski, M., Kerntopf, P.: Reversible logic. Invited tutorial, Proc.
EURO-MICRO, Warsaw, Poland, September 2001
4 Thapliyal, H., Srinivas, M.B.: Novel reversible TSG gate and its
et al. [21]
Vudadha

application for designing reversible carry look ahead adder and other
0.29
0.38
0.47
0.56
0.65
0.74
0.83
0.92
1.01

adder architectures. Proc. of the 10th Asia-Pacic Computer Systems

Architecture Conf. (ACSAC 05), (LNCS, 3740), 2005, pp. 775786
5 Bennet, C.H.: Logical reversibility of computation, IBM J. Res. Dev.,
1973, 17, pp. 525532
6 Kerntopf, P., Perkowski, M., Khan, M.H.A.: On universality of general
No. of

reversible multiple valued logic gates. IEEE Proc. of the 34th Int. Symp.
bits

128
256
512
16
32
64

on Multiple Valued Logic (ISMVL04), 2004, pp. 6873

2
4
8

138 IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139
& The Institution of Engineering and Technology 2014 doi: 10.1049/iet-cdt.2013.0066
 www.ietdl.org
7 Babu, H.M.H., Islam, M.R., Chowdhury, A.R., Chowdhury, S.M.A.: 18 Rangaraju, H.G., Hegde, V., Raja, K.B., Muralidhara, K.N.: Design of
Synthesis of full-adder circuit using reversible logic. 17th Int. Conf. efcient reversible binary comparator. Int. Conf. on Communication
on VLSI Design, 2004, pp. 757760 Technology and System Design, 2012, vol. 30, pp. 897904
8 Biswas, A.K., Hasan, M.M., Chowdhury, A.R., Babu, H.M.H.: 19 Rangaraju, H.G., Hegde, V., Raja, K.B., Muralidhara, K.N.: Design of
Efcient approaches for designing reversible binary coded decimal low power reversible binary comparator. Proc. Engineering
adders, Microelectron. J., 2008, 39, (12), pp. 16931703 (ScienceDirect), 2011
9 Nielsen, M., Chuang, I.: Quantum computation and quantum 20 Thapliyal, H., Ranganathan, N., Ferreira, R.: Design of a comparator
information (Cambridge Univ. Press, 2000) tree based on reversible logic. Proc. Tenth IEEE Int. Conf. on
10 Feynman, R.P.: Quantum mechanical computers, Opt. News, 1985, 11, Nanotechnology Joint Symp. with Nano, August 2010, pp. 11131116
(2), pp. 1120 21 Vudadha, C., Phaneendra, P.S., Sreehari, V., Ahmed, S.E.,
11 Peres, A.: Reversible logic and quantum computers, Phys. Rev., 1985, Muthukrishnan, N.M., Srinivas, M.B.: Design of prex-based optimal
32, (6), pp. 32663276 reversible comparator. IEEE Computer Society Annual Symp. on
VLSI, 2012, pp. 201206
12 CMOS 45 nm Open Cell Library: URL http://www.si2.org/openeda.si2.
22 Nagamani, A.N., Jayashree, H.V., Bhagyalakshmi, H.R.: Novel low
org/projects/nangatelib
power comparator design using reversible logic gates, Indian
13 Microwind DSCH Schematic Editor and Digital Simulator, http://www.
J. Comput. Sci. Eng., 2011, 2, (4), pp. 566574
microwind.net/dsch.ph 23 Morrison, M., Lewandowski, M., Ranganathan, N.: Design of a
14 Mui, M.L., Banerjee, K., Mehrotra, A.: A global interconnect tree-based comparator and memory unit based on a novel reversible
optimization scheme for nanometer scale VLSI with implications for logic structure. IEEE Computer Society Annual Symp. on VLSI,
latency, bandwidth, and power dissipation, IEEE Trans. Electron 2012, pp. 331336
Devices, 2004, 51, (2), pp. 195203 24 Shamsujjoha, M., Babu, H.M.H.: A low power fault tolerant reversible
15 Saraswat, K.Prof.: Interconnect Scaling, Stanford University Lecture decoder using MOS transistor. Proc. 26th Int. Conf. on VLSI Design and
Slide, URL: http://www.stanford.edu/class/ee311/NOTES/Interconnect the 12th Int. Conf. on Embedded Systems, Pune, India, 2013, pp. 368373
ScalingSlides.pdf 25 Mehta, D.N., Sanghavi, P.N.: Intels 45 nm CMOS technology
16 Dadda, L.: Multioperand parallel decimal adder: a mixed binary and performance parameters in VLSI Design, Int. J. Electron. Commun.
BCD approach, IEEE Trans. Comput., 2007, 56, (10), pp. 13201328 Comput. Eng., REACT-2013, 4, (2), ISSN 2249071X
17 Al-Rabadi, A.N.: Closed system quantum logic network 26 Samanta, J., De, B.P., Bag, B., Maity, R.K.: Comparative study for
implementation of the viterbi algorithm, Facta Universitatis Elec. delay & power dissipation of CMOS Inverter in UDSM range,
Energ., 2009, 22, (1), pp. 133 Int. J. Soft Comput. Eng., ISSN: 22312307, 2012, 1, (6)

IET Comput. Digit. Tech., 2014, Vol. 8, Iss. 3, pp. 129139 139
doi: 10.1049/iet-cdt.2013.0066 & The Institution of Engineering and Technology 2014