5
\$\begingroup\$

I was reading through a textbook of mine and found a question that I really can't figure out. It asks to find a pair of two's complement numbers which will result in an overflow if they're multiplied together using a 4x4 array multiplier, and I'm not really sure how to go about finding them. The exact question is "Give an example of the multiplication of two numbers (in 2’s complements), using a 4 bits x 4 bits array multiplier, to show that an overflow occurs" in case I misinterpreted it

From my understanding of binary multiplication, a 4x4 array multiplier just takes two 4-bit numbers and represents the product as an 8-bit number. As far as I know, any two unsigned n-bit numbers multiplied by each other can always be represented by 2n bits, so an overflow can't occur when an array multiplier is used for that, but I don't really understand how that translates over to two's complement and why it would be any different.

My initial thought was to work backwards since binary multiplication is just a series of additions and figure it out that way. I know that if you add a pair of two's complement numbers, you can check if their addition causes an overflow by looking at the most significant bits. If both the operands' MSBs are the same but are different from the sum's MSB, that indicates an overflow. While this is great and it makes sense to me for addition, I can't figure out any way to connect that requirement to the question asked.

I really don't have any ideas on where to go from here, and the Wikipedia article (my textbook doesn't really cover this all that well) on two's complement numbers seems to suggest that you can properly represent the product of two n-bit numbers with a 2n-bit number even if they're in two's complement, so I'm not even confident that a solution exists and I think I might just be totally misunderstanding the question. Any help in understanding this would be much appreciated.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ If this is part of a class assignment, I'd get clarification from the instructor. \$\endgroup\$
    – Tony Ennis
    Commented Nov 22, 2012 at 14:52
  • 1
    \$\begingroup\$ It's not from an assignment unfortunately After looking at the problem a bit more I think I've got the idea of it. A 4x4 array multiplier takes 4-bit operands, but when you multiply two's complement numbers, you should extend the MSB and make both of them 8 bits before performing the multiplication. Since an array multiplier can't actually do this it will lead to the wrong answer. \$\endgroup\$
    – Matt
    Commented Nov 22, 2012 at 22:10
  • 1
    \$\begingroup\$ Just as an additional example if anyone else ever wonders about this, look at multiplying 7 (0111) and -1 (1111) Without using something like Booth's algorithm, the proper procedure would be to multiply 11111111 by 00000111 by extending the sign bits. But since the array multiplier can't add bits to each operand, it represents -1 as 00001111 (not actually as 8 bits, but the most significant bits are all assumed to be zero) and it results in an overflow error. I don't know if that totally solves my problem, but it's helped me get a better understanding of why there might be problems \$\endgroup\$
    – Matt
    Commented Nov 22, 2012 at 22:16
  • 1
    \$\begingroup\$ If this really answers your question, you can post it as an answer, and accept it. It'll also gain you some rep, perhaps \$\endgroup\$
    – clabacchio
    Commented Nov 23, 2012 at 22:54

1 Answer 1

Reset to default
2
\$\begingroup\$

My notation: n x n → m

Two operands with length "n" bits and product with length "m" bits.

1. Multiplication result depends on operands being signed /unsigned

Ex. 4x4 → 8:

Fh x Fh = E1h, unsigned integer: 15 x 15

Fh x Fh = 01h, signed integer: -1 x -1

Note: The 4 LSbs are the same for signed and unsigned multiplication.

2. Signed product Fh x 8h (-1 x -8) depends on target size

4 x 4 → 8: 08h (or 8), OK

4 x 4 → 4: 8h (or -8), INCORRECT (overflow).

Generalization: Negating (or getting the two's complement) a byte containing -128, a word containing -32768, or a double word containing -2147483648, cause no changing in the operand, but the NEG instruction will set the overflow flag (ex. for x86 architecture).

Unsigned x Signed

\$\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.