Arithmetic Division in Verilog

Question

module averager(
    clk,
    rst,
    n,
    sum,
    cnt,
    out,
    avg
 );

input  [9:0] n;
input clk;
input rst;
output reg [19:0] out;
output reg [9:0] cnt;
output reg [19:0] sum;
output reg [9:0] avg;

integer i = 0;

always @(posedge clk ) 
    if (rst == 1) begin 
        sum = 20'b0;
        cnt = 10'b0;
        out = 20'b0; 
        avg = 10'b0;
    end else if (rst == 0) begin
        sum = sum + n;
        out = sum;
        cnt = cnt + 1;
        avg = 0;

        for (i=0; i<641; i=i+1) begin
            if(out >= cnt) begin
                out = out - cnt;
                avg = avg + 1;
            end
        end
    end
endmodule

The above is the code to implement a cumulative moving average filter. The for loop is used for division to find the average and involves repeated subtraction. However I am getting the following warning and error:

WARNING:Xst:2254 - Area constraint could not be met for block , final ratio is 509. WARNING:Xst:1336 - (*) More than 100% of Device resources are used ERROR:Pack:18 - The design is too large for the given device and package.

This must be because I am using large values in the for loop and thus am getting a large circuit that can't be implemented. I am looking for an alternative of the for loop, which could find the average for me. I just need the quotient value.

Design Properties: Family: Spartan3E Device: XC3S500E

This is the exact same question as: http://electronics.stackexchange.com/questions/163565/arithmetic-division-in-verilog — Greg, Apr 07 '15 at 17:26

score 3 · Accepted Answer · edited May 23 '17 at 12:09

Full details answer is with the original posted question on EE stack-exchange. This is the primary requierment for the solution:

The for-loop logic is huge when it after it static unrolls. With your current code, you cannot handle the worst case scenario where n=1023. To cover this with your current code you'd need a for loop with 1024 iterations.

Instead of a up counter, you can use a down counter and only examine a slice of the array, where the index represents lsb of the array slice. For example:
for (i=10; i>=0; i=i-1) begin // lsb index of the slice
  if (out[i+:10] >= cnt) begin // 10-bit slice compare
    out[i+:10] = out[i+:10] - cnt; // 10-bit slice subtraction
    avg[i] = 1'b1; // 1-bit assign
  end
end
This for loop unravels to 11 iterations (10 to 0), each iteration only looks at a 10 bit slice of out and only one bit of avg. You might not be familiar with the +: operator. It is a bit-slice operator introduced in IEEE Std 1364-2001. Left side if the start index (dynamic is allowed) and the right side is the bit with offset (must be a static constant). You can read more about it here.

Since it is a count down, we can can safely assume (proven mathematically) the upper bits of the slice are zeros and we will never have underflow with the guarding if condition. So we now have 11 10-bit subtracters each with 1-bit assigners which is much smaller logic then the original 642 (should be 1024) 20-bit subtracters each with 10-bit adder.

Arithmetic Division in Verilog

1 Answers1