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