Analytical Comparison of Conventional Algorithms with Vedic Algorithm for Digital Multiplier

Authors: Akhilesh G. Naik, Dipankar Pal

Abstract:

In today’s scenario, the complexity of digital signal processing (DSP) applications and various microcontroller architectures have been increasing to such an extent that the traditional approaches to multiplier design in most processors are becoming outdated for being comparatively slow. Modern processing applications require suitable pipelined approaches, and therefore, algorithms that are friendlier with pipelined architectures. Traditional algorithms like Wallace Tree, Radix-4 Booth, Radix-8 Booth, Dadda architectures have been proven to be comparatively slow for pipelined architectures. These architectures, therefore, need to be optimized or combined with other architectures amongst them to enhance its performances and to be made suitable for pipelined hardware/architectures. Recently, Vedic algorithm mathematically has proven to be efficient by appearing to be less complex and with fewer steps for its output establishment and have assumed renewed importance. This paper describes and shows how the Vedic algorithm can be better suited for pipelined architectures and also can be combined with traditional architectures and algorithms for enhancing its ability even further. In this paper, we also established that for complex applications on DSP and other microcontroller architectures, using Vedic approach for multiplication proves to be the best available and efficient option.

Keywords: Wallace tree, Radix-4 Booth, Radix-8 Booth, Dadda, Vedic, Single-Stage Karatsuba, Looped Karatsuba.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1316095

References:

[1] H. Jiang, J. Han, F. Qiao and F. Lombardi, “Approximate Radix-8 Booth Multipliers for Low-Power and High-Performance Operation”, IEEE Trans. Computers, vol. 65, no. 8, pp. 2638-2644, Aug. 2016.
[2] R. S. Waters and E. E. Swartzlander, “A Reduced Complexity Wallace Multiplier Reduction,” IEEE Trans. Computers, vol. 59, no. 9, pp. 1134-1137, Aug. 2010.
[3] K. Tsoumanis, S. Xydis, C. Efstathiou, N. Moschopoulos and K. Pekmestzi, “An Optimized Modified Booth Recoder for Efficient Design of the Add-Multiply Operator”, IEEE Trans. Circuits and Systems I, vol. 61, no. 4, pp.1133-1143, 2014.
[4] W. Liu, L. Qian, C. Wang. H. Jiang, J. Han, F. Lombardi, “Design of Approximate Radix-4 Booth Multipliers for Error-Tolerant Computing", IEEE Trans. Computers, vol. 66, no. 8, pp.1435-1441, 2017.
[5] N. Sureka, R. Porselvi and K. Kumuthapriya, “An Efficient High Speed Wallace Tree Multiplier”, IEEE International Conference on Information Communication and Embedded Systems (ICICES), pp. 1023-1026, 2013.
[6] B. Jeevan, S. Narendar, Dr. C.V. Krishna Reddy, Dr. K. Sivani, “A High Speed Binary Floating Point Multiplier Using Dadda Algorithm”, 2013 International Multi-Conference on Automation, Computing, Communication, Control and Compressed Sensing(iMac4s), pp. 455-460, 2013.
[7] Vinod Budhe, Prasanna Palsodkar, Prachi Palsodakar, “Design and Verification of Dadda Algorithm Based Binary Floating Point Multiplier”, 2014 International Conference on Communication and Signal Processing, pp. 1073-1077, 2014.
[8] K. B. Jaiswal, N. Kumar V, and P. Seshadri, Lakshminarayanan G., “Low Power Wallace Tree Multiplier Using Modified Full Adder”, IEEE International Conference on Signal Processing, Communication and Networking (ICSCN), pp. 1-4, 2015.
[9] Manjunath, V. Harikaran, K. Manikanta, Sivananthan S. and Sivasankaran K., “Design and Implementation of 16x16 Modified Booth Multiplier”, IEEE Online International Conference on Green Engineering and Technologies (IC-GET), pp. 1-5, 2015.
[10] S. Asif and Y. Kong, “Performance Analysis of Wallace and Radix-4 Booth-Wallace Multipliers”, IEEE Electronic System Level Synthesis Conference (ESLsyn), pp. 17-22, 2015.
[11] Srini Devadas, “Introduction to Algorithms,” Lecture 11: Integer Arithmetic, Karatsuba Multiplication, MIT Open Course Ware, Massachusetts Institute of Technology, 6.006, Fall 2011. Available at: https://www.youtube.com/watch?v=eCaXlAaN2uE.
[12] A. Mehta, C. B. Bidhul, S. Joseph and Jayakrishnan P., “Implementation of Single Precision Floating Point Multiplier using Karatsuba Algorithm”, International Conference on Green Computing, Communication and Conservation of Energy (ICGCE), pp. 254-256, 2013.
[13] K. Shruthilaya and M. Vinoth, “Power Estimation of Modified Booth Recoder for Efficient Add-Multiply Operator”, IEEE Conference on Computing for Sustainable Global Development (INDIACom), pp. 1684-1689, 2015.
[14] R. Pratibha, P. Sandhya, and R. Varun, “Design of High Performance and Low Power Multiplier using Modified Booth Encoder”, IEEE International Conference on Electrical, Electronics and Optimization Techniques (ICEEOT), pp. 794-798, 2016.