A Reduced-Bit Multiplication Algorithm for Digital Arithmetic

Authors: Harpreet Singh Dhillon, Abhijit Mitra

Abstract:

A reduced-bit multiplication algorithm based on the ancient Vedic multiplication formulae is proposed in this paper. Both the Vedic multiplication formulae, Urdhva tiryakbhyam and Nikhilam, are first discussed in detail. Urdhva tiryakbhyam, being a general multiplication formula, is equally applicable to all cases of multiplication. It is applied to the digital arithmetic and is shown to yield a multiplier architecture which is very similar to the popular array multiplier. Due to its structure, it leads to a high carry propagation delay in case of multiplication of large numbers. Nikhilam Sutra, on the other hand, is more efficient in the multiplication of large numbers as it reduces the multiplication of two large numbers to that of two smaller numbers. The framework of the proposed algorithm is taken from this Sutra and is further optimized by use of some general arithmetic operations such as expansion and bit-shifting to take advantage of bit-reduction in multiplication. We illustrate the proposed algorithm by reducing a general 4x4-bit multiplication to a single 2 x 2-bit multiplication operation.

Keywords: Multiplication, algorithm, Vedic mathematics, digital arithmetic, reduced-bit.

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

References:

[1] K. Hwang, Computer Arithmetic: Principles, Architecture And Design. New York: John Wiley & Sons, 1979.
[2] M. M. Mano, Computer System Architecture. Englewood Cliffs, NJ: Prentice-Hall, 1982.
[3] G.-K. Ma, F. J. Taylor, "Multiplier Policies for Digital Signal Processing", IEEE ASSP Mag., vol. 7, no. 1, pp. 6-20, Jan. 1990.
[4] D. Goldberg, "Computer Arithmetic", in Computer Architecture: A Quantitative Approach, J.L. Hennessy and D.A. Patterson ed., pp. A1- A66, San Mateo, CA: Morgan Kaufmann, 1990.
[5] A.D. Booth, "A Signed Binary Multiplication Technique", Qrt. J. Mech. App. Math.,, vol. 4, no. 2, pp. 236-240, 1951.
[6] G. Goto. "High Speed Digital Parallel Multiplier." U. S. Patent 5 465 226, Nov. 7, 1995.
[7] L. Ciminiera and A. Valenzano, "Low Cost Serial Multiplier for High Speed Specialised Processors", IEE Proc., vol. 135, no. 5, pp. 259-265, Sept. 1988.
[8] D. Ait-Boudaoud, M. K. Ibrahim and B. R. Hayes-Gill, "Novel Pipelined Serial/Parallel Multiplier", Electron. Lett., vol. 26, no. 9, pp. 582-583, April 1990.
[9] R. Gnanasekran, "A Fast Serial-Parallel Binary Multiplier", IEEE Trans. Comput., vol. 34, no. 8, pp. 741- 744, Aug. 1985.
[10] B. K. Tirtha, Vedic Mathematics. Delhi: Motilal Banarsidass Publishers, 1965.
[11] P. D. Chidgupkar and M. T. Karad, "The Implementation of Vedic Algorithms in Digital Signal Processing", Global J. of Engg. Edu., vol. 8, no. 2, pp. 153-158, 2004.
[12] H. Thapliyal and M. B. Srinivas, "High Speed Efficient N £ N Bit Parallel Hierarchical Overlay Multiplier Architecture Based on Ancient Indian Vedic Mathematics", Enformatika Trans., vol. 2, pp. 225-228, Dec. 2004.
[13] H. Thapliyal, R. V. Kamala and M. B. Srinivas, "RSA Encryption/ Decryption in Wireless Networks Using an Efficient High Speed Multiplier", in Proc. IEEE Int. Conf. Personal Wireless Comm. (ICPWC- 2005), New Delhi, Jan. 2005, pp. 417-420.
[14] H. Thapliyal and M. B. Srinivas, "An Efficient Method of Elliptic Curve Encryption Using Ancient Indian Vedic Mathematics", in Proc. IEEE MIDWEST Symp. Circuits. Systems, Cincinnati, Aug. 2005, pp. 826- 829.
[15] H. Thapliyal, M. B. Srinivas and H. R. Arabnia , "Design And Analysis of a VLSI Based High Performance Low Power Parallel Square Architecture", in Proc. Int. Conf. Algo. Math. Comp. Sc., Las Vegas, June 2005, pp. 72-76.