# A New Algorithm for Reversible Logic Circuit Synthesis

DOI : 10.17577/IJERTV7IS020081

Text Only Version

#### A New Algorithm for Reversible Logic Circuit Synthesis

Naga Kumar Gaju

Department of Electrical and Computer Engineering Texas Tech University, Lubbock, Texas, USA

Abstract In traditional CMOS technology the energy is expended in the form of loss of bits. This dissipation of energy is in the form of heat dissipation and plays a vital role in low power design of circuits. The conventional circuit design results in the Irreversible circuits which mean the number of outputs is not equal to the number of inputs which implies the loss of bits result in loss of energy. Circuit design based on reversible logic synthesis generate circuits with the number of outputs equal to the number of inputs resulting circuits with no energy loss and furthermore providing the advantage of retrieving the inputs from the outputs. The Reversible Logic design has application in extensive fields like Quantum Computing, Low power CMOS design, and Cryptography. The existing algorithms for realization of a Boolean function as reversible circuit is framed as a network of basic reversible gate library including Cnot gate, Toffoli gate, Fredkin gate etc known as Replacement based approach. In this paper a new algorithm for realizing a function as reversible circuit is based on Truth table approach is proposed and used to synthesize many benchmark circuits with simpler circuits, less gate count.

KeywordsReversible; bijective; Truth table approach; ancilla; gatecount

1. INTRODUCTION

Energy loss is a vital consideration in any circuit design. The requirement for energy efficient and faster computing circuits leads to physical limitations. As predicted by Moore the transistor count in a chip will double everyone year. Shrinking in transistor size resulted in many implementational and operational difficulties like energy dissipation. Data processing is accompanied by a least amount of heat generation. According to Landauers principle the loss in one bit of information will result in an estimated energy dissipation equal to KTln2 Joules, where K is Boltzmanns constant and T is absolute temperature of operation [1]. In 1973 C.H. Bennett proved that this loss in energy and information can be conserved by making the computation reversible. Conventional computations by its nature are irreversible. Logically irreversible if the output does not uniquely define the inputs and the input cannot be retrieved from its output as all the input bits do not propagate till output[2]. Logical irreversibility implies physical irreversibility accompanied by dissipative effects. Due to limitations of conventional computing reversible computing seems to be the possible solution. Reversible computing saves energy dissipation by avoiding bit destruction.

Lauders principle states that the source of heat generation

in computation is destruction of bits not their transformation[2]. The reversible computation is simply based on fact that, the existing information in any system cant just be destroyed but transformed in according to fact that at low level physics reversible means in closed system energy transforms from one state to another overtime in a mathematically invertible way. Because of less or no energy dissipation we can achieve high density and so we can achieve smaller size overcoming the physical limitations.

Any function of Boolean variables is said to be reversible if the number of outputs is equal to the number of inputs and function mapping from input vectors to output vectors is bijective function[4].

Any irreversible Boolean function can be made reversible by transforming the irreversible truth table to reversible truth table which requires extra inputs to bias it known as ancilla and extra outputs known as garbage outputs to hold the information which provides reversibility[5].

The important parameters to be considered in synthesis of reversible logic[4]: minimum number of ancilla, minimum number of garbage outputs, minimum number of gates, and minimum quantum cost.

2. PREVIOUS WORK

There are two approaches for conversion of irreversible circuit to reversible circuit:

1. Replacement based approach [Fig.1(a)]and

2. Truth table approach[Fig.1(b)].

The replacement based approach involves the irreversible circuit is directly converted into reversible circuits by replacement based reversible conversion.

The truth table is based on generating a truth table for the given circuit and then using reversible synthesis tools to generate reversible circuit.

The basic classifications with brief descriptions of methods 1.Composition method[4]: A Boolean function is realized as a network of small and well known reversible gates.

1. Decomposition method[4]: A Boolean function is decomposed into small functions which are realized as separate reversible networks.

2. EXOR logic based method[4]: Uses only Toffoli gate network to realize a Boolean function by decomposing it.

3. Search method[4]: A function is expanded and reduced with maintaining the output functionality unchanged. This method results in large circuits comparatively.

Schematic representation

Boolean function realization using existing algorithm[5]

Boolean function realization using proposed algorithm

[1]

1. b0 c c0

1

[1] [2] [3] [6] [5] [7]
2. c0

[9]

b

a0

[3]

Fig.2.1(a)

[7]

c

[8] [4]

1

[5]

a

[2]

a0

[6]

b0

[4]

Fig.2.2(a) Fig.2.3(a)

a b0

[1] [4] [2]

c

0

[6]

b0

[7]

Fig.2.1(b)

1. c0

[5] [9] [6]
2. a0

[3] [7] [8]

a

[1]

b

1

[3]

1

[2] [4]

a0

[5]

c0

Fig.2.2(b) Fig.2.3(b)

a

b

Fig.2.1(c)

[1] [5] [2] [3] [4]

bo a

ao

b

[8]

1

[9]

bo

1

co

[6]

c

[6] [10] [7] [11] [8]

co [2]

c

1

[1] [3] [5] [4]

ao

[7] [9]

Fig.2.2(c)

Fig.2.3(c)

Fig.1(a) Replacement based Fig.1 (b)Truth table based approach approach

In this paper the truth table-based approach is used for reversible logic synthesis. The circuits generated for the functions with schematic representation Fig.2.1(a), Fig.2.1(b) and Fig.2.1(c) using replacement based approach are Fig.2.2(a), Fig.2.2(b) and Fig.2.2(c) and the truth table based approach are Fig.2.3(a), Fig.2.3(b) and Fig.2.3(c) respectively showing the gate count. The algorithm proposed in this paper resulted in circuits with less number of gates compared to existing algorithms.

3. DEFINITIONS

1. Irreversible Logic Function

A Boolean function is said to be irreversible if the outputs of the function does not uniquely define the inputs.

2. Bijective Function

A function is bijective if each element in the input set has a unique mapped output also known as one-to-one mapping.

G1

1 0 0

0 0 0

0 1 0

1 1 0

0 0 1

1 0 1

1 1 1

0 1 1

0

1

0

1

0

1

1

0

2

3

4

5

#### 0

G2

G1

F

G2

G1

F

G2

G1

F

G2

G1

F

G2

F

0 1 1 0 0 0

1 0 0 1 0 0

0

1

0

1

1

0

2

3

4

5

6

7

2 0 2 0 1 0

3 1 3 1 1 0

4 0 4 0 0 1

5 1 5 1 0 1

#### 6

6 1 7 0 1 1

7 0 6 1 1 1

Step:1

Step:2

Step:3

Step:4

Step:5

Fig. 3 An example illustrating step by step procedure for multiple input and single output algorithm

3. Reversible Logic Function

A Boolean function is said to be reversible if the number of the outputs and the inputs are equal and the outputs of the function have the unique preimage. If the function is one-to-one mapping or bijective function.

4. Ancilla

The constant input added to the circuit to make it reversible and whose original state is known in advance.

5. Garbage outputs

Refers to the number of outputs added to make a circuit reversible such that

Number of inputs + Ancilla = Number of outputs + Garbage outputs

6. Gate count

The number of logic gates used in realization of reversible logic circuit.

4. ALGORITHM FOR MULTI-INPUT SINGLE OUTPUT

1. Algorithm

Let f (a1, a2, a3,…., an) = (m0, m1, … mm) be a Boolean function defined in terms of minterms and let the number of minterms be m.

Classifying the given functions into two cases:

1s such that a unique vector exists, and number of inputs are equal to number of outputs

1. rearrange back the sequence to the initial sequence

2. using Quine McCluskey technique represent the output functions in minimized form

3. Choose the garbage output functions which uses minimum number of gates to realize corresponding to the arranged sequence in the pattern of MSB or LSB.

Case II: If number of minterms not equal to half the number of input vectors

Constant input ancilla is added to make the function reversible

• the outputs of the reversible circuit include the original inputs and ancilla f (a1, a2, …, an)

2. Example

Case I: Let f (1,2,3) = (0,3, 5, 6) be the given Boolean function. To make it a reversible function the number of outputs must be equal to number of inputs (n=3) we must add two garbage outputs.

For the given function the number of minterms (m) = 4, implies m=23-1 belongs to the first category no ancilla required.

Minimizing the columns in the Step v using the Quine McCluskey method results in the best possible minimized functions correspondingly are:

1. with number of minterms(m) equal to half of the number of input vectors 2/2.

2. with number of minterms(m) greater than or less than the

number of input vectors.

F:

G1:

G2:

+ + +

2

3

(1)

(2)

(3)

Case I: If number of minterms = half of the number of input vectors

1. Fill the truth table marking the corresponding minterms

2. number the sequence of 0s and 1s from 0 to 2 1

3. arrange the sequence in the pattern of Least Significant Bit(LSB) or the Most Significant Bit(MSB)

F is the main function and G1, G2 are the garbage outputs

Case II: Let f(1,2,3) = (0,3) be the given Boolean function. The number of minterms in the given function are not equal to half the number of input vectors. This falls into second category. Ancilla(x) is added to the input and the outputs are a1, a2, a3 and x f (a1, a2, a3)

4. add the garbage outputs by filling the missing components of the corresponding vector with 0s and

Inputs:

Outputs:

a1, a2, a3, x

, , ,

+ +

+

(4)

(5)

Algorithm I: For single output Boolean function

Input: number of inputs(n), number of minterms(m) and minterms

Output: reversible logic with main function and garbage outputs in minimized form

begin

If m=2n-1

for i=0 to 2n-1

do if output function has minterm i a[0][i]=1

else

a[0][i]=0

end

arr[i]=i

end

for i=0 to 2n-1

do

count=0

if a[0][i%2] Th 0 for j=1 to 2n-1 do

if a[0][j]=1 & count=0 swap a[0][i] a[0][j] swap arr[i] & arr[j] count=count+1

end if end end if

end

for k=1 to n-1

do

for i=0 to 2n-1

fill a[k][i] as 2k 0s 2k 1s

end else

do

constant input ancilla is added to make the function reversible

the outputs of the reversible circuit include the

original inputs and ancilla f (a1, a2,

…, an)

end end

do

Using Quine McCluskey technique finding prime implicants

choosing essential prime implicant

Print the output functions in minimized form

end end

 F1 F2 G G G G G G G G G 0 1 2 3 4 5 6 7 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 Step:1 2 3 4 5 6 7 8 9

Fig. 4 An example illustrating step by step procedure for proposed algorithm for multiple output

5. ALGORITHM FOR MULTI-INPUT MULTI OUTPUT

1. Algorithm

Let f1 (a1, a2, a3, …., an) = (m0, m1, … mm1), f2 (a1, a2,

a3, …., an) = (m0, m1, … mm2) ,………,

fout (a1, a2, a3, …., an) = (m0, m1, … mmout) be a Boolean functions defined in terms of minterms and let the number of minterms be m1,m2,….,mout in each output function respectively.

Classifying the given functions into two cases:

Case I:If number of 1s in f1f2……fout = m1=m2………= mout

If the row of outputs occurs for the first time join 0 to the row

else join 1 to the row Continue until number of outputs equal number of inputs

Case II: Else

a constant input ancilla is added to make the

function reversible Outputs are ancillaf1, ancillaf2,

………,ancilla fout and the functions as a result of repeating caseI after adding ancilla

2. Example

Case I: Let number of inputs n=3(a1,a2,a3), number of outputs out=2, number of minterms in first output function m1=4, number of minterms in second output function m2=4 f1(a1,a2,a3)=(1,3,5,7) and

f2(a1,a2,a3)=(2,3,6,7)

For given functions number of ones in f1f2=m1=m2 Minimizing the columns in the Step v using the QuineMcCluskey method results in the best possible minimized functions correspondingly as

F1: a1 (6)

F2: a2 (7)

G: a3 (8)

F1, F2: main function G: Garbage functions

Case II: Let n=3, out=2, m1=3, m2=4, f1(a1,a2,a3) =

(1,3,5) and f2(a1,a2,a3)=(1,3,5,7)

Ancilla(x) is added to the input and the outputs are

TABLE I

GATE COUNT COMPARISON FOR SOME STANDARD FUNCTIONS FROM[8]

F1:

F2:

G1:

G2:

+

+ +

3 + 3

123

123

(9)

 Function Using Fredkin gate Using Peres gate Using Toffoli gate Using Proposed algorithm Gate Count AND OR AND OR AND OR AND OR F1 ABC 8 4 8 4 9 6 4 3 F2 AB 4 2 4 2 3 2 3 2 F3 ABC+ABC 12 6 16 8 12 6 5 4 F4 ABC+ABC 16 8 12 6 – – 5 4 F5 AB+BC 20 10 20 10 12 8 4 3 F6 AB+ABC 12 6 32 16 – – 4 2 F7 ABC+ABC +ABC 20 10 20 10 – – 7 3 F8 AB+BC+CA 32 16 4 22 – – 7 6 F9 AB+BC 4 2 16 8 12 8 6 4 F10 ABC+ABC +ABC+ABC 44 22 16 8 6 4 4 3

(10)

(11)

(12)

F1, F2: Main functions G1, G2: Garbage functions

Algorithm I: For multiple output Boolean function Input: Number of input variables(n), number of minterms in each function(mi), minterms in the function

Output: Main function and garbage outputs in minimal form

begin

Read n, number of outputs(out), number of minterms in each function(array arrm), minterms in each output function (array arrf1,array arrf2,…,array arrfout)

If

for i=0 to out-1

if number of ones in

arrf1arrf2.arrfout=arrm[i]

end if for i=out to n-1

do for j=0 to 2n-1

do for k=0 to out-1

do

if jth row occurs for first time arrfout+1[j][i]=0

else jth row is repeated arrfout+1[j][i]=1

end if end

end

TABLE II

GATE COUNT COMPARISON FOR BENCHMARK CIRCUITS FROM[9]

else

end

19×3

 Benchmark Circuit Ancilla Gate count (existing) Gate count (proposed) existing proposed AND gates OR gates AND gates OR gates 1 2of5 2 0 20×3 20×2 12 11 2 rd32 1 0 4×3 4×2 7 9 3 4_49 0 0 13×3 13×2 16 12 4 xor5 0 0 4×3 4×2 14 12 5 4mod5 1 1 5×3 5×2 8 7 6 5mod5 1 1 11×3 11×2 14 13 7 ham3 0 0 5×3 5×2 9 6 8 hwb4 0 0 15×3 15×2 16 12 9 6sym 0 0 14×3 14×2 26 25 10 9sym 0 0 73×3 73×2 74 73 11 alu 0 1 18×3 18×2 29 19 12 majority3 0 0 4×3 4×2 9 6 13 majority5 0 0 16×3 16×2 35 30 14 5one013 0 0 19×3 19×2 42 36 15 5one245 0 0 20×3 20×2 45 30 16 5one013 0 0 19×3 19×2 42 36 17 5one245 0 0 20×3 20×2 45 30 18 4b15g_1 0 0 15×3 15×2 23 19 19 4b15g_2 0 0 15×3 15×2 34 29 20 4b15g_3 0 0 15×3 15×2 29 24 21 4b15g_4 0 0 15×3 15×2 31 27 22 nth prime3 0 0 4×3 4×2 8 5 23 nth prime4 0 0 12×3 12×2 23 16 24 nth prime5 0 0 25×3 25×2 39 34 25 Mod5adder 0 0 19×2 25 19

do

outputs are ancillaarrf1, ancillaarrf2..ancillaarrfout and functions resulted by running caseI after adding ancilla

end end

do

Using Quine McCluskey technique finding prime implicants

choosing essential prime implicant

Print the output functions in minimized form

end end

6. RESULTS

The proposed algorithm is used to synthesis various Boolean functions and the results with comparison in terms of gate count are as follows:

70

60

50

40

30

20

10

0

Gate Count using Fredkin Gate

Gate Count using Peres Gate Gate Count using Toffoli Gate

Gate Count using Proposed Algorithm

F1 F2 F3 F4 F5 F6 F7 F8 F9 F10

Fig. 5 Graph showing Gate Count for standard function Table I

400

350

300

250

200

150

100

50

0

Existing Gate Count Proposed Gate Count

Fig. 6 Graph showing Gate Count for standard function Table II

7. CONCLUSIONS

An algorithm and a tool are described that uses truth table approach to synthesize the reversible logic circuits is framed. The algorithm uses the back tracing and bijective mapping technique to fill the truth table to find the garbage functions and ancilla if any in the minimized form using the Quine-McCluskey minimization within 2n-1 steps for n number of inputs. The tool designed basing on the proposed algorithm is used the synthesize the functions tabulated in table I and table II showing the reduced gate count of 36 percentage on average to realize the functions compared to existing algorithm. The proposed algorithm efficiently synthesizes the reversible function without using any network basic reversible gates such as Toffoli or Fredkin resulting in the reduced gate count.

8. REFERENCES

1. R. Landauer, Irreversibility and heat generation in the computing process, IBM J. Res. Develop., vol. 5, no. 3, pp. 183191, July 1961.

2. Micheal P. Frank, The Physical Limits of Computing, Vol.4, No.3, pp. 16-26, May-June 2002, doi:10.1109/5992.998637, IEEE, 2002.

3. C.H. Bennett, Logical Reversibility of Computation, IBM Research and Development, pp. 525-532, November 1973

4. Garbage in Reversible Designs of Multiple Output Functions, Dmitri Maslov and Gerhard W. Dueck, Faculty of Computer Science, University of New Brunswick

5. Irreversibility and Heat Generation in the Computing Process IBM Journal of Research and Development ( Volume: 5, Issue: 3, July 1961)

6. An Algorithm for Synthesis of Reversible Logic Circuits, Pallav Gupta, Student Member, IEEE, Abhinav Agrawal, and Niraj K. Jha, Fellow, IEEE , IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 25,

NO. 11, NOVEMBER 2006

7. New Universal Gate Library for Synthesizing Reversible Logic Circuit Using Genetic Programming, Mustapha Yusuf Abubakar, Low Tang Jung, Mohamed Nordin Zakaria, Ahmed Younesy and Abdel-Haleem Abdel-Atyz, 2016 3rd International Conference On Computer And Information Sciences (ICCOINS)

8. Basic Logic Gate Realization using Quantum Dot Cellular Automata based Reversible Universal Gate, Saroj Kumar Chandra, Prince Kumar Sahu, International Journal of Computer Applications (0975- 8887)

9. Reversible Benchmark Circuits. Available: http://webhome.cs.uvic.ca/~dmaslov/