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:
|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?