17-03-2014, 10:12 PM
Abstract—Reversible shift registers are required to construct
reversible memory circuits. This paper presents novel designs
of reversible shift registers such as serial-in serial-out (SISO),
serial-in parallel-out (SIPO), parallel-in serial-out (PISO),
parallel-in parallel-out (PIPO) and universal shift registers. In
order to show the efficiency, lower bounds of the proposed
designs are shown in terms of number of gates required,
garbage outputs produced and quantum cost needed. As far as
it is known, this is the first attempt to apply reversible logic to
implement shift registers (except SISO). Appropriate theorems
and lemmas are presented to clarify the proposed designs. The
contribution of this paper will engender a new thread of
research in the field of reversible sequential circuits.
Keywords-shift register; PIPO shift register; universal shift
register; reversible logic; garbage output
I. INTRODUCTION
Energy loss is a very important issue in modern VLSI
designs. Though the improvement in higher-level integration
and the advancement of new fabrication processes have
significantly reduced the heat loss over the last decades,
physical limit exists in the reduction of heat. According to
Landauer [1, 2], logic computation generates kTln2 joules of
heat energy for every bit of information loss where k is
Boltzmann’s constant of 1.38×10-23 J/K and T is the absolute
temperature of the environment. At room temperature the
dissipating heat is around 2.9×10-21 J which is small but not
negligible. If Moore's Law [3] remains valid until 2020, the
amount of heat generated due to information loss will be
significant. This is due to the increasing density into circuits.
Reversible logic does not lose information. Bennett [4]
showed that zero energy dissipation would be possible if the
network consists of reversible gates only. The major
application of reversible logic is in quantum computation as
quantum circuits must be reversible [5]. Quantum
computation is gaining popularity as some exponentially
hard problems can be solved in polynomial time [6].
Reversible logic has also found its applications in several
technologies, such as optical computing [7], ultra low power
CMOS design [8] and nanotechnology [9]. Thus research in
reversible logic is essential for the development of future
technologies.
Toffoli [10] showed that a finite automaton is reversible
if its transition function is invertible. In order to realize a
finite automaton with the use of a reversible sequential
circuit, it is enough to build a reversible realization of its
transition function and use this as the combinational part of
the sequential network. Even though some significant works
have already been done in the field of reversible
combinational logic design, research on reversible sequential
logic [11-13, 20] has not flourished at that pace. To
synthesize reversible memory circuits, reversible sequential
circuits such as shift registers are very essential. This paper
proposes a novel concept on reversible sequential circuit
design that includes serial-in serial-out (SISO), serial-in
parallel-out (SIPO), parallel-in serial-out (PISO), parallel-in
parallel-out (PIPO) and universal shift registers.
Rest of the paper is organized as follows. Section II
provides the necessary background on reversible logic along
with the examples of popular reversible logic gates and their
quantum costs. Section III provides existing realization of
reversible D flip-flop which is used in Section IV to propose
reversible design of shift registers. Comparative study with
the existing SISO shift register design along with the lower
bounds for the proposed designs in terms of number of gates,
garbage outputs and quantum costs are also provided in
section IV. Proper theorems and lemmas are proved to
establish the lower bounds. Section V concludes the work.
reversible memory circuits. This paper presents novel designs
of reversible shift registers such as serial-in serial-out (SISO),
serial-in parallel-out (SIPO), parallel-in serial-out (PISO),
parallel-in parallel-out (PIPO) and universal shift registers. In
order to show the efficiency, lower bounds of the proposed
designs are shown in terms of number of gates required,
garbage outputs produced and quantum cost needed. As far as
it is known, this is the first attempt to apply reversible logic to
implement shift registers (except SISO). Appropriate theorems
and lemmas are presented to clarify the proposed designs. The
contribution of this paper will engender a new thread of
research in the field of reversible sequential circuits.
Keywords-shift register; PIPO shift register; universal shift
register; reversible logic; garbage output
I. INTRODUCTION
Energy loss is a very important issue in modern VLSI
designs. Though the improvement in higher-level integration
and the advancement of new fabrication processes have
significantly reduced the heat loss over the last decades,
physical limit exists in the reduction of heat. According to
Landauer [1, 2], logic computation generates kTln2 joules of
heat energy for every bit of information loss where k is
Boltzmann’s constant of 1.38×10-23 J/K and T is the absolute
temperature of the environment. At room temperature the
dissipating heat is around 2.9×10-21 J which is small but not
negligible. If Moore's Law [3] remains valid until 2020, the
amount of heat generated due to information loss will be
significant. This is due to the increasing density into circuits.
Reversible logic does not lose information. Bennett [4]
showed that zero energy dissipation would be possible if the
network consists of reversible gates only. The major
application of reversible logic is in quantum computation as
quantum circuits must be reversible [5]. Quantum
computation is gaining popularity as some exponentially
hard problems can be solved in polynomial time [6].
Reversible logic has also found its applications in several
technologies, such as optical computing [7], ultra low power
CMOS design [8] and nanotechnology [9]. Thus research in
reversible logic is essential for the development of future
technologies.
Toffoli [10] showed that a finite automaton is reversible
if its transition function is invertible. In order to realize a
finite automaton with the use of a reversible sequential
circuit, it is enough to build a reversible realization of its
transition function and use this as the combinational part of
the sequential network. Even though some significant works
have already been done in the field of reversible
combinational logic design, research on reversible sequential
logic [11-13, 20] has not flourished at that pace. To
synthesize reversible memory circuits, reversible sequential
circuits such as shift registers are very essential. This paper
proposes a novel concept on reversible sequential circuit
design that includes serial-in serial-out (SISO), serial-in
parallel-out (SIPO), parallel-in serial-out (PISO), parallel-in
parallel-out (PIPO) and universal shift registers.
Rest of the paper is organized as follows. Section II
provides the necessary background on reversible logic along
with the examples of popular reversible logic gates and their
quantum costs. Section III provides existing realization of
reversible D flip-flop which is used in Section IV to propose
reversible design of shift registers. Comparative study with
the existing SISO shift register design along with the lower
bounds for the proposed designs in terms of number of gates,
garbage outputs and quantum costs are also provided in
section IV. Proper theorems and lemmas are proved to
establish the lower bounds. Section V concludes the work.