Research and Reviews - International Journals

International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Menu

ISSN ONLINE(2278-8875) PRINT (2320-3765)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

FPGA Implementation of Low Power Booth Multiplier Using Radix-4 Algorithm

Prof. V.R.Raut1, P. R. Loya2
  1. Dept .of Electronics &Telecommunication Prof. Ram Meghe Institute of Technology and Research Badnera, Amravati, Maharashtra, India
  2. Lecturer Dept .of Electronics &Communication, LAM Institute Of Technology, Dhamangaon (Rly), Maharashtra, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

As the scale of integration keeps growing, more and more sophisticated signal processing systems are being implemented on a VLSI chip. These signal processing applications not only demand great computation capacity but also consume considerable amounts of energy. While performance and area remain to be two major design goals, power consumption has become a critical concern in today’s VLSI system design. Multiplication is a fundamental operation in most arithmetic computing systems. Multipliers have large area, long latency and consume considerable power. Previous work on low-power multipliers focuses on low-level optimizations and has not considered well the arithmetic computation features and application-specific data characteristics. Binary multiplier is an integral part of the arithmetic logic unit (ALU) subsystem found in many processors. Booth's algorithm and others like Wallace-Tree suggest techniques for multiplying signed numbers that works equally well for both negative and positive multipliers. This synopsis proposes the design and implementation of Booth multiplier using VHDL . This compares the power consumption and delay of radix 2 and modified radix 4 Booth multipliers. The modified radix 4 Booth multiplier has reduced power consumption than the conventional radix 2 Booth Multiplier

Keywords
Radix2, Radix4 Booth Multiplier, Booth Algorithm

INTRODUCTION
Multiplication is an essential arithmetic operation and its applications are dated several decades back in time. Earlier ALU’s adders were used to perform the multiplication originally. As the applicationsof Array multipliers were introduced the clock rates increased as well as timing constrains became austere. Ever since then methods to implement multiplication are proposed which are more sophisticated [1-4]. As known the use of multiplication operation indigital computing and digital electronics is very intense especially in the field of multimedia and digital signal processing (DSP) applications [6]. There are mainly three stages to perform multiplication: The first stage mainly consists of generating the partial products which are generated through an array of AND gates; Second stage consist of reducing the partial products by the use of partial product reduction schemes; and finally the product is obtained by adding the partial products [5]. The multiplication can be performed on: 1) Signed Numbers; 2) Unsigned Numbers. Signed multiplication a binary number of either sign (two numbers whose sign may are not necessarily positive) may be multiplied. But, in signed multiplication the sign-extension for negative multiplicands is not usable for negative multipliers and there are large numbers ofsummands due to the large sequence of 1’s in multiplier. Unsigned multiplication binary number (whose sign is positive) is multiplied. Continuous advances of microelectronic technologies make better useof energy, encode data more effectively, transmit information more reliable, etc. Particularly, many of these technologies address low-power consumption to meet the requirements of various portable applications [7]. In these application systems, a multiplier is a fundamental arithmetic unit andwidely used in circuits. VHDL is one of the commontechniques for the digital system emergent process. The technique is done by program using certain software which performs simulation and examination of the designed system. The designer only needs to describe his digital circuit design in textual form which can remove without the effort to alter the hardware. VHDL is more preferred because this technique can reduce cost and time, easy to troubleshoot, portable, a lot of platform software support the VHDL function and high references availability. All the processes will be running using Xilinx- Quartus software which means the process is simulated only without any hardware implementation .Multiplication is a fundamental operation in most signals processing algorithms. Multipliers have large area, long latency and consume considerable power. Therefore low-power multiplier design has been an important part in low- power VLSI system design. Fast multipliers are essential parts of digital signal processing systems. The speed of multiplier operation is of great importance in digital signal processing as well as in the general purpose processors today. The basic multiplication principle is twofold i.e., evaluationof partial products and accumulation of the shifted partial products.

LITERATURE REVIEW & RELATED WORK
Multipliers are the key components of many high performance systems such as FIR filters [9], microprocessors, digital signal processors, etc. A system’s performance is generally determined by the performance of the multiplier because the multiplier is generally the slowest clement in the system [10]. Furthermore, it is generally the most area consuming [11]. Hence, optimizing the speed and area of the multiplier is a major design issue. However, area and speed are usually conflicting constraints so that improving speedresults mostly in larger areas. As a result, a whole spectrum of multipliers with different area-speed constraints has been designed with fully parallel Multipliers at one end of the spectrum and fully serial multipliers at the other end. In between are digit serial multipliers where single digits consisting of several bits are operated on.
These multipliers have moderate performance in both speed and area. However, existing digit serial multipliers have been plagued by complicated switching systems and/or irregularities in design. Radix- 2n [12] multipliers which operate on digits in a parallel fashion instead of bits bring the pipelining to the digit level and avoid most of the above problems. They were introduced by M. K. Ibrahim in 1993[8]

COMPLEMENT REPRESENTATION
In complement representation, numbers are represented as two’s complement in the binary section. In this method, positive number is represented in the same way as signed-magnitude method. It is most widely used method of representation. Positive numbers are simply represented as a binary number with ‘0’ as sign bit. To get negative number convert all 0’s to 1’s, all 1’s to 0’s and then add ‘1’ to it. Suppose, a number which are in 2’s complement form and we have to find its value in binary, then if number starts with ‘0’ then it is a positive number and if number starts with ‘1’ then it is a negative number. If, number is negative take the 2’s complement of that number, we will get number in ordinary binary. Let us take, 1101. Take the 2’s complement then we will get 0011. As, number is started with ‘1’ it is negative number and 0011 is binary representation of positive 3. So, the number is -3. Similarly, we are representing other negative numbers in 2’s complement representation.
Suppose we are adding +5 and -5 in decimal we get ‘0’. Now, represent these numbers in 2’s complement form, then we get +5 as 0101 and -5 as 1011. On adding these two numbers we get 10000. Discard carry, then the number is represented as ‘0’.In this signed multiplication we had modified the Complex Multiplication strategy.
A. Booth’s Recoding Algorithm
Parallel Multiplication using basic Booth’s Recoding algorithm is used to generate efficient partial product. ThesePartial Products always have large number of bits than the input number of bits. This width of partial product is usually depends upon the radix scheme used for recoding. These generated partial products are added by compressors. So, these scheme uses less partial products which comprises low power and area.
There are two types of algorithm Radix-2 and Radix-4 to generate efficient partial products for multiplication. First we will explain basic technique of Booth’s Recoding algorithm and then Modified Booth’s Recoding technique for Radix-2 algorithm.. Radix- 2n [12] multipliers which operate on digits in a parallel fashion instead of bits bring the pipelining to the digit level and avoid most of the above problems. They were introduced by M. K. Ibrahim in 1993[8].
These structures are iterative and modular. The pipelining done at the digit level brings the benefit of constant operation speed irrespective of the size of’ the multiplier. The clock speed is only determined by the digit size which is already fixed before the design is implemented.

BASIC TECHNIQUE OF BOOTH’S RECODING ALGORITHM FOR RADIX-2
Booth algorithm provides a procedure for multiplying binary integers in signed-2’s complement representation [8]. According to the multiplication procedure, strings of 0’s in the multiplier require no addition but just shifting and a string of 1’s in the multiplier from bit weight 2k to weight 2m can be treated as 2k+1 - 2m.
Booth algorithm involves recoding the multiplier first. In the recoded format, each bit in the multiplier can take any of the three values: 0, 1 and -1.Suppose we want to multiply a number by 01110 (in decimal 14). This number can be considered as the difference between 10000 (in decimal 16) and 00010 (in decimal 2). The multiplication by 01110 can be achieved by summing up the following products:
i) 24 times the multiplicand (24 = 16)
ii) 2’s complement of 21 times the multiplicand (21 = 2).
In a standard multiplication, three additions are required due to the string of three 1’s.This can be replaced by one addition and one subtraction. The above requirement is identified by recoding of the multiplier 01110 using the following rules summarized in table 1.
image
State diagram
The state diagram of the Radix-2 Booth multiplier is shown in Fig.1. Here we have four different types of states. For 00, 11 states we can perform multiplication of multiplicand with zero. For 01 state, we can multiply multiplicand with one whereas for 10 state, we can multiply multiplicand with -1.
image
ASM chart
The Fig.2 shows the ASM chart for Radix-2 booth multiplier. It represents conventional procedure for various operations required with respect to state of machine. Here we generate the partial products by Radix-2 booth encoder. By using this technique we can reduce the partial products generation and the computation time delay is less than ordinary multiplication.
image
To generate recoded multiplier for radix-2, following steps are to be performed.
i) Append the given multiplier with a zero to the LSB side.
ii) Make group of two bits in the overlapped way Recode the number using the above table.
Consider an example which has the 8 bit multiplicand as 11011001 and multiplier as 011100010.
image
Where Vdd is the supply voltage and idd (t) is the amount of current drawn by the circuit at time.
Given this equation, minimization of the peak power at a given time is directly proportional to the amount of current drawn at time. Since current is flowing ideally only when a circuit is active, by minimizing the number of simultaneously active elements, we can reduce the spike in currentdrawn from the power supply, thus reducing the IR-voltage drop.
In order to optimize the peak power of a circuit, the number of circuit elements that are simultaneously switching must be reduced.
In this proposed work to realize high speed multipliers is to enhance parallelism which helps to decrease the number of subsequent calculation stages. The original version of the Booth algorithm (Radix-2) had two drawbacks.
They are: 1) The number of add subtract operations and the number of shift operations becomes variable and becomes inconvenient in designing parallel multipliers.(ii)The algorithm becomes inefficient when there are isolated 1’s. These problems are overcome by using modified Radix 4.Booth algorithm which scans strings of three bits is given below: 1) Extend the sign bit 1 position if necessary to ensure that n is even.2) Append a 0 to the right of the LSB of the multiplier.3) According to the value of each vector, each Partial Product will be 0, +M,-M, +2M or -2M.
The negative values of B are made by taking the 2’s complement and in this paper Carry-look-ahead (CLA) fast adders are used. The multiplication of M is done by shifting M by one bit to the left. Thus, in any case, in designing nbit parallel multiplier, only n/2 partial products are produced. The partial products are calculated according to the following rule
Zn= -2×Bn+1 + Bn +Bn-1 --------- (2)
Where B is the multiplier.
image
B. Booth Multiplication Algorithm for Radix-4
One of the solutions of realizing high speed multipliers is to enhance parallelism which helps to decrease the number of subsequent calculation stages. The original version of the Booth algorithm (Radix-2) had two drawbacks. They are:
(i) the number of add subtract operations and the number of shift operations become variable and become inconvenient in designing parallel multipliers. (ii) The algorithm becomes inefficient when there are isolated 1’s. These problems are overcome by using modified Radix-4 Booth multiplication algorithm. The design approach of Radix-4 algorithm is described with the pictorial views of state diagram and ASM chart. This algorithm scans strings of three bits as follows:
1) Extend the sign bit 1 position if necessary to ensure that n is even.
2) Append a 0 to the right of the LSB of the multiplier.
3) According to the value of each vector, each Partial
Products will be 0, +y, -y, +2y or -2y. Radix-4 booth encoder performs the process of encoding the multiplicand based on multiplier bits. It will compare 3 bits at a time with overlapping technique. Grouping starts from the LSB, and the first block only uses two bits of the multiplier and assumes a zero for the third bit. The functional operation of Radix-4 booth encoder is shown in the Table 2. The state diagram of the Radix-4 Booth multiplier is shown in Fig.3. It consists of eight different types of states and during these states we can obtain the outcomes, which are multiplication of multiplicand with 0,-1 and -2 consecutively. The pictorial view of the state diagram presents various logics to perform the Radix-4 Booth multiplication in different states as per the adopting encoding technique.
State diagram
image
ASM chart
The ASM chart for Radix-4 booth multiplier is as shown inFig.4. This represents the conventional flow of operations that are required for Radix-4 booth multiplier in various states. Here we can generate the partial products by Radix-4 booth encoder. By using this technique we can further reduce the partial products generation and the computation time delay, which is less than that of Radix-2 multiplication.
image
Consider example for radix 4:
Multiplicand 1 0 0 0 0 0 0 1
Multiplier 0 1 1 1 1 1 1 0 0
image

RESULTS
We evaluate the performance of Radix-2 and Radix-4 booth multipliers and implement them on FPGA. For Design Entry, we used ModelSim 6.3f and design with VHDL. In order to get the power report and delay report we synthesize these multipliers using Xilinx ISE 9.1i. The comparison of synthesis report for Radix-2 and Radix-4 Booth multipliers is given in Table 3.
image

CONCLUSION
In this paper, the Radix-2 and Radix-4 booth multipliers are designed using VHDL. The delay and power dissipation of modified radix-4 Booth multiplier is less as compared to the Radix-2 booth multiplier. When implemented on FPGA, it is found that the radix-4 booth multiplier consumes less power than radix-2 booth multiplier. Also estimated delay is less for radix-4 booth multiplier.

References