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.