Hi Tang Cheng,

Please refer to my comments below.

Hello Dr. Jason,

I have two questions and my conjecture regarding to today’s lecture.

1. I notice that the hardware multiplier uses a 1+2n right shift register to hold the product.

Usually we just need 2n bits for n bits times n bits.

What is the use for the extra MSB here?

My guess is that it is for holding the carry out which might occur during the shift and adding. For the finally product we just ignore the MSB. Is it correct?

[Jason] For hardware multiplier, for simplicity, please consider only unsigned integers, and hence, ignore the extra bit.

1. The Booth multiplication algorithm.

When I do the unsigned multiplication of 0110(6)x1100(12), the correct answer should be 0100 1000(72).

But as I use booth algorithm:

0110      multiplicand

    1100(0)    multiplier

00000000  (00)

0000000   (00)

111010    (10+)

00000     (11)

11101000  (wrong)

I follow step by step, but the result is wrong.

However, if I add a ‘0’ in front of the multiplier, it becomes (0)1100(0), and then the result will be correct.

0110      multiplicand

  (0)1100(0)    multiplier

00000000  (00)

0000000   (00)

111010    (10-)

00000     (11)

0110      (01+)

01001000  (correct)

So my conjecture is that: for unsigned multiplication, if the MSB of the multiplier is 1, we need to add a ‘mythical’ 0 in front of it. For signed multiplication, there is no need to do so.

Is it correct?

[Jason] Binary bits “1100” may represent an unsigned number +12 or signed number -4. Recall, sign extension for an unsigned/signed number. If the sign is extended for the binary bits “1100”, and it is treated as an unsigned number, you’ll expect “…01100”. If the sign is extended and the number is treated as signed number, you’ll expect “…11100”.  Hope this clarifies the issue.

Regards,

Tang Cheng