FPGA除法器设计实现

（添加于20180812）对于32的无符号除法，被除数a除以除数b，他们的商和余数一定不会超过32位。首先将a转换成高32位为0，低32位为a的temp_a。把b转换成高32位为b，低32位为0的temp_b。在每个周期开始时，先将temp_a左移一位，末尾补0，然后与b比较，是否大于b，是则temp_a减去temp_b将且加上1，否则继续往下执行。上面的移位、比较和减法（视具体情况而定）要执行32次，执行结束后temp_a的高32位即为余数，低32位即为商。

除法实现的核心算法推导（非原创）：

假设4bit的两数相除 a/b，商和余数最多只有4位 （假设1101/0010也就是13除以2得6余1）

我们先自己做二进制除法，则首先看a的MSB，若比除数小则看前两位，大则减除数，然后看余数，以此类推直到最后看到LSB；而上述算法道理一样，a左移进前四位目的就在于从a本身的MSB开始看起，移4次则是看到LSB为止，期间若比除数大，则减去除数，注意减完以后正是此时所剩的余数。而商呢则加到了这个数的末尾，因为只要比除数大，商就是1，而商0则是直接左移了，因为会自动补0。这里比较巧因为商可以随此时的a继续左移，然后新的商会继续加到末尾。经过比对会发现移4位后左右两边分别就是余数和商。

画个简单的图：

我们都知道，FPGA是由多个LE构成的集成电路，逻辑电路的特点就是只能输出0或者1，也就是说只能用来表示整数而不是小数，那么对于除法器这种可能会出现小数的运算如何处理呢？简单的思路就是将被除数扩大，从而得到量化后的商值以及余数。

那么采用基于减法的算法有两种实现方式（这里采用除数和被除数都是21位的情况对计算的精确度以及占用的资源做了整理）

1.组合逻辑的实现法

RTL编程

module div  
(  
input[31:0] a,   
input[31:0] b,  
input enable,
output reg [31:0] yshang,  
output reg [31:0] yyushu,
output reg done 
);  
  
reg[31:0] tempa;  
reg[31:0] tempb;  
reg[63:0] temp_a;  
reg[63:0] temp_b;  
  
integer i;  
  
always @(a or b)  
begin  
    tempa <= a;  
    tempb <= b;  
end  
  
always @(tempa or tempb)  
begin  
if(enable)
  begin
    temp_a = {32'h00000000,tempa};  
    temp_b = {tempb,32'h00000000};  
    done = 0; 
    for(i = 0;i < 32;i = i + 1)  
        begin  
            temp_a = {temp_a[62:0],1'b0};  
            if(temp_a[63:32] >= tempb)  
                temp_a = temp_a - temp_b + 1'b1;  
            else  
                temp_a = temp_a;  
        end  
  
    yshang = temp_a[31:0];  
    yyushu = temp_a[63:32]; 
    done = 1; 
  end
end  
  
endmodule  

 

testbeach

`timescale 1ns/1ns  
  
module test();  
  
reg [31:0] a;  
reg [31:0] b; 
reg enable; 
wire [31:0] yshang;  
wire [31:0] yyushu;  
wire done;
initial  
begin  
enable=1;
    #10 a = $random()%10000;  
        b = $random()%1000;  
          
    #100 a = $random()%1000;  
        b = $random()%100;  
          
    #100 a = $random()%100;  
        b = $random()%10;     
          
    #1000 $stop;  
end  
  
div DIV_RILL  
(  
.a (a),  
.b (b),  
.enable(enable), 
.yshang (yshang),  
.yyushu (yyushu),
.done(done)  
);  
  
endmodule  

 

仿真波形

资源占用

2.时序逻辑的实现法

 

RTL编程

`timescale 1ns / 1ps
module div_rill #( parameter N=21)
(
input clk,
input rst, 
input enable,
input [N-1:0] a, 
input [N-1:0] b, 
output reg [N-1:0] yshang,
output reg [N-1:0] yyushu, 
output reg done
);
parameter S=N<<1; 
reg[N-1:0] tempa;
reg[N-1:0] tempb;
reg[S-1:0] temp_a;
reg[S-1:0] temp_b; 
reg [5:0] status;
parameter s_idle = 6'b000000;
parameter s_init = 6'b000001;
parameter s_calc1 = 6'b000010;
parameter s_calc2 = 6'b000100;
parameter s_done = 6'b001000;
 
reg [N-1:0] i;
 
always @(posedge clk)
begin
    if(rst)
        begin
            i <= 21'h0;
            tempa <= 21'h1;
            tempb <= 21'h1;
            yshang <= 21'h1;
            yyushu <= 21'h1;
            done <= 1'b0;
            status <= s_idle;
        end
    else
        begin
            case (status)
            s_idle:
                begin
                    if(enable)
                        begin
                            tempa <= a;
                            tempb <= b;
                            status <= s_init;
                        end
                    else
                        begin
                            i <= 21'h0;
                            tempa <= 21'h1;
                            tempb <= 21'h1;
                            yshang <= 21'h1;
                            yyushu <= 21'h1;
                            done <= 1'b0;
                            status <= s_idle;
                        end
                end
                
            s_init:
                begin
                    temp_a <= {21'h00000000,tempa};
                    temp_b <= {tempb,21'h00000000};
                    status <= s_calc1;
                end
                
            s_calc1:
                begin
                    if(i < N)
                        begin
                            temp_a <= {temp_a[S-2:0],1'b0};
                            status <= s_calc2;
                        end
                    else
                        begin
                            status <= s_done;
                        end
                    
                end
                
            s_calc2:
                begin
                    if(temp_a[S-1:N] >= tempb)
                        begin
                            temp_a <= temp_a - temp_b + 1'b1;
                        end
                    else
                        begin
                            temp_a <= temp_a;
                        end
                    i <= i + 1'b1;    
                    status <= s_calc1;
                end
            
            s_done:
                begin
                    yshang <= temp_a[N-1:0];
                    yyushu <= temp_a[S-1:N];
                    done <= 1'b1;
                    
                    status <= s_idle;
                end
            
            default:
                begin
                    status <= s_idle;
                end
            endcase
        end
   
end
 
 
endmodule

 

 

testbeach

`timescale 1ns / 1ps
//////////////////////////////////////////////////////////////////////////////////
// Company: 
// Engineer: 
// 
// Create Date: 2018/07/27 22:16:33
// Design Name: 
// Module Name: test
// Project Name: 
// Target Devices: 
// Tool Versions: 
// Description: 
// 
// Dependencies: 
// 
// Revision:
// Revision 0.01 - File Created
// Additional Comments:
// 
//////////////////////////////////////////////////////////////////////////////////

 
module test();
 
reg clk;
reg rst;
reg enable; 
reg [20:0] a;
reg [20:0] b;
wire [20:0] yshang;
wire [20:0] yyushu; 
wire done;
 
initial
begin
    clk = 0;
    
    #10
    rst = 1;
    #20
    rst = 0;
    
    #15
    enable =1;
    a = $random()%10000;
    b = $random()%1000;
    #10
    enable =0;
    
    #1000
    enable =1;
    a = $random()%1000;
    b = $random()%100;
    #10
    enable =0;
    
    #1000
    enable =1;
    a = $random()%100;
    b = $random()%10;    
    #10
    enable =0;
    
    #1000 $stop;
end
 
always # 5 clk = ~clk;
always #1000 a=a+8;
always #1000 b=b+9; 
div_rill DIV_RILL
(
.clk (clk),
.rst (rst),
.enable (enable),
.a (a), 
.b (b),
.yshang (yshang),
.yyushu (yyushu), 
.done (done)
);
 
endmodule

仿真波形(可以看出，该设计下从开始做除法到完成一共需要（2515-2065）/10=45个时钟周期)每做一次计算的延时较长。

 

资源占用

 

结论：可以看出我们通常的设计中一般建议采用时序电路的实现方法而不是组合逻辑，虽然时序逻辑的实现方法会导致计算延时，但是因为组合逻辑占资源较多而且可能在时序约束部分出现错误，要远远大于延时的错误。