Information Technology Reference
In-Depth Information
Fig. 5.
Testable design for the reversible circuit of Fig. 4
Algorithm 1.
DFT
Input:
A reversible circuit RC of size n with depth
N
consisting of
N
number of gates
G
1
,G
2
, ..., G
N
.
Gate
G
i
with its control at lines
x
i
1
,x
i
2
, ......, x
i
l
gets an input
x
1
,x
2
, ..., x
n
.
Output:
Testable Design for the reversible circuit RC
1: Introduce 2 control lines
C
1
,C
2
.
2:
for
i=1 to
N
-1
2.1.
if
(
Con
(
G
i
)=0)
{
Con(
G
i
) is the number of control lines of gate
G
i
.
}
2.1.1. duplicate
G
i
with an additional
control on
C
1
2.2.
if
(
Con
(
G
i
)
=0)
2.2.1.
if
(
Con
(
G
i
)
≤n/
2
)
2.2.1.1.
if
(
Con
(
G
i−
1
)
= 1OR
G
i
and
G
i−
1
donot share
target and control on the same line)
2.2.1.1.1.Insert TOF(TARGET(
G
i
),
C
2
)before
G
i
2.2.1.2. Insert TOF(TARGET(
G
i
),
C
2
),
TOF(
C
1
,C
2
,TARGET(
G
i
))
after
G
i
.
2.2.1.3.
if
(
Con
(
G
i
)
= 1OR
G
i
and
G
i
+1
donot share
control and target on the same line
,
G
i
+1
≤ N −
1)
2.2.1.3.1.Insert TOF(
x
i
1
,x
i
2
, ......, x
i
l
,
C
2
)
2.2.2.
if
(
Con
(
G
i
)
> n/
2
)
2.2.2.1.
if
(
Con
(
G
i−
1
)
= 1OR
G
i
and
G
i−
1
donot share
target and control on the same line)
2.2.2.1.1.Insert TOF(TARGET(
G
i
),
C
2
)before
G
i
2.2.2.2. Insert TOF(TARGET(
G
i
),
C
2
),
TOF(
C
1
,C
2
,TARGET(
G
i
)) and
TOF(
n − Con
(
G
i
),
C
2
)
after
G
i
.
3:
END