Information Technology Reference
In-Depth Information
2.4
Modeling of Faults and Their Detection
Several fault models for
k
-CNOT based reversible circuits were introduced earlier [6]
as described below.
A
single missing gate fault
(SMGF) describes the removal of one
k
-CNOT gate from
the circuit. Fig. 2(b) shows an SMGF for the circuit shown in Fig. 2(a). In the example
of Fig. 2(b), if we apply (1,0,1,1) at the input of the circuit, the normal output in Fig.
2(a) would be ( 1,1,0,1), whereas in the presence of SMGF fault marked by the dotted
box, the output in Fig. 2(b) will be (1,0,1,1).
The
repeated-gate fault
(RGF) model assumes that a gate in a circuit is repeated, i.e
it shows up several times. Fig. 2(c) shows an an RGF fault.
The
multiple missing-gate fault
(MMGF) model assumes that several consecutive
gates are missing. Fig. 2(d) shows an MMGF.
A partial missing-gate fault (PMGF) corresponds to removing
m
of the
k
control
inputs of a
k
-CNOT gate, thus transforming it into a (
k
m
)-CNOT gate. The number
m
is called the order of the PMGF. Fig. 2(e) shows an PMGF with a box marking
the position of the missing control. All
k
first-order PGMFs of a gate have detection
conditions that conflict with each other and with the SMGF at the same gate;
k
+1test
vectors are required to test for all such faults that also cover all the higher-order PMGFs
at the same gate.
−
Lemma 1.
In an (n
n) reversible gate to detect SMGF, all PMGFs and all detectable
RGFs involving this gate, the following set of vectors is sufficient.
×
⊛
⊝
⊞
⊠
x
1
x
2
···
x
n
01
···
1
10
···
1
T
=
.
.
.
.
.
.
11
···
0
Fig. 2.
(a) Fault-free circuit, (b) the same circuit with SMGF, (c) an RGF, (d) an MMGF,
(e) a PMGF
3
Proposed Testable Design
Our goal is to design a DFT with a universal test set. The next result follows from
Lemma 1.
Lemma 2.
A universal test set for detecting all SMGFs and all PMGFs in a general
(
n
×
n
)
reversible circuit, must include at least
n
test vectors.
