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,
X = -xN-12N-1 +
? ai 2i (1)
Y = -yN-12N-1 +
? bi 2i (2)
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.
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.
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
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
Where, ppN-1 = M*SN-1 , ppN-2
= M*S1,pp0 = M*S0
are called partial products.
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
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.
2.2 Modified Radix-4 Booth Encoding Methods 1 & 2. (MR4BE1)
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:
= ajb2i+1b2ib2i-1+ ajb2i+1b2ib2i-1+
= (b2i ?
b2i-1) (b2i+1 ? aj) (5)
output of MR4BE2 is given in (6) as follows:
= ajb2i+1 + ajb2i+1
PPij = aj ? b2i+1 (6)
2.3 Sign Conversion
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
2.3 Logic diagram of sign converter
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.
Figure 2.3. 16 x16
multiplier for signed-unsigned numbers.
WALLACE TREE STRUCTURE
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.
Wallace Tree Multiplier
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.