Reversible logic based multiplication computing unit using binary tree data structure

Saurabh Kotiyal, Himanshu Thapliyal, Nagarajan Ranganathan

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


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$$N×N reversible multiplier. The proposed binary tree-based design methodology for $$N \times N$$N×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–60.34 % improvement in terms of ancilla inputs; and 21.43–52.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$$N×N reversible signed multiplier based on modified Baugh–Wooley multiplication methodology.

Original languageEnglish
Pages (from-to)2668-2693
Number of pages26
JournalJournal of Supercomputing
Issue number7
StatePublished - Jul 29 2015

Bibliographical note

Publisher Copyright:
© 2015, Springer Science+Business Media New York.


  • Arithmetic circuits
  • Arithmetic logic unit (ALU)
  • Array multiplier
  • Baugh–Wooley multiplier
  • Binary tree
  • Reversible computing

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Reversible logic based multiplication computing unit using binary tree data structure'. Together they form a unique fingerprint.

Cite this