0
$\begingroup$

In the general case of an n bit booth multiplier, the maximum negative value is -2n-1. So with 4 bits we can represent -8 x -8 (M=1000, Q=1000). Now if we follow Booth's algorithm for multiplying n-bit numbers:

count A Q Q-1 Operation
4 0000 1000 0 Initial Conditions
3 0000 0100 0 (00) Shift and decrement count
2 0000 0010 0 (00) Shift and decrement count
1 0000 0001 0 (00) Shift and decrement count
1 1000 0001 0 (10) A <= A-M
0 1100 0000 1 Shift and decrement count

The result is 110000002 = -6410 which is clearly not correct. Am I missing something? Is this just a limitation of Booth's algorithm? I have a hard time believing this isn't a known issue, but I can't seem to find any source that even mentions it.

I can see the issue is when we need to do A<=A-M, since the result should be +8 in this case which can't be expressed in 4-bit 2's complement. How would this be addressed in an actual hardware implementation of Booth's algorithm?

$\endgroup$
2
  • 1
    $\begingroup$ (See The above-mentioned technique is inadequate… in en.wikipedia's Example.) $\endgroup$ – greybeard Feb 10 at 8:53
  • $\begingroup$ @greybeard Thanks! Guess I should have read the Wikipedia article more carefully. $\endgroup$ – Tony Gweesip Feb 10 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.