Signed multiplication overflow detection in Verilog

Question

Beginner here. I'm trying to code a simple 16-bit microprocessor in Verilog and implement it on a Spartan 6. The ALU implements all signed operations (no unsigned operations at all). All inputs are wires and are signed. The result is stored in a signed register.

My problem is finding a sensible way to detect overflow. It doesn't currently matter how quickly the overflow is detected, since all it does is trigger a fault and halt the system.

I believe I've figured out how I could detect overflow in addition and subtraction, but I'd like assurance anyway.

Here's addition, where o is the overflow flag register:

if((a_in >= 0) && (b_in >= 0) && (res_out < 0)) o <= 1'b1;
else if((a_in < 0) && (b_in < 0) && (res_out >= 0)) o <= 1'b1;
else o <= 1'b0;

Here's subtraction:

if((a_in >= 0) && (b_in < 0) && (res_out < 0)) o <= 1'b1;
else if((a_in < 0) && (b_in > 0) && (res_out >= 0)) o <= 1'b1;
else o <= 1'b0;

The control matrix takes care of the hold times for a_in and b_in so that the overflow detection could complete, as it's only done once the result has been calculated (on the next clock cycle that is).

I did some looking around here and all I've found is detecting overflow in other languages such as C or C++. I'm looking for an example implementation for detection overflow in signed multiplication.

Both inputs a_in and b_in are signed wires and are 16 bits wide. The result register res_out is signed, also 16 bits wide. Ideally, I'd have a 33 bit wide result register, in which overflow cannot occur anyway, but this is not an option.

Help is appreciated. Any better ways to detect overflow in addition and subtraction are also welcome.

Answer 1

Looking at detecting Overflow and underflow in addition, Analysing a simple 4 bit example, sign extended to 5 bits.

Addition all +ve

  3 : [0]0011
+ 3 : [0]0011
= 6 : [0]0110

With negative numbers

  -3 : [1]1101 
+ -3 : [1]1101
= -6 : [1]1010

Now causing an overflow : Result should be +8 but can not represent that in 4 bits.

  +7 : [0]0111
  +1 : [0]0001 
  +8 : [0]1000

Now cause underflow : Result should be -9 but can not represent that in 4 bits.

  -8 : [1]1000
+ -1 : [1]1111
  -9 : [1]0111 

Therefore overflow and underflow are easy to detect if we sign extend the inputs by 1 bit

localparam WIDTH = 4;
localparam MSB   = WIDTH-1;
logic [WIDTH-1:0] a;
logic [WIDTH-1:0] b;
logic [WIDTH-1:0] result;
logic extra;
logic overflow;
logic underflow;


always @* begin
  {extra, result} = {a[MSB], a} + {b[MSB], b} ;
  overflow  = ({extra, result[MSB]} == 2’b01 );
  underflow = ({extra, result[MSB]} == 2’b10 );
end

Regarding multiplication I do not understand why you can not have a 32 bit register. even if you reduce the final output to 16.

When performing the bit reduction you would need to check that the value is under the max and above the minimum negative number that you can support with the reduced width.

NB: In addition the result grows 1 bit bigger than largest input. The overflow/underflow occurs when truncating back to original width.

With multiplication the result is the width of both added together, 16bits * 16bits results in a 32 bit answer. Pretty sure you do not need 33 bits. If you do not keep the full width then it is pretty hard to tell if the result will overflow when truncated. It is quite common to design these things with a wide combinatorial result and only output so many bits through a flip-flop for the final output from the ALU.

I think that keeping a 32 bit output and comparing it to the max/min of a signed 16 bit number, will synthesise smaller than only using 16 bit multiplier and extra logic to detect the overflow condition.

Answer 2

Just wants to provide an explanation for @Morgan's answer above.

First, it should be noted that in Two's complement representation, no matter how many leading zeros for a positive number or leading ones for a negative number you have, the value is still the same. That is: 1110 is the same as 11110, both are -2.

Now, consider the first overflow example:

  +7 : [0]0111
  +1 : [0]0001 
  +8 : [0]1000

We can see that it we take the carry bit/signed bit of the result, the value is correct in two's complement form (01000 is +8). However, since the result wire can only hold 4 bits, from the hardware perspective, the value is only 1000, which is -8 in two's complement.

Therefore, if we do an XOR on the carry bit and the MSB of the result binary number, we could identify whether the value hardware recognized is the same as the intended, or determine whether overflow happened.