Electronic – Two’s Complement Multiplication Overflow

multiplier

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 4×4 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 4×4 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.

Best Answer

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