Toffoli Based Reversible Sequential Circuits

Toffoli Based Reversible Sequential Circuits

B. Anuradha1,

PG scholar Department f ECE, Karpagam University,

1. Sivakumar2, Assistant Professor Department Of ECE. Karpagam University,

   Abstract – A Number of fundamental principles of physics such as reversibility of dynamic laws is conservative logic. Conservative logic is reversible. Reversible logic is one of the emerging technologies and several researchers have focused their efforts on the design of reversible logic circuits. The design of reversible logic circuits is mostly used in Quantum Computing, Nano Technology and Low Power Digital Circuits. The number of garbage outputs and quantum cost depend upon reversible logic. Low power consumption, speed and delay are the major requirements in VLSI technology. In this paper, deals with the design of Toffoli gate based on Double edge Triggered Flipflop (DET). Toffoli gate is better than the Fredkin gate in terms of power consumption, number of gates and area. The proposed design of reversible sequential circuits using Toffoli gate are verified by using cadence simulation and the simulated results are presented.

   Keywords Conservative logic, Toffoli gate, Reversible logic, Feynman gate, Peres gate.

   1. INTRODUCTION

      Power dissipation is one of the most important factors in VLSI technologies. Heat is one of the factor that takes care in reversible circuits. In reversible circuits the input vectors are mapped to each output vectors. It is proved that zero energy dissipation is possible only if the gating network consists of reversible gates. Thus, the reversibility will become a future trend towards low power dissipating circuit design. One of the challenging tasks is to reduce these garbages and minimization of gate count.

      The Conservative logic is used for one to one mapping and it has equal number of ones as in the inputs and outputs. This logic may be reversible or irreversible in nature. Reversible circuits are desired using reversible gates that can generate unique output vector from each input. Reversible logic has been used in the recent years due to less heat dissipation. Reversible logic circuits are classified as reversible combinational and reversible sequential circuits. A reversible logic circuit is designed with minimum number of constant inputs and minimum number of reversible logic gates. Reversible logic is easier to test and improves the controllability and observability of the circuit. The basic principle of reversible computing means that there is no information is lost during computing process. From 1960s, reversible gates have been studied, the reversible gates dissipate less heat. Generally in normal gate, input states are not there and less information is present in the output compared to input. Because of thermodynamic entropy, this

      loss of information loses energy to the surrounding area in terms of heat. A reversible gate moves the states around since no information is lost and energy is conserved. More recent motivation comes from quantum computing. Quantum mechanics requires the transformations to be reversible but allows more general states of the computation. Thus, the reversible gates form a subset of gates allowed by quantum mechanics.

      In 1961, the scientist Landaulet said that each bit of information lost generates KTIn2 Joules of heat energy where K is the Boltzmanns constant and T is the Absolute Temperature. In 1973, Bennett showed that KTln2 energy dissipation would not occur if a computation is carried out in a reversible manner. For one input bit, there are two possible reversible gates. One of them is NOT gate and the other is identity gate which maps its input to the output,In first two input bits, the only non trivial gate is the controlled NOT gate which XORs the first bit to second bit and leaves the first bit unchanged.

      Some of the reversible gates are Feymann, Toffoli and Fredkin. According to Toffoli, sequential network is reversible if its combinational part is reversible. In this literature, the design of D latch using Toffoli gate, design of Testable negative enable Reversible D latch, using Toffoli gate, design of Testable Master slave Design of Master slave D Flipflops using Toffoli gate, design of Testable Reversible Double edge triggered (DET) flipflop using Toffoli gate are analyzed. The proposed technique is extended towards Master slave flipflops and design of Testable edge triggered (DET) flipflops.

      This paper is organized as follows: Section III presents Proposed Reversible Toffoli gate. Section IV describes the design of Toffoli based testable reversible latch. Section V deals with the design of Toffoli based Negative enable D latch. Section VI demonstrates the design of Toffoli based Master slave D flip-flop. Section VII describes the design of Toffoli based reversible double edge triggered (DET) FF. Section VIII Provides comparison chart of existing and proposed method. Section IX deals with results and conclusion

   2. BACK GROUND

      A gate is reversible if and only if the Boolean function is Bijective. It means that a reversible function f:(x1,x2,..xn) to (y1,y2,.yn). It satisfies that the condition of one to one and onto mapping between the input and output domains. A set of

      reversible gates is needed to synthesize reversible circuits. There are objectives in reversible circuit. They are synthesis, number of gates and minimize the number of garbage outputs. The fault patterns in the conservative reversible gates are analyzed [3]. A testing technique requires only a constant number of test vectors to achieve 100% fault coverage [6]. Toffoli gate and Peres gate are designed using reversible D latch and D flipflop with asynchronous set/reset capability [14].

      2.1. Related work

      The design of Reversible sequential circuits is addressed in various contribution in which the designs are optimized in terms of various parameters. They are listed as delay, garbage output and number of reversible gates. The reversible logic synthesis which are used in reversible gates are Feynman and Toffoli gates. Fan out problem is avoided by using Feynman gate. One of the major issues in designing a reversible circuit is garbage minimization [10]. In this literature Toffoli gate is designed in D latch, Master slave flipflop and Double edge triggered flipflop. Toffoli gate is tested in two mode of operation compared to previous literature. By using Toffoli gate, the number of gates and the power consumption are less. Delay calculations are based on the logical depth as measure of the delay.

   3. PROPOSED REVERSIBLE TOFFOLI GATE Toffoli gate was proposed by Toffoli in 1980. This gate has

      3 bit inputs and outputs. If the first two bits are set,then flip the

      third bit. Each input of Toffoli gate is mapped to each output. The Toffoli gate is universal, for any Boolear function F (x1,x2, –xm) There is a circuit consisting of Toffoli gates which takes X1, X2, —-Xm and some extra bits set to 0 or 1 and outputs X1, X2, —-Xm,F(X1, X2, —-Xm ) and some extra bits (called garbages). A Toffoli gate can be generalized as Tof(C,T) where C is a set of control variables{x1,x2,..xn- 1},T is the target variable{xn}. A Toffoli gate has three inputs and three outputs, where A,B and C are inputs, which are mapped to the three outputs (P=A,Q=B,R=A.B C). Toffoli gate is one of the most popular reversible gates and has quantum cost of 5. Toffoli is a universal reversible logic gate which means that any reversible circuit can be constructed from Toffoli gates. It is also known ascontrolled-controlled NOTgate which describes its action.

      Fig Toffoli gate logic design

      Fig 2 Toffoli gate

      TABLE 1 TRUTH TABLE

      Input			Output
      0	0	0	0	0	0
      0	0	1	0	0	1
      0	1	0	0	1	0
      1	0	0	1	0	0
      1	0	1	1	0	1
      1	1	0	1	1	1
      1	1	1	1	1	0

   4. DESIGN OF TESTABLE REVERSIBLE LATCHES

      When the enable signal is 1, then the value of D is obtained at the output Q+=D. When the enable signal is 0, the latch maintains the previous state Q+=Q.

      Fig 3 Toffoli gate based D latch

      Fig 4 Toffoli gate based D latch with Control signals C1 and C2

      Fig 5 Toffoli gate based D latch in Normal mode

      Fig 6 Toffoli gate based D latch in Test mode with control signal as 1

      Fig 7 Toffoli gate based D latch in test mode with control signal as 0

      In this paper, the work is proposed to cascade another Toffoli gate to output Q. The design can work in two modes, Normal mode and Test mode. In Normal mode, the control signal which has the value of C1C2=01. The design works as D latch without any changes in glitches. In test mode the control signals are C1C2=00, the output is having some shift in the glitches compared to normal mode.

   5. DESIGN OF TOFFOLI BASED NEGATIVE

      ENABLE D LATCH

      In this, latch two Toffoli gate is used. When enable is Zero, a negative enable reversible D latch will pass Input D to the output Q. Otherwise, it maintains the same state. The control signals C1 and C2 are connected.

      Fig 8 Toffoli gate based negative enable testable D latch

      The output of second Toffoli gate is given as input to the first Toffoli gate. The Negative enable D latch is used in the design of Testable reversible Master slave flip flop.

   6. DESIGN OF TOFFOLI BASED MASTER SLAVE

      D FLIPFLOP

      In existing literature, the Fredkin gate is used in the Master slave D flipflop. In proposed literature, Toffoli gate is used. The output follows the same as the inputs. The testable reversible D flipflops using Toffoli gate has four control signals mC1,mC2,sC1and sC2,mC1 and mC2 control modes for the master latch. sC1,and sC2 control the modes for slave latch. The positive enable Toffoli gate based testable D latch acts as a

      master latch.Whereas, the negative enable Toffoli gate based testable D latch acts as a slave latch. In Toffoli gate, it will select either the Master or slave circuit at time by considering the enable input. When enable is Zero, then slave circuit mT2 and sT2 is zero else mT2,sT2 works accordingly. It operates in two modes normal mode and test mode. In normal mode the value of control signal mC1=0 and mC2=1 for master circuit, the value of control signal for slave circuit is sC1=0 and sC2=1.

      In Test mode the value of control signal will be mC1=0 and mC2=0,sC1=0 and sC2=0 or mC1=1 and mC2=1,sC1=1 and sC2=1. In both modes, there will be a shift in the glitches obtained in the output.

      Fig 9 Toffoli gate based master slave D Flipflop.

   7. DESIGN OF TOFFOLI BASED REVERSIBLE DET

      FLIPFLOP

      In the previous work, the Fredkin gate is used in DET flipflop,it samples and stores input data at both edge. While using Toffoli gate in DET flipflop, When enable is one the master stores the input and the slave remains in the previous state. When enable is zero, the master is in storage state, while slave passes the output, since, it waits for the next rising edge of the latch. In double edge triggered, it can receive data at both edges that can sample and receive two data values in a clock period. When data rate is same, the frequency is half of the total frequency.

      Fig 10 Toffoli gate based DET flip flop

      Fig 11 Normal mode

      Fig 12 Test mode with control signals as 0

      Fig 13 Test mode with control signals as 1.

      In this work, Toffoli gate is proposed. When a2=0, the pT1 and nT1 work accordingly and pT2 and nT2 wont work and give the zero output, because the frequency is proportional to power consumption. The Toffoli gate labeled as 1 and 2 forms the positive enable testable D latch, while the Toffoli gate labeled as 3 and 4 forms the negative enable testable D latch. The Toffoli gate labeled as 5 works as 2:1 MUX and transfer the output from one of the testable latches that is in storage state to the output Q. It works in normal mode and test mode. In normal mode, the value of control signal is pC1=0 and pC2=1, nC1=0 and nC2=1. In test mode, it works in zero input and one input. The output is tested for two modes. The resulted output is shift in the glitches.

   8. COMPARISON CHART TABLE 2

      FREDKIN AND TOFFOLI BLOCKS

      TABLE 3

      FREDKIN D LATCH CONTROL SIGNAL AND TOFFOLI D LATCH CONTROL SIGNAL

      Parameters	Existing System (Fredkin )	Proposed System (Toffoli)
      Power	2698.533nw	1718.990nw
      No of Gates	4	2
      Area	53	33.264mm

      TABLE 4

      FREDKIN NEGATIVE ENABLE D LATCH AND TOFFOLI NEGATIVE ENABLE D LATCH

      Parameters	Existing System (Fredkin )	Proposed System (Toffoli)
      Power	4560.404nw	4254.809nw
      No of Gates	4	2
      Area	93	33

      TABLE 5

      FREDKIN MASTER SLAVE D FLIPFLOP AND TOFFOLI MASTER SLAVE D FLIPFLOP

      Parameters	Existing System (Fredkin )	Proposed System (Toffoli)
      Power	8614.477nw	6882.843nw
      No of Gates	8	7
      Area	160	133

      TABLE 6

      Parameters	Existing System (Fredkin )	Proposed System (Toffoli)
      Power	12682.377nw	12013.885nw
      No of Gates	11	9
      Area	213	193

      FREDKIN DET FLIPFLOP AND TOFFOLI DET FLIPFLOP

      Parameters	Existing System (Fredkin )	Proposed System (Toffoli)
      Power	2698.533nw	1718.990nw
      No of Gates	2	2
      Area	53	33.264mm

   9. RESULTS AND CONCLUSION

      Fig 14 Output waveform of Toffoli

      Fig 15 Output waveform Toffoli D latch control signal

      Fig 16 Output waveform Negative enable D latch

      Fig 17 Output waveform of Master slave D Flipflop in normal mode

      Fig 18 Output waveform of Master slave D Flipflop in Test mode

      Fig 19 Output waveform of DET Normal mode

      Fig 20 Output waveform of DET Test mode

      In fig 14, Output waveform is obtained by testing the various values of input using Toffoli gate. In fig 15 and fig 16 D latch is tested when enabe is 1 or 0, output is tested for two modes of operation. In fig 17 and fig 18 output is tested for master slave and DET in normal mode and test mode by giving various values of control signals. The DET normal mode and Test mode are described with 0 enable signal in fig 19 and fig 20.

      Table 2 summarizes power and area are better in Toffoli gate compared to Fredkin gate.

      Table 3 describes power consumption, number of gates and areas in proposed system are better than power consumption in existing system.

      Table 4 demonstrates power, number of gates and areas in proposed system are better than the existing system.

      Table 5 explains power, number of gates and area in proposed system is better than the existing system.

      Table 6 summarizes power, number of gates and areas in proposed system are better than the existing system.

   10. CONCLUSION

Reversible logic circuits avoid energy loss by uncomputing. The computed information recycles the energy in the system. Some of the reversible gates are Feynman, Toffoli and Peres. In this literature uses the Toffoli gate. In this work, the design of Master slave D flipflop and DET flipflop in terms of Toffoli gate are designed and utilizes the reversible circuits and optimized. It analyses the glitches in both test mode and normal mode of operation. The proposed design is better than the existing design in terms of power consumption, number of gates and area. In future works as, using reversible gates,memory design and Adders can be designed.

REFERENCES

[1]. Sivakumar Sastra Hari,Shyam Shroff,v.Kamakoti,"Efficient Building blocks for reversible sequential circuit design Indian Institute of Technology,pp.437- 441,2006.

[2]. Min-lun Chunang, Chun-yao Wang,"Synthesis of Reversible sequential elements National Tsing Hua university, pp.420-425, 2007.

[3]. E.Fredkin and T.Toffoli,"Conservativelogic", int.j.theor, phys., pp.219- 253, 1982.

[4]. M.Hasan, A.Islam and A.Chowdhury,"Design and analysis of online testability of reversible sequential circuits", in proc, int, conf.comput.inf.technol, pp.180-185, Dec 2009.

[5]. X.Ma, J.Huang, c.Metra and F.lombardbi, "Reversible gates and testability of one dimensional arrays of molecular QCA", J.Electr, test., pp.1244-1245,Jan 2008.

[6]. P.Kartschoke,"Implementation issues in conservative logic networks,"M.S.thesis, Dept.Electr.Eng. univ.virginia, Charlottesville, 1992.

[7]. H.Thapiyal and N.Ranganathan,Design of reversible sequential circuits optimizing quantum cost, delay and garbage outputs,ACM J Emerg technol,comput.syst.,vol.6,no.4,Dec 2010

[8]. S.Mahammad and K.Veezhinathan,"constructing online testable circuits using reversible logic", IEEE trans,Instrum,meas.,pp.101-109,Jan 2010.

[9]. Dilip p.vasudevan,parag k.lala,Jia Di and Patrick Paterson,Reversible logic design with online testability,IEEE trans,Vol.55,No.2,Apr 2006

[10]. Himanshuthapiyal, Nagarajan Ranganathan,Reversible logic based concurrently testable latches for molecular QCAvol.9, IEEE trans, Jan 2010.

[11]. M.B Tahoori, J.Huang, M.Momenzadeh and F.Lombardi,Testing of Quantum cellular automata, IEEE trans.Nanotechnol, vol.3, no.4, pp.432-442, Dec 2004.

[12]. SheenuThapar,ParminderKaur,Nidhisyal,Multiplier circuit based on Reversibility principle,IRAST vol.2,No,4,Aug 2012

[13]. H.Thapiyal, M.B.Srinivas and M.Zwolinski"A beginning in the reversible logic synthesis of sequential circuits, in proc, int, conf, military aerospace program logic devices, pp.1-5, sep 2005.

[14]. M.Pedrum, Q.Wu, and X.Wu,"A New design for double edge triggered flipflops",in proc.Asia south pacific design Autom,conf.,pp-417- 421,1998.