Reversible logic based multiplication computing unit using binary tree data structure

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–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\) reversible signed multiplier based on modified Baugh–Wooley multiplication methodology.