I have been trying since last few days to design a modified radix 4 booth multiplier. I want to implement compressors, so as to reduce the delay while adding the partial products. But, I am facing a great deal of difficulty in understanding the sign extension. If I use the conventional method of sign extension, hardware will become quite large and in turn will increase the delay of the system. I have tried looking up on google, but the method that has been described doesn't seem to work. Does anyone know a proven and an efficient scheme that will reduce the delay of the system and will work alongside the compressors and parallel prefix adder?
The booth multiplier works as follow:
- Suppose we want to multiply a[7:0] with b[7:0]
- The, suppose we boot-code a. Then a is split in 4 terms
a[7:5]
a[5:3]
a[3:1]
{a[1:0],0}
These 4 terms are input to the boot coder. The boot coder essentially multiplies b with -2,-1,0,1,2 following next table:
100 : -2 ;
110, 101 : -1
111, 000 : 0
010, 001 : 1
011 : 2
Suppose b is a signed operand. b is now precoded to term_b0 .. term_b3, sign_b0 .. sign_b1
-2: sign_b = 1, term_b = 2*~b (complement)
-1 : sign_b = 1, term_b = ~b
0 : sign_b = 0, term_b = 0
1 : sign_b = 0, term_b = b
2: sign_b = 0, term_b = 2*b
For the final sum, we will then use a Wallace tree that calculates
term_b0 + sign_b0 + term_b1*4 + sign_b1*4 + term_b2*16+sign_b2*16 +
term_b3*64 + sign_b3*64
There is one possible optimization to get rid of the sign extension on term_b0, term_b1, term_b2
Let term_bb0 = {~term_b0[8], term_b0[7:0]} (the MSB is inverted)
Then we have: sign_extend(term_b0) = term_bb0 - 0x100
Now, we can calculate the product with the following wallace tree:
term_bb0 + sign_b0 + .. + term_bb3*64 + sign_bb3*64 - 0x5500
(The wallace tree with the correction term is cheaper than the wallace tree
with the sign extend on the different terms.)
That's it. Have fun !
Hi Henri
in the sign extend (term_bb0) is it subtraction that is being done here ? and also in final summation. And also if the first term term_b0 is the multiplied by 2 then, it will see a shift in 1 bit, so for it if we invert the 8th bit does it imply that the inversion is done after appending zero on the LSB end ?
Raiyyan,
- Subtraction is not done in the term_bb0. It was done before, on term_b0. On term_b0, term_b1, term_b2, term_b3, the most significant bit is a sign-bit, meaning it needs to be subtracted in the Wallace tree if it is one. All other bits need to be added if they are one.
- One technique (used normally in standard full adders), when bits need to be subtracted , is to sign-extend them. Eg suppose you want to calculate
a - b, a is a 4-bit operand, b is a 1-bit operand, then to do the subtraction, you will
calculate a + {b,b,b,b}.
- In multipliers (boot or otherwise), there are typically several bits to be subtracted, and then, an optimization is applied. You can easily see that:
{b,b,b,b} = {0,0,0,~b} + 4'b1111 (check that this is true for b = 0 and for b = 1)
and then, we can calculate a - b = a + {0,0,0,~b} + 4'b1111
- Now, if there is only one term b, this is not an optimization. However, if there are several bits to be subtracted, this is an optimization. Suppose eg we need to calculate
a - b - c = a + {0,0,0,~b} + {0,0,0,~c} + 4'b1111 + 4'b1111 =
a + {0,0,0,~b} + {0,0,0,~c} + 4'b1110
- Likewise, in the example I gave, there is sign extension on term_b0 to term_b3, not on term_bb0 to term_bb3. The fixed term (0x5500) need to be converted to 2-complement and sign-extended to have the subtraction. The advantage is that only one term (0x5500) needs the sign extension, and the variable terms not.
Regards,
Henri
Henri
Can you illustrate a little bit more please, I am trying to multiply 128 * 130 , 130 being the multiplier. Both positive.
Raiyyan,
Can you please ask for an example that is possible with the multiplier shown ?
Regards,
Henri.
OK. lets then take a = -126 (10000010) and b = -128 (10000000)
a[7:5] = 100 -> term_b3 = ~(2 * b) = 255, sign_b3 = 1
a[5:3] = 000 -> term_b2 = 0, sign_b2 = 0
a[3:1] = 001 -> term_b1 = b = 384, sign_b1 = 0
a[1:0],0 = 100 -> term_b0 = ~(2 * b) = 255, sign_b0 = 1
term_bb3 = term_b3 ^ 256 = 511
term_bb2 = term_b2 ^ 256 = 256
term_bb1 = term_b1 ^ 256 = 128
term_bb0 = term_b0 ^ 256 = 511
prod = term_bb3 * 64 + sign_b3 * 64 +
term_bb2 * 16 + sign_b2 * 16 +
term_bb1 * 4 + sign_b1 * 4 +
term_bb0 + sign_b0 - 0x5500 ;
= 16128 = 128 * 130
(I had to correct in 2 places, both in the calculation of term_bx)
- if the coefficient is -2, then term_b = ~(2*b), sign_b = 1
- If the coefficient is 1 and b represents a negative number, b needs to be sign-extended by 1 bit. eg coef = 1, b = 128 -> term_b = 384. (bit 8 is a sign bit.)
Regards,
Henri
128 * 130 gives 16640. I am still not getting it , anyways thank a lot for your help henri,
- Badges
- Science topic
- Similar topics
- Computer Communications (Networks)
- Simulators