Directory
- Preface
- 1. Basic principles of divider
- 2. Pipeline divider programming
- 3. Simulation verification
- Summarize
Foreword
Hello, everyone! This is Xiao Rui. In this article, we will introduce the design of pipeline divider in FPGA.
1. Basic principles of divider
Dividers are more complex than multipliers, and there are many implementation algorithms, such as restoring remainder algorithm, non-restoring remainder algorithm, series expansion algorithm, Newton-Raphson algorithm, etc. Interested readers can Check it out and learn by yourself. Here we only introduce the basic principles of the divider, taking 27?5=5…2 as an example:
1 0 1 (5) -----> Business
________
Divisor <-----(5) 101 /1 1 0 1 1 (27) -----> Divisor
1 0 1
--------
0 0 1 1
0 0 0 0
--------
0 1 1 1
1 0 1
--------
1 0 (2)----->remainder
- In the first operation, the first M bits of the dividend are compared with the divisor (M is the bit width of the divisor). If the former is greater than the latter, then the quotient of the corresponding bits is 1, and the remainder is the result of the subtraction of the two; if the former is less than In the latter case, the quotient of the corresponding bit is 0, and the remainder is the former.
- Next, the remainder obtained by the previous level operation is concatenated with the highest bit of the remaining dividend to obtain a new level of dividend, which is then compared with the divisor to obtain the quotient and remainder of this level.
- Then repeat process 2 until the last digit of the original dividend is also involved in the operation.
- The remainder obtained in the last step is the final result; the final quotient is the result of splicing the 1-bit quotients obtained at each level.
In each operation step, what is obtained is the 1-bit quotient and the remainder of (M + 1) bit. During the transmission process, in addition to passing the quotient and remainder obtained from the upper level to the next level, the original information of the dividend and divisor must also be retained Passed to the next level because the new dividend requires splicing as described in 2.
2. Pipeline divider programming
Disclaimer: The code is imitated by the masters on the Internet (confused by various bits)
For an introduction to the pipeline, please refer to an article I wrote before: Multiplier Design in FPGA (2)
The overall idea of programming is to first write sub-modules that implement first-level functions, and then repeatedly instantiate the sub-modules in the top-level module to achieve pipeline flow.
The program design is as follows:
①Submodule: divider_cell.v
/************************************
=========divider_cell.v==============
Author: Classmate Xiaorui
Date: 2023.10.26
Description: Submodule
Source: learning experience
*************************************/
module divider_cell
#(parameter N=5,
parameter M=3)
(
inputclk,
input rstn ,
input div_en ,
input [M:0] dividend ,
input [M-1:0] divisor ,
input [N-M:0] merchant_i ,
input [N-M-1:0] dividend_src_i ,//Original dividend
output reg div_end ,
output reg [M-1:0] remainder ,
output reg [M-1:0] divisor_src_o ,//Original divisor information
output reg [N-M:0] merchant_o ,
output reg [N-M-1:0] dividend_src_o //Original dividend information
);
always@(posedge clk or negedge rstn)begin
if(!rstn)begin
div_end<='b0;
remainder<='b0;
divisor_src_o<='b0;
merchant_o<='b0;
dividend_src_o<='b0;
end
else if(div_en)begin
div_end<=1'b1;
dividend_src_o<=dividend_src_i;//original information transfer
divisor_src_o<=divisor;
if(dividend>={1'b0,divisor})begin
merchant_o<=(merchant_i<<1) + 1'b1;//Join the quotients obtained from each step of operation
remainder<=dividend-{1'b0,divisor};//The remainder at this level is the difference between the dividend and the divisor at this level
end
else begin
merchant_o<=merchant_i<<1;
remainder<=dividend;
end
end
else begin
div_end<='b0;
remainder<='b0;
divisor_src_o<='b0;
merchant_o<='b0;
dividend_src_o<='b0;
end
end
endmodule
②Top-level module: divider_top.v
/************************************
=========divider_top.v==============
Author: Classmate Xiaorui
Date: 2023.10.26
Description: Pipeline divider
Source: learning experience
***********************************/
module divider_top
#(parameter N=5,//N: dividend bit width M: divisor bit width
parameter M=3)
(
inputclk,
input rstn ,
input div_en ,//enable
input [N-1:0] dividend ,//dividend
input [M-1:0] divisor ,//divisor
output [N-1:0] merchant ,//merchant
output div_end ,//end mark
output [M-1:0] remainder //remainder
);
//Transfer array of intermediate data
wire div_end_t[N-1:0];
wire [M-1:0] remainder_t [N-1:0];
wire [N-1:0] merchant_o_t[N-1:0];
wire [N-2:0] dividend_t[N-1:0];
wire [M-1:0] divisor_t[N-1:0];
//first instantiation
divider_cell #(.N(N + M-1),.M(M))
divider_U0
(
.clk (clk) ,
.rstn (rstn) ,
.div_en (div_en) ,
.dividend ({<!-- -->{(M){1'b0}}, dividend[N-1]}) ,
.divisor (divisor) ,
.merchant_i ({(N){1'b0}}) ,
.dividend_src_i (dividend[N-2:0]) ,
.div_end (div_end_t[N-1]) ,
.remainder (remainder_t[N-1]) ,
.divisor_src_o (divisor_t[N-1]) ,
.merchant_o (merchant_o_t[N-1]) ,
.dividend_src_o (dividend_t[N-1])
);
//Instantization of other levels
genvar i;
generate
for(i=N-1;i>=1;i=i-1)begin
divider_cell #(.N(N + M-1),.M(M))
divider_Ux
(
.clk (clk) ,
.rstn (rstn) ,
.div_en (div_end_t[i]) ,
.dividend ({remainder_t[i],dividend_t[i][i-1]}) ,
.divisor (divisor_t[i]) ,
.merchant_i (merchant_o_t[i]) ,
.dividend_src_i (dividend_t[i]) ,
.div_end (div_end_t[i-1]) ,
.remainder (remainder_t[i-1]) ,
.divisor_src_o (divisor_t[i-1]) ,
.merchant_o (merchant_o_t[i-1]) ,
.dividend_src_o (dividend_t[i-1])
);
end
endgenerate
assign div_end=div_end_t[0];
assign merchant=merchant_o_t[0];
assign remainder=remainder_t[0];
endmodule
3. Simulation verification
The simulation results are as follows:
It can be seen from the figure that the first output result has gone through4 clock cycles. According to the calculation, the output quotient and remainder are both correct.
Summary
This article mainly explains the basic principles and pipeline implementation of the divider. In hardware, there are many algorithms for implementing dividers. A thorough study requires further discussion.
Since I have been ill recently, this article is a little rough, so I apologize for it!
If you think the article is helpful to you, please like and follow. See you in the next issue!