What does the extra 0 added to the LSB in Modified Booth Algorithm do?

Question

I have tried to find a answer to this question but the only other thread about it didn't give as much details as I wished for.

Why is the extra 0 to the right of the LSB needed in Modified Booth Algorithm?

What exactly does it do and why does it need to be 0 and not 1?

I know that you need an even number of Bits for your input in Radix-4 Modified Booth Algorithm (or in general iirc) and that it uses 3 Bits to decide what operation has to be done, for example adding 2*multiplicand.

But the added 0 can't only be there so that we have a Bit-length that can be divided by 3, right?

Answer 1

Assume we have to multiply A×B, where B=(b_n-1 ... b₁ b₀)
Booth, in its standard or modified version, works by rewriting terms b_i.

Lets look at the standard Booth that is simpler.
Rewriting is correct if it leaves the value of B unchanged.
If B is coded in two's complement, its value is
B=−b_n-1×2^n-1+∑_i=0^n-1b_i×2ⁱ
Note the minus at weight n-1 due to two's complement coding.

Now rewriting consists to change every b_i to b'_i=b_i−b_i-1
If we now say that
B=∑_i=0^n-1b'_i×2ⁱ
it is easy to see by replacing b'_i by b_i−b_i-1 in this expression that the value of B is unchanged, provided that for i=0, we add an extra bit b_i-1=0

Of course, we could add a special rule for i=0:
if i≠0, b'_i=b_i−b_i-1
otherwise b'_i=b_i
But the main initial motivation for Booth algorithm was to replace the particular case of the minus at weight n-1 in two's complement by a regular expression where all the bits are processed identically independently of i.
Indeed, when designing a circuit, it is much easier to just duplicate an operator than to have to consider specific conditions depending on the bit position. For this reason, the best solution is to add an extra bit at LSB.

For modified Booth, the situation is similar.
We try to rewrite b with digits b''_2i in such a way that
B=∑_i=0^n/2-1b''_2i×2 ²ⁱ
Rewriting is done with a basis of 4, the expressions are more complex and to generate a digit b'' we need to take into account bits b_2i+1, b_2i and b_2i-1.

Here is the corresponding truth table.

b_2i+1    b_2i    b_2i-1   |    b''_2i
-----------------------------------
0         0       0        |    0
0         0       1        |    1
0         1       0        |    1
0         1       1        |    2
1         0       0        |   -2
1         0       1        |   -1
1         1       0        |   -1
1         1       1        |    0

It can be proofed that this way, the numerical value of B is unchanged, provided we add a bit at 0 at weight -1 b_-1=0. Actually, b''_2i=−2×b_2i+1+b_2i+b_2i-1 and one can replace if expression B=∑_i=0^n/2-1b''_2i×2 ²ⁱ to find the value of B in two's complement.
Again, we could consider differently the situation where i=0 and say that b''₀=−2×b₁+b₀, but this would add extra complexity.

So to answer your questions:

Could anyone tell me why the extra 0 to the right of the LSB is needed in Modified Booth Algorithm?

This extra bit simplifies the rewriting algorithm and avoids to have a particular case to deal with when i=0

What exactly does it do and why does it need to be 0 and not 1?

If this bit was at one, we could not have the value of B unchanged after rewriting. This is essential to ensure correctness of the multiplication algorithm.