A Reduced-Bit Multiplication Algorithm for Digital Arithmetic

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.

• Harpreet Singh Dhillon
• Abhijit Mitra

• Multiplication
• algorithm
• Vedic mathematics
• digital arithmetic
• reduced-bit.

[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.