【赛灵思FPGA】DSP in FPGA:除法器
0赞专题四：除法器
除法运算也是数字信号处理中经常需要使用的。在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除法器相对节省资源，在应用时可根据实际需求决定采用哪一种结构的除法器。
