An Optimal Approach to Design 4-bit Reversible Power Efficient Comparator

An Optimal Approach to Design 4-bit 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 1-bit, 2-bit and 4-bit comparator have been presented and compared with the existing designs.

Keywords: – Reversible gate, Reversible comparator, Quantum cost, ancillary input, garbage output.

1. INTRODUCTION

   A general-purpose 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×10-23 J at room temperature) where k = 1.3806505×10-23 m2kg-2K-1 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.

2. BASIC DEFINITIONS

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

   1. Reversible logic gate

      A reversible logic gate is an m-input and m-output 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.

   2. Quantum cost

      Quantum cost of circuit designed with reversible logic gates depends upon the elementary quantum gates which defines all input-output 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 q-bit 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 q-bit is reversed), the CNOT gate (the second q-bit is inverted if the single control q-bit is high or 1), the controlled-V gate.

   3. 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].

   4. 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.

   5. 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 m-input, m-output 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).

      1. Feynman Gate (FG): Feynman gate is 2×2 reversible CNOT (Controlled NOT) gate. It is widely used as fan-out 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).

      2. 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 two-input 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).

3. 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 grouping-based 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 1-bit comparator circuit becomes 26. Then they have proposed 4-bit 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 single-bit 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 four-bit reversible comparator was obtained with complex 8-bit 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 4-bit 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 single-bit comparator has two ancillary inputs and single garbage output utilizing 7 units of quantum cost and that of a four-bit 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.

4. PROPOSED DESIGN

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

   1. 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.

   2. Proposed CCG gate: CCG is new 3×3 reversible gate is shown in figure 4. CCG gate has input-output 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.

   3. 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.

   4. 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 2-bit and 4-bit comparator circuits are designed using these basic cells. As shown in figure, A 2-bit 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 2-bit 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 2-bit comparator and three times in the 4-bit comparator, this means for n-bit comparator there are (n-1) 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 2-bit camparator.

   Fig. 11 Proposed design of the 4-bit reversible comparator.

   Fig. 12 Simulation waveform of the proposed single bit reversible comparator.

   Fig. 13 Simulation waveform of the proposed 2-bit reversible comparator.

   Fig. 14 Simulation waveform of the proposed 4-bit reversible comparator.

5. 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 2-BIT 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 4-BIT 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

6. COMPARISON

This paper has presented the different design methodologies to design compact reversible comparator circuit up to 4-bits 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 n-bit comparison due to its hierarchical model.

REFERENCES

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

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

3. Bennett C. H., Logical reversibility of Computation, IBM J. Research and Development,pp.525-532,1973.

4. Synthesis of full-adder circuit using reversible logic. 17th Int. Conference on VLSI Design, 2004, pp. 757760.

5. 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.

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

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

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

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

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

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

12. Ri-gui Zhou, Man-qun Zhang, Qian Wu, Yan-Cheng Li, Optimization Approaches for Designing a Novel 4-Bit Reversible Comparator, Int. J. of Theoretical Physics, 52, pp. 559-575, 2013.

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

14. 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.

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