0
\$\begingroup\$

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?

enter image description here

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.

\$\endgroup\$
10
  • \$\begingroup\$ I'm assuming you fully apprehend sign-extension, as an idea. Otherwise you would not even be this far. But have you taken out a piece of paper and performed this same multiplication using your own idea? I'd like to see that work, first. (Also, just a note that stopped me in my tracks, while reading. You quote this: "sign-extended bits are shown in blue" and then write "Why are the pink sign extensions necessary"... Um. What diagram with blue?) \$\endgroup\$ Commented Dec 9, 2023 at 20:29
  • \$\begingroup\$ Oof, the blue is an error (much of the rest of the book uses blue), thanks for poingting that out. Yes, I have taken out a pen and paper and done this same calculation out and it seems to work, so that's why I'm not following. I generally follow the need for sign extension when adding two numbers of different lengths (e.g. the first sign extension of \$PP_0\$ in the above). But once I have the two at the same length, why do I need to extend again as long as I make my result large enough (i.e. one bit longer than each of the summands)? @periblepsis \$\endgroup\$
    – EE18
    Commented Dec 9, 2023 at 20:44
  • \$\begingroup\$ Could you please show your work? I'd rather not have to attempt a replication of what you have already done. And it would help me to more narrowly address your questions after seeing your own work. I think it would be a big help. I'd either say you were right (upon seeing it) or else be more readily able to show where it might fail, otherwise. \$\endgroup\$ Commented Dec 9, 2023 at 20:47
  • \$\begingroup\$ Sure, I will work on porting that over to the question right now. @periblepsis \$\endgroup\$
    – EE18
    Commented Dec 9, 2023 at 20:59
  • \$\begingroup\$ @periblepsis I am having some trouble structuring the math in the tabular way shown in the figure but my "change" to the figure is so small that hopefully conveying it in words is clear: let's look at Fig 3.36b and imagine deleting all of the pink numbers except for the single sign extension in the zeroth partial product. The calculation seems to proceed to the very same conclusion? \$\endgroup\$
    – EE18
    Commented Dec 9, 2023 at 21:03

3 Answers 3

2
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ Thank you so much for this very helpful and very detailed answer. I am just about ready to accept but want to confirm I understand. Underlying your answer, I think, is that my question is really a question about addition (and addition of signed numbers in particular). You claim that (1) for the addition of two n-bit unsigned numbers, if one is interested in the full sum then we get the correct answer is we take the carry out of the last full adder and form the corresponding (n+1)-bit value. In contrast (2) for the addition of two n-bit signed numbers, if one is interested in the full sum.. \$\endgroup\$
    – EE18
    Commented Dec 10, 2023 at 15:34
  • \$\begingroup\$ ...we do not get the correct answer is we take the carry out of the last full adder and form the corresponding (n+1)-bit value. Instead, we must sign extend the two summands to (n+1)-bit numbers, perform the addition to get an (n+1)-bit number (and we throw away the carry out here as is standard with the addition of two numbers which "fit" in the number of bits being used). Is this a correct understanding of what you've written? \$\endgroup\$
    – EE18
    Commented Dec 10, 2023 at 15:35
  • \$\begingroup\$ If the above is correct then I suppose it means that sign extension in the unsigned case is unnecessary (even though Fig 3.62a does it) even though it still produces the right answer. Is the reason we still do that sign extension to point out that we can use multiplier units on both signed and unsigned integers (if we use the correct control logic around it), and so the multiplier unit should be arranged with sign extension since the signed case demands it? \$\endgroup\$
    – EE18
    Commented Dec 10, 2023 at 15:38
  • \$\begingroup\$ I think much of this perhaps has to do with the author's claim (as in the OP) that "overflow has to be avoided". Is this the same thing as what we have discussed above here? Also, in your example in which the outcome is erroneous, would we arrive at the wrong answer if we simply used logic to say that the answer is acceptable under the erroneous strategy if we get no overflow? That is, in the erroneous case the XOR of the carry out of the last two stages is 0, so there is no overflow. Thus we can just delete the 0 and take 10101 which is correct? Is there a situation where this wouldn't work? \$\endgroup\$
    – EE18
    Commented Dec 10, 2023 at 16:01
  • \$\begingroup\$ @EE18 Just try yourself the erroneous way with the example given, and look at the complete product. ;-) -- Since I cannot look into the referenced book, I cannot say anything about claims not presented here. \$\endgroup\$ Commented Dec 10, 2023 at 16:11
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

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