A New High Speed Easily Expandable Digital Multiplication Algorithm without Pipeline
Subject Areas : electrical and computer engineeringebrahim hosseini 1 , Morteza Mousazadeh 2
1 -
2 -
Keywords: High speed multiplier, non-pipelined adder, modified Kogge-Stone tree adder, carry look-ahead adder (CLA),
Abstract :
This paper proposes a new high speed low power algorithm for unsigned digital multiplier without pipeline which could be easily expanded to a wider number of bits. The blocks of multiplier works in parallel which significantly increase the speed of multiplier. In proposed algorithm, the input bits of multiplier, are divided into smaller groups of bits which multiplication of these groups are in parallel and simultaneously. This division continues until the minimum number of input bits which is 2×2. In calculating the product of each category, the proposed algorithm is used, which leads to acceleration of the product of each category.The final result will be obtained from the sum of these smaller categories.Modified tree adder have been used to add smaller groups, which can increase the multiplication speed. Multipliers with input bit lengths of 64, 32, 16, 8, 4, and 2 have been implemented using the proposed algorithm in 180 nm and 90 nm technology, which its delay and power consumption with bit length of 32 in 180 nm are 3.05 ns and 40 mW respectively. In 90 nm technology and with the 32 bit length the delay is 1.53 nm and power consumption is 9.7 mW. Also, using the proposed method, it is estimated that the delay of 128×128 bits multiplier in the 180 nm and 90 nm technology are equal to 5.4ns and 2.5ns, respectively. According to the results and in comparison with other works reported in the articles and in the same process, without increasing the power consumption and with a silicon area of 1.5 times, the proposed multiplication speed has increased more than 2 times.
[1] A. D. Booth, "A signed binary multiplication technique," the Quarterly J. of Mechanics and Applied Mathematics, vol. 4, no. 2, pp. 236-240, 1951.
[2] C. S. Wallace, "A suggestion for a fast multiplier," IEEE Trans. on Electronic Computers, vol. 13, no. 1, pp. 14-17, Feb. 1964.
[3] O. L. MacSorley, "High-speed arithmetic in binary computers," in Proc. of the IRE, vol. 49, no. 1, pp. 67-91, Jan. 1961.
[4] D. A. Pucknell and K. Eshraghian, Basic VLSI Design: Systems and Circuits, Prentice Hall Englewood Cliffs, New Jersey, USA, 1988.
[5] R. Fried, "Minimizing energy dissipation in high-speed multipliers," in Proc. of the Int. Symp. on Low Power Electronics and Design, pp. 214-219, Monterey, CA, USA, 8-20 Aug. 1997.
[6] H. Ghasemizadeh, E. Azadi, K. Hadidi, and A. Khoei, "A 1.6 GHz 16×16-bit low-latency pipelined booth multiplier," in Proc. 19th Iranian Conf. on Electrical Engineering, ICEE'11, 6 pp., Tehran, Iran, 17-19 May 2011.
[7] A. Weinberger and J. Smith, "A logic for high-speed addition," Nat. Bur. Stand. Circ, vol. 591, pp. 3-12, 1958.
[8] L. Morgan and D. Jarvis, "Transistor logic using current switching and routing techniques and its application to a fast 'carry' propagation adder," Proc. of the IEE-Part B: Electronic and Communication Engineering, vol. 106, pp. 467-468, 1959.
[9] M. Lehman and N. Burla, "Skip techniques for high-speed carry-propagation in binary arithmetic units," IRE Trans. on Electronic Computers, vol. 10, no. 4, pp. 691-698, Dec. 1961.
[10] R. P. Brent and H. T. Kung, "A regular layout for parallel adders," IEEE Trans. on Computers, vol. 31, no. 3, pp. 260-264, Mar. 1982.
[11] J. Sklansky, "Conditional-sum addition logic," IRE Trans. on Electronic Computers, vol. 9, no. 2, pp. 226-231, Jun. 1960.
[12] P. M. Kogge and H. S. Stone, "A parallel algorithm for the efficient solution of a general class of recurrence equations," IEEE Trans. on Computers, vol. 22, no. 8, pp. 786-793, Aug. 1973.
[13] H. C. Chow and I. C. Wey, "A 3.3 V 1 GHz high speed pipelined booth multiplier," in Proc. IEEE Int. Symp. on Circuits and Systems, ISCAS'02, pp. 1-1, Phoenix-Scottsdale, AZ, USA, 26-29 May 2002.
[14] K. H. Chen and Y. S. Chu, "A low-power multiplier with the spurious power suppression technique," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 15, no. 7, pp. 846-850, Jul. 2007.
[15] A. Saha, D. Pal, and M. Chandra, "Low-power 6-GHz wave-pipelined 8b×8b multiplier," IET Circuits, Devices & Systems, vol. 7, no. 3, pp. 124-140, May 2013.
[16] Z. Huang and M. D. Ercegovac, "High-performance low-power left-to-right array multiplier design," IEEE Trans. on Computers, vol. 54, no. 3, pp. 272-283, 2005.
[17] S. R. Kuang, J. P. Wang, and C. Y. Guo, "Modified booth multipliers with a regular partial product array," IEEE Trans. on Circuits and Systems II: Express Briefs, vol. 56, no. 5, pp. 404-408, May 2009.
[18] V. S. Dimitrov, K. U. Jarvinen, and J. Adikari, "Area-efficient multipliers based on multiple-radix representations," IEEE Trans. on Computers, vol. 60, no. 2, pp. 189-201, Feb. 2011.
[19] P. Mokrian, M. Ahmadi, G. Jullien, and W. Miller, "A reconfigurable digital multiplier architecture," in Proc. Canadian Conf. on Electrical and Computer Engineering. Toward a Caring and Humane Technology, CCECE’03, vol. 1, pp. 125-128, Montreal, Canada, 4-7 May 2003.