Present state
Next state
4 VLSI Design
Input |
Combinational logic
Memory
Clock
( a )
|
Output |
Reset
1 / 1 00 0 / 0
1 / 0 11 0 / 1 01
0 / 0
10
( b )
|
1 / 1 |
Figure 4 : ( a ) Model of a sequential circuit . ( b ) State transition diagram of an example sequential circuit .
cost and garbage outputs , and the universal register in [ 26 ] improves upon the design in [ 40 ] again for both quantum cost state 4.1 . Representing and the next the state
+
Next of State a sequential . Let Q circu and it , respectively Q be the . Q
+ present
+
and garbage output . can be expressed as a function of Q and Q as follows :
A further improvement of the work in [ 26 ] is presented in [ 43 ]. In [ 43 ], a new technique for representing the next states using exclusive-OR sum-of-product ( ESOP ) expressions is where
Q + = Q⊕ Q⊕ Q + = Q⊕ Q ∗ , ( 2 ) presented . Using this technique , designs for a four-bit fallingedge triggered up / down counter with asynchronous loading
and a four-bit falling-edge triggered universal register are presented . Both designs in [ 43 ] offer improvements over
those from [ 26 ] in terms of both quantum cost and ancilla input . This work is an extended version of [ 43 ].
3.2 . Related Work on Testing of Reversible Combinational Circuits . Several works offer techniques for online testing
∗
Q ∗ = Q⊕ Q + . ( 3 )
We call Q the modified next state . In our proposed
technique , the modified next state is determined using ( 3 ) and is expressed as a minimized ESOP expression of a function of the inputs and the present state . The next state is then expressed using ( 2 ). reversible circuits . In [ 17 ] three new reversible gates are next state Q is generated , as a function of the inputs and of reversible combinational circuits . Some propose new testable gates which are then used to construct online testable proposed , two of which are used to design an online testable block and the other is used to create a checker circuit . The checker circuit compares the two parity bits produced by the online testable blocks in order to test a single bit fault . In [ 23 ] an improved approach to single bit fault testing is proposed that does not require a checker circuit .
The most generalized approaches offer online testing of reversible circuits synthesized using NOT , CNOT , and Toffoli gates . In [ 44 ], all of the Toffoli gates are replaced by extended Toffoli gates , and two sets of CNOT gates and one additional parity line are added to the original circuit to achieve online testability for single line faults . In [ 45 ], a DFT- ( design for testability- ) based offline approach is proposed for detecting single missing gate faults . In [ 46 ], an online fault detection approach is proposed for detecting single missing gate faults . In [ 47 ], each of the Toffoli gates is accompanied by a duplicate Toffoli gate of the same size with the same control lines , but the target is placed on an additional parity line to make the Toffoli gate a testable Toffoli block . Two sets of CNOT gates are also used , for which the targets are the parity line . This approach detects all three types of faults .
To the best of our knowledge , no work has been reported in the literature on offline or online testing of reversible sequential circuits .
4 . Synthesis of Sequential Reversible Circuits
In this section , we present our proposed method for synthesis of sequential reversible circuits .