Information Technology Reference
In-Depth Information
Proof.
Notice that
S
U
includes
T
of Lemma 1 at the inputs
x
1
,x
2
, ...., x
n
.Sothesame
test set
T
is always applied to each gate in the original circuit. Thus in the DFT design,
the gates of the original circuit are becoming testable.
Now we look into the testing of the additional gates.
G
1
and
G
2
or
G
1
and
G
2
are
1-CNOT gates with control either at one of the input lines
x
1
,x
2
, ...., x
n
.
G
4
or
G
4
is
a k-CNOT gate with control on any improper subset of
x
1
,x
2
, ...., x
n
. Thus
G
4
or
G
4
gets the test set T at its control lines, hence it is tested. The first
n
vectors of
S
U
provides
test case for these 3 gates. For
G
3
or
G
3
, we require (
C
1
,C
2
) as (1,0) (1,1) and (0,1).
There exist at least one test vector among the first n vectors in
S
U
, when the target of
gate G is [not]flipped, In this case control line
C
2
of gate
G
3
(or
G
3
) becomes [0]1, thus
G
3
(or
G
3
) gets (1,1)[(1,0)] at (
C
1
,C
2
). The first two conditions are always achieved
by the first
n
vectors in
S
U
, (1,1) is created on (
C
1
,C
2
) by vectors which inputs 1 in
all controls and (0,1) is developed by vectors which donot input 1 to all controls for a
given gate, and The value (1,0) in (
C
2
,C
1
) is achieved by the second last vectors in
S
U
.
Test to detect fault in
G
5
is also present in
S
U
. Hence, all faults in the original as well
as additional circuits are also detected.
Sometimes the second last vector in
S
U
becomes unable to produce (1,0) at (
C
2
,C
1
)
of
G
3
or
G
3
, in such case the work is done by the last vector in
S
U
. This situation arises
due to the presence of 0 on
C
1
, as a result the additional gates fails to undo the changes
made by the NOT gate. NOT gate produces 1 in the vector which causes other gates to
act on the vector. Hence (0,0,......,0,1) fails to produce (0,1) at (
C
2
,C
1
)of
G
3
or
G
3
.In
such situation the work is done by the vector (0,0,...,0).
4
Experimental Result
We have synthesized several reversible benchmark circuits, the results of which are
shown in Table 2. Columns 2 and 3 denote the circuit name, input size, and the gate
Ta b l e 2 .
Comparative results on quantum cost
% increment in Q.C
DFT[4]
Circuit
size depth
Our design
5mod5d1
6
17
227.56%
100.54%
4 49d1
4
16
274.59%
274.46%
mod5adderd2
6
15
232.53%
161.45%
nth prime6 inc 6
55
222.44%
95.95%
rd53d1
7
28
216.81%
107.75%
rd53d2
7
12
230.33%
130%
rd53d4
7
20
228.205% 135.899%
ham15d1
15
132
232.64%
150.55%
cycle10 2d1
12
19
204.75%
68.36%
hwb6d1
6
126
224.73%
103.34%
hwb7d1
7
289
216.29%
87.5%
hwb7d3
7
236
218.28%
98.99%
hwb7d4
7
331
237.69%
147.53%
hwb5d1
5
56
252.72%
203.83%
