An efficient design of reversible decoder

The reversible logic design is more attractive field for research in recent scenario. Now-a-days many researchers are using reversible logic for implementing sequential and combinational logics. There are various applications of reversible gate in different field such as CMOS design, quantum cost, NANO technology, DNA computing, computer graphics, optical computing, low power VLSA etc. A decoder is a combinational logic circuit that is widely used in various applications including data de-multiplexing, seven segment displays and memory address decoding. In this thesis, we have designed a 2: 4 decoder. Using our proposed 2: 4 decoder and Fredkin gate, we have also implemented a 3: 8 decoder. The proposed design has been compared with a previously existing design and the design has been generalized to decoder with n-inputs. The proposed design is efficient in terms of gate count, garbage outputs, constant inputs and quantum cost than the existing ones. We have used Proteus software for implementing and simulating the circuit.

As it is the period of unrest of science and technology, world relies upon the computerized electronics. In the process of computation, maximum computers lose information [7]. Consider two input OR gate. Observing an output of 1 does not give correct information to define the input combination that give to the rise of the output. In fact any one of the three different input combinations (01, 10, 11) would force the output of the OR gate to 1 [1]. So the simple two input Boolean OR gate would reject the input information. Launder [2] demonstrated that the heat created during calculation isn’t because of handling bits, however because of the loss of data. Wiping of each bit of data causes a kTln2 amount of heat dissipation where k is the Boltzmann’s constant = 1. 3805×10-23 J/k and T is the temperature in absolute scale. Later Bennett demonstrated that heat dissipation can be maintained by utilizing reversible calculation. For this reason reversible logic has received great importance in the recent years because of its feature of reduction in power dissipation. There are various applications of reversible gate in different fields such as CMOS design, Quantum computing, NANO technology, DNA computing, computer graphics, optical computing, low power VLSI etc.

Reversible gates are circuit that one-to-one mapping between vectors of inputs and outputs [3]. Thus the vector of input states can be always constructed from the vector of output states [3]. Classical logic gates are irreversible because it is impossible to reconstruct input vector states from output vector states. There are many reversible gates such as Feynman gate, Fredkin gate, Peres gate, Toffoli gate, Thapiyal gate (TSG), TR gate.

Decoders are one of the most important circuits used in combinational logic. They are used for addressing memories and caches and they are used in conjunction with counters in multiphase with clock generators [7]. As n-to-2n decoder takes an n bit input combination and asserts the output line addressed by that input combination. Each output line corresponds to exactly one input line. Modern computers reduce power by taking advantage of reversibility and quantum computers operate reversibly. Researchers have already proposed reversible designs of many common arithmetic and logical units, including adders, multipliers, shifters, and even registers.

In this thesis, we have proposed a novel reversible decoder design and analyze it in terms of quantum cost, garbage outputs, constant inputs, number of gates and quantum delay. We have found that our proposed designs are much better than the existing ones.

This section defines reversible logic, reversible gate, constant input, garbage output and quantum cost.

Reversible Logic

Reversible gates have equal number of inputs and outputs and each of this input output combination is unique. Reversible gates are n*n logic gates where the input vectors I = I (I1, I2, I3,……, In) are mapped to the output vectors O = O (O1, O2, O3,……, On) [9]. In other words we can say a gate is reversible if and only if there is a one-to-one mapping between its inputs and outputs [3]. Direct fan-outs from the outputs from the reversible gates or connecting reversible gate G directly to any input of G are not permitted while constructing circuits with reversible gates [11]. Fan-outs are not allowed in reversible circuit since they violate one-to-one mapping [3]. In Figure-1, reversible gate mapping is shown.

NOT Gate

The NOT gate is simplest reversible gate which just flips the input as shown in Figure- 2. Its quantum cost is 0.

Feynman Gate

Feynman gate is a 2*2 reversible gate and its quantum cost is 1. The inputs are A, B and the outputs are and . Only linear reversible function can be built that only using 2*2 Feynman gates and inverters [3]. The block diagram and quantum cost of Feynman gate are shown in Figure-3(a) and Figure-3(b) respectively.

Fredkin Gate

Fredkin Gate is a fundamental concept in reversible and quantum computing [3]. Fredkin gate is a gate that maps three inputs onto three outputs. Every arithmetic or logical function can be implemented by using 3*3 Fredkin gate. Its quantum cost is 5. Figure-4(a) and Figure-4(b) represent the block diagram and quantum representation of Fredkin gate respectively.

TR Gate

Figure-5(a) and Figure-5(B) show the block diagram and the quantum realization of TR gate. It has three inputs and three outputs. The inputs are A, B, C and outputs P = A, Q = and R = AB ’ C. The quantum cost of TR gate is 4.

Peres Gate

Figure- 6(a) shows a 3*3 Peres gate. The input vector of Peres gate is I (A, B, C) and the output vector is O (P, Q, R). The output is defined by P = A, Q = A ⨁ B and R= AB ⨁ C. The quantum representation of Peres gate is shown in Figure-6(b) and quantum cost of a Peres gate is 4.

G. Constant Input and Garbage Output

Constant inputs refer to the input lines that are either set to zero (0) or one (1). Sometimes it is needed to apply constant input to any reversible gate for a specific logic operation. A reversible circuit without constants on inputs realizes on all outputs only balanced functions [3].

Some outputs may not be used in the circuit for computation. Such outputs are called garbage output. It is not primary outputs. It needs only to maintain reversibility. Reversible circuit can be realized unbalanced functions only with additional inputs and garbage outputs [3].

Different type of reversible decoder such as 2 X 4, 3 X 8, 4 X 16 are implemented by using CNOT gate, TR gate and Fredkin gates. Fredkin gates are mainly used to implement these circuits. These decoder are used to design some combinational circuit such as multiplexer, sub-tractor, comparator adder, seven segment display etc.

Many proposal are given for the design of reversible decoder. A 2: 4 decoder using Peres gate, TR gate and 3 CNOT gates are proposed in [5]. The quantum cost of this design is 11. In [6], a proposal has been given for designing 2: 4 decoder. Peres gate, TR gate and three Feynman gate have been used for designing this proposal, as shown in Figure-7.

The total quantum cost of this design is also 11. A proposal also have been given for designing 4: 16 decoder using this 2: 4 decoder. In the sub-division, We propose our design of 2: 4 decoder, 3: 8 decoder and using this 2: 4 decoder, we have also designed our 3: 8 decoder having lower quantum cost.

Proposed 2: 4 decoder

We know 2: 4 decoder means 2 input lines and 4 outputs lines that means X, Y are two inputs , then the outputs are X’Y’, X’Y, XY’, XY respectively. For designing reversible 2: 4 decoder, we have used a Fredkin gate, TR gate and CNOT gate as shown in Figure-8. Fredkin gate gives output X, X’Y ⨁ XZ, X’Z ⨁ XY. Since Z sets zero as constant input. So we gate X’Y (second output of decoder), XY. TR gate gives output X (garbage output), X Å Y and XY’ (third output of decoder). To flip the output of X Å Y, a NOT gate is used but does not increase the quantum cost. (X Å Y) ’ ⨁ XY = X’Y’ (first output of the decoder). The first output of the CNOT gate is XY (fourth output of the decoder). Since the quantum cost of Fredkin gate, TR gate and CNOT gate is 5, 4, 1 respectively, so the total quantum cost of our proposed 2: 4 decoder is 10.

Proposed 3: 8 decoder

A 3: 8 decoder means 3 inputs lines and 8 outputs lines. If inputs are X, Y, Z then the outputs are X’Y’Z’, X’Y’Z, X’YZ’, X’YZ, XY’Z’, XY’Z, XYZ’, XYZ. By using TR gate and CNOT gate we can also design a 3: 8 decoder as shown in Figure-9. But for better efficiency and to minimize quantum cost, we use only Fredkin gate because each Fredkin gate is capable of performing two multiplications. The total quantum cost of our proposed 3: 8 decoder is 30. To design 4: 16 decoder, 8 Fredkin gates and 3: 8 decoder will be needed. Since the quantum cost of 3: 8 decoder is 30 and 8 fredkin gates are 40, so the total quantum cost of 4: 16 is 70.

Generalisation to n : 2n decoder

If we have a (n-1): 2n-1 decoder and Fredkin gate, then we can easily design a n: 2n . So the design’s quantum cost increases by 5∗2n-1. 2: 4 decoder can be built in the same process, but our proposed design has lower quantum cost.