 Open Access
 Total Downloads : 409
 Authors : Supriya S. Saste, Anil G. Sawant
 Paper ID : IJERTV5IS090557
 Volume & Issue : Volume 05, Issue 09 (September 2016)
 DOI : http://dx.doi.org/10.17577/IJERTV5IS090557
 Published (First Online): 28092016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Design and Implementation of Radix 4 Based Multiplication on FPGA
Supriya S. Saste1
Dept. of Electronics & Telecommunication Trinity College of Engineering & Research Pune, India.
Prof. Anil G. Sawant2
Dept. of Electronics & Telecommunication Trinity College of Engineering & Research
Pune, India.
Abstract With the recent rapid increase in scale of integration, many sophisticated signal processing as well as video processing systems are being implemented on VLSI chip in which multiplication is dominant operation. The performance of these systems is based on computation capacity and power consumption. This paper presents novel approach of multiplication scheme based on Radix 4 and its implementation on FPGA which results in great computational capacity and reduced power consumption. This system has been designed and simulated using Xilinx 13.4 for 8×8 bit numbers.
Key WordsBooths Algorithm, Radix 4, VLSI, Xilinx 13.4.

INTRODUCTION
Multiplication is one of the most important arithmetic operations which is used in high performance systems such as microprocessors, digital signal processors and multimedia applications [1][2][5]. Previously multiplication was done by repetitive sequence of other two basic arithmetic operations viz., addition, subtraction along with shift operations. Hence, multiplication is repetitive addition of numbers. The multiplicand is a number which is to be added and number of times it is added is called as multiplier. The repetitive addition method to employ multiplication is comparatively slow.
Multiplication is mainly performed in three different stages: In first stage partial products are generated. The next stage i.e. stage two deals with reduction of partial products and finally in stage three all the partial products are summed together to get the final result of multiplication operation. The fundamental principle of multiplication is generation of partial products and accumulation of partial products [2]. Multiplication can be performed both on signed as well as unsigned numbers [3]. However signed multiplication is careful operation. Signed numbers cannot be multiplied in same manner as that of the unsigned numbers. Here the Booths algorithm comes in.
The motivation of Booths multiplication scheme is to increase the speed of multiplication process. As compared to conventional methods Booths multiplication helps to reduce the number of iteration steps and results in faster computation. In this paper we present 8 bit multiplication by using modified Booths (Radix 4) algorithm and its implementation on hardware platform.

BOOTHS RECODING (RADIX 2) ALGORITHM The Booths algorithm was invented by Andrew D.
Booth which employs multiplication of both signed and
unsigned numbers. This algorithm has been used to generate the partial products which firstly encode the multiplier bits. Radix2 and Radix4 are two algorithms which generate reduced and efficient partial products for multiplication [3]. The basic technique stated by Booth is explained further.
The technique invented by Booth allows for smaller and faster multiplication of binary integers in 2s complement representation. In order to do multiplication by Booths recoding algorithm, we have to recode the multiplier first. Each bit of the recoded multiplier can take any value from: 0, 1 and 1. In order to do this, 2 bits of multiplier are compared at a time by overlapping technique. Thus, in Radix2 grouping of multiplier bits starts from LSB for which the first block uses only single bit of multiplier and another bit is assumed zero [4]. The recoded multiplier for Radix2 is obtained by performing following steps:

Add a zero to the LSB side of given multiplier.

By using overlapping technique, group two bits of multiplier and recode the number using following table:
TABLE I. RADIX2 BOOTH ENCODING
Xn
Xn+1
Recoded Bits
Operations Performed
0
0
0
0
0
1
+1
1*Multiplicand
1
0
1
1*Multiplicand
1
1
0
0
Consider following example in which multiplicand and multiplier have 4 bits.
Multiplicand 1100
Multiplier 1010
So, according to the table shown above the recoding bits will be obtained as partial product:
PP0=00000 PP1=00100 PP2=11100 PP3=00100
Finally, all the partial products are added to get final product result.
The main version of Booths algorithm (Radix2) had two drawbacks:

With the invariability of add/subtract operations, the algorithm became inconvenient while designing parallel multipliers.

If there is a string of isolated 1s, the algorithm becomes inefficient [10].

The drawbacks enlisted in Booths algorithm are overcome by using Modified Booths Algorithm (Radix4).


MODIFIED BOOTHS (RADIX 4) ALGORITHM The number of bits multiplier/multiplicand is composed of,
gives exact number of partial products generated in multiplication operation. So, to perform the addition of partial product is main bottleneck in multiplication operation and considered as the important factor to speed up multiplication. In Booths recoding (Radix2) algorithm, if 2 n bit numbers are multiplied then n partial products will be generated. The desired high speed can be achieved if the partial products are reduced. Modified Booths (Radix 4) Algorithm uses the technique of partial product reduction to speed up multiplication operation. So, if 2 even n bit numbers are multiplied, the number of partial products generated is n/2 and if n is odd, number of partial products are n+1/2.Thus, in Radix 4 the number of partial products is reduced to half. To have high speed multipliers, Modified Booths Algorithm is an ultimate solution. This algorithm scans strings of three bits at a time.
The numbers of steps involved in Radix 4 multiplication algorithm are shown below:
Fig.1 Radix 4 multiplication steps
In Modified Booths (Radix 4) Algorithm, the multiplicand is recoded based on bits of multiplier which can take any value from + 1, + 2 or 0. Three bits of multiplier are compared at a time, by using overlapping technique. Similar to Radix 2, we have to group bits of multiplier starting from LSB for which first block only uses two bits, considering third bit as zero. Following steps are to be performed in order to generate recoded multiplier of Radix4:

In order to ensure that n is even, extend the sign bit 1 position (if necessary).

Add a 0 to right of the LSB of multiplier.

Based on the value of each recoded bit, each partial product will be 0, +M, M, +2M or 2M.
For Radix 4 bit pairing is done as shown below: 0 1 1 1 0 0 1 1 0
Following table depicts the functional operation of Radix 4 Booth encoder:
TABLE II. RADIX4 ENCODING RULES
0
Xn
Xn+1
Xn 1
Recoded Bits
Operations Performed
0
0
0
0
0
0
0
1
+1
+M
0
1
+1
+M
0
1
1
+2
+2M
1
0
0
2
2M
1
0
1
1
1M
1
1
0
1
1M
1
1
1
0
0
In above table M is nothing but multiplicand
Consider multiplicand and multiplier is composed of 4 bits respectively.
Multiplicand 1100
Multiplier 1010
So, according to Radix 4 recoding rules, partial products obtained are:
PP0= 1000
PP1= 0100
From above example, it can be concluded that if there is 4 bit number, obtained partial products are 2 i.e. for n bit number we get n/2 partial products. Since, the number of partial products are reduced, speed of multiplication process increases. Final product of multiplication is obtained by adding partial products.


RESULTS AND DISCUSSION
Fig.2 RTL schematic of Radix4 Booth Multiplier
Fig.3 Internal RTL Schematic
Fig.4 Simulation result of Radix4 multiplication for unsigned number
Fig.5 Simulation result of Radix4 multiplication for signed number
TABLE III. DEVICE UTILIZATION OF RADIX4 BOOTH MULTIPLIER
Logic Utilization
Used
Available
Utilization
Number of 4 input LUTs
169
7,168
2%
Number of occupied slices
86
3,584
2%
Number of slices containing only related logic
86
86
100%
Number of bonded IOBs
33
141
23%
The multiplication based on Radix4 Booth algorithm has been simulated on ISim simulator of Xilinx 13.4 software and implemented on FPGA platform for which above results are obtained. Table III gives device utilization information of Radix4 Booth multiplication.

CONCLUSION
When taken into consideration the examples of Radix2 and Radix4 multiplication, it can be concluded that, Radix4 Booth multiplication halves the number of partial products and helps to increase the speed of multiplication operation. This algorithm can be extended to Radix8 for which complexity is somewhat high, but the generated partial products will reduce to n/3.
ACKNOWLEDGMENT
I am sincerely thankful to my project guide Prof. Anil G. Sawant who has always been guiding and motivating throughout the project time. I could not have achieved desired objective without his support. It has been a great pleasure for me to work under his guidance.
I am also proud to thank Prof. V. S. Hendre, Head of our Department, for approving our project work with great interest.
This project could never have been completed without referring works of many other people whose details are mentioned in references section. I thank everyone and acknowledge my indebtedness to all these people.
REFERENCES

Sukhmeet Kaur, Suman and Manpreet Signh Manna, Implementation of Modified Booth Algorithm (Radix 4) and its Comparison with Booth Algorithm (Radix 2), Advance in Electronic and Electric Engineering, Vol. 3, No.6, pp.683690, 2013.

Shubhi Shrivastva, Pankaj Gulhane, Optimized model of Radix4 Booth Multiplier in VHDL, International Journal of Emerging Technology and Advanced Engineering, Vol.4, Issue 9, September 2014.

Prof .V .R. Raut, P. R .Loya, FPGA Implementation of Low Power Booth Multiplier Using Radix4 Algorithm, International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering, vol.3, Issue 8, August 2014.

K. Babulu, G. Parasuram, FPGA Realization of Radix4 Booth Multiplication Algorithm for High Speed Arithmetic Logics, International Journal of Computer Science and Information Technologies, vol.2 (5), 2011.

Bodasingi Vijay Bhaskar, Valiveti Ravi Tejesvi, Reddi Surya Prakash Rao, Implementation of Radix4 Multiplier with a parallel MAC unit using MBE Algorithm, International Journal of Advanced Research in Computer Engineering and Technology, vol.1, Issue 5,July2012.

WaiLeong Pang, KahYoong Chan, SewKin Wong, Choon Siang Tan, VHDL Modeling of Booth Radix4 Floating Point Multiplier for VLSI Designers Library WSEAS TRANS. on SYSTEMS. Issue 12, Vol. 12, December 2013.

Rashmi Ranjan, Pramodini Mohanty, A New VLSI Architecture of Parallel Multiplier Based on Radix4 Modified Booth Algorithm using VHDL, International Journal of Computer Science and Engineering Technology (IJCSET), vol.3, No.4, April 2012.

Khalid Javeed, Xiaojun Wang, Mike Scott, Serial and Parallel Interleaved Modular Multipliers on FPGA Platform, 2015 25th International conference on Field Programmable Logic and Applications (FPL), pp.14.

S.Shafiulla Basha, Syed. Jahangir Badashah, Design and Implementation of Radix4 Based High Speed Multiplier using Minimal Partial Products, International Journal of Advances in Engineering & Technology, vol.4, Issue 1, pp.314325, July 2012.

A. B. Pawar, Radix2 Vs Radix4 High Speed Multiplier, International Journal of Advanced Research in Computer Science and Software Engineering, Vol.5, Issue 3, March 2015.