ISSN: 2277-3754

ISO 9001:2008 Certified International Journal of Engineering and Innovative Technology (IJEIT) Volume 1, Issue 6, June 2012

Arithmetic & Logic Unit (ALU) Design using Reversible Control Unit
Akanksha Dixit, Vinod Kapse
AbstractReversible logic has received great attention in the recent years due to its ability to reduce the power dissipation which is the main requirement in low power digital design. It has wide applications in advanced computing, low power CMOS design, Optical information processing, DNA computing, bio information, quantum computation and nanotechnology. Conventional digital circuits dissipate a significant amount of energy because bits of information are erased during the logic operations. Thus, if logic gates are designed such that the information bits are not destroyed, the power consumption can be reduced dramatically. The information bits are not lost in case of a reversible computation. This has led to the development of reversible gates. ALU is a fundamental building block of a central processing unit (CPU) in any computing system; reversible arithmetic unit has a high power optimization on the offer. By using suitable control logic to one of the input variables of parallel adder, various arithmetic operations can be realized. In this paper, ALU based on a Reversible low power control unit for arithmetic & logic operations is proposed. In our design, the full Adders are realized using synthesizable, low quantum cost, low garbage output DPeres gates. This paper presents a novel design of Arithmetic & Logical Unit using Reversible control unit. These Reversible ALU has been modeled and verified using Verilog and Quartus II 5.0 simulator. Comparative results are presented in terms of number of gates, number of garbage outputs, number of constant inputs and Quantum cost. Index TermsReversible gates, Quantum computing, Reversible gates, Reversible ALU.

techniques such as use of alternate logic styles, energy recovery methods are common. At Architecture (System) level and Algorithmic level, techniques such as use of parallel structures, pipelining, state machine encoding, alternate encoding methods, etc are more common. Ref. [4] offers one such method at circuit and logic level, the energy recovery method, which employs reversible logic concepts. In 1973, C. H. Bennett [1, 3] concluded that no energy would be dissipated from a system as long as the system was able to return to its initial state from its final state regardless of what occurred in between. It made clear that, for power not to be dissipated in the arbitrary circuit, it must be built from reversible gate. Reversible circuits are of particular interest in low power CMOS VLSI design. II. LITERATURE REVIEW 1. R. Landauer, Irreversibility and Heat Generation in the Computational Process, IBM Journal of Research and Development, vol. 5, pp. 183-191, 1961.[2] R. Landauers showed, the amount of energy (heat) dissipated for every irreversible bit operation is given by KT ln2, where K is the Boltzmanns constant (1.380710-23 JK-1) and T is the operating temperature. At room temperature (300 K), KT ln2 is approximately 2.810-21 J, which is small but not negligible. He also showed that only the logically irreversible steps in a computation carry an unavoidable energy penalty. If we could compute entirely with reversible operations, there would be no lower limit on energy consumption. 2. C.H. Bennett, "Notes on the History of Reversible Computation", IBM Journal of Research and Development, vol. 32, pp. 16-23, 1998.[3] Bennett showed that kTln2 energy dissipation would not occur, if a computation is carried out in a reversible way, since the amount of energy dissipated in a system bears a direct relationship to the number of bits erased during computation. 3. Yvan Van Rentergem and Alexis De Vos, Optimal Design of a Reversible Full Adder , International Journal of Unconventional Computing, vol. 1, pp. 339 355, 2005. Yvan Van Rentergem and Alexis De Vos presented four designs for Reversible full-adder circuits and the implementation of these logic circuits into electronic

I. INTRODUCTION Design of a control unit for any computing unit is the toughest part and involves more critical constraints. Power consumption is an important issue in modern day VLSI designs. The advancement in VLSI designs and particularly portable device technologies and increasingly high computation requirements, lead to the design of faster, smaller and more complex electronic Systems. The advent of multi-giga-hertz processors, high-end electronic gadgets bring with them an increase in system complexity, high density packages and a concern on power consumption. Power optimization can be done at various abstraction levels in CMOS VLSI design. At the Device (Technology) level, techniques such as VT reduction, multi-threshold voltages, gate oxide thickness, and length and width variations are more common. At Circuit level, techniques such as use of alternate devices, network re-structuring, at Logic level,

55

ISSN: 2277-3754
ISO 9001:2008 Certified International Journal of Engineering and Innovative Technology (IJEIT) Volume 1, Issue 6, June 2012 circuitry based on CMOS technology and pass-transistor Reversible gate is realized by using 1*1 NOT gates and 2*2 design. Reversible gates, such as V, V+ (V is square root of NOT gate 4. Lihui Ni, Zhijin Guan, and Wenying Zhu, A General and V+ is its hermitian) and FG gate which is also known as Method of Constructing the Reversible Full-Adder, CNOT gate. The V and V+ Quantum gates have the property Third International Symposium on Intelligent given in the Equations 1, 2 and 3. Information Technology and Security Informatics, V * V = NOT (1) pp.109-113, 2010. V * V+ = V+ * V = I .. (2) Lihui Ni, Zhijin Guan, and Wenying Zhu described V+ * V+ = NOT . (3) general approach to construct the Reversible full adder and The Quantum Cost of a Reversible gate is calculated by can be extended to a variety of Reversible full adders with counting the number of V, V+ and CNOTgates. only two Reversible gates. 1. NOT Gate 5. Bruce, J.W., M.A. Thornton, L. shivakuamaraiah, P.S. The Reversible 1*1 gate is NOT Gate with zero Quantum kokate and X. Li, Efficient adder circuits based on a Cost is as shown in the Fig. 1. conservative reversible logic gate , IEEE computer society Annual symposium on VLSI, Pittsburgh, Pennsylvania, and pp: 83-88, 2000. Bruce, J.W., M.A. Thornton, L. shivakuamaraiah, P.S. Fig. 1. NOT gate kokate and X. Li, used only Fredkin gates to construct full 2. Feynman / CNOT Gate [8] adder with gates cost equal to 4, 3 garbage outputs and 2 The Reversible 2*2 gate with Quantum Cost of one having constant input. mapping input (A, B) to output (P = A, Q= AB) is as shown 6. Zhijin Guan, Wenjuan Li, Weiping Ding, Yueqin in the Fig. 2. Hang, and Lihui Ni, An Arithmetic Logic Unit Design Based on Reversible Logic Gates, Communications, Computers and Signal Processing (PacRim), 2011 IEEE Pacific Rim Conference on , pp.925-931, 03 October 2011.[21] In this paper, a design constructing the Arithmetic Logic Unit (ALU) based on reversible logic gates as logic Fig. 2. Reversible Feynman/CNOT gate (FG) components is proposed. The presented reversible ALU 3. Toffoli Gate [6] reduces the information bits use an d loss by reusing the logic The Reversible 3*3 gate with three inputs and three outputs. information bits logically and realizes the goal of lowering The inputs (A, B, C) mapped to the outputs (P=A, Q=B, power consumption. R=A.B^C) is as shown in the Fig. 3. III. BASIC REVERSIBLE LOGIC GATES Reversible logic gate It is an n-input n-output logic function in which there is a one-to-one correspondence between the inputs and the outputs. Because of this bijective mapping the input vector can be uniquely determined from the output vector. This prevents the loss of information which is the root cause of power dissipation in irreversible logic circuits. In the design of reversible logic circuits the following points must be considered to achieve an optimized circuit. They are Fan-out is not permitted. Loops or feedbacks are not permitted Garbage outputs must be minimum Minimum delay Minimum quantum cost. Basic reversible logic gates The simplest Reversible gate is NOT gate and is a 1*1 gate. Controlled NOT (CNOT) gate is an example for a 2*2 gate. There are many 3*3 Reversible gates such as F, TG, PG and TR gate. The Quantum Cost of 1*1 Reversible gates is zero, and Quantum Cost of 2*2 Reversible gates is one. Any

Fig. 3. Reversible Toffoli gate (TG)

Toffoli gate is one of the most popular Reversible gates and has Quantum Cost of 5. It requires 2V, 1 V+ and 2 CNOT gates. Its Quantum implementation is as shown in Fig. 4.

Fig. 4. Quantum implementation of Toffoli Gate

56

ISSN: 2277-3754
ISO 9001:2008 Certified International Journal of Engineering and Innovative Technology (IJEIT) Volume 1, Issue 6, June 2012 IV. DESIGN & IMPLEMENTATION 4. Peres Gate [9] Reversible ALU The three inputs and three outputs i.e., 3*3 reversible gate ALU is a data processing component, which is an important having inputs (A, B, C) mapping to outputs (P = A, Q = A part in centre process unit (CPU). Different kinds of B, R = (A.B) C). Since it requires 2 V+, 1 V and 1 CNOT computers have different ALUs. But all of the ALUs contain gate, it has the Quantum cost of 4. The Peres gate and its arithmetic unit and logic unit, which are the basic structures. Quantum implementation are as shown in the Fig. 5 and 6 In arithmetic operations there are add, minus, while in respectively. logical operations there are NOT, OR, AND, XOR and so on. The above operations can be realized by using reversible logic gates, through which can avoid the energy consumption. In this thesis, the multi-function ALU based on reversible logic gates has been designed which contains the reversible control unit and the reversible full adder. The reversible Fig. 5. Reversible Peres Gate (PG) control unit and the reversible full adder are cascaded and arbitrary bit reversible ALU modules can be realized by this way. Here 1bit ALU has been designed. The A and B inputs of the reversible control unit are altered depending on the S0, S1and S2 values and applied as input to reversible full adder using DPeres gates. By controlling one of the inputs to adder, Fig. 6. Quantum implementation of Peres Gate various arithmetic and logic operations can be realized. 5. Fredkin Gate The designed circuit has three control signals with a Reversible 3*3 gate maps inputs (A, B, C) to outputs (P=A, provision for realizing eight arithmetic operations and four Q=A'B+AC, R=AB+A'C) having Quantum cost of 5 and it logic operations requires two dotted rectangles, is equivalent to a 2*2 Feynman gate with Quantum cost of each dotted rectangle is 1, 1 V and 2 CNOT gates. Fredkin gate and its Quantum implementations are shown in Fig 7 and 8 respectively.

Fig. 7. Reversible Fredkin gate

6. Double Peres (Dperes) Gate Double peres gate (DPG) which is combination of two peres gate can work singly as a reversible full adder circuit when its fourth input is set to zero (D=0). This gate requires only one clock cycle and produces no extra garbage outputs. Reversible 4x4gate maps inputs (A, B, C, D) to outputs (P=A, Q=AB, R=ABC, S= ((AB).C) ((A.B)D) having Quantum cost of 6. Double Peres (Dperes) gate and its Quantum implementations are shown in Fig. 8. a. Logic Symbol b. Quantum implementation

Fig. 9. Block diagram of reversible ALU

Fig. 8. Dperes gate

Reversible control unit Design of a control unit for any computing unit is the toughest part and involves more critical constraints. Reversible control unit has 9 reversible gates (3 NOT gate, 2 CNOT gate, 2 Fredkin gate, 1 3x3 Toffoli gate, 1 4x4 Toffoli gate). The complete control unit with reversible logic gate can be realized as in Fig. 10. The designed circuit has three control signals with a provision for realizing eight arithmetic Operations and four logic operations. Three control variables S2, S1, S0 along with Cin select twelve different arithmetic-logic operations, and the S2 distinguishes

57

ISSN: 2277-3754
ISO 9001:2008 Certified International Journal of Engineering and Innovative Technology (IJEIT) Volume 1, Issue 6, June 2012 between arithmetic and logic operations. The A and B inputs A Novel Reversible Full Adder Gate are altered depending on the S0, S1and S2 values and applied Full adder is the fundamental building block in almost every arithmetic logic circuit. Therefore, a gate that can work as input to full adder using DPeres gates. singly as a reversible full adder will be beneficial to the development of other complex logic circuits.

Fig. 12. Block Diagram of Reversible Full Adder

Fig. 10. Block Diagram of Reversible Control Unit

Reversible Logic Implementation of Full Adder Circuit Full adder is the fundamental building block in many computational units. The anticipated paradigm shift logic compatible with optical and quantum requires compatible reversible adder implementations. The full adder circuits output is given by the following equations: Sum=ABCin Cout= (AB)CinAB The reversible logic implementation of full-adder circuit and other adder circuits and their minimization issues has been discussed in [10-13]. It has been shown in [11] and [13] that any reversible logic realization of full adder circuit includes at least two garbage outputs and one constant input. The author in [10-13] has given a quantum cost efficient reversible full adder circuit that is realized using two 3x3 Peres gates only (shown in fig. 11). This implementation of reversible full adder circuit is also efficient in terms of gate count, garbage outputs and constant input than the existing counter parts.

This paper presents a novel reversible full adder gate namely DPeres Gate (DPG) shown in fig. 13. The gate is achieved by cascading two 3x3 Peres gate. The quantum realization cost of this gate is 6. Since it includes two 3x3 Peres gates. The gate can work singly as a reversible full adder circuit when its fourth input is set to zero (D=0) as shown in fig. 12. This gate requires only one clock cycle and produces no extra garbage outputs.

Fig 13. DPeres Gate (DPG)

Fig 11. The Only Cheapest Quantum Realization of Reversible Full Adder Circuit [9-10]

V. RESULTS Simulation results & discussion Reversible one bit Logic Function Generator & one bit ALU in chapter 6 are implemented using Verilog and Simulated using Quartus II 5.0 Simulator. The individual gate functionality and the overall logic is implemented using Structural style of Modeling and this paper shows simulation results of Reversible ALU shown in fig. 14. The simulation result of 1 bit Reversible ALU is shown in fig. 14.There are basically two inputs A,B at which different operations are performed. Depending on the values of s2, s1, s0 & cin we

58

ISSN: 2277-3754
ISO 9001:2008 Certified International Journal of Engineering and Innovative Technology (IJEIT) Volume 1, Issue 6, June 2012 Table: 2 Comparison of existing 1 bit ALU & proposed 1 bit can get different arithmetic & logical operations on func & ALU cout output signals. All the arithmetic & logical operations Parameter Existing 1 are shown in table 1.In the simulation result of reversible Proposed 1 Which has to bit bit ALU ALU the values of s2, s1, s0& cin are 1,1,1,1 respectively. be compared ALU[21] According to table 4 in chapter 6 we can verify our result, so 22 10 Gate count reversible ALU should be performed the operation of complement of an input. Now we can check the value of func Garbage 12 8 outputs output, its 0.The value of A is 1 in simulation waveform of fig. 14. Constant
Table: 1 ALU Function Function select S2 Cin 0 0 0 0 0 0 0 0 1 1 1 1 S1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 S0 0 1 0 1 0 1 0 1 x x x x F=A F=A+1 F=A+B F=A+B+1 F=A-B-1 F=A-B F=A-1 F=A F=A|B F=A^B F=A&B F=~A Transfer A Increment A Addition Add with carry Subtraction with borrow Subtraction Decrement A Transfer A OR X-OR AND Complement A Output equals Function input Quantum cost 10 53 4 29

Table: 3 Comparison of Existing Control Unit & Proposed Control Unit Parameter Which has to be compared Gate count Garbage outputs Constant input Quantum cost Existing control unit[21] 15 8 8 41 Proposed control unit 9 6 3 23

Results comparison and discussion From the point of view of reversible circuit design, there are six important parameters for determining the complexity and performance of circuits [10-11]: Gate count: Total number of reversible gates used in the circuit. Garbage outputs: The outputs that are not used for further computations. The output of the gate that is not used as a primary output or as input to other gate is called garbage output. It can not be avoid because these are very essential to achieve reversibility. Quantum cost: The number of 1x1 or 2x2 gates that are used in the circuit. The bigger gates such as 3x3 gates can not be directly realized. Therefore we use the 1x1 and 2x2 gates to implement the bigger once. The 1x1 gate has zero quantum cost and the quantum cost of 2x2 gate is 1. Logical calculation: Related to hardware complexity indicating the number of NOT and two input XOR and AND gates required to implement the logic of circuit. Quantum depth: It is defined as the Quantum cost of the longest path from input to output. Constant inputs: The inputs which are to be maintained constant at 1 or 0 throughout the circuit operation depending on the function required from the gate or circuit. Optimization of these parameters is very crucial in the design of circuits using reversible gates.

VI. CONCLUSION In this paper, arithmetic, logical unit using reversible control unit has been proposed. We have compared these proposed design with the existing designs[20,21] in terms of reversible gates used, Garbage outputs, Quantum Cost, Quantum depth, constant inputs, logical & arithmetic functions, and hardware complexity(no. of x-or, and, not gates). Arithmetic & logical unit using reversible control unit has also great improvement over existing designs [21].It has 10 gate count, 8 garbage output, 29 Quantum cost, 4 constant input which are very less in compare to existing design [21].And Total 16 arithmetic & logical operations. So the proposed design implementation of reversible ALU in terms of number of gates used, Garbage outputs and Quantum Cost can be used for low power applications. In future we can design complete reversible computer architecture with the help of proposed designs. The reversible ALU will be a central unit in a future design of a fully reversible architecture using only reversible logic elements. For a complete architecture, more key elements must be designed including a reversible control unit and a new approach to reversible memory. REFRENCES
[1] C H Bennett, "Notes on the History of Reversible Computation", IBM Journal of Research and Development, vol. 32, pp. 16-23, 1998. [2] R. Landauer, Irreversibility and Heat Generation in the Computational Process, IBM Journal of Research and Development, 5, pp. 183- 191, 1961. [3] C.H. Bennett, Logical Reversibility of Computation, IBM J.Research and Development, pp. 525-532, November 1973.

59

ISSN: 2277-3754
ISO 9001:2008 Certified International Journal of Engineering and Innovative Technology (IJEIT) Volume 1, Issue 6, June 2012
[4] William C. Athas, Lars J ,Svensson, Jeffrey G. koller, Nestoras Tzartzanis, and Eric Ying Chin Chou, Low-power Digital Systems based on Adiabatic-Switching principle, IEEE Transactions on VLSI systems, Vol. 2, No. 4, December 1994. [5] J.M. Rabaey and M. Pedram, Low Power Design Methodologies, Kluwer Academic Publis her, 1997. [6] T. Toffoli., Reversible Computing, Tech memo MIT/LCS/TM-151, MIT Lab for Computer Science 1980. [20] Y. Syamala, and A. V. N. Tilak, Reversible Arithmetic Logic Unit, Electronics Computer Technology (ICECT), 2 011 3rd International, vol. 5, pp.207-211,07 july 2011. [21] Zhijin Guan, Wenjuan Li, Weiping Ding, Yueqin Hang, and Lihui Ni, An Arithmetic Logic Unit Design Based on Reversible Logic Gates, Communications, Computers and Signal Processing (PacRim)v , pp.925-931, 03 October 2011. AUTHORS PROFILE
Akanksha Dixit born on December, 25th, 1987 in Jabalpur, India obtained his BE degree in Electronics and Communication from Gyan Ganga Institute of Technology & Sciences, Jabalpur in 2009, Rajiv Gandhi Technical University (RGTU), Bhopal. Currently, she is a MTech student in VLSI design and Embedded System in Electronics and Communication Engineering department at Gyan Ganga Institute of Technology & Sciences, Jabalpur under Rajiv Gandhi Technical University (RGTU), Bhopal. She is currently working on a project titled Design of Low power Arithmetic & Logic Unit using Reversible Logic as a partial fulfillment for his MTech Engineering degree. Vinod Kapse born at Nagpur in India. He received the B.E. degree in Industrial Electronics from Amaravati University, Amaravati , India, in 1998, M. Tech. degree in Electronics Engg. From Nagpur University, Nagpur , India in 2007. In 1999, he joined the Srijan Control Drives in R & D department. In 2000, he joined the Sibar Software Services (India) Ltd. as a Design Engineer. In 2002, he joined as a Lecturer in Department of Electronics & Communication in Guru Ramdas Khalsa Institute of Science & Technology, Jabalpur (M.P.) India. He has been member of IEEE. He is currently a Asst. Professor in Gyan Ganga Institute of Technology & Science, Jabalpur (M.P.) India. His research interest includes VLSI Design, Fuzzy logic, Robotics.Email:kapse.vinod@rediffmail.com.

[7] E. Fredkin and T. Toffoli, Conservative logic, Intl J. Theoretical Physics, Vol. 21, pp.219253, 1982. [8] Feynman, R., Quantum mechanical computers Optics, News, 11, pp: 11-20, 1985. [9] Peres, A., Reversible logic and quantum computers. Physical Rev.A, 32, pp: 3266-3276, 1985. [10] Vivek V. Shende, Aditya K. Prasad, Igor L. Markov, and John P. Hayes, Synthesis of Reversible Logic Circuits, IEEE Transaction on computer-aided design of integrated circuits and systems, vol. 22, No. 6, June 2003 [11] Md. Saiful Islam, Md. Rafiqul Islam, Muhammad Rezaul Karim and Abdullah Al Mahmud, Synthesis of Adder Circuits using Reversible Logic, In Proc. of 3rd IEEE Inte rnational Conference for Upcoming Engineers, ICUE 2004, Ryerson University, Toronto, Canada, May 13-14,2004. [12] Yingtao Jiang, Abdulkarim Al- Sheraidah, Yuke Wang, Edwin Sha, and Jin- Gyun Chung, A Novel Multiplexer -Based Low-Power Full Adder, IEEE Transact ions on circuits and systems -II: express briefs,vol. 51,No. 7 July 2004 [13] Dmitri Maslov and Gerhard W. Dueck, Reversible Cascades With Minimal Garbage , IEEE Transaction on computer-aided design of integrated circuits and systems, vol. 23, No. 11, November 2004. [14] James Donald and Niraj K. Jha, Reversible logic synthesis with Fredkin and Peres gates , ACM Journal on Emerging Technologies in Computing Systems (JETC), vol. 4 issue 1, March 2008. [15] Fateme Naderpour and Abbas Vafaei, Reversible multipliers: Decreasing the depth of the circuit, Proceedings of 5th International Conference on Electrical and Computer Engineering, Bangladesh, pp: 306-310, 2008. [16] M.S. Islam, M.M. Rahman, Z. Begum and M.Z. Hafiz, Low cost quantum realization of reversible multipl ier circuit, Information Technology Journal 8(2), pp: 208-213, 2009. [17] Lihui Ni, Zhijin Guan, and Wenying Zhu, A General Method of Constructing the Reversible Full-Adder, Third International Symposium on Intelligent Information Technology and Security Informatics, pp.109-113, 2010. [18] M. K. Thomson, Robert Gluck and Holger Bock Axelsen, Reversible Arithmetic Logic Unit for Quantum arithmetic, Journal of Physics A: Mathematical and Theoretical. 43 (2010). [19] H. R. Bhagyalakshmi, M. K. Venkatesha, An improved design of a multiplier using reversible logic gates, International Journal of Engineering Science and Technology, Vol. 2(8), pp: 3838-3845, 2010.

60