VLSI Design 3
x x x x w w w w x x x x y x⊕y y z x⊕y y wx ⊕ y y wx ⊕y wx⊕z z x⊕z x⊕z z wx⊕ z z
( a)
( b)
Figure 2: The symbol and logic level implementations for( a) the extended Feynman gate and( b) a 2-control extended Toffoli gate.
A B C D 0
A B C D
F = A ⊕ B D ⊕ ACD ⊕ BCD Figure 3: Reversible circuit implementing( 1).
EFG is 2. In Figure 2( b), a 2-control ETG and its logic level implementation are shown. The quantum cost of an ETG is 2 plus the quantum cost of the corresponding Toffoli gate. The quantum cost of the ETG in Figure 2( b) i s 5 + 2 = 7.
2.2. Reversible Logic Synthesis Using ESOP Expressions. An exclusive-OR sum of products( ESOP) expression is similar to a conventional sum of products( SOP) expression, except that product terms are combined with exclusive-OR( EXOR) operators rather than OR operators [ 31 ]. A common technique in reversible logic synthesis is to express the logic function as an ESOP expression and then realize the ESOP expression as a cascade of NOT, CNOT, and Toffoli gates [ 32 ]. An example ESOP expression is given in( 1) and its reversible realization as a cascade of NOT, CNOT, and Toffoli gates is shown in Figure 3. in normal operation. In online testing, however, the circuit must be able to continue normal operations while testing is carried out. For online testing additional circuitry is generally added to the original circuit to determine whether the circuit is faulty or not. There are three fault models: line faults( or bit faults) [ 33 ], missing control faults, which is one instance of crosspoint faults [ 34 ], and missing gate faults [ 35 ]. In a line fault, the logic value of a line is flipped and produces faulty output. In a missing control fault, the control point of a gate either is not working or disappears from the gate, resulting in an incorrect value for the target output. Ina missing gate fault, the entire gate does not work or the gate disappears from the circuit causing faulty output.
3. Related Work
In this section, we discuss related work on reversible sequential circuit design and on online testing of reversible combinational circuits.
3.1. Related Work on Reversible Sequential Circuit Design. There are many attempts at designing reversible latches, flipflops, and sequential circuits. Some important but nonexhaustive work on reversible sequential logic design includes [ 25, 26, 36 – 42 ]. References [ 36 – 39 ] present reversible designs for latches and flip-flops using reversible gates and sug- gest that sequential circuits be synthesized by replacing the latches, flip-flops, and gates of the combinational part of the traditional irreversible designs with their reversible counterparts. Following this replacement approach, the work in [ 40 ] presents a design for a four-bit falling-edge-triggered universal register and the work in [ 41 ] presents a design for a four-bit level-triggered up counter with asynchronous parallel load. The work in [ 25 ] again uses the replacement technique and demonstrates that reversible circuits can be implemented using QCA technology with offline testing of the QCA-based sequential circuit. The work in [ 42 ] offers the first attempt to synthesize a sequential circuit using direct feedback of the state output and without using any flip-flops.
F( A, B, C, D) = A⊕ B D⊕ A C D⊕( 1)
BCD. 2.3. Sequential Circuits. The classical model of a sequential circuit is shown in Figure 4. A sequential circuit has a memory whose content during the present clock cycle is called the present state. The combinational circuit produces the output as a function of the present state and the input. The combinational circuit also produces the next state as a function of the present state and the input; this computed next state becomes the present state during the next clock cycle. The behavior of a sequential circuit is described using a state transition diagram. In describing a sequential circuit Reference [ 42 ] also presents a design for a level-triggered represented by. An example sequential circuit is shown the present state is represented by Q and the next state is up counter using positive polarity Reed-Muller expressions
Q for representing the next states. The up counter design is
( x
+ of both quantum cost and garbage outputs( outputs that are
), 1-bit output( z), and 2-bit state( Q1Q0). The reset state is more efficient than the replacement design in [ 41 ] in terms in the state transition diagram in Figure 4. It has 1-bit input
00.
2.4. Testing of Reversible Circuits. Testing is very important to ensure quality, availability, and reliability of a circuit. There are two approaches to circuit testing: offline testing and online testing [ 33 ]. In offline testing, a circuit is tested when it is not
not used for the intended circuit realization). The next step to this work is presented in [ 26 ], which details the direct design of arbitrary sequential circuits using pseudo-Reed- Muller expressions for representing the next states. This work also introduces modifications making the circuit falling-edge triggered and asynchronous loadable. The up / down counter in [ 26 ] is better than that in [ 41 ] in terms of both quantum