Q: Verilog Accumulator/Decrementer and Testing for Overflow/Underflow?
Asher C. Martin
Does anyone know how to test for overflow/underflow in an accumulator
that can take both signed and unsigned vectors? I am using the
following algorithm and wanted to verify with someone else if this is
correct or not.. Or more simply if it makes sense...
Also, I put my main questions at the end of the e-mail if you want to
just skip the general info...
Here is what I am tryn? to do...
BLOCK DIAGRAM:
+---------------------+
| +-------------+ |
| | | |
+---+ | |
| ACCUMULATOR +---+----> DATAOUT
DATAA >----+ +/- |
| +--------> ACCOVERFLOW
+-----+-+-+---+
| | |
ADDorSUB >-------+ | |
DATASIGN >---------+ |
RESET >-----------+
NOTE: If ADDorSUB line is ONE it?s an ACCUMULATOR otherwise it will
DECREMENT.
NOTE: If DATASIGN is a ONE then the bus is in binary 2?s complement
form.
NOTE: If one bus is signed both buses are signed...
Here are the four cases that the accumulator needs to worry about and
therefore I have to worry about...
ALGORITHIM/VERILOG:
1.) Overflow for unsigned accumulate..
CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
I 0 1111..1111
I+1 1 0000..0000
I+2 0 0000..0001
VERILOG CODE: (case for ADDorSUB = 1 and DATASIGN = 0)
if( (dataout + data) >= (1 << (dataout_width)) )
accoverflow = 1; // OVERFLOW CASE
else
accoverflow = 0;
(PS: Warning: The ABOVE DOES NOT WORK - WHY???!!!)
2.) Overflow for signed accumulate..
CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
I 0 0111..1111
I+1 1 1000..0000
I+2 0 1000..0001
VERILOG CODE: (case for ADDorSUB = 1 and DATASIGN = 1)
if( (dataout + data) >= (1 << (dataout_width-1)) )
accoverflow = 1; // OVERFLOW CASE
else
accoverflow = 0;
(PS: Warning: The ABOVE DOES NOT WORK WHY???!!!)
3.) Underflow for unsigned decrement..
CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
I 0 0000..0000
I-1 1 1111..1111
I-2 0 1111..1110
VERILOG CODE: (case for ADDorSUB = 0 and DATASIGN = 0)
if(data > dataout)
accoverflow = 1; // UNDERFLOW CASE
else
accoverflow = 0;
(PS: Warning: The ABOVE DOES NOT WORK - WHY???!!!)
4.) Underflow for signed decrement..
CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
I 0 1000..0000
I-1 1 0111..1111
I-2 0 0111..1110
VERILOG CODE: (case for ADDorSUB = 0 and DATASIGN = 1)
if( (dataout ? data) <= (1 << dataout_width-1))
accoverflow = 1; // OVERFLOW CASE
else
accoverflow = 0;
(PS: Warning: The ABOVE DOES NOT WORK - WHY???!!!)
THE QUESTIONS I HAVE:
if( (dataout + data) >= (1 << (dataout_width)) )
accoverflow = 1; // OVERFLOW CASE
else
accoverflow = 0;
I have a few questions...
First off, why doesn?t the above Verilog work? (Simple... q?s go a
long way sometimes...) When I simulate that code it seems like it
usually picks the first option (even if dataout and data are zero) and
almost never picks the accoverflow = 0 option.
Secondly, are there any other cases that I have not considered? For
example, say that the data already inside the accumulator is unsigned
but the data on the outside coming in is signed.
Please e-mail your suggestions/comments to ash...@asherm.com
Thanks for your help!
Take care,
>Asher<
John_H
> ALGORITHIM/VERILOG:
>
> 1.) Overflow for unsigned accumulate..
> CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
> I 0 1111..1111
> I+1 1 0000..0000
> I+2 0 0000..0001
>
> VERILOG CODE: (case for ADDorSUB = 1 and DATASIGN = 0)
> if( (dataout + data) >= (1 << (dataout_width)) )
> accoverflow = 1; // OVERFLOW CASE
> else
> accoverflow = 0;
> (PS: Warning: The ABOVE DOES NOT WORK - WHY???!!!)
Try sign-extending the first part of the compare so you end up with
if( {1'b0,dataout} + data >= 1 << dataout_width )
without this accoverflow should never assert.
> 2.) Overflow for signed accumulate..
> CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
> I 0 0111..1111
> I+1 1 1000..0000
> I+2 0 1000..0001
>
> VERILOG CODE: (case for ADDorSUB = 1 and DATASIGN = 1)
> if( (dataout + data) >= (1 << (dataout_width-1)) )
> accoverflow = 1; // OVERFLOW CASE
> else
> accoverflow = 0;
> (PS: Warning: The ABOVE DOES NOT WORK WHY???!!!)
I'd expect the overflow to be continuously asserted for any negative
result since you say the inputs and outputs are 2's complement.
> 3.) Underflow for unsigned decrement..
> CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
> I 0 0000..0000
> I-1 1 1111..1111
> I-2 0 1111..1110
> VERILOG CODE: (case for ADDorSUB = 0 and DATASIGN = 0)
> if(data > dataout)
> accoverflow = 1; // UNDERFLOW CASE
> else
> accoverflow = 0;
> (PS: Warning: The ABOVE DOES NOT WORK - WHY???!!!)
This looks legitimate to me. data and dataout are the same widths? Even
that shouldn't cause problems.
> 4.) Underflow for signed decrement..
> CLOCK CYCLE ACCOVERFLOW ACCUMULATOR [MSB:0]
> I 0 1000..0000
> I-1 1 0111..1111
> I-2 0 0111..1110
>
> VERILOG CODE: (case for ADDorSUB = 0 and DATASIGN = 1)
> if( (dataout ? data) <= (1 << dataout_width-1))
> accoverflow = 1; // OVERFLOW CASE
> else
> accoverflow = 0;
> (PS: Warning: The ABOVE DOES NOT WORK - WHY???!!!)
If the "?" above should be a "+" then, as in #2, any positive result would
trigger the overflow.
> THE QUESTIONS I HAVE:
>
> if( (dataout + data) >= (1 << (dataout_width)) )
> accoverflow = 1; // OVERFLOW CASE
> else
> accoverflow = 0;
>
> I have a few questions...
>
> First off, why doesn?t the above Verilog work? (Simple... q?s go a
> long way sometimes...) When I simulate that code it seems like it
> usually picks the first option (even if dataout and data are zero) and
> almost never picks the accoverflow = 0 option.
dataout_width isn't 32, is it? There might be a problem with Verilog
number size (32'h1==1, I think) which might shift the 1 right off the edge
(I try not to test some limits of the synthesizer so I'm not certain).
> Secondly, are there any other cases that I have not considered? For
> example, say that the data already inside the accumulator is unsigned
> but the data on the outside coming in is signed.
To avoid these kinds of troubles, I'd suggest designing for either signed
or unsigned but not allow both.
A cleaner design approach may be to sign-extend the combinatorial
addition/subtraction and look at the MSBs of the result which is one bit
larger than the accumulator. Look at the two MSbits of the combinatorial
result to check for the overflow: 2'b10 is a negative overflow and 2'b01
is a positive overflow.
input [n-1:0] data;
output [n-1:0] dataout;
reg [n-1:0] dataout;
reg acc_overflow;
wire [n :0] next_dataout;
assign next_dataout[n:0] = {dataout[n-1],dataout}
+ (Add_Subn ? {data[n-1],data}
: -{data[n-1],data});
always @(posedge Clock)
begin
acc_overflow <= next_dataout[n] ^ next_dataout[n-1];
dataout <= next_dataout[n-1:0];
end
There is a more efficient way to code this for the Altera architecture.
The above code is geared more toward efficient Xilinx implementation.
Look for the thread "I needs a saturable adder" (needs?) in comp.arch.fpga
where I spoke some about the same overflow detection and the Altera
architecture.