FPGA Implementation ALU Based on Reversible Logic

FPGA Implementation ALU Based on Reversible Logic

Khushboo Ahirwar1 , Sachin Bandewar2 , Anand Kumar Singp

1,2,3 Department of Electronics and communication, SSSCE, Bhopal

Abstract

Programmable reversible logic is emerging as a prospective logic design style for implementation in modern nanotechnology and quantum computing with minimal impact on circuit heat generation. Recent advances in reversible logic using and quantum computer algorithms allow for improved computer architecture and arithmetic logic unit designs. In this paper, the two novel 4*4 reversible logic gates (MRG and PAOG) are used with minimal delay, and may be configured to produce a variety of logical calculations on fixed output lines based on programmable select input lines. The proposed ALU design is verified and its advantages over the only existing ALU design are quantitatively analyzed. The proposed design is implemented for SPARTEN3 FPGA board and is synthesized using Xilinx ISE software and simulated using MODEL SIM 6.5b.

Keywordsreversible gates, ALU, garbage output,quantum cost.

1. Introduction

   In modern VLSI system power dissipation is very high due to rapid switching of internal signals. The complexity of VLSI circuits increases with each year due to packing more and more logic elements into smaller volumes. Hence power dissipation has become the main area of concern in VLSI design. Reversible logic has its basics from thermodynamics of information processing. According to this, traditional irreversible circuits generate heat due to the loss of information during computation. In order to avoid this information loss the conventional circuits are modeled using reversible logic. Landauer [1961] showed that the circuits designed using irreversible elements dissipate heat due to the loss of information bits [1]. It is proved that the loss of one bit of information results in dissipation of KT*log2 joules of heat energy where K is the Boltzmann constant and T is the temperature at which the operation is performed. Benett [1973] showed that this heat dissipation due to information loss can be

   avoided if the circuit is designed using reversible logic gates [2]. A gate is considered to be reversible only if for each and every input there is a unique output assignment. Hence there is a one to one mapping between the input and output vectors. A reversible logic gate is an n input, n- output device indicating that it has same number of inputs and outputs. A circuit that is built from reversible gates is known as reversible logic circuit. In this paper, we design a 16 bit reversible ALU that can perform eight operations simultaneously. The eight operations include addition, subtraction, AND, NAND,OR, NOR and XOR. All the modules are simulated in modelsim SE 6.5 and synthesised using Xilinx ISE 9.2.

2. Litrature survey

   The research on reversible logic is being pursued towards both design and synthesis. Inthe synthesis of reversible logic circuits there has been several interesting attempts in the literature such as the work in [8-10]. A reversible arithmetic logic unit was designed by Thomsen, Glück, and Axelsen[18] that was based on the V-shaped design of the Van Rentergem adder [19]. The ALU had five fixed select lines, and produced the following logical outputs: ADD, SUB,NSUB, XOR and NOP. The least significant bit comprised of two Feynman gates and two Toffoli gates. Each additional bit also had two Fredkin gates.

   Asher Peres . This article is concerned with the construction of a quantum-mechanical Hamiltonian describing a computer. This Hamiltonian generates a dynamical evolution which mimics a sequence of elementary logical steps. This can be achieved if each logical step is locally reversible (global reversibility is insufficient). Computational errors due to noise can be corrected by means of redundancy. In particular, reversible error-correcting codes can be embedded in the Hamiltonian itself. An estimate is given for the minimum amount of entropy which must be dissipated at a given noise level and tolerated error rate.

   A Review on Reversible Logic Gates and their Implementation by Raghava Garipelly, P.Madhu Kiran, A.Santhosh Kumar in International Journal of Emerging Technology and Advanced Engineering in this paper the Reversible logic is one of the most vital issue at present time and it has different areas for its application, those are low power CMOS, quantum computing, nanotechnology, cryptography, optical computing, DNA computing, digital signal processing (DSP), quantum dot cellular automata, communication, computer graphics. It is not possible to realize quantum computing without implementation of reversible logic. The main purposes of designing reversible logic are to decrease quantum cost, depth of the circuits and the number of garbage outputs. This paper provides the basic reversible logic gates, which in designing of more complex system having reversible circuits as a primitive component and which can execute more complicated operations using quantum computers. The reversible circuits form the basic building block of quantum computers as all quantum operations are reversible. This paper presents the data relating to the primitive reversible gates which are available in literature and helps researches in designing higher complex computing circuits using reversible gates.

   Design of Efficient Reversible Binary Subtractors Based on A New Reversible Gate by Himanshu Thapliyal and Nagarajan Ranganathan in 2009 IEEE Computer Society Annual Symposium on VLSI, this paper tells about the extensive applications of Reversible logic in quantum computing, low power VLSI design, quantum dot cellular automata and optical computing. While several researchers have investigated the design of reversible logic elements, there is not much work reported on reversible binary subtractors. In this paper, we propose the design of a new reversible gate called TR gate. Further, we investigate the design of reversible binary subtractors based on the proposed TR gate. The proposed TR gate is better for designing reversible binary subtractor compared to such gates discussed in literature in terms of quantum cost, garbage outputs and complexity of gates.

   Design of a novel reversible ALU using an enhanced carry look- ahead adder by Morrison, M. in Nanotechnology (IEEE-NANO), 2011 11th IEEE Conference Reversible logic is gaining significant consideration as the potential logic design style for implementation in modern nanotechnology and quantum computing with minimal impact on physical entropy. Recent advances in reversible logic

   allow schemes for computer architectures using improved quantum computer algorithms. Significant contributions have been made in the literature towards the design of reversible logic gate structures and arithmetic units, however, there are not many efforts directed towards the design of reversible ALUs. In this work, a novel programmable reversible logic gate is presented and verified, and its implementation in the design of a reversible Arithmetic Logic Unit is demonstrated. Then, reversible implementations of ripple-carry, carry- select and Kogge-Stone carry look-ahead adders are analyzed and compared. Next, implementations of the Kogge-Stone adder with sparsity-4, 8 and 16 were designed, verified and compared. The enhanced sparsity-4 Kogge-Stone adder with ripple-carry adders was selected as the best design, and its implemented in the design of a 32-bit arithmetic logic unit is demonstrated.

3. REVERSIBLE GATES

   Reversible logic is gaining importance in areas of CMOS design because of its lo power dissipation. The traditional gates like AND, OR, XOR are all irreversible gates. Consider the case of traditional AND gate. It consists of two inputs and one output. As a result, one bit is lost each time a computation is carried out. According to the truth table shown in Fig.1, there are three inputs (1, 0), (0, 1) and (0, 0) that corresponds to an output zero. Hence it is not possible to determine a unique input that resulted in the output zero. In order to make a gate reversible additional input and output lines are added so that a one to one mapping exists between the input and output. This prevents the loss of information that is main cause of power dissipation in irreversible circuits. The input that is added to an m x n function to make it reversible is known as constant input (CI). All the outputs of a reversible circuit need not be used in the circuit. Those outputs that are not used in the circuit is called as garbage output (GO). The number of garbage output for a particular reversible gate is not fixed. The two main constraints of reversible logic circuit is

   1. Fan out not allowed

   2. Feedbacks or loops not allowed.

   3.1 Basic Reversible Gates

   Several reversible gates have come out in the recent years. The most basic reversible gate is the Feynman

   gate and is shown in Fig.2. It is the only 2×2 reversible gate available and is commonly used for fan out purposes. Consider the input B as constant. When B is zero, the gate acts as a copying gate or a buffer where both the output lines contain the input

   A. When B is one, the complement of A is obtained at the output Q. The 3×3 reversible gates include Toffoli gate, Fredkin gate, New gate and Peres gate, all of which can be used to realize various Boolean functions. Fredkin gate is shown in Fig.3.The 4×4 reversible gates include TSG gate, MKG gate, HNG gate, PFAG gate etc.

   Fig.1. 2×2 Feynman gate

   Fig.2. 3×3 Fredkin gate

   Fig.4 shows the TSG gate. Some of the 4×4 gates are designed for implementing some important combinational functions in addition to the basic functions. Most of the above mentioned gates can be used in the design of reversible adders.

   Fig.3. 3 x3 Peres Gate

   Several 4×4 and 5×5 gates have been described in the literature targeting low costand delay which may be implemented in a programmable manner to produce a high

   number of logical calculations. The HNG gate, presented in [10], produces the followinglogical output calculations:

   P = A, Q = B, R = AB C and S = (AB) . C

   (AB D ) . The quantum cost and delay of the HNG is 6. When D = 0, the logical calculations produced on the R and S outputs are the required sum and carry-out operations for a full adder. The quantum representation of the HNG is presented in Fig. 5.

   Fig. 4: Quantum Representation of the HNG Gate

   A new programmable 4×4 reversible logic structure – Peres And-Or(PAOG) gate is presented which produces outputs P = A, Q = AB, R = ABC and S = (ABC) ((A B) D ) .Fig. 6 shows the block diagram of the PAOG gate. This gate is an extension of the Peres gate for ALU realization.

   Fig. 5: Block Diagram of the PAOG

4. REVERSIBLE ALU DESIGN

   4.1 Proposed Design

   The ALU utilizes the PAOG gate and HNG gate to produce six logical calculations: ADD, SUB, AND, NAND, OR and NOR. The cost and delay calculations are identical to the ALU in Fig. 6.2. The proposed ALU is shown in Fig. 16, and the logical results based on the input opcodes are presented in

   Table 1.

   S4	S3	S2	S1	S0	RESULT
   0	0	0	0	0	AND
   0	0	0	1	0	NAND
   1	0	0	0	0	OR
   0	1	1	0	0	NOR
   1	1	0	0		ADD
   1	0	0	0	0	SUB

   Table 1: ALU Opcodes and Logical Result for proposed design

   Fig 6. Proposed Design

   .

5. SIMULATION RESULTS

   Fig.7 shows the output of 4 bit reversible ALU for different operations. The inputs to this module are the 4 bit data A and B and a control signal S0, S1 , S2, S3 ,S4 , S5. The control signals selects the type of operation to be performed on the data bits shown in Table 1.

   The project was simulated with the help of the Xilinx ISE 9.2 tool. Remember that the real inputs for this project were the 4 bits A and B and the 1 bit Cin (Carry In) and 4 control signals S),S1,S2,S3,S4 . The rest (g1 to g21 ) are only the ancilla bits and they need to remain always in zero. Figure 7 shows the RTL schematic of ALU as well as Figure 8 shows the simulation waveform for the ALU.

   Fig 7: RTL schematic for reversible ALU

   Fig 8: Simulation wave for for different arithmetic/logic operations

6. CONCLUSION

The 4bit reversible ALU is designed by integrating various sub modules that includes adder/subtractor, and logical unit. The logical unit performs AND, OR, NOR, XOR, NAND. The performance evaluation of the various submodules are carried out using Model sim 6.5 tools and it was found that the circuits designed using reversible logic showed a reduced dealy and power. As a future work more arithmetic and logical function can be used.

References

1. H. Thapliyal and N. Ranganathan, "Design of Efficient Reversible Binary Subtractors Based on A New Reversible Gate," Proc. of the IEEE Computer Society Annual Symposium on VLSI, 2009.

2. M. Morrison and N. Ranganathan, "Design of a Reversible ALU Based on Novel Programmable Reversible Logic Gate Structures," IEEE International Symposium on VLSI, 2011, pp. 126- 131.

3. M. Haghparast, S. J. Jassbi, K. Navi and O. Hashemipour, Design of a NovelReversible Multiplier Circuit using HNG Gate in Nanotechnology, World Applied Sci. J., Vol. 3, , 2008, pp. 974-978.

4. H. Thapliyal, N. Ranganathan, and R. Ferreira, "Design of a Comparator Tree Based on Reversible Logic," 10th Proceedings of the IEEE International Conference on Nanotechnology, 2010, pp 1113-6.

5. P. Gupta, A. Agarwal, and N. K. Jha. An algorithm for synthesis of reversible logic ciruits. IEEE Trans. Computer-Aided Design, 25(11):2317 2330, Nov 2006.

6. D. Maslov and G. W. Dueck. Reversible cascades with minimal garbage. IEEE Trans. Computer-Aided Design, 23(11):14971509, November 2004.

7. M. Nachtigal and N. Ranganathan. Design and analysis of a novel reversible en-coder/decoder. In Nanotechnology (IEEE-NANO), 2011 11th IEEE Conference on,pages 1543 1546, aug. 2011.

8. James Donald and Niraj K. Jha. Reversible logic synthesis with fredkin and peres gates. J. Emerg. Technol. Comput. Syst., 4:2:12:19, April 2008.

9. Oleg Golubitsky and Dmitri Maslov. A study of optimal 4-bit reversible toffoli circuits and their synthesis. IEEE Transactions on Computers, 99(PrePrints), 2011.

10. Oleg Golubitsky, Sean M. Falconer, and Dmitri Maslov. Synthesis of the optimal 4-bit reversible circuits. In Proceedings of the 47th Design

Automation Conference, DAC 10, pages 653656, New York, NY, USA, 2010. ACM.