 Open Access
 Total Downloads : 89
 Authors : Pranay Kumar Saha
 Paper ID : IJERTV5IS100187
 Volume & Issue : Volume 05, Issue 10 (October 2016)
 DOI : http://dx.doi.org/10.17577/IJERTV5IS100187
 Published (First Online): 15102016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 raredundancy rnredundancy and rp redundancy in reversible circuit. A circuit is raredundant, 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 rnredundant, 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 rpredundant, 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, raRedundancy, rnRedundancy, rpredundancy, Missing Gate Fault.

INTRODUCTION
There are several types of logical redundancy such as a redundancy, bredundancy and credundancy in classical combinational circuit were studied by Hayes[5]. A network is aredundant 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 bredundancy. A network realizing a function F is said to be credundant if it is possible to obtain a subnetwork 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 credundancy includes both aredundancy and bredundancy 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 kCNOT gate into kÂ´CNOT gate, where k > kÂ´. The kkÂ´ 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 untestable 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 00> + 11>, where 0 and 1 are complex number called amplitude. Various physical realization based on trappedion 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 raredundancy, rnredundancy, 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.

PRELIMINARIES

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.

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 conjugatetranspose 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 (2CNOT) (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 controlledSWAP 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.

(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


TESTING METHOD
Most common fault models of reversible circuits are,
Single Missing Gate Fault Model (SMGF), Multiple Missing Gate Fault Model (MMGF), RepeatedGate Fault Model (RGF) and Partial MissingGate 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 kCNOT 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 kCNOT 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).

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.

raRedundancy in Reversible Circuits
A circuit is raredundant 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 raredundant 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).

raRedundancy 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 kCNOT 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.

(b)
Fig . 6 : (a) raredundancy 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 raredundant, if there is no test vector can detect the missing of a kCNOT gate from the circuit in presence of one or more single missing gate faults.
Proof : A kCNOT 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 kCNOT gate
i.e. the corresponding reversible circuit is raredundant circuit.


raRedundancy in Partial MissingGate Fault Model
A partial missinggate fault is a effect of partially misaligned or mistuned gate pulses [9].
Fig.7. Partial MissingGate 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 kCNOT gate, then the removal of this control bit cannot effect to the circuit output.
(a)
(b)
Fig . 8 : (a) raredundancy 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) raredundancy in PMGF (b) Unitary Matrix
Lemma 2: In a partial missing gate fault, the reversible circuit is raredundant, if control bit of a kCNOT gate is redundant.
Proof: A kCNOT 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 cj1. cj. cj+1… ck) t = (c1. c2. c3 cj1. cj+1… ck) t. i.e. the same output realize by the (k1) CNOT gate with the disappearance of c th control bit of kCNOT gate. So, there is no test vector for detecting the missing of c th control bit. So, the corresponding reversible circuit is raredundant circuit.

rnRedundancy in Reversible Circuits.
Two reversible circuits are rnequivalent 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.

(b)
Fig. 10 : Both (a) and (b) are rnequivalent circuit
A reversible circuit is called rnredundant, 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.

(b)
Fig . 11 : (a) rnredundancy in SMGF (b) Unitary Matrix

(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)

(c)

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



rpRedundancy in Reversible Circuits
Two reversible circuits are rpequivalent if one can be transformed to other by permuting of output terminals. A reversible circuit is called rpredundant, 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) : rpredundant 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 network2 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 subnetwork2 is redundant and the circuit in fig 14(a) is rpredundant circuit.

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.

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.


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
raredundancy
1
6Sym \ d#2
SMGF
raredundancy
1
9Sym \ d#2
SMGF
raredundancy
1
Mod5 \ d#2
SMGF
raredundancy
3
2 of 5 \ d#1
PMGF
raredundancy
1
4_49 \ d#3
SMGF
rnredundancy
1
Mod5 \ d#2
SMGF
rnredundancy
2
Mod5 \ d#3
SMGF
rnredundancy
1
5Mod5 \ d#3
SMGF
rnredundancy
2
5Mod5 \ d#4
SMGF
rnredundancy
2

CONCLUSION
Different types of redundancy, raredundancy, rn Redundancy, rpredundancy 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 rnredundancy 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

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

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.

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

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

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

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

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, quantph/0404003

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

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.

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

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