Printer Friendly

A novel design of reversible squarer circuit.

1 INTRODUCTION

Reversible logic is an emerging field of research which has been attracted researchers in the past decade and has applications in hardware and software designs such as low power circuit design, photonic circuits, cryptography, nanotechnology and particularly quantum computing. In reversible computation there is no information loss and it is possible to determine inputs from outputs in the backward trace [1, 2]. Moreover reversible computation was proposed to minimize energy dissipation [1, 3]. According to Von Neumann estimation, minimum energy loss per bit is KTLn2 Joules where K=1.380 x [10.sup.-23] [JK.sup.-1] is Boltzmann constant and T is environment temperature [4]. Landauer proved that in irreversible computation, losing one bit of information dissipates energy as heat and this dissipation is at least KTLn2 Joules of energy loss per bit [1]. Later Bennett showed that if we use reversible circuits we can save this amount of energy loss [3].

In reversible gates and circuits, number of inputs and outputs is equal and inputs are mapped to output as a one-to-one correspondence. This mapping leads to ability to determine each input from outputs. Because in conventional irreversible functions number of inputs and outputs are not equal, in order to design a reversible circuit for an irreversible function, some inputs and outputs need to be added to circuit to keep the property of reversibility. This inputs that we add to a circuit to make it reversible are called constant inputs and the outputs added to make a circuit reversible is called garbage outputs [5]. To optimize a reversible circuit design, decreasing these two parameters is important. Quantum cost of a reversible circuit is defined as the number of elementary quantum operations required to realize a reversible circuit [5].

Reversible logic has applications in both hardware and software design such as low power circuits design, photonic circuits, cryptography, nanotechnology and quantum computing.

Squarer is an arithmetic circuit used in some special processors such as digital signal processors. Square operation is a special multiplication operation which has two equal operands. So a multiplier circuit with two equal inputs can be used as a squarer circuit but in some arithmetic processors, due to the increased delay and power which caused by using the multiplier circuit as squarer, a special squarer circuit can be designed for square operation. In this paper, we propose a reversible squarer circuit by means of PG and HNG gates [6, 7]. Also F2G [8] gate are used to generate fan-outs. Peres gate is used for AND operation and as reversible half adder and HNG gate is used as reversible full adder. Both gates have optimal quantum cost as reversible half adder and full adder. Unlike prior proposed reversible multiplier circuits, our reversible squarer circuit has simplified in only two main stages and the partial product reduction stage which used in prior reversible multiplier circuits has removed. Also our design has optimal computation stages, number of gates, quantum cost, constant inputs and garbage outputs. The proposed reversible squarer design can be used as squarer circuit in reversible arithmetic unit in reversible digital signal processors.

The rest of this paper organized as follows. In section 2, the reversible gates used in our proposed reversible design, have been presented and then irreversible squarer circuit and simplification steps are shown in section 3. These simplification steps lead to decrease in the squarer operation into only one carry ripple addition. In section 4, our proposed reversible squarer design based on simplified irreversible squarer design has been presented and also we propose some notes to further simplification in our design. In section 5 we evaluate our proposed design and compare it to other related works in this field.

2 REVERSIBLE GATES AND CIRCUITS

A gate is reversible if number of its inputs and outputs is equal and there is a one-to-one mapping between its inputs and outputs [9, 10] as Figure 1. So recovering inputs from outputs is possible in this design. A circuit designed with reversible gates is called a reversible circuit. An n x n reversible gate or circuit has equal numbers of inputs and outputs that are represented with input vector (Iv) and output vector ([O.sub.v]) [13] as:

[I.sub.v] = ([i.sub.1], [i.sub.2], [i.sub.3] ... [i.sub.n]) [O.sub.v] = ([o.sub.1], [o.sub.2], [o.sub.3] ... [o.sub.n])

Reversible circuit design is more complex than irreversible circuit design. In reversible design fan-out and feedback are not allowed [9, 10]. For using fan-out in the circuit, some reversible gates can be used as fan-out generator gates. In the rest of this section, we investigate the reversible gates that we used in our reversible squarer design.

F2G gate. This reversible gate can be used as fan-out generator [8] and we use it in the proposed design. This gate can produce three fan-outs on its three output lines. If "B" and "C", both become"0", each of its three outputs become equal to input "A". This 3x3 reversible gate which is shown in Figure 2 can be represented as:

[I.sub.v] = (A, B, C), [O.sub.v] = (A, A [direct sum0] B, A [direct sum] C)

Quantum cost of F2G gate is 2.

Peres gate. This is a 3x3 reversible gate (Figure 3) that is represented as:

[I.sub.v] =(A,B,C), [O.sub.v] =(A, A [direct sum] B, AB [direct sum] C)

This reversible gate is used as reversible half adder in our reversible squarer design. In this gate the second output is equal to A[direct sum]B which is the sum output of the half-adder circuit and if C = 0 then the third output is equal to "A.B" which is the carry output of the half-adder circuit. Quantum cost of Peres gate is equal to 4.

HNG gate. This gate is a 4x4 reversible gate that is represented as:

[I.sub.v] = (A, B, C, D), [O.sub.v] = (A, B, A [direct sum] B [direct sum] C, (A [direct sum] B). C [direct sum] AB [direct sum] D)

This reversible gate is used as reversible full adder in our reversible squarer design. The third output of this gate is A[direct sum]B[direct sum]C which is the sum output of the full-adder circuit and the fourth output becomes (A[direct sum]B).C[direct sum]AB if D = 0, which is the carry output of the full-adder circuit, see Figure 4. In this case input D is constant input.

Moreover the first and second outputs are garbage outputs, since they have not used for more computation in the circuit. Quantum cost of HNG gate is equal to 6.

3 IRREVERSIBLE SQUARER CIRCUIT

Squarer operation is a special multiplication with two equal operands. Multiplier circuit can be used as squarer circuit but in some processors to decrease delay and power, a special circuit for square operation is designed. A 4-bit squarer operation is depicted in Figure 5.

In this squarer circuit, each product term [x.sub.i][x.sub.i] can be replaced by [x.sub.i] and each two equal terms [x.sub.i][x.sub.j] and [x.sub.j][x.sub.i] in a column can be replaced by [x.sub.i][x.sub.j] in the next column [11, 12]. Therefore the partial product matrix can be converted to new partial product in the Figure 6.

To have even further simplification one can also use the following equation [11]:

[x.sub.i][x.sub.j] + [x.sub.i] = 2[x.sub.i][x.sub.j] + [x.sub.i] - [x.sub.i][x.sub.j]

= 2[x.sub.i][x.sub.j] + [x.sub.i] (1 - [x.sub.j]) (1)

= 2[x.sub.i][x.sub.j] + [x.sub.i][bar.x.sub.j]

For example: [x.sub.1][x.sub.0] + [x.sub.1] = 2[x.sub.1][x.sub.0] + [x.sub.1][bar.x.sub.0]

So applying equation (1), in columns 3, 5 and 7 of Figure 6, the depth of the partial product matrix is reduced to 2 and partial product reduction step is removed and squarer circuit be reduced to a carry ripple addition and some AND gates [11] as Figure 7.

From Figure 7, we further find out that when column 6 has carry propagation to column 7, the term [x.sub.3][[bar.x].sub.2] in the column 7 is 0, so we conclude that column 7 never propagates carry to column 8. Since column 6 does not propagate carry to the next column the length of carry propagation adder decreases to 4. In other words, when the term [x.sub.3][[bar.x].sub.2] is in logic 1, four conditions can occur: the 4-bit input to the squarer circuit which has the form [x.sub.3][x.sub.2][[x.bar].sub.1][x.sub.0] can have the values 1000, 1001, 1010 or 1011. In these cases when the term [x.sub.3][x.sub.2] in column 7 is in logic 1, no carry propagates to this column from less significant columns and as a result there is no propagation to column 8. In the case of [x.sub.3][[bar.x].sub.2] =0 it is clear that we have no carry propagation to column 8.

Now we have all ingredients to implement a reversible circuit of the above optimized irreversible squarer.

4 OUR PROPOSED REVERSIBLE SQUARER CIRCUIT

A multiplier circuit has three main stages for producing the final result. These stages are partial product generation, partial product reduction and final two operand addition. Our proposed reversible squarer circuit design has no partial product reduction stage and is simplified to only two main stages. In the first stage, partial products are generated which is done by a series of AND operations and then these partial products are used in the next stage to produce the final result. Because fan-out is not considered reversible, in this design we have a fan-out generation circuit for generating the necessary inputs. In this step we use four F2G gates for producing the necessary inputs. The circuit in Figure 8 produces all of the required inputs for our proposed reversible squarer circuit.

After generating fan-out signals, the required partial products are generated by means of Peres gates as reversible AND operation. In the final stage carry propagation adder circuit has been designed that consists of two Peres gates as reversible half adder and two HNG gates as reversible full adder. This circuit is responsible of producing the final result of the design from output [P.sub.3] to [P.sub.6] and also [P.sub.1]. We merged these two steps in one circuit which is shown in Figure 9. We reduced the length of the adder stage to 4 sequential gates which two of them act as reversible half adders (Peres gates) and two of them act as reversible full adder (HNG gates).

The sequence of producing final results is as follows: The second Peres gate of partial product generation circuit has an [x.sub.0] in the output which is not used for further computation and we use this output for the first bit of final result because in the squarer circuit this bit is always [x.sub.0]. Furthermore in the last Peres gate which produces [P.sub.6], its third output is always 0 and we use this logic value for the second bit of the result, [P.sub.1], that is always 0 in the squarer circuit described in the previous section. By this task we have removed one line that is always in logic "0". At the same time one garbage output of the Peres gate has been removed. So both P0 and [P.sub.1] bits of the final result are produced with no extra cost and because there is no carry propagation to the third column, the bit [P.sub.2] of the result is produced with Just one Peres gate as a AND operation. In this circuit, we decrease the number of garbage outputs and number of fan-out gates by using some Peres gates garbage outputs similar to [16] in partial product generation stage.

According to the functionality of the proposed design, we are needless to use the last Peres gate. This is due to the fact that the carry bit in the seventh bit is zero and we only need to calculate the sum output. Therefore, we replace the Peres gate with a Feynman gate [17] as an XOR gate and this will lead to a more optimized structure of the proposed squarer. In this case for generating [P.sub.1] a constant line must be added.

5 EVALUATION OF OUR PROPOSED DESIGN

Our proposed reversible 4-bit squarer design has 4 F2G gates for generating the necessary fan-out inputs in the first stage. In the second stage, 9 Peres gates have been used to implement 9 AND operations and in the last stage of our circuit 2 Peres gates have been used as reversible half adder and 2 HNG gates have been used as reversible full adder. Thus the total number of gates in our proposed squarer design is 17. Another important factor in the reversible circuits is quantum cost. In our work, the quantum cost of the fan-out generation circuit is 8. The quantum cost of the partial product generation circuit is 36 and the quantum cost of carry ripple addition circuit which consists of 2 Peres gates and 2 HNG gates is 20. So the total quantum cost of this reversible circuit is 64. The critical path of this circuit considering the conventional definition of the critical path in logical circuits consists of one F2G gate, three Peres gates and two HNG gates. And finally the total number of constant inputs in our design is 21 and the total number of garbage outputs is 17. In our proposed design, all of the important criteria in reversible design consist of quantum cost, number of gates, and number of gates in critical path, constant inputs and garbage outputs are better than all of the 4-bit reversible multipliers proposed so far. Table I shows comparison between our reversible squarer design and 4-bit multiplier circuits in [13], [14] and [15] which can be used as squarer circuit.

Using Feynman gate instead of the last Peres gate which was aforementioned in section 4, quantum cost of proposed circuit is decreased to 61.

6 CONCLUSION

In this paper, we have suggested a new design of squarer circuit in reversible logic. Because squarer is mostly used especially in DSPs, having a specific squarer circuit can save time and power consumption and lead to a better and more efficient designs. Our circuit is optimized in reversible logic, using minimum number of gates, garbage outputs, constant inputs and low quantum cost compared to multiplier circuits which can be used as squarer. Also we performed an investigation about timing behavior of the proposed design and have shown it has less execution delay compared to multiplier circuits. The proposed design can be very useful in designing a reversible DSP processor and other arithmetic units inside processors.

REFERENCES

[1.] Landauer. R, "Irreversibility and Heat Generation in the Computing Process," In IBM Journal of Research and Development, July 1961; vol. 3, pp. 183-191.

[2.] Toffoli. T, "Reversible computing," Tech Memo MIT/LCS/TM-151, MIT Lab for Computer Science, 1980.

[3.] Bennett. C.H, "Logical reversibility of computation," In IBM Journal of Research and Development 17, 1973; pp. 525-532.

[4.] Von Neumann. J, "Theory of Self-Reproducing Automata," Univ. of Illinois Press, USA. 1966.

[5.] Maslov. D, "Reversible Logic Synthesis," Ph.D. dissertation, Dept. Comput. Sci., Univ. New Brunswick, Fredericton, NB, Canada, 2003.

[6.] Peres. A, "Reversible logic and quantum computers, Physical Review," 1985; A 32 (6) pp. 3266-3276,

[7.] Haghparast. M and Navi. K, "A novel reversible BCD adder for nanotechnology based systems," American Journal of Applied Sciences, 2008; pp. 282-288.

[8.] Parhami.B, "Fault tolerant reversible circuits," Proc. 40th Asilomar Conf. Signals, Systems and Computers, Pacific Grove, CA, 2006; pp. 1726-1729.

[9.] Perkowski. M, Al-Rabadi. A, Kerntopf. P, Buller. A, Chrzanowska-Jeske. M, Mishchenko. A, Azad Khan. M, Coppola. A, Yanushkevich. S, Shmerko. V and Jozwiak. L, "A general decomposition for reversible logic," In Proceedings of the RM2001, Starkville, 2001; pp. 119-138.

[10.] Kerntopf. P, Perkowski. M.A and Khan M.H.A, "On universality of general reversible multiple valued logic gates, "In IEEE Proceedings of the 34th International Symposium on Multiple Valued Logic (ISMVL'04), 2004; pp .68-73.

[11.] Parhami. B, "Computer arithmetic algorithms and hardware designs", Oxford University Press 2000.

[12.] Ienne. P and Viredaz. M. A., "Bit-Serial Multipliers and Squarers," IEEE Transactions on Computers. December 1994; vol. 43, no. 12.

[13.] Haghparast. M, Mohammadi. M, Navi. K and Eshghi. M, "Optimized Reversible Multiplier Circuit", Journal of Circuits, Systems, and Computers world scinet.com, World Scientific Publisher, 2009.

[14.] Islam. MS et al, "Low cost quantum realization of reversible multiplier circuit", Information technology journal, 8(2): pp. 208-213, 2009.

[15.] Bhagyalakshmi. HR and Venkatesha. MK., "An Improved Design of a Multiplier Using Reversible Logic Gates", International Journal of Engineering Science and Technology, 2010; vol. 2(8), 3838-3845.

[16.] P. A. Akbar. E, Haghparast. M, Navi. K, "Novel design of a fast reversible Wallace sign multiplier circuit in nanotechnology", Microelectronics Journal, 2011; 4(8):973-981.

[17.] Barenco. A, Bennett. CH, Cleve. R, DiVincenzo. DP, Margolus. N, Shor. P, Sleator. T, Smolin. JA and Weinfurter. H. "Elementary gates for quantum computation". Physical review A. 52, 5, 3457-3467,1995.

Mahmood Kalemati, Mariam Zomorodi Moghadam, Keivan Navi

Faculty of Electrical and Computer Engineering, Shahid Beheshti University, G. C., Tehran, Iran m.kalemati@mail.sbu. ac.ir, m_zomorodi@sbu.ac.ir, navi@sbu.ac.ir

Table 1. Comparison results of the proposed reversible squarer and
reversible multipliers as squarer

Reversible      Gates   Quantum    Constant    Garbage
circuit                   cost      inputs

[13]             28       137         28         28
[14]             28       144         28         52
[15]             40       152         52         52
Our proposed     17        64         21         17
  reversible
    squarer

Figure 5. 4-bit squarer operation

P7           P6                   P5                   P4

                                                       x

                                               [x.sub.3][x.sub.1]

                          [x.sub.3][x.sub.2]   x.sub.2][x.sub.2]

     [x.sub.3][x.sub.3]   [x.sub.2][x.sub.3]   [x.sub.1][x.sub.3]

        P3                   P2                   P1

    [x.sub.3]            [x.sub.2]            [x.sub.1]

    [x.sub.3]            [x.sub.2]            [x.sub.1]

[x.sub.3][x.sub.0]   [x.sub.2][x.sub.0]   [x.sub.1][x.sub.0]

[x.sub.2][x.sub.1]   [x.sub.1][x.sub.1]   [x.sub.0][x.sub.1]

[x.sub.1][x.sub.2]   [x.sub.0][x.sub.2]

[x.sub.0][x.sub.3]

        P0

    [x.sub.0]

    [x.sub.0]

[x.sub.0][x.sub.0]

Figure 6. Simplified 4-bit squarer operation

P7           P6                   P5                   P4

                                               [x.sub.3][x.sub.0]

                          [x.sub.3][x.sub.1]       [x.sub.2]

         [x.sub.3]                             [x.sub.2][x.sub.1]

     [x.sub.3][x.sub.2]

        P3                   P2           P1      P0

[x.sub.2][x.sub.0]   [x.sub.1][x.sub.0]   0    [x.sub.0]

                         [x.sub.1]

Figure 7. Final simplified 4-bit squarer

P7                             P6                     P5

[x.sub.3][x.sub.2]   [x.sub.3][bar.x.sub.2]   [x.sub.3][x.sub.1]

                                              [x.sub.2][x.sub.1]

          P4                     P3

  [x.sub.3][x.sub.0]     [x.sub.1][x.sub.0]

          P2              P1       P0

[x.sub.1][bar.x.sub.0]    0     [x.sub.0]
COPYRIGHT 2013 Springfield Publishing Corporation
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Kalemati, Mahmood; Moghadam, Mariam Zomorodi; Navi, Keivan
Publication:International Journal of Emerging Sciences
Article Type:Report
Geographic Code:7IRAN
Date:Dec 1, 2013
Words:3276
Previous Article:Strategic assessment of brand identity in organizations by using Aaker model (Case Study: Iran and Asia insurance companies).
Next Article:An Ad-Hoc approach for data clustering using meta-heuristic algorithms.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |