"A Beginning in the Reversible Logic Synthesis of Sequential Circuits"

Himanshu Thapliyal and M.B Srinivas
International Institute of Information Technology


In the recent years, reversible logic has emerged as a promising technology having its applications in low power CMOS, quantum computing, nanotechnology, and optical computing. The classical set of gates such as AND, OR, and EXOR are not reversible. From the classical set of gates NOT is the only reversible gate. In the past, several reversible gates have been proposed, the important one being Feynman gate, the Toffoli gate, Fredkin gate and New gate. The synthesis of reversible logic differs significantly from traditional irreversible logic synthesis approaches as fan-outs and loops are not permitted in the reversible logic synthesis. Outputs from one gate are used as inputs to the next gate without fan-out of more than one. This results in a high degree of interdependence among gates. Further, reversible logic synthesis of sequential logic differs from combinational logic in that the output of the logic device is dependent not only on the present inputs to the device, but also on past inputs; i.e., the output of a sequential logic device depends on its present internal state and the present inputs. The design of complex system will require sequential circuits based on Flip Flops. This paper provides the initial threshold to building of more complex system having sequential circuits and which can execute more complicated operations using quantum computers. The reversible circuits form the basic building block of quantum computers as all quantum operations are reversible. The important reversible gates used for reversible logic synthesis are Feynman Gate, Toffoli Gate, and New Gate and Fredkin gate. The novelty of the paper is the reversible logic synthesis of Flip Flops. To the best of our knowledge and the survey of literature, this is the first work in this area. The Flip Flops that are synthesized using reversible logic are RS Flip Flop, JK Flip Flop, D Flip Flop, T Flip Flop and Master Slave Flip Flop. Thus all the pulse as well as edge triggered Flip Flops are synthesized using reversible logic. The circuits are highly optimized in terms of number of gates and garbage outputs. The modularization approach i.e synthesizing small circuits and thereafter using them to construct bigger circuits is used for designing the optimal reversible Flip Flops.

Keywords: Reversible Logic Synthesis, Quantum Computing, Sequential Circuits


2005 MAPLD International Conference Home Page