Vol: 54(68) No: 1 / March 2009 Hardware Integer Multiplier Design Based on Booth's AlgorithmsAlexandru AmaricaiDepartment 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.roMihai UdrescuDepartment of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: mudrescu@cs.upt.roLucian ProdanDepartment of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: lprodan@cs.upt.roMircea VladutiuDepartment of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: mvlad@cs.upt.roOana BoncaloDepartment of Computer Science and Engineering University Politehnica of Timisoara, 2 Vasile Parvan Blvd, 300223, Timisoara, Romania, e-mail: oana.boncalo@cs.upt.ro Computer Arithmetic, Integer Multiplication, Booth Algorithm, Modified Booth AlgorithmKeywords:AbstractThis 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. |