Reversible and DNA Computing. Hafiz M. H. Babu

as it is likely that the growth of heat generation causing information loss will be noticeable in future.

      Reversible circuits are fundamentally different from traditional irreversible ones. In reversible logic, no information is lost, i.e., the circuit that does not lose information is reversible. Zero energy dissipation would be possible if the network consists of reversible gates only. Thus, reversibility will be an essential property for the future circuit design. Quantum computation is also gaining popularity as some exponentially hard problems can be solved in polynomial time. It is known that quantum computation is reversible. Thus, research in reversible logic is helpful for the development of future technologies; it has the potential to methods of quantum circuit construction resulting in more powerful computers. Quantum technology is not the only one where reversibility is used.

      Reversible logic has also found its applications in several other disciplines such as nanotechnology, DNA technology, and optical computing. In computers, numbers are stored in straight binary format. Due to inherent characteristics of floating‐point numbers and limitations on storing formats, not all floating‐point numbers can be represented with desired precision. So, the computing in decimal format is gaining popularity because precision can be avoided in this format.

      This part starts with some backgrounds and preliminary studies about reversible logic synthesis and some popular reversible gates that are given in Chapter 1. Many of the reversible gates are included in different chapters. Some approaches of designing different reversible adders (full adder, carry skip adder, carry look‐ahead adder, and ripple carry adder) and subtractor circuits are given in Chapter 2. Chapter 3 presents the design of a reversible signed multiplier which is based on Booth's recoding. A design of sequential division circuit using reversible logic is shown in Chapter 4. The hardware has its application in the design of a reversible arithmetic logic unit. The design of a reversible low power n‐bit binary comparator is discussed in Chapter 5. Chapter 6 shows the designs of reversible latches and flip‐flops are presented, which are being optimized in terms of quantum cost, delay, and garbage outputs. The contents of this chapter have optimized the reversible sequential circuit designs in terms of reversible gates and garbage outputs. The designs of reversible D latch and D flip‐flop are also discussed with asynchronous set/reset capability. A reversible design for both

‐bit synchronous and asynchronous counter is described in Chapter 7. This chapter also describes a synthesized design of the reversible counter that is optimized in terms of quantum cost, delay, and garbage outputs.

Chapter 8 is divided into two parts, namely, reversible barrel shifter and reversible shift register. In the first part of this chapter, the design methodology of a reversible barrel shifter is presented. In the second part of this chapter, reversible logic synthesis is carried out for SISO shift register.The key contribution of this part is the reversible realization of SIPO, PISO, PIPO and universal shift registers. Two reversible gates have been introduced in Chapter 9, named as R‐I gate and R‐II gate, for realizing reversible combinational logic circuits. These two gates can be used for realization of basic logical functions such as AND, XOR, and MUX. Chapter 10 is also divided into two parts, namely, reversible field programmable gate array (FPGA) and reversible programmable logic array (PLA). In the first part of this chapter,a design of reversible architecture of the logic element of Plessey FPGA is described, which results in significant power savings. In the second part of this chapter, a design of reversible PLA is described, which is able to realize multi‐output ESOP (exclusive‐OR sum‐of‐product) functions by using a

reversible gate, called MG (MUX gate).

      Chapter 11 is also divided into two parts namely reversible random access memory (RAM) and reversible programmable read‐only memory (PROM). In the first part of this chapter, the reversible logic synthesis of RAM is described with a

reversible gate named as FS. In the way of designing a reversible RAM, an

reversible decoder, reversible D flip‐flop, and write‐enabled master–slave D flip‐flops are also designed. In the second part of this chapter, a reversible PROM design is described. A reversible decoder named ITS and another reversible gate TI are also introduced. In addition, for designing the reversible PROM, an AND‐plane and an Ex‐OR plane are also described. The design of programmable reversible logic gate structures is presented in Chapter 12, which implements ALU and presents its different uses. Finally, a reversible control unit is presented in Chapter 13. Two

reversible gates, namely HL gate and BJ gate, are introduced to design reversible decoder and JK flip‐flop.

1 Reversible Logic Synthesis

Reversible logic plays a vital role at present time and it has different areas for its applications, namely low‐power CMOS, quantum computing, nanotechnology, cryptography, optical computing, DNA computing, digital signal processing (DSP), quantum‐dot cellular automata (QCA), digital communications, and computer graphics. It is not possible to realize quantum computing without implementation of reversible logic. The main purposes of designing reversible logic circuits are to decrease quantum cost, depth of the circuits, and the number of garbage outputs. This chapter explains the basic reversible logic gates for more complex system, which may have reversible circuits as a primitive component and can execute complicated operations using quantum computers. The reversible circuits form the basic building block of quantum computers, as all quantum operations are reversible. This chapter presents the information related to the primitive reversible gates and helps researchers in designing higher complex computing circuits using reversible gates.

1.1 Reversible Logic

      In this section, basic definitions and ideas related to reversible logic are presented. Formal definitions of reversible gate, garbage output, and the popular reversible gates, along with their input–output vectors, are presented here. Illustrative figures and examples are also included in respective discussions.

1.2 Reversible Function

      The multiple‐output Boolean function

of n Boolean variables is called reversible if:

      1 The number of outputs is equal to the number of inputs.

      2 Any output pattern has a unique pre‐image.

      In other words, the functions that perform permutations of the set of input vectors are referred to as reversible functions.

1.3 Reversible Logic Gate

Reversible logic has unique mapping between input and output bit pattern. A unit logic entity is represented as a gate. The gates or circuits that do not lose information are called reversible gates or circuits.

      Property 1.3.1

      A reversible circuit is a circuit in which the number of input and the number of output is equal and there is one‐to‐one mapping between input and output vectors.

Let us consider the gate shown in Figure 1.1. According to the definition, the gate is a reversible gate, because it has k number of inputs and k number of outputs and the gate is known as

reversible gate. Without the NOT gate, classical logic gates are called irreversible, since they cannot determine the input vector states from the output vector states uniquely.

      Example 1.1

There