Reversible logic based multiplication computing unit using binary tree data structure

详细信息    查看全文

• 作者：Saurabh Kotiyal ; Himanshu Thapliyal ; Nagarajan Ranganathan
• 关键词：Reversible computing ; Arithmetic circuits ; Arithmetic logic unit (ALU) ; Baugh–Wooley multiplier ; Array multiplier ; Binary tree
• 刊名：The Journal of Supercomputing
• 出版年：2015
• 出版时间：July 2015
• 年：2015
• 卷：71
• 期：7
• 页码：2668-2693
• 全文大小：1,849 KB
• 参考文献：1.Nielsen MA, Chuang IL (2000) Quantum computation and quantum information. Cambridge University Press, New YorkMATH
  2.Vedral V, Barenco A, Ekert A (1996) Quantum networks for elementary arithmetic operations. Phys Rev A 54(1):147-53MathSciNet View Article
  3.Vos AD, Rentergem YV (2005) Power consumption in reversible logic addressed by a ramp voltage. In: Proceedings of the 15th international workshop patmos (2005) LNCS, vol 3728, pp 207-16
  4.Ercan I, Anderson N (2011) Heat dissipation bounds for nanocomputing: theory and application to qca. In: Proceedings of 11th IEEE conference on nanotechnology (IEEE-NANO), pp 1289-294
  5.Anderson N, Ercan I, Ganesh N (2012) Toward nanoprocessor thermodynamics. In: Proceedings of 12th IEEE conference on nanotechnology (IEEE-NANO), pp 1-
  6.Stearns K, Anderson N (2013) Throughput-dissipation tradeoff in partially reversible nanocomputing: a case study. In: Proceedings of nanoscale architectures (NANOARCH), 2013 IEEE/ACM international symposium, pp 101-05
  7.Cuccaro SA, Draper TG, Kutin SA, Moulton DP (2004) A new quantum ripple-carry addition circuit. arXiv:?quant-ph/-410184
  8.Takahashi Y, Kunihiro N (2005) A linear-size quantum circuit for addition with no ancillary qubits. Quantum Inf Comput 5(6):440-48MATH MathSciNet
  9.Draper TG, Kutin SA, Rains EM, Svore KM (2006) A logarithmic-depth quantum carry-lookahead adder. Quantum Inf Comput 6(4):351-69MATH MathSciNet
  10.Takahashi Y, Tani S, Kunihiro N (2004) Quantum addition circuits and unbounded fan-out. arXiv:-910.-530
  11.Takahashi Y (2010) Quantum arithmetic circuits: a survey. In: Proceedings of IEICE transactions on fundamentals, vol E92-A, no 5, pp 276-283
  12.Desoete B, Vos AD (2002) A reversible carry-look-ahead adder using control gates. Integr VLSI J 33(1):89-04MATH View Article
  13.Biswas AK, Hasan MM, Chowdhury AR, Babu HMH (2008) Efficient approaches for designing reversible binary coded decimal adders. Microelectron J 39(12):1693-703View Article
  14.Kotiyal S, Thapliyal H, Ranganathan N (2011) Design of a reversible bidirectional barrel shifter. In: Proceedings of 11th IEEE conference on nanotechnology (IEEE-NANO), pp 463-68
  15.Haghparast M, Jassbi S, Navi K, Hashemipour O (2008) Design of a novel reversible multiplier circuit using hng gate in nanotechnology. World App Sci J 3(6):974-78
  16.Sultana S, Radecka K (2011) Reversible adder/subtractor with overflow detector. In: Proceedings of circuits and systems (MWSCAS), 2011 IEEE 54th international midwest symposium, pp 1-
  17.Sultana S, Radecka K (2011) Reversible implementation of square-root circuit. In: Proceedings of electronics, circuits and systems (ICECS), 18th IEEE international conference, pp 141-44
  18.Sultana S, Radecka K (2013) Testing reversible adder/subtractor for missing control points. In: Proceedings of the 56th IEEE international midwest symposium on circuits and systems (MWSCAS), Columbus
  19.Shams M, Haghparast M, Navi K (2008) Novel reversible multiplier circuit in nanotechnology. World Appl Sci J 3:806-10
  20.Haghparast M, Mohammadi M, Navi K, Eshghi M (2009) Optimized reversible multiplier circuit. J Circuits Syst Comput 18(2):311-23View Article
  21.Thapliyal H, Srinivas M (2006) Novel reversible multiplier architecture using reversible tsg gate. In: Proceedings of computer systems and applications, IEEE international conference, vol 8, pp 100-03
  22.Thapliyal H, Srinivas M, Arabnia HR (2005) A reversible version of \(4 \times 4\) bit array multiplier with minimum gates and garbage outputs. In: Proceedings of the 2005 international conference on embedded systems and applications, ESA-5, pp 106-16
  23.Peres A (1985) Reversible logic and quantum computers. Phys Rev A Gen Phys 32(6):3266-276
  24.Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21:219-53MATH MathSciNet View Article
  25.Zhou R, Shi Y, Wang H, Cao J (2011) Transistor realization of reversible “zs-series gates and reversible array multiplier. Microelectron J 42(2):305-15View Article
  26.Thapliyal H, Jayashree H, Nagamani A, Arabnia H (2013) Progress in reversible processor design: a novel methodology for reversible carry look-ahead adder. In: Gavrilova M, Tan C (eds) Proceedings of transactions on computational science XVII, ser lecture notes in computer science, Springer, Berlin, vol 7420, pp 73-7
  27.Thapliyal H, Arabnia H (2006) Combined integer and floating point multiplication architecture (cifm) for fpgas and its reversible logic implementation. In: Proceedings of circuits and systems, MWSCAS-6, 49th IEEE international midwest symposium, vol 2, pp 438-42
  28.Bruce JW, Thornton MA, Shivakumaraiah L, Kokate PS, Li X (2002) Efficient adder circuits based on a conservative reversible logic gate. Proc IEEE Symp VLSI 2002:83-8
  29.Thapliyal H, Srinivas M, Arabnia HR (2005) Reversible logic synthesis of half, full and parallel subtractors. In: Proceedings of
• 作者单位：Saurabh Kotiyal (1)
  Himanshu Thapliyal (2)
  Nagarajan Ranganathan (1)
  
  1. Department of Computer Science and Engineering, University of South Florida, Tampa, USA
  2. Department of Electrical and Computer Engineering, University of Kentucky, Lexington, USA
  
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484

文摘

Reversible logic has emerged as a promising computing paradigm having applications in quantum computing, optical computing, dissipationless computing and low-power computing, etc. In reversible logic there exists a one-to-one mapping between the input and output vectors. Reversible circuits require constant ancilla inputs for reconfiguration of gate functions and garbage outputs that help in keeping reversibility. Reversible circuits of many qubits are extremely difficult to realize; thus, reduction in the number of ancilla inputs and the garbage outputs is the primary goal of optimization. In existing literature, researchers have proposed several designs of reversible multipliers based on reversible full adders and reversible half adders. The use of reversible full adders and half adders for the addition of partial products increases the overhead in terms of the number of ancilla inputs and garbage outputs. This paper presents a binary tree-based design methodology for an \(N \times N\) reversible multiplier. The proposed binary tree-based design methodology for \(N \times N\) reversible multiplier performs the addition of partial products in parallel using the reversible ripple adders with zero ancilla bit and zero garbage bit; thereby, minimizing the number of ancilla and garbage bits used in the design. The proposed design methodology shows a 17.86-0.34?% improvement in terms of ancilla inputs; and 21.43-2.17?% in terms of garbage outputs compared to all the existing reversible multiplier designs. The methodology is also extended to the design of \(N \times N\) reversible signed multiplier based on modified Baugh–Wooley multiplication methodology.