Iterative Division Algorithm Implementation on FPGA
FPGA division operations can be implemented using various methods including restoring division, non-restoring division (add-subtract alternation), Goldschmidt's method, and Taylor series expansion. This article presents a straightforward iterative division algorithm along with simulation verification.
The fundamental algorithm operates as follows:
When implementing this approach, several key considerations must be addressed:
1. Normalization is required first. In this implementation, we assume the dividend is greater than the divisor. The divisor must then be normalized to a value less than the dividend but greater than or equal to half of the dividend.
2. The number of shift operations serves as the termination criterion, with a total of 6 shifts performed in this example.
The detailed implementation code is as follows:
module IterativeDivider(
input clk ,
input rst_n ,
input [27:0] dividend_num ,
input [27:0] divisor_num ,
output [27:0] result ,
output [13:0] shift_amount
);
// Internal signal declarations
reg [13:0] iteration_count ;
reg [13:0] shift_counter ;
reg [27:0] normalized_divisor;
reg [27:0] quotient_reg ;
reg [27:0] remainder_reg ;
reg [27:0] remainder_temp ;
reg [27:0] comparison_val ;
reg normalization_complete;
// Normalization process
always @(posedge clk or posedge rst_n) begin
if(rst_n) begin
comparison_val <= dividend_num - divisor_num;
shift_counter <= 14'd0;
normalization_complete <= 1'b0;
normalized_divisor <= divisor_num;
end
else if(!comparison_val[27] && !normalization_complete) begin
shift_counter <= shift_counter + 1'b1;
normalized_divisor <= normalized_divisor << 1;
comparison_val <= dividend_num - normalized_divisor;
end
else begin
normalization_complete <= 1'b1;
normalized_divisor <= divisor_num << (shift_counter - 1'b1);
end
end
assign shift_amount = shift_counter - 1;
// Division iteration process
always @(posedge clk or posedge rst_n) begin
if(rst_n) begin
remainder_temp <= 28'd0;
iteration_count <= 14'd0;
remainder_reg <= dividend_num;
quotient_reg <= 28'd0;
end
else if(normalization_complete && (iteration_count < 27)) begin
remainder_temp = remainder_reg - normalized_divisor;
if(!remainder_temp[27]) begin
quotient_reg <= (quotient_reg << 1) + 1'b1;
remainder_reg <= remainder_temp << 1;
end
else begin
quotient_reg <= quotient_reg << 1;
remainder_reg <= remainder_reg << 1;
end
iteration_count <= iteration_count + 1'b1;
end
end
assign result = quotient_reg;
endmodule
Testbench code:
`timescale 1ns/1ps
module IterativeDivider_tb;
reg clk ;
reg rst_n ;
reg [27:0] dividend_num ;
reg [27:0] divisor_num ;
wire [27:0] result ;
wire [13:0] shift_amount ;
IterativeDivider IterativeDivider_inst(
.clk ( clk ),
.rst_n ( rst_n ),
.dividend_num( dividend_num ),
.divisor_num( divisor_num ),
.result ( result ),
.shift_amount( shift_amount )
);
initial
begin
$fsdbDumpfile("wave.fsdb");
$fsdbDumpvars(0,IterativeDivider_tb);
end
initial
begin
clk = 1'b0;
forever #10 clk = ~clk;
end
initial
begin
#1;
rst_n = 1'b1;
dividend_num = 28'd200;
divisor_num = 28'd3;
#201;
rst_n = 1'b0;
#1000;
rst_n = 1'b1;
dividend_num = 28'd300;
divisor_num = 28'd7;
#201;
rst_n = 1'b0;
#1000;
rst_n = 1'b1;
dividend_num = 28'd800;
divisor_num = 28'd7;
#201;
rst_n = 1'b0;
#10000000;
$finish;
end
endmodule
The simulation results demonstrate the correct functionality of the iterative divider implementation.
