Loading...

Parity Preserving Adder/Subtractor using a Novel Reversible Gate Ragani Khandelwal

Sandeep Saini

Department of Electronics and Communication Engineering The LNM Institute of Information Technology Jaipur, India Email: [email protected]

Department of Electronics and Communication Engineering The LNM Institute of Information Technology Jaipur,India Email: [email protected]

major problem of power dissipation with no information loss. A Reversible logic is characterized by : 1. Equal number of inputs and outputs. 2. There exists one to one mapping between the respective inputs and outputs. 3. Loops and fan out are not allowed. In classical computers, only NOT gate performs reversible operation since it has an equal number of inputs and outputs with their unique one to one mapping. Some reversible gates have already been proposed in literature like the controlled-not (CNOT) (proposed by Feynman) [3], Toﬀoli and Fredkin gates [4], IG Gate[5] and MIG gate [6]. Reversible gates have various application in the designing of adders, subtractors, multipliers[7], [8] etc, same like classical computers. The main focus of this paper is to design a circuit that can work as adder as well as subtratctor simultaneously with minimum numbers of garbage outputs, constant inputs and area. Remaining part of the paper is devised as follows: Explanation of Design constraints of reversible circuits and some important deﬁnitions are given in section II. Reversible gates present in literature are given in section III. Proposed gate is shown in section IV. Application of the proposed design is shown in section V. Results with comparison table is shown in section VI and ﬁnally conclusion and future work are made in section VII.

Abstract—Modern VLSI circuit design is governed by low power consumption requirements of ICs. Reversible logic has received great importance because of no information bit loss during computation which results in low power dissipation. Moreover, there is a need to convert the reversible circuits into fault tolerant reversible circuits to detect the occurrence of errors. Parity preserving property can be used for this. A new 5*5 parity preserving reversible gate is proposed in this paper, named as P2RG. The most signiﬁcant aspect of this work is that it can work both as a full adder and a full subtractor by using one P2RG and Fredkin gate only. Proposed design is better in terms of gate count, garbage outputs, constant inputs and area than the existing similitudes. Thus, this paper provides the initial threshold to design more complex systems which will be able to execute more complicated operations using parity preserving reversible logic. Index Terms—Reversible logic; Parity Preserving; P2RG; Adder/Subtractor

I. Introduction In todays technical world, thermal considerations, reliability issues and eﬃciency have become major concerns. Nowadays, research is being done to design a system with high performance, speed and very low power dissipation or ideally no heat generation. As power consumption is a major constraint in designing of VLSI circuits so we need to switch to that computing world where no information loss exists because according to Landauers principle, on every bit of computation, conventional digital systems dissipate KTln2 amount of energy, where K is Boltzmanns constant and T is the temperature at which the computation is performed [1]. Bennett showed that this energy dissipation would not occur if the same number of information bits are generated, i.e. no information loss exists [2] . Present irreversible technologies dissipate a lot of heat in terms of bit loss which reduces life of the circuit. All logical operations in todays classical computers are irreversible. It means extraction of input from the respective output is not possible. On the other hand, reversible computation has a salient feature of unique one to one mapping between inputs and outputs which reduces the 978-1-4799-1797-6/15 $31.00 © 2015 IEEE DOI 10.1109/CSNT.2015.14

II. Design Constraints and Definitions Minimizing the number of Ancillary (constant) Inputs: An extra, auxiliary bit or ﬁxed qubit state that is added to the primary inputs in order to achieve the speciﬁc functionality but they need to be minimized for minimizing auxiliary storage. Minimizing the number of Garbage Outputs: Outputs that are not used further, needed only to make the function reversible (which results to minimize area and power). Minimizing the Gate Count: Number of gates that are used to realize the system is gate count[9]. 885

Truth table of this gate is shown in Table 1, where A, B, C, D and E are the inputs and P, Q, R, S and T are the outputs. It can be seen from the table that all the input and output vectors are uniquely related. The parity preserving property is promptly veriﬁed from the table by comparing the parity of the input to the parity of the output that is (A ⊕ B ⊕ C ⊕ D ⊕ E) and (P ⊕ Q ⊕ R ⊕ S ⊕ T). Example : from the truth table of P2RG i.e Table 1, for the inputs 00010 respective outputs are 01011. According to the equation 1: 0⊕0⊕0⊕1⊕0=1=0⊕1⊕0⊕1⊕1 Like the above example, parity preserving property can be easily veriﬁed for the remaining inputs with their outputs also.

Fault Tolerance: Any physical device while performing classical or quantum computation is subjected to error either due to noise in the environment or fault in the device. It can be detected by fault tolerant computing. Although reversibility is able to recover bit loss, but it is unable to detect bit errors in the circuit [10]. Recent digital circuit designing is now focusing on the faulttolerant reversible circuits. Parity Preservation: It can be used for the fault tolerance computation. Faults in the circuit can be detected by comparing the parity of inputs and outputs. The idea of the parity preserving property in the design reversible logic circuits was given by Parhami [11]. It is known that reversible gates have an equal number of inputs and outputs. Therefore, for parity preservation, this is suﬃcient to prove that parity of inputs and outputs should be equal. As an example, in a parity preservation, 4*4 reversible gate must satisfy the equation which is given below: A⊕B⊕C⊕D=P⊕Q⊕R⊕S Where A, B, C and D are gate inputs and P, Q, R and S are gate outputs. III. Literature Survey In Fig.1, some existing fault- tolerant reversible gates are shown:

Fig. 2: (a) 5*5 parity preserving reversible gate (P2RG) (b) P2RG as universal gate V. Application of P2RG In this machine dependent era, we expect computers to do some kind of arithmetic operation like addition, subtraction. In this section main contribution of the paper is presented. It shows how the idea works. Idea behind the designing of P2RG gate is to construct a combinational circuit that can work as full adder as well as full subtractor on a single unit. We need only a control gate to control the mode of operation for the addition / subtraction.

Fig. 1: (A) Toﬀoli Gate (B) MIG Gate (C) Fredkin Gate (D) NCG Gate IV. Proposed Design A new 5*5 parity preserving reversible gate, P2RG is introduced in Fig.2 (a). • This gate is one through which means one of its inputs is also an output. • It is shown in Fig.2 (b) that Proposed gate is universal since it is able to perform NOR operation. When input B= 1 and D= 0 then output Q performs NOR operation i.e. (A+C)’ . As it is known that NAND and NOR gates are universal gates so it can be concluded that it can be exploited to realize any arbitrary Boolean function.

A. Parity Preserving Half Adder/Subtractor The parity preserving half adder/subtractor is realized using one P2RG gate and one Fredkin gate as shown in Fig.3. Half adder and subtractor are the basic building block to design full adder and subtractor. We need two input i.e. A and B to design a half adder/subtractor. No previous carry or borrow is needed in this. So, this design has two inputs A and B and a control line Ctrl which will control mode of operation, i.e. when Ctrl is

886

using one P2RG gate and one Fredkin gate. In Fig.4, the circuit has three inputs A, B, Cin and a control line Ctrl which will control mode of operation. If Ctrl= 0, it will work as a full adder else it would function as a full subtractor. It has 2 constant inputs, C is set to 0 and E can be set to either 0 or 1. The basic Boolean expressions for sum/diﬀerence, carry and borrow are given below for full adder and subtractor:

TABLE I: Truth Table of P2RG Gate A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

B 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

C 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

D 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

E 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Q 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1

R 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0

S 0 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0

T 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1

(Sum/Di f f erence = (A ⊕ B ⊕ Cin)) (Carry = ((A ⊕ B).Cin) ⊕ AB)) (Borrow = ((A) .B) ⊕ (((A ⊕ B) ).Cin)) Proposed circuit is optimized in terms of number of constant inputs and garbage outputs. Fig.4 shows the implementation of parity preserving full adder/subtractor in which g1, g2, g3 and g4 are garbage outputs.

Fig. 4: Parity Preserving Full Adder/Subtractor using P2RG gate

at logic 0, the circuit will act as half adder and when ctrl is at logic 1, the circuit will act as half subtractor. It will give three constant inputs and four garbage bits g1 to g4. Boolean expressions to realize the functionality of half adder and half subtractor are given below:

C. Parity Preserving 8-bit Parallel Adder/Subtractor An n-bit parallel adder/subtractor will need a chain of (n-1) full adders/subtractor and one half adder/subtractor. Therefore 8-bit parity preserving parallel adder/subtractor is designed by using one parity preserving half adder/subtractor (P2RG HAS) and seven parity preserving full adder/subtractor (P2RG FAS). It has two 8-bit numbers which are A0 to A7 and B0 to B7 as inputs and a control line ctrl which will control the mode of operation. When ctrl line is set at logic 0, the circuit will perform 8-bit addition operation and when ctrl line is set at logic 1, the circuit will perform 8-bit subtraction. The Carry/Borrow received after addition/subtraction is represented by C1/B1 to C7/B7.Output carry/borrow of each block, i.e. C1/B1 to C7/B7 will be the third input for the next block. The outputs, Sum/Diﬀerence and Carry/Borrow are shown in the Fig.5 as S0/D0 to S7/D7 and C8/B8 respectively. Fig.5 shows the parity preserving 8-bit parallel adder/subtractor.

Sum/Di f f erence = A ⊕ B Carry = AB Borrow = A B

Fig. 3: Parity Preserving Half Adder/Subtractor using P2RG gate

VI. Results

B. Parity Preserving Full Adder/Subtractor

In previous sections, an approach for designing parity preserving reversible full adder/subtractor has been discussed. Then an approach for parity preserving 8-bit parallel reversible full adder/subtractor has been discussed.

Many adder designs using reversible gates by several authors have been studied. The proposed design will work as adder as well as subtractor on a single unit. The parity preserving full adder/subtractor is realized

887

Fig. 5: Parity Preserving 8-Bit Adder/Subtractor using P2RG gate In this section, evaluation of the proposed circuits with the help of the comparative results is presented. Table II represents that the performance of proposed parity preserving reversible full adder circuit is better compared to existing counterparts. This design has been optimized in terms of constant inputs, garbage outputs and area. For area calculation, CMOS realization is done in Microwind by using 90nm technology node. Table III shows that performance of parity preserving 8-bit parallel adder/subtractor is better than existing designs.

irreversible gate is 33.59milliwatt. So 33.376milliwatt amount of power is saved here. Likewise, we can see here the power dissipation in reversible circuits is almost negligible compared to irreversible circuits because of no bit loss. The reversible circuits proposed and designed in this work can form the basis of parity preserving reversible ALU of a primitive quantum CPU. References [1] R. Landauer, “Irreversibility and heat generation in the computing process,” IBM journal of research and development, vol. 5, no. 3, pp. 183–191, 1961. [2] C. H. Bennett, “Logical reversibility of computation,” IBM journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973. [3] R. P. Feynman, “Quantum mechanical computers,” Foundations of physics, vol. 16, no. 6, pp. 507–531, 1986. [4] E. Fredkin and T. Toﬀoli, Conservative logic. Springer, 2002. [5] M. Islam, Z. Begum et al., “Reversible logic synthesis of fault tolerant carry skip bcd adder,” arXiv preprint arXiv:1008.3288, 2010. [6] P. NG and M. Anandaraju, “Design and synthesis of fault tolerant full adder/subtractor using reversible logic gates.” [7] P. Garg and S. Saini, “A novel design of compact reversible sg gate and its applications,” in Communications and Information Technologies (ISCIT), 2014 14th International Symposium on. IEEE, 2014, pp. 400–403. [8] S. Saini and S. B. Mandalika, “A new bus coding technique to minimize crosstalk in vlsi bus,” in Electronics Computer Technology (ICECT), 2011 3rd International Conference on, vol. 1. IEEE, 2011, pp. 424–428. [9] USYD, “State Reduction,” http://www.ee.usyd.edu.au/tutorials/ digital tutorial/part3/st-red.htm, 2008, [Online; accessed 19-July2008]. [10] G. Paul, A. Chattopadhyay, and C. Chandak, “Designing parity preserving reversible circuits,” arXiv preprint arXiv:1308.0840, 2013. [11] B. Parhami, “Fault-tolerant reversible circuits,” in Signals, Systems and Computers, 2006. ACSSC’06. Fortieth Asilomar Conference on. IEEE, 2006, pp. 1726–1729. [12] P. Kaur and B. S. Dhaliwal, “Design of fault tolearnt full adder/subtarctor using reversible gates,” in Computer Communication and Informatics (ICCCI), 2012 International Conference on. IEEE, 2012, pp. 1–5.

TABLE II: Comparative Experimental Results Of Various Parity Preserving Full Adder/Subtractor

F2G[12] MIG[6] Proposed Gate

Gate Count 9 5 2

Constant Input 9 5 2

Garbage Output 11 7 4

Area(μm)2 923.1 671.0 454.5

TABLE III: Comparative Experimental Results Of Various Parity Preserving 8-Bit Full Adder/Subtractor

F2G[12] MIG[6] Proposed Gate

Gate Count 67 37 16

Constant Input 67 37 17

Garbage Output 82 52 32

Area(μm)2 9860.5 7923.1 5289.1

VII. Conclusion and Future Work In this paper, a novel parity preserving reversible gate, P2RG and its applications were proposed. The proposed circuit was compared with the existing designs in terms of constant inputs, garbage outputs, and area. The constant inputs and garbage outputs are optimized. Area is improved by 50% for full adder/subtractor and 46.36% for 8-bit full adder/subtractor compared to the F2G gate while 32.26% of area is improved for full adder/subtractor and 33.24% of area is improved for 8-bit full adder/subtractor compared to the MIG gate. The design is better among all its existing Counterparts in terms of constant inputs, garbage outputs and area. Power calculated of the full adder/subtractor is 0.214milliwatt while power calculated of the same circuit using

888

Loading...