3
$\begingroup$

This is a picture of faster multiplication hardware taken from Computer Organization and Design (5th Edition). I'm having some difficulty understanding it. I was trying to simulate this for a test multiplication of : 1011 x 101. Firstly, P0 is simply the LSB of the (Mplier0 * Mcand) which gives P0 = 1 The two operands of the upper rightmost adder would be then, 1011 (Mplier0 * Mcand) and 0000 (Mplier1 * Mcand) which would produce the result 1011 with P1 = 1. This 1011 would then be one of the inputs of the second stage adder. The other input of the second stage/level adder would come from the upper 2nd rightmost adder. Which gives 1011 (Mplier2 * Mcand) + 0000 (Mplier3 * Mcand) = 1011. So the two inputs of the second stage adder are both 1011. Finally the output of this second stage adder will be 1011 + 1011 = 10110. The penultimate result is 1011011. But the correct answer is 110111. What am I doing wrong here?

enter image description here

Improve this question
$\endgroup$
4
  • $\begingroup$ You're focusing too much on the details. Instead of looking at the diagram, try coming up with the circuit on your own. It's more important to understand the idea than the exact implementation details. $\endgroup$
    – Yuval Filmus
    Jul 28, 2018 at 21:59
  • $\begingroup$ I've looked at it for a long time. Tried to come up with my own implementation but failed. Any help would be appreciated. @YuvalFilmus $\endgroup$
    – Robur_131
    Jul 28, 2018 at 22:39
  • $\begingroup$ Another question came to my mind that do the adders need to be wider as we go down ? Because my product is 64 bits but all the adders are 32 bits. Wouldn't it cause some problems? $\endgroup$
    – Robur_131
    Jul 28, 2018 at 22:40
  • $\begingroup$ Okay, I seem to have understood it. The LSB goes to P_n at each step and the rest goes to adder input. $\endgroup$
    – Robur_131
    Jul 28, 2018 at 22:49

1 Answer 1

Reset to default
4
$\begingroup$

You want to multiply x by y, where both are 32 bit numbers.

The result is the sum of 32 numbers. The first number is x if bit #31 of y is 1, and 0 if bit #31 of y is 0. This number is shifted by 31 bits. The second number is x if bit #30 of y is 1, and 0 if bit #30 of y is 0. This number is shifted by 30 bits. And so on. The last number is x if bit #0 of y is 1, and 0 if bit #0 of y is 0. This number is shifted by 0 bits.

So you have 32 numbers to add. You use 16 adders in parallel to add the first and second, the third and fourth, the fifth and sixth number and so on. You get sixteen 34 bit results. Next you use 8 adders in parallel to each add two of these sums. Then 4 adders in parallel, then 2 adders in parallel, then one adder to get the final result.

Obviously you figure out how big each result can be, and where you would be adding zeroes (which obviously don't need adding). In total you need 31 adders, five levels deep, so the delay for the multiplier is about five times that of a 32 bit adder.

(BTW. There are methods that can get the result faster and I think with less hardware).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I've been thinking about this for quite a while, and found out the left part of the diagram is incorrect, to fix it we should use wider adders. For more information, see: Parallel multiplication hardware $\endgroup$
    – J3soon
    Apr 18, 2019 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.