Radix-4 N-bit numbers- multiplicand (X) and multiplier (Y)

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.