Radix-4

Booth Multiplication

To

improve the performance of multiplication process encoding is used. Booth

encoder plays an important role in Booth’s multiplier as it reduces the number

of partial product stages. Consider the multiplication of two N-bit numbers-

multiplicand (X) and multiplier (Y) in two’s complement form as,

N-2

X = -xN-12N-1 +

? ai 2i (1)

i=0

N-2

Y = -yN-12N-1 +

? bi 2i (2)

i=0

In this structure each group is

encoded and decoded by selecting by ±1, ±2 or 0, instead of shifting and adding

for every column of the multiplier term and multiplying to obtain the same result

which is shown in table 2.1.

Table

2.1 Function table of Booth Multiplier

Radix-4 booth encoder performs the process

of encoding the multiplicand based on multiplier bits. Using overlapping

technique, 3 bits at a time is compared. Grouping of the multiplier bit to

obtain the encoding value starts from the LSB of the multiplier and the first

block only uses two bits of the multiplier and assumes a zero for the third bit

as shown in figure 2.2.

111000110

Figure

2.2 3-bit pairing as per booth recoding

The number of partial products

can be reduced to ‘n/2’ if two ‘n’ bits numbers are multiplied, if ‘n’

is even number, or ‘(n+1)/2’ , if ‘n’ is an odd number by using modified radix-4

booth multiplier. Thus the speed of the multiplier can be increased by a factor

equal to 2, if the generation of partial product stages is reduced

Final

product equation is given in (3) as,

MxR = ppN-1 x 22*(N-1) + ppN-2

x 22*(N-2) …….+ pp1 x

22+ pp0 x 20

(3)

Where, ppN-1 = M*SN-1 , ppN-2

= M*SN-2…,

pp1

= M*S1,pp0 = M*S0

ppk

are called partial products.

The

full radix-4 booth multiplier equation is given in (4) as,

MxR = M*SN-1 x

22*(N-1) + M*SN-2 x 22*(N-2) …….+

M*S1 x2+ M*S0x

20 (4)

By using radix-4 encoding scheme

to generate partial products, each partial product will be shifted by 2 bits

instead of 1 bit thus reducing the partial product stages.

2.2 Radix-4 Booth Encoding Methods

The circuit diagrams of the

radix-4 Booth encoding methods 1 & 2 are provided in figure 4.4 and 4.5. By

using MR4BE1 design, the error obtained is smaller; hence the approximate

product value is smaller when compared with the actual product.

Figure

2.2 Modified Radix-4 Booth Encoding Methods 1 & 2. (MR4BE1)

The

complexity and critical path delay of Booth encoding can be notably cut down by

using MR4BE1. The approximate product obtained throughMR4BE2 (Modified Radix-4

Booth Encoding Method 2) can be either larger or smaller than the exact product

and errors in the partial product reduction process complements each partial

product stages. Therefore, when compared with MR4BE1 encoding in Booth

multiplier, the error obtained by MR4BE1 may not be larger for a Booth

multiplier. The output of MR4BE1 is given in equation (5) as follows:

PPij

= ajb2i+1b2ib2i-1+ ajb2i+1b2ib2i-1+

ajb2i+1b2ib2i-1 +

ajb2i+1b2ib2i-1

= (b2i ?

b2i-1) (b2i+1 ? aj) (5)

The

output of MR4BE2 is given in (6) as follows:

PPij

= ajb2i+1 + ajb2i+1

PPij = aj ? b2i+1 (6)

2.3 Sign Conversion

In

sign conversion by adding a negative bit (Ni), negative partial

products are converted to 2’s complement form. To indicate whether the

multiplication operation which is to be performed is signed or unsigned number

signed_unsigned (s_u) bit is used. This is useful to perform operation using

higher order bits. Signed number operation takes place when s_u bit = 1 and

when s_u = 0, it indicates unsigned operation which is shown in table 2.2. From

this it is to be noted that, when unsigned opearation takes place, for both

multiplier and multiplication the sign extended bit must be extended to zero

(i.e, x16 = x17 = y16 = y17 = 0) to

avoid false product generation. Similarly when signed multiplication operation

takes place the sign bit depends on the nature of the bits used in

multiplication (multiplicand or multiplier is negative or both the operands are

negative). For signed bit s_u =1, x15 = y16 = y16

= 1, y16 = x17 = x16 = 0.

Table 2.2 Sign conversion

operation

Signed_unsigned

(s_u)

Operation

0

Unsigned

multiplication

1

Signed

multiplication

y16

x16

y15

s_u

x15

Figure

2.3 Logic diagram of sign converter

Signed-unsigned

modified booth multiplication process is shown in figure 2.3.

The partial products

are generated by using the circuit in figure 2.2. All the partial products are

generated in parallel.

x15x14…………..x2x1x0

y15y14…………..y2y1y0

P016P016……..P002P001P000 X1

1P116P115 P114….P103P102P001N0

X2

……………………………

……………………….

P816P815

……………….P803P802P801N X9

P31P30P29……………………….

.P3P2P1P0

Figure 2.3. 16 x16

multiplier for signed-unsigned numbers.

3

WALLACE TREE STRUCTURE

Wallace tree

structure is used to generate the partial products from the given multiplier

and multiplicand bit. Due to the use of Wallace tree structure the organisation

and perfomance of booth multipliers is enhanced. Thid section explains about

the structure of Wallace tree multiplier from which the partial product

generation is used in Modified Radix-4 Booth Multiplier structure.

3.1

Wallace Tree Multiplier

Like Booth

multipliers Wallace Tree Multipliers are also used in high speed multiplication

process. Since it reduces the partial product stages by employing CSA (Carry

Save Adder) structure it has better performance. It can operate only on

unsigned numbers since it does not use any encoding technique to encode the

multiplier bit as applied in Booth Multiplier. By using column compression

technique, numbers of partial product stages are reduced and the total delay is

proportional to the logarithm of word length of multiplier bit. The basic

process of Wallace Tree Multiplier is shown in figure.3.1.