A Fast Multiplication Approach Using A Tree-Based Structure
##plugins.themes.bootstrap3.article.sidebar##
##plugins.themes.bootstrap3.article.main##
Abstract
This paper presents a technique for integer number multiplication using a tree-based structure. In the proposed method , both the generation of the partial products and the addition of partial products are completed in the tree structure. The proposed multiplication approach has been designed in two steps: Firstly, the partial products are generated in a tree-based structure using the fewest numbers of gates. Secondly, diagonal partial products additions have been done by the partial products residing in the diagonal partial product nodes to get a faster multiplication result, where two partial product nodes P;,j and Pk,l are diagonal only if Ii - kl = lj - LI where i and k are the multiplicand bits; and j and l are the multiplier bits. The comparative study shows that the proposed multiplication algorithm outperforms the existmg techniques ; e.g., the proposed 4 x 4 multiplication algorithm improves 50% on the worst case running time complexity over the best known existing ones.
##plugins.themes.bootstrap3.article.details##
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
[I] C. S. Wallace, "A suggestio n for a fast mu lti plie r", IEEE Trans. Electronic Computers, vol. 13, pp. 14 -17 , 1964.
Y. Liu and S. Furber, " The design ofa low power asynchronous multiplier", in Proc . International Symposium on Low Power Ele ctronics and Desig n, pp. 301-306, 2004.
Z. Huang , " High-le vel optimi zation techniques for low-power multiplier design", PhD dissertation in Computer Science, UCLA , 2003.
M. C. Wen, S. J. Wang and Y. N. Lin, " Low-power parallel multiplier with column bypassing", Electronics Letters, vol. 41, no. 10 , pp. 581-583 , 2005 .
I. S. A. Khater, A. Bellaouar and M. I. El ma sry , "Circuit techniques for CMOS low-power high-performance multiplie rs" , IEEE Journal on Solid-State Circuits, vol. 31, no. 10, pp. 1535-1546, 1996 .
S. Hong, S. Kim, M. C. Papaefthymiou and W. E. Stark, "Low power parallel multiplier design for DSP applications through coefficient optimization" , in Proc. 12th IEEE International ASIC /SOC Conference, pp. 286-290, 1999.
A. A. Nasar, "The history of algorithmic comple xity", The Mathematics Enthusiast, vol. 13, no. 3, pp. 217-242, 2016.
F. de Dinechin, S. I. Filip, L. Forget and M. Kumm, "Table Based versus Shift-And-Add constant multipliers for FPGAs", 26"' IEEE Symposium on Computer Arithmet ic , pp. 1- 8, 2019.
B. Smestad and K. Niko la ntonakis , "Historical methods for multiplication", in Proc. European Summer University on the History and Epistemology of Mathematics Conference , 2010.
D. R. Smith, "The design of divide and conquer algori thms", Science of Computer Programming, vol. 5, pp. 37-58 , 1985.
A. Booth , "A signed binary multiplication tec hnique", Quarter ly Journal of Mechanics and App lie d Mathemat ics , vol. 4, no. 2, pp. 236-240, 1951.
"Best, worst and average case. Wikip edia.or g. https: //en.wikipedia .org/wiki/Best, worst and average case (accessed Sep. 22, 2020).
