Why is this extra bit width necessary in a multiplier?

Question

In a discussion on multiplier circuits, my textbook (Brown and Vranesic's Fundamentals of Digital Logic, 3e) write that

When a shifted version of the multiplicand is added to a partial product, overflow has to be avoided. Hence the new partial product must be larger by one extra bit. Figure 3.36a illustrates the process of multiplying two positive numbers. The sign-extended bits are shown in pink. Part (b) of the figure involves a negative multiplicand. Note that the resulting product has 2n bits in both cases.

I have supplied Figure 3.36 below.

I am confused about two things:

(1) Why are the pink sign extensions necessary at all (I think this has to do with the overflow discussion above but I can't quite understand why). In particular, I see no issue with simply adding \$PP_n\$ to \$M_{n+1}\$ in order to generate \$PP_{n+1}\$, while allowing \$PP_{n+1}\$ to be one bit longer than each of the inputs to that adder row so that any carry-out is stil accounted for. Why then do we still do sign extension?

(2) Why does the very first partial product have two bits of extension?

A very nice answer below sees to suggest that the issue is that without sign extension, the "extra bit" that I suggested keeping can be wrong. In the below, the extra 0 bit is wrong.

Partial product 1    101011
                   + 00000↓
                   -------
                    010101

One might ask why can't we just delete the extra bit if it might be wrong: after all, in the above we would get the correct 10101 output under this strategy. But of course that won't work in general (we know this on the general grounds that we need an n+1 bits to account for the addition of two n-bit numbers) and also by explicit example:

Partial product 1    101011
                   + 10000↓
                   -------
                    100101

Here ignoring the carry out of the final stage gives us the wrong answer again, 00101. Thus neither keeping nor excluding the final bit gives us the right answer in general. Only sign extension gives us the right answer in general.

See also my question here which I think bears on this.

Answer 1

The multiplication algorithm you show bases on multiple additions.

(1) [...] Why then do we still do sign extension?

Adding two numbers always needs one bit more to hold the result completely. Therefore, each partial product of your examples has 6 bits.

To do this correctly with signed numbers, you need to sign extend each summand by one bit before the addition. You cannot simply use the carry-out bit for this.

Let's look at figure 3.36b when partial product 2 is calculated.

Correctly, with sign extension:

Partial product 1   1101011
                  + 000000↓
                   -------
                    110101

Erroneously, with carry-out:

Partial product 1    101011
                   + 00000↓
                   -------
                    010101

(Please note that for unsigned numbers, you have both alternatives. You can extend by a "0" on the left of the summands, or use the carry-out. It makes no difference.)

(2) Why does the very first partial product have two bits of extension?

You can look at it as the result of a "hidden" addition to the initial value of zero for the least significant bit of the multiplier:

Multiplicand M      10010
Multiplier Q      × 01011
                  -------
Initial value      000000
                 + 110010
                 --------
Partial product 0  110010

The multiplicand was sign extended before the addition.

As adding some value to zero is trivial, you start right away with the sign extended multiplicand as partial product 0, and repeat the sign extension for the addition to partial product 1.

---

Confirming your instinct:

Yes, your understanding is correct.

In general you need one additional bit if you add two numbers, independent of signed or unsigned.

Therefore, we sign extend each summand by one bit before the addition. The carry out of the sum can be happily ignored, as the result always fits.

If you want to simplify your mind set, remember how to sign extend an unsigned number: You prepend a zero bit.

However, since the sum of these two zero bits and the carry out bit is simply the carry out bit, the logic for this sign extension is commonly omitted and the carry out bit is used.

Answer 2

The reason is quite simple.

Not regarding even signed numbers, for adding anything else than a 0 to a 5-bit number, the result will need to be a 6-bit result. Of course you don't have to extend the result beforehand, but depending on your circuitry, it might or might not make sense.

e.g. 31 + 31 = 62.

If you are doing multiplication like 15*3, for the second bit, you anyway have to shift the 5-bit number to be a 6-bit number, and for adding two 6-bit numbers, the result needs 7 bits.

e.g. 31 × 3 = 31 × 1 + 31 × 2 = 31 + 62 = 93.

If you are working with logic that multiplies two numbers together, it may make sense for the logic to do the multiplication with a loop containing shifts and adds, so anyway the registers holding the numbers need to be wide enough to contain the result.

Answer 3

if you multiply an n bit number by an m bit number, in general, you have 2^n * 2^m possible outcomes.

Written in another form this is 2^(n+m) possible outcomes.

So, in general, the product must be represented in n+m bits, to uniquely identify all possible products.