Various Type of Redundancy in Reversible Circuit

Various Type of Redundancy in Reversible Circuit

Pranay Kumar Saha

Dept. of Computer Sc. & Technology,

B. P. C. Institute of Technology Krishnagar, Nadia, W.B., India

Abstract – Reversible logic plays an important role in quantum computing. Reversible circuits are a special case of quantum circuits because quantum computations are inherently reversible in nature. Various types of redundancies may can occur in a reversible circuit are investigated in the single missing gate fault model, partial missing gate fault model and multiple missing gate fault model of a reversible circuit. Missing gate fault model of the reversible circuit is technology independent. This paper shows that redundancy is possible in reversible circuit. This paper presents three kind of redundancy called ra-redundancy rn-redundancy and rp- redundancy in reversible circuit. A circuit is ra-redundant, if it is possible to remove control bit or gate in such a way that the resulting circuit behave as a fault free circuit in presence of partial or single missing gate fault. A reversible circuit is called rn-redundant, if it is possible to realize the same output by inverting some input literals, in the presence of single missing gate fault in the reversible circuit. A reversible circuit is called rp-redundant, if it is possible to realize the same output by permuting the output terminals in presence of multiple missing gate fault. A detectable fault become undetectable in presence of another undetectable fault. This type of redundant fault is also possible in reversible circuit.

Keywords : Reversible Circuit, ra-Redundancy, rn-Redundancy, rp-redundancy, Missing Gate Fault.

1. INTRODUCTION

   There are several types of logical redundancy such as a- redundancy, b-redundancy and c-redundancy in classical combinational circuit were studied by Hayes[5]. A network is a-redundant if it is possible to remove lines and gates from the circuit network in such a way that the resulting circuit network behaves same as previous. When any line in a circuit contains two or more consecutive inverters, then circuit is said to have b-redundancy. A network realizing a function F is said to be c-redundant if it is possible to obtain a sub-network by cutting some r lines in the network and then connecting some q lines among those r lines to any signal sources such that the reduced network also realize F. The c-redundancy includes both a-redundancy and b-redundancy as special case in classical combinational circuit. Reversible logic plays an important role in quantum computing. Reversible circuits are a special case of quantum circuits because quantum computations are inherently reversible in nature [3], [4]. Quantum circuits offer a new kind of computation. Here qubits instead of traditional bits are used that allow representing not only 0 and 1 but also superposition of both. As a result, qubit can represent multiple states at the same time enabling enormous speed- ups in computation. Even if research in the domain of quantum circuits is still at the beginning, first quantum circuit have already been built. Reversible

   logic is important in this area, because every quantum operation is inherently reversible. Thus progress in the domain of reversible logic can directly be applied to quantum logic. Most of gates are used in classical digital system are not reversible. The Controlled NOT(CNOT) proposed by Feynman[2], Toffoli[7], and Fredkin[1] gates are well known reversible gates that needed to design the reversible circuits. There are many types of algorithms for reversible circuits synthesis have studied in [8][10][11]. Recently several researchers have studied the different fault models. Polian et al has presented [6][9] single missing gate, multiple missing gate, partial missing gate and repeated missing gate fault models. A single missing gate fault (SMGF) is defined by complete disappearance of single CNOT gate from a reversible circuit. The pulse implementation of the gate operation is short, missing, misaligned or mistuned[9] are the physical justification of a SMGF. The multiple missing gate fault (MMGF) is defined as that the several consecutive gate are missing from the circuit[9]. A partial missing gate fault (PMGF) is a result of partially misaligned or mistuned gate pulses. A PMGF turns a k-CNOT gate into k´-CNOT gate, where k > k´. The k-k´ is known as order of a PMGF[9]. A repeated gate fault (RGF) is an unwanted replacement of a CNOT gate by several instances of the same gate[9]. If no test vectors exist for a fault, then that fault is known as an un- testable fault. An un-testable fault in a reversible circuit is known as a redundant fault because it does not change the input output of the circuit. The unit of quantum information is called a qubit. A qubit can be in a zero or a one state represented by |0> or |1> respectively and superposition of these states, represented by 0|0> + 1|1>, where 0 and 1 are complex number called amplitude. Various physical realization based on trapped-ion technology which uses the certain spin and vibration modes of electrically charged ions as the qubit representation. Quantum computation can solve exponentially hard problems in polynomial time [4]. The paper proposes that various types of redundancies may be present in a single, partial and multiple missing gate fault model of the reversible circuit. These various types of redundancies are called ra-redundancy, rn-redundancy, rp- redundancy and second generation redundancy in a reversible circuit. Although, actual implementation of the redundancies are yet to be established but the results may be applicable to the missing gate fault model or future immerging technologies of reversible logic circuit. Different type of redundant fault is also possible in reversible circuit. Identification of different type of redundancy play an important role to synthesis of irredundant reversible circuit.

2. PRELIMINARIES

   1. Reversible Gate/Circuit

      A gate is reversible, if the mapping from input set to output set is bijective. Thus every distinct inputs gives a distinct output. This bijective mapping from a unique input set to corresponding unique output set implies that a reversible circuit contain the same number of inputs and outputs. A reversible circuit having n number of inputs and n number of outputs is called n x n reversible circuit.

   2. Unitary Matrix

      A unitary matrix is a square matrix U whose entries are complex numbers and whose inverse is equal to its conjugate transpose U*. That means that U*U = UU* = I, where U* is the conjugate-transpose of U and I is the identity matrix. The most common reversible gates operate on spaces of one or two qubits, just like the common classical logic gates operate over one or two bits. This means that as matrices, reversible gates can be described by 2 × 2 or 4 × 4 unitary matrices. The NOT (Fig.1) is a one input one output gate. It inverts the input. The CNOT gate (Fig..2 ) is a 2×2 gate. The value at the first input is left unchanged and the value on the second input is inverted if and only if the value at the first input is 1, else remains unchanged. The Toffoli gate (2-CNOT) (Fig.3) is a 3×3 gate. It passes the first two inputs through and inverts third if the first two are both 1, else remain unchanged and a Fredkin gate(Fig.4) is a 3×3 reversible gate. It is a controlled-SWAP gate. It passes the first input through. If the first input is 0, passes the second and third inputs through, otherwise swap the second and third inputs.

      1. (b) (c)

   Fig.1 : NOT gate representation (a) Symbol, b) Truth table and

   (c) Unitary Matrix

   (a) (b) (c)

   Fig. 2 : CNOT gate representation (a) Symbol, (b) Truth table and

   (c) Unitary Matrix

   Fig. 3 :2- CNOT gate representation (a) Symbol, (b) Truth table and

   (c) Unitary Matrix

   Fig. 4 Fredkin gate representation (a) Symbol, (b) Truth table and

   (c) Unitary Matrix

3. TESTING METHOD

   Most common fault models of reversible circuits are,

   Single Missing Gate Fault Model (SMGF), Multiple Missing Gate Fault Model (MMGF), Repeated-Gate Fault Model (RGF) and Partial Missing-Gate Fault Model (PMGF). A Single Missing Gate Fault (SMGF) corresponds to the missing gate fault discuss in [9]. A Multiple Missing Gate Fault (MMGF) is the disappearance of two or more consecutive gate from the reversible circuit[9]. A Repeated Gate Fault (RGF) is an unwanted replacement of a k-CNOT gate by several instance of the same gate[9]. A Partial Missing Gate Fault (PMGF) is define by the missing of control bit of a gate from the circuit, as a result a k-CNOT gate turns into a k´-CNOT gate, where k´< k [9]. A fault set F, generates a set of test vectors T that can be used to detect all faults of the reversible circuit. Such a test set is said to be complete test set. Single test vector is necessary and sufficient to detect single missing gate fault in a reversible circuit.

   Fig. 5. Single Missing Gate Fault

   Last gate is missing in the 3_17tc reversible benchmark circuit (shown in fig. 5). Test vector 110 can detect that single missing gate fault. All the single missing gate faults of the circuit are detected by single test vector (110).

4. PROPOSED REDUNDANCY IN REVERSIBLE CIRCUIT

   The faulty output will remain same as fault free output, if we introduce some missing gate faults in a reversible circuit.

   1. ra-Redundancy in Reversible Circuits

      A circuit is ra-redundant if it is possible to remove control bit or gate in such a way that the resulting circuit behave as a fault free circuit by introducing some missing gate faults (MGF) in the circuit. In other word a circuit network N N(Z) is ra-redundant if it is possible to remove control bit or gate from N in such a way that the resulting circuit network N is in N(Z).

   2. ra-Redundancy in Single Missing Gate Fault Model

      A single missing gate fault model is the complete disappearance of one gate from the circuit i.e. the pulse (s) implementing the operation of the gate is missing or mistuned. A k-CNOT gate has k control inputs and one target input. The removal of a gate from the reversible circuit cannot effect to the circuit output. If any one control bit is always zero, then the removal of that gate can not effect to the circuit output. i.e. single missing gate fault (SMGF) is undetectable.

      1. (b)

         Fig . 6 : (a) ra-redundancy in SMGF (b) Unitary Matrix

         Fig. 6a and Fig. 6b shows a reversible circuit and corresponding Unitary matrix respectively. The SMGF occur by disappearance of gate G in fig 6a. The corresponding Unitary matrix for the faulty circuit is same as in fig. 6b. No test vectors can detect the missing of the gate G of the reversible circuit shown in fig.6a.

         Lemma 1: The reversible circuit is ra-redundant, if there is no test vector can detect the missing of a k-CNOT gate from the circuit in presence of one or more single missing gate faults.

         Proof : A k-CNOT gate having k control bits ci where i = 1,2,3,..k and one target bit t. By the property of reversible gate, the values of control input are left unchanged and the values of target input is inverted if and only if all the values of control inputs are 1. i.e. the output of target bit tout = (c1. c2. c3.. ck) t. If cj = 0, 1 j k then tout = 0 t = t i.e. in this case, output of the circuit is always same as disappearance of the gate. Hence no test vector can detect the missing of that type of k-CNOT gate

         i.e. the corresponding reversible circuit is ra-redundant circuit.

   3. ra-Redundancy in Partial Missing-Gate Fault Model

   A partial missing-gate fault is a effect of partially misaligned or mistuned gate pulses [9].

   Fig.7. Partial Missing-Gate Fault

   The test vector (101) can detect the partial missing gate fault of the 3_17tc reversible benchmark circuit(shown in Fig.7). Similarly the test vector (110) can also detect the fault of the first control input of the last gate. Two test vectors are sufficient to detect the partial missing gate fault, which is equal to the maximum number of control inputs of largest gate of the circuit. If a control bit is set to the logic 1 in a k-CNOT gate, then the removal of this control bit cannot effect to the circuit output.

   (a)

   (b)

   Fig . 8 : (a) ra-redundancy in PMGF (b) Unitary Matrix

   Fig 8a and Fig 8b shows a reversible circuit and corresponding Unitary matrix respectively. The PMGF occur by disappearance of control bit C in Fig 8a. The corresponding Unitary matrix for the faulty circuit is same as in Fig 8b. No test vectors can detect the missing of the control bit of the reversible circuit shown in Fig.8a in presence of the partial missing gate fault (PMGF).

   Fig 9a and Fig 9b shows a reversible circuit and corresponding Unitary matrix respectively. If any one control bit among the control bit C1, C2 & C3 or both control bits C1 & C2 are missing from the circuit shown in Fig.9a, the corresponding Unitary matrix for the faulty circuit will remain same as in Fig 9b.

   (a)

   (b)

   Fig . 9 : (a) ra-redundancy in PMGF (b) Unitary Matrix

   Lemma 2: In a partial missing gate fault, the reversible circuit is ra-redundant, if control bit of a k-CNOT gate is redundant.

   Proof: A k-CNOT gate having k control bits ci, where i = 1,2,3,., k and one target bit t. By the property of reversible gate, the values of control input is left unchanged and the values of target input is inverted if and only if all the values of control inputs are 1. i.e. the output of target bit tout = (c1. c2. c3.. ck) t. Let cj is redundant control bit.

   j

   j

   j

   j

   Now tout = (c1. c2. c3 cj-1. cj. cj+1… ck) t = (c1. c2. c3 cj-1. cj+1… ck) t. i.e. the same output realize by the (k-1) CNOT gate with the disappearance of c th control bit of k-CNOT gate. So, there is no test vector for detecting the missing of c th control bit. So, the corresponding reversible circuit is ra-redundant circuit.

   1. rn-Redundancy in Reversible Circuits.

      Two reversible circuits are rn-equivalent if one can be transformed to other by negation of one or more input literals. The circuits in Fig.10(a) and Fig 10(b) are rn- equivalent.

      1. (b)

         Fig. 10 : Both (a) and (b) are rn-equivalent circuit

         A reversible circuit is called rn-redundant, if it is possible to realize the same output by inverting one or more input literals, in the presence of certain missing gate faults in the reversible circuit.

         1. (b)

            Fig . 11 : (a) rn-redundancy in SMGF (b) Unitary Matrix

            1. (b)

               Fig . 12 : (a) Faulty Circuit and corresponding (b) Unitary Matrix

               Fig 11a and Fig 11b shows a reversible circuit and corresponding Unitary matrix respectively. After introducing the some SMGF by the missing of the gate G in Fig 11a, the faulty circuit is shown in Fig 12a and the corresponding Unitary matrix is shown in Fig 12b. If the literal c is negated in faulty circuit (Fig.12a), original fault free output is restored. Fault made by disappearance of first gate of the circuit in Fig 11a. i.e. the reversible circuit is rn- redundant.

               Fig 13a and Fig 13b shows a reversible benchmark circuit main\4_49\design#3 and corresponding Unitary matrix respectively. After introducing some SMGF by the missing of the gate G in Fig 13a, the corresponding Unitary matrix of the faulty circuit is shown in Fig 13c. If the literal a is negated in faulty Unitary matrix ( Fig 13c) we restored the Unitary matrix as in Fig 13b. i.e. the fault i rn- redundant fault.

               (a)

            2. (c)

         Fig . 13 : (a) rn-redundant reversible circuit, (b) Unitary Matrix and ( c ) Unitary matrix of faulty circuit

   2. rp-Redundancy in Reversible Circuits

      Two reversible circuits are rp-equivalent if one can be transformed to other by permuting of output terminals. A reversible circuit is called rp-redundant, if it is possible to realize the same unitary matrix by permuting output terminals, in the presence of certain multiple missing gate faults in the reversible circuit.

      Fig. 14(a) : rp-redundant reversible circuit

      Fig. 14(b) : Faulty circuit

      Fig 14(a) shows an reversible circuit and corresponding outputs are O1, O2 and O3 respectively. After introducing some MMGF by the missing of the multiple gate of sub- network-2 in fig 14(a) we get the faulty circuit shown in fig 14(b) and corresponding outputs are O2, O3 and O1 respectively. It is observe that if we permute the outputs of the faulty circuit we realize the unitary matrix corresponding to fault free circuit. So, the sub-network-2 is redundant and the circuit in fig 14(a) is rp-redundant circuit.

   3. Second Generation Redundancy Definition

      If f is detectible fault and g is undetectable fault, then f become undetectable in presence of g. Such a fault f is called second generation redundant fault.

      Fig. 15 : Second Generation redundant circuit

      In fig 15 the test vector 1011 can detect the Partial Missing Gate Fault (PMGF) for the missing of control bit C1. So, this PMGF is detectable fault. On the other hand, if we miss the control bit C2, there is no test vector, so this PMGF is undetectable fault. If we miss both control bit C1 and C2, there is no test vector, to detecting the fault for missing the both control bit C1 and C2. Hence, the detectable fault for missing control bit C1 is become undetectable in presence of another undetectable fault for missing control bit C2. So, the PMGF for missing control bit C1 is second generation redundant fault.

   4. Another type of Redundancy (Definition)

   Two undetectable single fault f and g may become detectable if both fault simultaneously present in the circuit. In other word the multiple fault { f, g } may be detectable even its single fault components are not.

   Fig. 16 : Another type redundant circuit

   In the fig 16, if we miss the control bit C1, there is no test vector to detecting this fault. Similarly, if we miss the control bit C2, there is no test vector to detecting the fault. Hence both fault are undetectable, i.e. redundant fault. Further if we miss the control bits both C1 and C2, the test vector 1001 can detect this multiple fault. So, the fault missing of control bits both C1 and C2 detectable even the fault by missing of control bit C1 or C2 are undetectable.

5. EXPERIMENTAL RESULT

   This paper present different types of redundancy in reversible circuit. Column 1,2,3 and 4 of table 1 represent the different type of reversible bench mark circuit, type of fault, type of redundancy and number of redundant gate or control bit respectively.

   Table 1 Experimental result

   Benchmark Circuit	Type of Fault	Type of Redundancy	No of redundant Gate / Control bit
   2 of 5 \ d#2	SMGF	ra-redundancy	1
   6Sym \ d#2	SMGF	ra-redundancy	1
   9Sym \ d#2	SMGF	ra-redundancy	1
   Mod5 \ d#2	SMGF	ra-redundancy	3
   2 of 5 \ d#1	PMGF	ra-redundancy	1
   4_49 \ d#3	SMGF	rn-redundancy	1
   Mod5 \ d#2	SMGF	rn-redundancy	2
   Mod5 \ d#3	SMGF	rn-redundancy	1
   5Mod5 \ d#3	SMGF	rn-redundancy	2
   5Mod5 \ d#4	SMGF	rn-redundancy	2

6. CONCLUSION

Different types of redundancy, ra-redundancy, rn- Redundancy, rp-redundancy and second generation redundancy have been introduced in a reversible circuit. ra- redundancy shows some bizarre effects in a single and partial missing gate fault model and rn-redundancy show some bizarre effects in a single missing gate fault model of the reversible circuit. Currently, we are investigating on the effect of such redundancy in the reversible cyclic combinational circuit. Removal of redundant gate / control bit may increase / decrease quantum cost of the circuit. Presently we are investigating the relationship between redundancy and quantum cost of a reversible circuit and novel synthesis of irredundant reversible circuit.

REFERENCES

1. A. De Vos, B. Desoete, A. Adamski, P. Pietrzak, M. Sibinski and T. widerski:, Design of reversible logic circuits by means of control gates, In: D. Soudris, P. Pirsch and E. Barke (eds.): Procedings10th International Workshop Patmos, Gottingen (Sept. 2000) 255- 264

2. D. Vion, A. Aassime, A. Cottet, P. Joyez, H. Pothier, C. Urbina, D.Esteve, M. H. Devoret, Manipulating the Quantum State of an Electrical Circuit, arXiv:cond- mat/0304232, V2 15 Apr 2003.

3. J. Han, P. Jonker, A System Architecture Solution of Unreliable Nanoelectronic Devices, IEEE Transaction On Nanotechnology, Vol. 1, December 2002 pp. 201-208.

4. J. Kim, J-S. Lee, S. Lee and C. Cheong, Implementation of the redined Deutsch-Jozsa algorithm on a 3-bit NMR quantum computer, Phys. Rev. A 62, 022312 (2000)

5. John P. Hayes On the Properties of Irredundant logic Networks, IEEE Transactions on Computers, September 1976.

6. J. P Hayes, I. Polian, B. Becker, Testing for Missing-Gate Faults in Reversible Circuits, Proc. Asian Test Symposium, Taiwan, November 2004.

7. K. N. Patel, J. P. Hayes and I. L. Markov., Fault testing for Reversible circuits, IEEE Transaction On CAD, 23(8), pp. 1220- 1230, August 2004, quant-ph/0404003

8. M. Saeedi, M. Sedighi, M. Saheb Zamani, A Novel synthesis algorithm for Reversible Circuits, ACM International Conference on CAD, 2007.

9. Polian I., Hayes J.P., Fiehn T., Becker B., A Family of Logical Fault Models for Reversible Circuits, Asian Test Symp., pp. 422- 427, December 2005.

10. Saeedi, M. Saheb Zamani, M. Sedigh, On the Behavior of Substitution Based Reversible Circuits Synthesis Algorithms: Investigating and Improvement, ISVLSI, 2007.

11. V.V.Shende, A.K.Prasad, I.L.Markov and J.P.Hayes, Synthesis of Reversible Logic Circuits, TCAD, Vol. 22(6), pp.710-722, 2003.