14 VLSI Design
I1 I2 I3
L = 0 Figure 9: Online testing of a single line fault in a Fredkin circuit.
( 5) At the end of the circuit, p CNOT gates are added, where the controls of the CNOT gates are the p input lines and the target of all the CNOT gates is the parity line L.
( 6) If the circuit is fault free then the parity output will be 0, otherwise it will be 1.
6.2. Online Testing of Single Line Faults in Fredkin Circuits. A Fredkin circuit is a cascade consisting of only Fredkin( controlled swap) gates. To our knowledge, there is no existing work on offline or online testing of Fredkin circuits. We propose herea technique for online testing of single line faults in Fredkin circuits. The procedure is as follows:
( 1) A 0-initialized parity line L is added to the given circuit.
( 2) Assume that the given circuit has p inputs / outputs. At
the beginning of the circuit, p CNOT gates are added, p input
L.
where the controls of the CNOT gates are the
p
O1 O2 O3
O p the Toffoli circuits in the( i) Modified Next State Logic and Next State Logic sections together and test the( ii) Feedback section and( iii) Output Logic section separately. We then
use our proposed technique for online testing of single line faults in Fredkin circuits in the Falling-Edge Trigger and Reset / Asynchronous Load sections together.
The online testable version of the reversible sequential circuit in Figure 6 is shown in Figure 10. The design of the testable circuit is described below:
( 1) The Modified Next State Logic and Next State Logic sections together are a Toffoli circuit. We make this circuit testable by adding 0-initialized parity input
LMN. This portion of the circuit has five active inputs: x, two 1-initialized inputs, Q1, and Q0. Five gates CNOT are added at the beginning of this portion and another five CNOT gates are added at the end of this portion. One CNOT gate and three Toffoli gates in the original circuit are replaced by their corresponding extended versions. There are three NOT gates in the original circuit, so an extra NOT gate is added along the parity line. If any single line fault occurs in this section, then the parity output will be 1, otherwise OMN it will be 0. The overhead quantum cost of this section is 20.
( 2) The Falling-Edge Trigger and Asynchronous Reset
circuit testable by adding 0-initialized parity input L
R
TL
C, Q1 +, Q1, Q0 +, Q0, and two 0-initialized inputs.
sections together are a Fredkin circuit. We make this lines and the target of all the CNOT gates is the parity. This portion of the circuit has eight active inputs: line
,( 3) At the end of the circuit, CNOT gates are added, Eight CNOT gates are added at the beginning of this where lines and the the controls target of the all the CNOT CNOT gates gates are is the the parity input portion and another eight CNOT gates are added at L the end of this portion. If any single line fault occurs
line. in this section then the parity output OTL will be 1,
( 4) If the circuit is fault free then the parity output will be otherwise it will be 0. The overhead quantum cost of
0, otherwise it will be 1. A simple example of the above technique is shown in Figure 9. In a controlled swap gate the target inputs are either swapped or not swapped depending on the control value. Thus the
permutation the inputs. Similarly of the inputs, the outputs. In Figure of a Fredkin 9, the parity circuit output are a is
this section is 16. L FQ1
( 3) The Feedback section of the circuit is a Toffoli circuit.
We make this Q0 circuit testable by adding 0-initialized parity input. This portion of the circuit has four
technique This portion described of the circuit in Section is made 6.1. testable If any single using line the
will be 1, otherwise it will be 0. The overhead quantum cost of this section is 10.