专题四：除法器

除法运算也是数字信号处理中经常需要使用的。在FPGA设计中，通常为了简化算法，通常将除法近似为对数据进行移位操作即除数是2的整数次幂，因为在FPGA中进行移位很容易，比如右移2位相当于除4；但是在某些特殊情况下，为了满足数据处理的指标要求，不得不进行非2的整数次幂除法运算，此时就需要设计除法器。

对于被除数Nom，除数Den，除法可产生商Quo和余数Rem，计算式如下：

直接用上式在FPGA中实现，好像不是那么容易，对上式做一变换得到Rem=Nom-Den*Quo，这样些灵感，被除数Nom和除数Den是给定的，可以通过比对Nom和Den*Quo值大小来调节商Quo的值，因为FPGA中数值都是以二进制表示的，因此按位来调节Quo的值，Den*Quo的乘法操作可用移位实现，因此可以完全使用逻辑实现整个除法器。

本文介绍两种常用除法器结构：Restoring除法器和NonRestoring除法器

NonRestoring除法器：

Verilog HDL代码如下：

//nonrestoring division module div_uu(clk,rst,clk_en,nom,den,quo,rem); parameter integer n_width=32; parameter integer d_width=16; parameter integer q_width=n_width; parameter integer r_width=d_width; input clk; input rst; input clk_en; input [n_width-1:0] nom; input [d_width-1:0] den; output reg [q_width-1:0] quo; output reg [r_width-1:0] rem; reg [n_width+d_width-1 : 0] den_d[q_width : 1]; reg [q_width-1 : 0] quo_d[q_width : 1]; reg [n_width+d_width-1 : 0] rem_d[q_width : 1]; reg clk_en_d[q_width : 1]; always@(posedge clk) if(rst) begin rem_d[1]<={(n_width+d_width){1'b0}}; den_d[1]<={(n_width+d_width){1'b0}}; quo_d[1]<={q_width{1'b0}}; clk_en_d[1]<=1'b0; end else if(clk_en) begin rem_d[1]<={{d_width{1'b0}},nom}; den_d[1]<={1'b0,den,{(n_width-1){1'b0}}}; quo_d[1]<={q_width{1'b0}}; clk_en_d[1]<=1'b1; end else begin rem_d[1]<={(n_width+d_width){1'b0}}; den_d[1]<={(n_width+d_width){1'b0}}; quo_d[1]<={q_width{1'b0}}; clk_en_d[1]<=1'b0; end generate genvar i; for(i=2;i<=q_width;i=i+1) begin:U always@(posedge clk) if(rst) begin rem_d[i]<={(n_width+d_width){1'b0}}; den_d[i]<={(n_width+d_width){1'b0}}; quo_d[i]<={q_width{1'b0}}; clk_en_d[i]<=1'b0; end else if(clk_en_d[i-1]) begin if(rem_d[i-1] >= den_d[i-1]) begin rem_d[i]<=rem_d[i-1] - den_d[i-1]; den_d[i]<=den_d[i-1]>>1; quo_d[i]<={quo_d[i-1][q_width-2:0],1'b1}; end else begin rem_d[i]<=rem_d[i-1]; den_d[i]<=den_d[i-1]>>1; quo_d[i]<={quo_d[i-1][q_width-2:0],1'b0}; end clk_en_d[i]<=1'b1; end else begin rem_d[i]<={(n_width+d_width){1'b0}}; den_d[i]<={(n_width+d_width){1'b0}}; quo_d[i]<={q_width{1'b0}}; clk_en_d[i]<=1'b0; end end endgenerate always@(posedge clk) if(rst) begin rem<={d_width{1'b0}}; quo<={q_width{1'b0}}; end else if(clk_en_d[q_width]) begin if((rem_d[q_width] >= den_d[q_width])) begin rem<=rem_d[q_width] - den_d[q_width]; quo<={quo_d[q_width][q_width-2:0],1'b1}; end else begin rem<=rem_d[q_width]; quo<={quo_d[q_width][q_width-2:0],1'b0}; end end else begin rem<={d_width{1'b0}}; quo<={q_width{1'b0}}; end endmodule

上述代码实现了32位除16位无符号除法操作，综合得到结果如下：

Number of Slice Registers: 2112

Number of Slice LUTs: 1565

Minimum period: 2.070ns (Maximum Frequency: 483.139MHz)

仿真结果如图1所示

图1

Restoring除法器：

Verilog HDL代码如下：

module div_uu_restoring(clk,rst,clk_en,nom,den,quo,rem); parameter integer n_width=32; parameter integer d_width=16; parameter integer q_width=n_width; parameter integer r_width=d_width; input clk; input rst; input clk_en; input [n_width-1:0] nom; input [d_width-1:0] den; output reg [q_width-1:0] quo; output reg [r_width-1:0] rem; reg [n_width+d_width-1 : 0] den_d[2*q_width-1 : 1]; reg [q_width-1 : 0] quo_d[2*q_width-1 : 1]; reg signed [n_width+d_width-1 : 0] rem_d[2*q_width-1 : 1]; reg clk_en_d[2*q_width-1:1]; always@(posedge clk) if(rst) begin rem_d[1]<={(n_width+d_width){1'b0}}; den_d[1]<={(n_width+d_width){1'b0}}; quo_d[1]<={q_width{1'b0}}; clk_en_d[1]<=1'b0; end else if(clk_en) begin rem_d[1]<={{d_width{1'b0}},nom} - {1'b0,den,{(n_width-1){1'b0}}}; den_d[1]<={1'b0,den,{(n_width-1){1'b0}}}; quo_d[1]<={q_width{1'b0}}; clk_en_d[1]<=1'b1; end else begin rem_d[1]<={(n_width+d_width){1'b0}}; den_d[1]<={(n_width+d_width){1'b0}}; quo_d[1]<={q_width{1'b0}}; clk_en_d[1]<=1'b0; end generate genvar i; for(i=1;i
        
         >1; clk_en_d[2*i]<=1'b1; end else begin rem_d[2*i]<={(n_width+d_width){1'b0}}; den_d[2*i]<={(n_width+d_width){1'b0}}; quo_d[2*i]<={q_width{1'b0}}; clk_en_d[2*i]<=1'b0; end always@(posedge clk) if(rst) begin rem_d[2*i+1]<={(n_width+d_width){1'b0}}; den_d[2*i+1]<={(n_width+d_width){1'b0}}; quo_d[2*i+1]<={q_width{1'b0}}; clk_en_d[2*i+1]<=1'b0; end else if(clk_en_d[2*i]) begin //restoring rem_d[2*i+1]<=rem_d[2*i] - den_d[2*i]; den_d[2*i+1]<=den_d[2*i]; quo_d[2*i+1]<=quo_d[2*i]; clk_en_d[2*i+1]<=1'b1; end else begin rem_d[2*i+1]<={(n_width+d_width){1'b0}}; den_d[2*i+1]<={(n_width+d_width){1'b0}}; quo_d[2*i+1]<={q_width{1'b0}}; clk_en_d[2*i+1]<=1'b0; end end endgenerate always@(posedge clk) if(rst) begin rem<={n_width{1'b0}}; quo<={q_width{1'b0}}; end else if(clk_en_d[2*q_width-1]) begin if(rem_d[2*q_width-1]<0 ) begin rem<=rem_d[2*q_width-1] + den_d[2*q_width-1]; quo<={quo_d[2*q_width-1][q_width-2:0],1'b0}; end else begin rem<=rem_d[2*q_width-1][n_width-1:0]; quo<={quo_d[2*q_width-1][q_width-2:0],1'b1}; end end else begin rem<={d_width{1'b0}}; quo<={q_width{1'b0}}; end endmodule
        

上述代码实现了32位除16位无符号除法操作，综合得到结果如下：

Number of Slice Registers: 3875

Number of Slice LUTs: 2974

Minimum period: 1.794ns (Maximum Frequency: 557.414MHz)

仿真结果如图2所示，

图2

两种结构的乘法器有所区别，通过比较可发现，NonRestoring除法器没有“Rem=Nom-Den*Quo”的操作，而是直接比较Nom和Den*Quo的值，加上移位操作都在一个时钟周期内完成；而Restoring除法器将“Rem=Nom-Den*Quo”的结果寄存，并且在下一个时钟周期进行移位操作。因此，NonRestoring除法器Fmax较高，Restoring除法器相对节省资源，在应用时可根据实际需求决定采用哪一种结构的除法器。