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