An Extended Approach for Online Testing of Reversible Circuits

IOSR Journal of Computer Engineering (IOSR-JCE)
e-ISSN: 2278-0661, p- ISSN: 2278-8727Volume 16, Issue 1, Ver. I (Jan. 2014), PP 01-11
www.iosrjournals.org
www.iosrjournals.org 1 | Page
An Extended Approach for Online Testing of Reversible Circuits
Anugrah Jain1
, Nitin Purohit2
, Sushil Chandra Jain3
1, 3
(Department of Computer Engineering, Rajasthan Technical University, Kota, India)
2
(Department of Computer Engineering, MNIT, Jaipur, India)
Abstract : Reversible computing has tremendous benefits in terms of power consumption, less heat dissipation
and packaging density. Because its applications are found in diverse fields including quantum computing,
nanotechnology, low power CMOS designs and cryptography, Reversible computing has gained attraction of
many researchers recently. In order to incorporate fault testing capability in reversible circuits, a number of
offline and online approaches have been proposed. In order to extend online testability of reversible circuits, an
analysis followed by a Peres gate substitution is presented here. The proposed extension has identified online
testing capabilities of MCF gates and has made all available libraries including MCT+MCF, MCT+P online
testable. Furthermore a conversion for parity-preserving reversible circuits is presented. Finally the paper is
concluded by proposing a generic online testable substitution of n*n reversible gate.
Keywords: reversible circuits, online testable reversible circuits, online testable reversible substitution
I. INTRODUCTION
Reversible computing has emerged as a possible low cost alternative to conventional computing in
terms of speed, power consumption, and computing capability. According to Landauer [1] in 1961, every
operation performed by a conventional computer dissipates at least kTln2 amount of energy for every erasure of
bits, where k is the Boltzmann constant and T is the temperature where computation is performed. Reversible
circuits are capable to provide less or almost zero heat dissipation [2]. With providing low power VLSI designs,
this sort of computing has interesting applications in various areas including quantum computing
nanotechnology, cryptography, bioinformatics etc.
Reversible computing is the application of principle of recycling to the computing. It is based on the
fact that input can be reconstructed from output. In other means a bijective function is used for mapping of input
vectors to output vectors. A number of reversible gates that support bijective mapping have been proposed in
literature and circuits have been built around using these gates. Fault tolerance enables a system to continue
operating in the event of failure of some of its components. Like conventional circuits, the reversible circuits
should also be protected from faults. In consequences several fault models and testing approaches have been
proposed in the literature. Depending on their detection time, these approaches have been categorized into
offline and online.
This paper extends an existing online testing approach by proposing a testable substitution of the Peres
gate. The proposed extension including Peres gate substitution identifies online testing capabilities of MCF
gates and makes all MCF-Peres based reversible circuits online testable. Then a methodology for transforming a
parity-preserving reversible circuit into an online testable reversible circuit is presented. Finally an online
testable reversible substitution of n*n reversible gate is given.
II. BACKGROUND
A. General Reversible Gates
An n*n reversible gate performs bijective mapping between n input vectors and n output vectors.
Means all input vectors are uniquely maps to some output vector and the gate generates a permutation of input
vectors in their output. Unlike conventional irreversible gates, their output can be used to construct the input.
Reversible gates commonly reported in literature are described as follows:
1) Multiple Control Toffoli
A multiple control Toffoli (MCT) gate is a generalized Toffoli gate defined for m control lines and 1
target line makes total n = m + 1 lines [3]. The gate maps input vectors (I1, I2…..Im) to output vectors (O1,
O2…..Om) with same values for control lines and On can be obtained by operation I1I2….In-1⊕In as shown in
Fig. 1(a). A Generalized MCT is defined as Cm
NOT gate. A NOT gate is a generalized Toffoli gate with no
control lines (i.e. m = 0). The CNOT gate, also known as Feynman gate is an MCT gate with only one control
line (for m = 1). The well known Toffoli gate with two control lines is known as C2
NOT gate.

2) Multiple Control Fredkin
A Multiple-Control Fredkin (MCF) gate is a generalized Fredkin gate which has some control lines and
two target lines [3]. The values on target lines are interchanged with each other iff all control lines have value 1
at their inputs. For n-bit MCF, there are m control lines and two target lines makes total n = m + 2 lines. This
gate with no control lines is known as Swap gate. An n*n multiple-control Fredkin gate is as shown in Fig. 1(b).
3) Peres
A Peres gate is a 3*3 reversible gate which has quantum cost of only 4 [4]. This gate maps input
vectors (I1,I2,I3) to output vectors (O1,O2,O3) where, O1 = I1, O2 = I1⊕I2 and O3 = I1I2⊕I3 respectively. Fig. 1(c)
shows a 3*3 Peres gate.
(a) n-bit MCT gate (b) n-bit MCF gate (c) Peres gate
Figure 1: General Reversible Gates
B. Other Reversible Gates
Some other reversible gates are found in literature for enhancing the performance of reversible circuits
in different areas. These gates include:
1) Negative Control Toffoli
A negative control Toffoli (NCT) gate is an MCT gate which has some negative controls [5]. The value
on target line is inverted if and only if all positive controls have value 1 and all negative controls have value 0.
A 3-bit negative control Toffoli gate with a negative control on their first input is as shown in Fig. 2(a).
2) Extended Toffoli Gate
An extended Toffoli gate (ETG) is a multi-target Toffoli gate having two target lines instead of one [6].
These two target lines perform same function with their inputs. An n+1 bit extended Toffoli gate maps input
vectors (I1,I2….In+1) to output vectors (O1,O2…On+1) where, Oj = Ij (for all j < n), On = I1I2…In-1⊕In and On+1 =
I1I2…In-1⊕In+1. Fig 2(b) shows an n-bit Extended Toffoli gate.
(a) A 3-bit negative control Toffoli gate (b) An (n+1)-bit ETG gate
Figure 2: Other Reversible Gates
C. Parity Preserving Reversible Gates
A reversible gate is said to be parity preserving when parity of input data is preserved in the output.
Means, EX-OR of all inputs is equal to the EX-OR of all outputs. There are some parity preserving reversible
gates presented in literature such as 3*3 Feynman Double gate [7] as shown in Fig. 3(a), 3*3 Fredkin gate [8] as
shown in Fig. 3(b), 3*3 NFT gate [9] as shown in Fig. 3(c) and 4*4 MIG gate [10] as shown in Fig. 3(d).
(a) Feynman Double gate (b) Fredkin gate (c) NFT gate (d) MIG gate
Figure 3: Parity Preserving Reversible Gates

D. Reversible Circuit Synthesis
The synthesis approaches for reversible circuits are found in literature including transformation based,
PPRM (positive polarity Reed-Muller expression) based, ESOP based and decision based. The transformation
based synthesis is based on examination of the truth table of respective function. The basic approach proposed
by Miller et al. [11] in 2003 identifies transformations that can be applicable on output representing columns of
the truth table in order to match input-output pattern. These transformations are directly converted into cascades
of reversible gates. The PPRM based approach was proposed by Gupta et al. [12] in 2006 for generation of
reversible circuits. This approach creates a search tree based on PPRM expressions of the given function. Here,
paths from root to leaf which leads best solution are converted into Toffoli gates.
Our proposed work compared to an existing which uses ESOP approach for their primarily circuits.
The ESOP approach uses an ESOP representation of the given function. The ESOP representation is similar to
sum of product form with one exception, the OR operator is replaced by EXOR. The basic approach was
introduced by Fazel et al. [13] in 2007, then improved in a number of works including [14, 15]. One another
approach as decision based synthesis was introduced by Wille et al. [16], based on a BDD representation of the
given function.
E. Cost Metrics
Gate Count is the first step of measuring any reversible circuit. It refers to the number of reversible
gates used in order to realize a reversible circuit. When gate count does not give accurate measure then the other
cost metric, quantum cost is used [17]. The quantum cost of a reversible circuit is equal to the sum of quantum
costs of its gates. For quantum cost calculation, we use the costs of gates given in [18]. Garbage outputs show
the wastage of calculation. We cannot use them as primary outputs or as inputs to other gates. So for reversible
circuits their minimization is required.
III. RELATED WORK
Various techniques are presented in literature for fault testing of reversible circuits. They have been
categorized into offline and online approaches. Offline approaches are those which perform fault testing in
additional time by using a well defined test set whereas online do this in normal operation using a normal input
vector. In this paper we dealt only with online testing of reversible circuits. Online testing approaches for
reversible circuits found in literature include testable circuits based on R1, R2 and R3 gates [19, 20], based on
testable reversible cells (TRCs) [21], based on online testable gates (OTGs) [22], dual-rail reversible gates [23,
24], parity-preserving reversible gates [7, 25, 26] and based on extended toffoli gates (ETGs) [27, 28]
respectively. These approaches except ETG based [27, 28] have been further categorized as parity-generating
[19, 20, 21, 22], parity-preserving [7, 25, 26] and dual rail online error detection methods [23, 24]. According to
results of [27, 28], the approaches based on ETG are far superior to others in terms of quantum cost and
garbage’s generated. This paper categorized these (ETG based) approaches and proposed extension for scaling it
in their next section. Here we described these approaches as presented in the literature [27, 28].
The basic approach based on ETGs was introduced in [27] for generation of online testable reversible
circuits. This approach takes reversible circuits generated by the ESOP based synthesis approach. An example
of this approach is as shown in Fig. 4. This approach performs some substitution and addition of reversible
gates. ESOP based circuits as shown in Fig. 4(a) have independent input and output lines. Here one parity line L
is added to the end of the given circuit. Then all n-bit Toffoli gates are replaced by (n+1)-bit ETGs. And for
each NOT gate found in the circuit, a NOT is added to the line L. Afterwards q CNOTs are added from all
output line to L, where q is the number of output lines. And finally 2p CNOT gates are added from all input
lines to L before and after the circuit, where p is the number of input lines. Figure 4(b) shows the resultant
online testable circuit generated after applying the given approach on ESOP based circuit depicted in Fig. 4(a).
Figure 4: (a) An ESOP-based reversible circuit and (b) An online testable reversible circuit
In the literature several fault models for reversible logic are proposed among which stuck-at, bit and
missing gate fault model have drawn more attention [29]. These fault models can be applied for combinational
[18, 30] as well as sequential reversible circuits [31]. The existing approach [27] and their extension [28] detect
a single-bit fault which flips the value at output from the actual [29]. Here, detection is achieved by initializing

the parity line L with a value 0 and reading a value 1 on the same at the end of the circuit. This change shows
the presence of fault occurred in the circuit. When no fault occurs, this value will be 0. Instead of several
advantages this approach had one severe limitation. This limitation restricted their application for circuits
generated by the ESOP based synthesis only.
An extended approach for generation of ETGs based testable circuits was proposed in [28]. This
extension has removed the limitation of application to circuits only generated by the ESOP synthesis approach.
The newer version as presented in [28] is applicable for all synthesis approaches that generate a Toffoli network
in their output. An example of this approach is as shown in Fig. 5.
Figure 5: (a) A Toffoli circuit, (b) An online testable reversible circuit
Here similar to previous version some substitution and addition of gates have been performed. First a
parity line L is added to the end of the circuit. Then all n-bit Toffoli gates are replaced by (n+1)-bit ETGs.
Unlike previous the number of NOT gates is counted and adds a NOT on line L to the end of the circuit where
the number found is to be odd. Here the input Toffoli network has combined input and output lines as depicted
in the Fig. 5(a). So only 2p CNOT gates are added from all input lines to L at the beginning and end of the
circuit, where p is the number of input lines. Like previous version [27], the parity line L is initialized with 0
and a single-bit fault is detected by reading the value 1 on L at the end of the circuit. This extension has reduced
quantum cost to a great extent. But the limitation of application has continued with a small reduction of having
circuits consisting of Toffoli gates, irrespective of the particular (ESOP) synthesis method. The next section
detailed our proposed analysis and extension by following a conversion for parity preserving reversible circuits.
IV. PROPOSED WORK
A. Analysis
Parity checking is one of the important error detection mechanisms of digital logic and data
communication. This mechanism is still valid for reversible logic. Various approaches including [19, 20, 21, 22]
use a comparison of parity generated before and after the computation for checking faults are categorized as
parity-generating methods. The approaches presented in [7, 25, 26] use reversible gates that match parity of the
output with their input are considered as parity-preserving methods. Another type found in [23, 24], based on
dual-rail reversible gates is considered as dual-rail error detection methods. Our analysis given in this section
provides a new category for approaches presented in [27, 28] which we were considered as an exception from
this categorization in earlier section. The category provided by our proposed analysis is a new category named
hybrid containing a combination of parity-generating and parity-preserving methods.
This section analyzed the recently proposed Toffoli based approach [28], since it has compatibility to
previous approach [27]. For sake of convenience we divided this approach in two phases. Phase 1 includes
addition of the parity line L to the end of the circuit and 2p CNOT gates from all lines to L at the beginning and
at the end of the circuit where, p is the no. of input lines presented in the original circuit. While phase 2 contains
the replacement of each n-bit Toffoli gate by an (n+1)-bit ETG gate with an optional addition of a NOT gate (If
the number of NOT gates found in the circuit is odd). Here it will be proved that the operations of phase 1 are
performed for providing a comparison between parities generated at the beginning and at the end of the circuit.
And the phase 2 conducted operations for preserving the parity of original circuit in between each and every
computation. Then the final value on L at the end of the circuit is representing the result of their comparison.
Both of the statements are proved here via exploring a simple example of one (3-bit) Toffoli circuit depicted in
Fig. 6(a). So we discussed operations of these two phases on the original circuit as follows.
Figure 6: (a) A 3-bit Toffoli circuit, (b) Resultant designs of Phase 1 and (c) Phase 2

Phase 1: is started by adding the parity-line L to the end of the circuit. After that the addition of 2p
CNOT gates from all lines to L at the beginning and at the end of the circuit is performed. Here the value on L at
the end of the resultant circuit depicted in Fig. 6 (b) will show the difference of parities generated by the 2p
CNOT gates at the beginning and at the end of the circuit. The value on L is calculated as follows:
L = I1⊕I2⊕I3 ⊕ I1⊕I2⊕ (I1I2⊕I3) = I1I2
This value showing the parity of the inputs has changed by the function I1I2 as compared to the outputs.
For retaining input parity at the outputs the whole circuit requires EXORed with I1I2.
Phase 2: conducted the replacement of each n-bit Toffoli gate by an (n+1)-bit ETG gate. The circuit
depicted in Fig. 6 (c) is the resultant of phase 2 that has one (3+1)-bit ETG representing a replacement of the
earlier 3-bit Toffoli gate. In other means, this replacement has EXORed I1I2 with original circuit. So the final
value of L at the end of the circuit has become:
L = I1⊕I2⊕I3 ⊕ I1⊕I2⊕ (I1I2⊕I3) ⊕I1I2
= I1I2 ⊕ I1I2 = 0
This value 0 on L at the end of the circuit shows the equivalence of both sides of parity. When the
(n+1)-bit ETG compared to a parity-preserving reversible gate (PPTG) [26], we found that the (3+1)-bit ETG is
a parity-preserving reversible gate. Similarly when we compared the (2+1)-bit ETG with a parity-preserving
gate F2G [7], same thing was again found. So we have concluded that the computation performed in an (n+1)-
bit ETG is parity-preserving (parity of the outputs matches with that of inputs). With such parity-preserving
characteristics and Toffoli functionality we can say the (n+1)-bit ETG is a generalized parity-preserving Toffoli
gate.
Now we discussed the operation of a NOT gate added to the resultant circuit. We know a NOT gate
changes the parity of the circuit from even to odd or vice versa. The even number of NOT gates does not change
the circuit’s parity. So when the number of NOT gates found in the original circuit is odd then the addition of a
NOT gate to the end of the circuit on line L takes place to maintain the circuit’s parity same at the outputs.
Thus, for a parity-preserving reversible circuit (Circuit that preserves inputs parity in their outputs) the
value of L at the end of the circuit remains 0. Any single-bit fault occurred in the circuit changes their parity
from even to odd or vice-versa. At the end of the circuit this change reflects in the form of 1 on line L. So by
reading a single-bit value on line L fault can be detected.
Hence, it has proved that the parity-checking and parity-preserving techniques are working behind the
fault detection of existing approaches [27, 28]. So we are categorizing them as hybrid approaches. And another
thing that we have concluded is, we can use the parity-preserving substitutions of other reversible gates (such as
Peres) in order to make their circuits online testable.
B. Proposed Extension for MCF-Peres Based Reversible Circuits
This section proposed an extension of the approaches presented in [27, 28] for MCF and Peres based
reversible circuits. As we have identified in above section that the parity checking and parity-preserving
mechanisms both are used for detecting a fault in a testable circuit formed by the existing [27, 28]. By using
parity-preservation this section proposed online testable designs for multiple control Fredkin (MCF) and Peres
gates. Here, we first proved the online testability of MCF gates using parity-preserving characteristics and then
proposed an online testable substitution of Peres gate. Under this we have proposed two lemma’s as follows:
Lemma 1: An n-bit MCF gate is an online testable (parity-preserving) reversible gate. Without
undergoing any replacements a single-bit fault can be detected at the outputs on parity line L when the circuit
contains only MCF gates with p number of circuit lines and 2p parity-checking CNOTs.
Proof: Consider an online testable reversible circuit that has one 3-bit MCF gate with 2p parity-
checking CNOTs as shown in Fig. 7. The value of L at the end of the circuit is:
L = I1⊕I2⊕I3 ⊕ I1 ⊕ f1I2 ⊕ f2I3 ⊕ f1I3 ⊕ f2I2
= I2⊕I3 ⊕ I2 (f1⊕f2) ⊕ I3 (f1⊕f2)
= I2⊕I3 ⊕ I2⊕I3 = 0 (Where, f1⊕f2 = 1 and f1 = f2’ = I1’)
Figure 7: Online Testable 3-bit MCF (Fredkin) Circuit
The value 0 on line L at the end of the circuit is showing that the given circuit (exclude Parity-checking
CNOT gates) is parity-preserving and has no fault. Based on our analysis we assumed that this circuit is online
testable and does not require any kind of replacements of MCF like Toffoli. Now, we are discussing all the cases
of how a fault can occur in the given circuit depicted in Fig. 7.

Case 1: We assume that a fault has occurred on line I1 before doing the gate operation. This fault will
affect both targets of MCF (m1). And due to this fault, functions performed in first and second target will change
from (f1, f2) to (f1’, f2’) and the value of line I1 will become I1’. Finally the value on line L at the end of the
circuit will become:
L = I1⊕I2⊕I3 ⊕ I1’ ⊕ f1’I2 ⊕ f2’I3 ⊕ f1’I3 ⊕ f2’I2
= I1⊕I2⊕I3 ⊕ I1’⊕I2 (f1’⊕f2’) ⊕ I3 (f1’⊕f2’)
= I1⊕I1’ = 1 (Where, f1’⊕f2’ = 1)
Case 2: Suppose a fault has occurred on line I2 before doing the gate operation. Due to the faulted line
I2 is not connected to control of MCF (m1), the both functions (f1 and f2) performed by the gate will remain same
and only the line I2 will affect. Finally the value on line L at the end of the circuit will become:
L = I1⊕I2⊕I3 ⊕ I1 ⊕ f1I2’ ⊕ f2I3 ⊕ f1I3 ⊕ f2I2’
= I2⊕I3 ⊕ I2’ (f1⊕f2) ⊕ I3 (f1⊕f2)
= I2⊕ I2’ = 1 (Where, f1⊕f2 = 1)
Case 3: Assume a fault has occurred on line I3 before doing the gate operation. Because of the line I3
connected to second target of the MCF gate (m1) functions (f1 and f2) performed on both targets will remain
same but the value of line I3 will changes to I3’. So the value of line L at the end of the circuit will become:
L = I1⊕I2⊕I3 ⊕ I1 ⊕ f1I2 ⊕ f2I3’ ⊕ f1I3’ ⊕ f2I2
= I2⊕I3 ⊕ I2 (f1⊕f2) ⊕ I3’ (f1⊕f2)
= I3⊕ I3’ = 1 (Where, f1⊕f2 = 1)
Here the value 1 on line L at the end of the circuit shows the presence of fault in the given
circuit. Any single fault that occurs after the gate operation will change parity of outputs directly from even to
odd and vice versa. And the effect of that change will automatically reflect on parity line L in the form of value
1.
Now we proposed our online testable substitution of Peres gate. But before discussing the proposed
substitution we will discuss the testable requirements of Peres gate. In this order consider a simple circuit
consisting of one Peres gate and 6 parity-checking CNOT gates with a parity line L as shown in Fig. 8. Before
using any substitution the value on parity line L at the end of the circuit is:
L = I1⊕I2⊕I3 ⊕ I1 ⊕ (f1⊕I2) ⊕ (f2⊕I3)
= I2⊕I3 ⊕ f1⊕I2⊕f2⊕I3
= f1⊕f2 = I1I2’ (Where f1 = I1 and f2 = I1I2)
Figure 8: Online testable requirements for Peres Gate
This value on L showing a difference of parities generated at the inputs and outputs of the given circuit.
And we require performing the function f1⊕f2 (or I1I2’) once again to make the difference 0.
The proposed online testable substitution of Peres gate using one MIG is as shown in figure 9. This is
similar to parity-preserving substitution of Peres gate proposed in [26]. And this similarity has come from the
proposed analysis. In literature [10], MIG gate is only found in block representation. So the representation
depicted in Fig. 9 is used for representing an MIG gate and as the substitution of Peres gate in rest of this paper.
The proposed substitution performs Peres gate operations in their upper three outputs and required function
(f1⊕f2) in bottom last output in order to make the parity-difference 0.
Figure 9: Proposed Online Testable Peres Substitution (MIG gate in symbolic form)
After using proposed substitution the value on parity line L at the end of the resultant circuit as shown
in Fig. 10 will:
L = I1⊕I2⊕I3 ⊕ I1 ⊕ (f1⊕I2) ⊕ (f2⊕I3) ⊕ (f1⊕f2)
= I2⊕I3 ⊕ f1⊕I2 ⊕ f2⊕I3 ⊕ f1⊕f2
= 0

Figure 10: Proposed Online Testable Peres Circuit
Lemma 2: A reversible circuit consisting of Peres gates and p circuit lines can becomes online testable
by replacing every Peres gate with an MIG gate (online testable substitution of Peres gate) following the
addition of 2p CNOTs.
Proof: Consider the same circuit as depicted in Fig. 10 in which one MIG has replaced the Peres gate
for online testing of the circuit. Now we will discuss all possibilities that a single fault can occur in the given
circuit.
Case 1: Assume a fault has occurred on line I1 just before the gate operation. This faulted line is
connected to the control of MIG (m1) gate as shown in Figure 4.8. Therefore, both target functions (f1 and f2) of
the gate and circuit line I1 will affect by the fault. And the resultant value on Line L at the end of the circuit will
become:
L = I1⊕I2⊕I3⊕ I1’ ⊕ (f1’⊕I2) ⊕ (f2’⊕I3) ⊕ (f1’⊕f2’) = I1⊕ I1’ = 1
(Where f1’ = I1’, f2’ = I1’ I2 and f1’⊕ f2’ = I1’ I2’).
Case 2: Suppose a fault has occurred on line I2 before doing the gate (MIG, m1) operation. Now only
function f2 and circuit line I2 will affect by this fault. And the final value on Line L at the end of the circuit will
become:
L = I1⊕I2⊕I3 ⊕ I1⊕ (f1⊕I2’) ⊕ (f2’⊕I3) ⊕ (f1⊕f2’) = I2⊕ I2’ = 1
(Where f1 = I1, f2’ = I1I2’ and f1⊕f2’ = I1I2).
Case 3: Assume a fault has occurred on line I3 just before the gate MIG (m1). Here the fault will not
affect any gate functions (f1 or f2). Only value of the line I3 will change to I3’. Therefore the final value on Line
L at the end of the circuit will become:
L = I1⊕I2⊕I3 ⊕ I1⊕ (f1⊕I2) ⊕ (f2⊕I3’) ⊕ (f1⊕f2) = I3⊕I3’ = 1
Case 4: When a fault occurs on parity line L then the value on this line will automatically changes from
L to L’. If it is initially 0 then after the occurrence of a single fault on L it will automatically change to 1. Like
previous approaches [27, 28] the fault occurred on line L will not propagates its effect to any other line because
it is not connected to controls of any other gate. Any single fault occurs after the gate operation will change
parity of the outputs directly from even to odd and vice versa. Effect of that change will reflect on L in the form
of value 1. And we will find the presence of a single-bit fault in the given testable circuit.
1) Example
This example compares proposed extension with their exiting [28]. The only limitation of the existing
approach [28] is that it works only for Toffoli networks. Reversible circuits consisting of other gates (such as
Fredkin and Peres) require Toffoli based realizations to become testable by the earlier approach. For this
example we consider a circuit depicted in Fig. 11(a) consisting of two Peres gates. The existing approach
requires Toffoli based realization of the given circuit which is as shown in Fig. 11(b). The resultant online
testable reversible circuit produced after applying the existing approach [28] is as shown in Fig. 11(c), of
quantum cost 51. Reversible circuits with larger number of such gates (MCF and Peres) lead high overhead in
terms of quantum cost and Gate Count. Our proposed extension has reduced this overhead to a great extent. Fig.
11(d) shows the resultant testable circuit generated by applying the proposed extension on the original circuit as
presented in Fig. 11(a). The new circuit produced by the proposed extension has quantum cost of only 41 which
is less as compare to 51 of circuit depicted in Fig. 11(c) and created by the existing approach.
Figure 11: (a), (b), (c) existing Approach and (d) proposed approach for Peres-based reversible circuit

For testing assume a single fault has occurred on line I2 between MIG gates (m1 and m2) of the
resultant circuit produced after applying the proposed extension. Assume f1 and f2 are the two output functions
performed by the first MIG (m1) in their two targets on lines I2 and I4. Similarly assume f3 and f4 are the two
functions performed by the second MIG (m2) on line I3 and I4. Now before reaching to MIG (m2) the value of L
will become I1⊕I2⊕I3⊕I4⊕f1⊕f2, equal to their normal operation (when no fault occurs). Because of the
faulted line is connected to control of the second MIG (m2), functions f3 and f4 with circuit line I2 will affect.
And the final value on L at the end of the circuit will become:
L = I1⊕I2⊕I3⊕I4 ⊕ f1⊕f2⊕f3’⊕f4’ ⊕ I1 ⊕ (f1⊕I2’) ⊕ (f3’⊕I3) ⊕ (f2⊕f4’⊕I4)
= I2⊕I2’ = 1
This value 1 will show the occurrence of a fault in the given circuit.
2) Applicability
Here proposed approach posses ability of converting MCF-Peres based reversible circuit into their
testable reversible circuit without undergoing into Toffoli gates. By the proposed extension all reversible circuits
of available libraries [18, 30] (including MCT+MCF and MCT+P) will become online testable. Table 1 shows
reversible libraries covered by the existing [27, 28] and proposed approaches.
Table 1: Coverage of Reversible Libraries
Approach NCT NCTSF NCTSFP GT/MCT MCT+MCF MCT+P
Existing [14, 15] √ √
Proposed √ √ √ √ √ √
C. Proposed Conversion for Parity-Preserving Reversible Circuits
Our proposed analysis has discussed the applicability of parity-preserving logic towards testable
circuits generated by the existing [27, 28]. And it has shown that the existing performs Toffoli substitution only
to make the original circuit parity-preserving. Since the circuit taken here is already parity-preserving, no
substitution will require. And by using the simple addition of 2p CNOTs a parity-preserving reversible circuit
will become an online testable reversible circuit. For example we have taken a parity-preserving reversible
circuit depicted in Fig. 12(a) and generated by a substitution process presented in our earlier work [26]. For
conversion 2p CNOTs has added to the parity-preserving reversible circuit from all (p-1) lines to the pth
line,
where p is the number of circuit lines and pth
is the bottom most circuit line presented in the given circuit. The
resultant online testable circuit produced by the addition of 2p CNOTs is as shown in Fig 12(b). Here the pth
line
has used as the parity line L. Fault detection of the resultant circuit will perform on this pth line by reading a
value 1 at the end of the circuit, if has initialized with 0. Now the proposed conversion has reduced the overhead
of explicit (manual) parity-checking from parity-preserving reversible circuits in their online fault detection.
Figure 12: (a) A parity-preserving reversible circuit and (b) its online testable design
D. Proposed Online Testable Reversible Substitution of n*n Reversible Gate
An n*n reversible gate as shown in Fig. 13(a) has n number of inputs and outputs. Our proposed (n+1)-
bit online testable reversible substitution of n*n reversible gate is depicted in Fig 13(b). Here, the first n outputs
of our proposed design are kept the same with that of given n-bit reversible gate. But the last output EXORs its
input (In+1) with a new function f, where the function f is I1⊕ I2⊕…..⊕ In ⊕ O1⊕ O2 ⊕…..⊕On. This function
is equal to the parity-difference of all outputs from inputs. Our proposed substitution can also work as parity-
preserving implementation of an n*n reversible gate, so would be beneficial for parity-preserving based fault
tolerant reversible circuits [7, 25, 26]. By using this substitution any reversible circuit composed of one or more
reversible gates can become parity-preserving (via substitution process [26]) and online testable (via online
testing approaches [27, 28]).

Figure 12: (a) An n*n reversible gate and its (b) online testable reversible substitution
V. EXPERIMENTAL RESULTS
We have performed our approach on 10 benchmarks collected from [30] in java. As we have discussed
earlier that the approaches presented in [27, 28] are far superior to others. So we have compared our proposed
extension only with approaches presented in [27, 28]. For approach in [27], ESOP cube lists for the benchmarks
have generated from PLA files taken from [30]. This generation has done by the tool EXORCISM4 [32]. After
that an improved ESOP based synthesis [15] has implemented in java and has applied on all ESOP cube lists of
the benchmarks to generate their corresponding reversible circuits. These reversible circuits have converted to
online testable reversible circuits by using existing approach presented in [27]. Table 2 represents their resultant
overhead in terms of gate count (GC) and quantum cost (QC). In [28] Nayeem et al. had performed their
experiments on Toffoli networks generated by the same improved ESOP based synthesis approach used in [27].
But for fair comparison we have collected their optimal Toffoli realizations from [30]. These realizations are far
better to networks generated by the improved ESOP synthesis approach proposed in [15]. The resultant online
testable designs generated by the approach [28] are representing their overhead in terms of gate count and
quantum cost in the below Table 2. For proposed extension, optimal MCF-Peres based realizations have
collected from [30]. After applying the proposed extension a collection of overhead (in terms of GC and QC)
has collected which is as shown in last column of the Table 2.
Table 2: Comparison of proposed extension with their existing
Table 3 shows improvements achieved by the proposed extension on their previous versions [27, 28].
We have compared the improvements only in terms of gate count and quantum cost and have neglected the
garbage output measure because designs generated by the existing [28] and proposed produce same number of
garbage outputs.
Table 3: Improvements achieved by proposed extension
Improvements Parameters Approach in [27] Approach in [28]
By Proposed Extension
GC 39.44% 10.52%
QC 95.15% 16.07%
As mentioned in above table, our approach has shown significant advantage over [28] in terms of gate
count by 10.52% and in terms of quantum cost by 16.07% on 10 benchmark circuits, where as it offers huge
advantages over [27] by 39.44% advantage over Gate Count and 95.15% over quantum cost on the average over
same benchmark circuits.
Circuits
Existing [27] Existing [28] Proposed
GC QC GC QC GC QC
4mod5 13 38 15 29 14 26
decod24 16 35 15 37 14 34
decod24-E 17 51 21 51 15 33
ham3 15 31 11 25 10 22
rd32 14 45 12 28 10 22
rd53 30 267 28 84 24 72
rd73 58 953 40 136 34 118
rd84 86 2479 58 198 51 177
sym6 72 759 40 132 35 117
sym9 72 11059 52 188 45 167
Average 39.3 1571.7 26.6 90.8 23.8 76.2

VI. CONCLUSION
This paper proposed an extended approach for online testing of MCF-Peres based reversible circuits.
The proposed extension proved online testability of MCF Gates and given an online testable substitution for
Peres gate. We showed their applicability on reversible circuits of all available libraries including MCT+MCF
and MCT+P. Evaluation results stated that the proposed extension is better than existing in terms of quantum
cost and gate count. A conversion is also proposed to make any parity-preserving reversible circuit online
testable. Finally, a generic (n+1)-bit online testable substitution of n*n reversible gate is given. The proposed
generic substitution also realizes an n*n reversible gate in parity-preserving domain. By our proposed extension
and generic substitution all reversible circuits would become online testable.
REFERENCES
[1] R. Landauer, Irreversibility and heat generation in the computing process, IBM Journal of Research and Development, 5:183–191,
July 1961.
[2] Bennet C., Logical Reversibility of Computation, IBM Journal of Research and Development, vol. 17, no. 6, pp. 525-532, 1973.
[3] R. Wille, M. Saeedi and R. Drechsler, Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost, International
Workshop on Logic Synthesis (IWLS), USA, 2009.
[4] A. Peres, Reversible logic and quantum computers, Physical Review: A, vol. 32, no. 6, pp. 3266-3276, 1985.
[5] M. Arabzadeh, M. Saeedi, and M. Zamani, Rule-based optimization of reversible circuits, In Proceedings of Asia and South Pacific
Design Automation Conference (ASPDAC), pages 849–854, 2010.
[6] J. Chen, X. Zhang, L. Wang, X. Wei, and W. Zhao, Extended Toffoli gate implementation with photons, In Proceedings of 9th
International Conference on Solid-State and Integrated-Circuit Technology (ICSICT), pages 575–578, China, 20-23 Oct 2008.
[7] B. Parhami, Fault tolerant reversible circuits, In Proceedings of 40th Asimolar Conf. Signals, Systems, and Computers, Pacific
Grove, CA, pp. 1726-1729, October 2006.
[8] E. Fredkin and T. Toffoli, Conservative logic, International Journal of Theoretical Physics, pp. 219-253, 1982.
[9] M. Haghparast and K. Navi, A novel fault tolerant reversible gate for nanotechnology based systems, Am. J. of App. Sci., vol. 5,
no.5, pp. 519-523, 2008.
[10] S. Babazadeh and M. Haghparast, Design of a nanometric fault tolerant reversible multiplier circuit, J. Basic. Appl. Sci. Res.,
2(2)1355-1361, 2012.
[11] D. M. Miller, D. Maslov, and G. W. Dueck, A transformation based algorithm for reversible logic synthesis, In Proceedings of the
40th annual Design Automation Conference (DAC), pages 318–323, 2003.
[12] P. Gupta, A. Agrawal, and N. K. Jha, An algorithm for synthesis of reversible logic circuits, IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, 25(11):2317–2330, 2006.
[13] K. Fazel, M. Thornton, and J. E. Rice, ESOP-based Toffoli gate cascade generation, In Proceedings of the IEEE Pacific Rim
Conference on Communications, Computers and Signal Processing (PACRIM), pages 206–209, Victoria, BC, Canada, 22-24 Aug.
2007.
[14] Y. Sanaee and G. W. Dueck, Generating Toffoli networks from ESOP expressions, In Proceedings of IEEE Pacific Rim Conference
on Communications, Computers and Signal Processing (PACRIM), pages 715–719, Victoria, BC, Canada, 13-18 June 2009.
[15] N. M. Nayeem and J. E. Rice, Improved ESOP-based synthesis of reversible logic, In Proceedings of the Reed Muller Workshop,
Tuusula, Finland, 25-26 May 2011.
[16] R. Wille and R. Drechsler, BDD-based synthesis of reversible logic for large functions, In Proceedings of the 46th Annual Design
Automation Conference (DAC), pages 270–275, 2009.
[17] M. Mohammadi and M. Eshghi, On figures of merit in reversible and quantum logic designs, Quantum Information Processing, vol.
8, pp. 297–318, August 2009.
[18] D. Maslov, Reversible logic synthesis benchmarks page, http://www.cs.uvic.ca/˜dmaslov/.
[19] D. P. Vasudevan, P. K. Lala, and J. P. Parkerson, Online testable reversible logic circuit design using NAND blocks, In
Proceedings of IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems, pages 324–331, Los Alamitos, CA,
USA, 10-13 October 2004.
[20] D. P. Vasudevan, P. K. Lala, D. Jia, and J. P. Parkerson, Reversible logic design with online testability, IEEE Transactions on
Instrumentation and Measurement, 55(2):406–414, 2006.
[21] S. N. Mahammad, S. Hari, S. Shroff, and V. Kamakoti, Constructing online testable circuits using reversible logic, In Proceedings
of 10th IEEE International VLSI Design and Test Symposium (VDAT), pages 373–383, Goa, India, August 2006.
[22] H. Thapliyal and A. P. Vinod, Designing efficient online testable reversible adders with new reversible gate, In Proceedings of
IEEE International Symposium on Circuits and Systems (ISCAS), pages 1085–1088, New Orleans, LA, 27-30 May 2007.
[23] N. Farazmand, M. Zamani, and M. B. Tahoori, Online fault testing of reversible logic using dual rail coding, In Proceedings of 16th
IEEE International On-Line Testing Symposium (IOLTS), pages 204–205, 5-7 July 2010.
[24] Farazmand, N.; Zamani, M.; Tahoori, M.B., Online Multiple Fault Detection in Reversible Circuits, In Proceedings of the 2010
IEEE 25th International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT), vol., no., pp.429,437, 6-8 Oct. 2010
[25] Md. Saiful Islam, M. M.Rahman and Zerina Begum, Synthesis of fault tolerant reversible circuits, In Proceedings of the IEEE
International Conference on Testing and Diagnosis, 28-29 April, 2009, Chengdu, China.
[26] Anugrah Jain and Sushil Chandra Jain, Towards Implementation of Fault Tolerant Reversible Circuits, In Proceedings of the 2013
1st International Conference on Emerging Trends and Applications in Computer Science (ICETACS), pages 86–91, Shillong,
Meghalaya, India, September 2013.
[27] N. M. Nayeem and J. E. Rice, A simple approach for designing online testable reversible circuits, In Proceedings of the IEEE
Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), Victoria, Canada, August 2011.
[28] N. M. Nayeem and J. E. Rice, Online fault detection in reversible logic, In Proceedings of the IEEE International Symposium on
Defect and Fault Tolerance in VLSI Systems (DFT), Vancouver, Canada, October 2011.
[29] Rice, J.E., An overview of fault models and testing approaches for reversible logic, In Proceedings of the 2013 IEEE Pacific Rim
Conference on Communications, Computers and Signal Processing (PACRIM), vol., no., pp.125,130, 27-29 Aug. 2013.
[30] R. Wille, D. Große, L. Teuber, G. W. Dueck, and R. Drechsler, Revlib: An online resource for reversible functions and reversible
circuits, International Symposium on Multiple Valued Logic, pages 220–225, May 2008.

[31] Shubham Gupta, Vishal Pareek and S.C. Jain, Low Cost Design of Sequential Reversible Counters, International Journal of
Scientific & Engineering Research, Volume 4, No. 11, pp. 1234-1240, November 2013.
[32] A. Mishchenko and M. Perkowski, Fast heuristic minimization of exclusive sumof-products, In Proceedings of the 5th International
Reed-Muller Workshop, pages 242–250, Starkville, Mississippi, August 2001.

An Extended Approach for Online Testing of Reversible Circuits

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

Similar to An Extended Approach for Online Testing of Reversible Circuits (20)

More from IOSR Journals (20)

Recently uploaded (20)

An Extended Approach for Online Testing of Reversible Circuits