2 VLSI Design
A P = A
( a)
|
|
A |
P = A |
A |
P = A |
|
A
B
|
P = A
Q = A ⊕ B
( b)
|
B
C
|
Q = B
R = AB ⊕ C
( c)
|
B
C
|
Q = A B ⊕ AC
R = AB ⊕ AC
( d)
|
Figure 1: Commonly used reversible gates.( a) NOT gate,( b) CNOT or Feynman gate,( c) Toffoli gate, and( d) controlled swap or Fredkin gate.
a promising choice for low-power emerging computing technologies.
Reversible logic synthesis attempts have mostly focused on reversible combinational logic synthesis. Some of the most important but nonexhaustive work in this area is [ 14 – 23 ]. However, very few works have investigated reversible sequential logic synthesis. The major problem behind this lack of work is the prevailing thought that feedback is not possible in reversible logic and therefore reversible sequential circuits are not possible. However, in 1980, Toffoli [ 24 ] argued that if the feedback is provided through a delay element, then the feedback information will be available as the input to the reversible combinational circuit in the next clock cycle and thus a reversible sequential circuit is possible. Moreover, Thapliyal et al. [ 25 ] showed that reversible sequential circuits can be implemented using quantum dot cellular automata( QCA) technology by providing appropriate feedback timing by managing the clock of the QCA wire providing the feedback.
This paper presents a further improvement of our earlier work in designing a sequential circuit using direct feedback instead of flip-flops [ 26 ]. In addition, to our knowledge no other work has offered any technique for online testing of sequential circuits. Thus we also propose the first method of testing for single line faults in sequential circuits.
The rest of the paper is organized as follows. In Section 2, we discuss background for our proposed design method and related topics. We discuss related work on design of sequential circuits and online testing methods for combinational circuits in Section 3. In Section 4, we present our proposed method of designing sequential circuits. We show design examples in Section 5. In Section 6, we introduce our proposed method of online testing for single line faults in sequential circuits. We also present results for several benchmark circuits. Finally, in Section 8, we conclude the paper.
2. Background
mapping F: { 0, 1 } n 2.1. Reversible Logic. A reversible function is a bijective
{ 0, 1 n}, where n is the number of
input variables. A reversible gate( or a circuit) implements a reversible function; that is, it maps the input combination to the output combination in a bijective manner. Thus a reversible gate( or a circuit) has the same number of inputs and outputs. In addition every input combination produces a unique output combination in a reversible circuit, and therefore for every output combination, the corresponding input combination can be uniquely determined.
A reversible circuit is constructed using reversible gates. The commonly used reversible gates are shown in Figure 1.
Figure 1( a) shows the symbol of a NOT gate. It complements
the input at the output; that is, P = A. Figure 1( b) shows the symbol of a controlled-NOT( CNOT) or Feynman gate. The input A is called the control input and its value is passed unchanged to the output; that is, P = A. The input is called t he target input. The target output has the value Q = A ⊕ B. Figure 1( c) shows the symbol B of a three-input Toffoli gate( sometimes referred to as a controlled-controlled-NOT gate or CCNOT gate). The inputs A and B are called the inputs control and their values are passed unchanged to the outputs; that is, P = A and Q = B. Theinput C is called the target and the input target output has the value R = AB ⊕ C. Toffoli may have more than three inputs, in gates which case they may be referred to as multiple-controlled Toffoli gates. In an ninput inputs and the last input( say xn) is the target input.
Toffoli gate, the first( n−1)
) are the control The inputs value( say of x the, x target,..., x1 output 2 is x x ⋅⋅ ⋅ x ⊕ x. Figure n−1 1( d) 1 2 shows the symbol of a controlled swap gate n−1, or Fredkin n gate. Input A is the control input and inputs B and C are targets. When the control input value is A = 0, then the target inputs B and C are passed unchanged to the outputs; that is, Q = and B R = C
. When the control input value target is inputs A = are 1, then swapped the at the outputs; that is, Q = C and R = B. The outputs Q and R can be expressedas Q = AB⊕AC
an d R = A B⊕A C.
When A = 0, then Q = 0 ⋅B⊕0⋅C = B
R = 0 ⋅B
⊕ 0 ⋅ C = C. Wh. en A = 1, then Q = 1 ⋅ B ⊕ 1 ⋅ C = and
Quantum
R = 1 ⋅ B cost ⊕ 1 and ⋅ C the = B number of ancilla inputs are widely
C
used as metrics for comparing reversible circuits. Quantum cost refers to the number of primitive quantum gates required to realize the circuit, while ancilla inputs are the constantinitialized working inputs, in addition to the function inputs, that are required for the functionality of the circuit.
NOT and CNOT gates are technology realizable primitive gates, and their quantum costs are assumed to be one. Toffoli and controlled swap gates are macro-level gates and must be realized through a combination of primitive quantum gates.
The three-input Toffoli gate and the controlled swap gate can thus their quantum cost is five each.
be realized using five primitive quantum gates [ 27, 28 ] and
Realization of multiple-controlled Toffoli gates from primitive quantum gates is presented in [ 29 ], where quantum costs for up to 16-input Toffoli gates are reported. The quantum costs for 4-input, 5-input, and 6-input Toffoli gates are 14, 20, and 32, respectively.
In [ 30 ], extended Toffoli gates( ETG) are proposed, which have two target outputs. ETGs are very useful in online testing of reversible combinational circuits. In Figure 2( a), the extended Feynman gate( EFG) and its logic level implementation are shown. The quantum cost of the