|
Vol: 54(68) No: 1 / March 2009 Hardware Integer Multiplier Design Based on Booth's Algorithms Alexandru Amaricai Department of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: alexandru.amaricai@cs.upt.ro, web: http://www.acsa.upt.ro Mihai Udrescu Department of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: mudrescu@cs.upt.ro Lucian Prodan Department of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: lprodan@cs.upt.ro Mircea Vladutiu Department of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: mvlad@cs.upt.ro Oana Boncalo Department of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: oana.boncalo@cs.upt.ro Keywords: Computer Arithmetic, Integer Multiplication, Booth Algorithm, Modified Booth Algorithm Abstract This paper presents an overview of the Booth’s based algorithms for integer multiplication. The presented algorithms are Booth radix2, Booth radix 4, Booth radix 8 and modified Booth. These algorithms are analyzed from the perspective of the number of additions/subtraction operations required for sequential multipliers and the number of partial products produced in the case of array or tree multipliers. Based on the modified Booth algorithm, a radix-4 version for this is proposed. The encoding table for this algorithm is presented. Furthermore, the radix-4 modified Booth algorithm is analyzed in terms of number of additions/subtractions operations needed when designing sequential multipliers and the number of partial products needed for array and tree multipliers. References [1] H. A. AlTwaijry “Area and Performance Optimized CMOS Multipliers” PhD. Thesis, Stanford University, 1997. [2] A. Amaricai “On the Design of Floating Point Units for Interval Addition and Multiplication”, PhD. Report Nr.1, University Politehnica Timisoara, March 2008. [3] S.M. Aziz, C.N. Basheer, .J. Kamruzzaman. “A Synthesisable VHDL Model for an Easily Testable Generalised Multiplier”. Proceedings of the 1st IEEE International Workshop on Electronic Design, Test and Applications (DELTA.02), 2002. [4] G.W. Bewick. “Fast Multiplication: Algorithms and Implementation.” PhD Dissertation, Electrical Eng. Dept., Stanford University, 1994. [5] P. Bonato, V. G. Oklobdzija “Evaluation of Booth’s Algorithm for Implementation in Parallel Multipliers” Proceedings 29th Asilomar Conference on Signals, Systems and Computers, 1995, pp 608-610. [6] A.D. Booth. “A Signed Binary Multiplication Technique”. Quarterly Journal of Mechanics and Applied Mathematics, vol. 4, pp. 236-240, 1951. [7] D.G. East, J.W. Moore. “Overflow Indication in Two\'s Complement Arithmetic” IBM Technical Disclosure Bulletin, vol. 19, no.8, pp. 3135-3136, 1977. [8] J.P. Hayes. “Computer Architecture and Organization 3rd Edition”. McGraw-Hill, 1998. [9] J.L. Hennessy, D.A. Patterson. “Computer Architecture. A Quantitative Approach 3rd edition|. pp. A-11, Morgan Kaufmann, 2002. [10] A.A. Katkar, J.E. Stine “Modified Booth Truncated Multipliers” Proceedings 14th ACM Great Lakes Symposium on VLSI, pp. 444-447, 2004. [11] S.F. Oberman “Design Issues in High Performance Floating Point Arithmetic Units”, PhD. Thesis, Stanford University, 1996. [12] A.R. Omondi. “Computer Arithmetic Systems. Algorithms, Architecture and Implementations.” Prentice-Hall, 1994. [13] W.J. Paul, P.M. Seidel “To Booth or Not to Booth” Integration, the VLSI Journal, Vol. 32, No. 11, 2002, pp. 5-40. [14] L.P. Rubinfeld “A Proof of Modified Booth Algorithm for Multiplication,” IEEE Trans. On Computer, Vol. 24, No.10, pp 1014-1015, 1975. [15] M.J. Schulte, P.I. Balzola, A. Akkas, R.W. Brocato. “Integer Multiplication with Overflow Detection or Saturation.” IEEE Transactions on Computers, Vol. 49, No. 7, pp. 681-691, 2000. |