FPGA的快速除法及取余运算(Verilog)

最近在使用 FPGA 开发时，需要用到除法及取余运算，最开始使用了 lpm_divide 功能（也就是直接用/和%运算符），效率确实很高，不过特别占用资源，如图 1 所示。

资源几乎被用完，为了减少资源占用，找了一种快速的除法及取余运算。

一、基于减法的除法器的算法

相较于乘法器的左移相加，除法器就是移位相减。

例如，十进制数 99 除以十进制数 5——99/5，即二级制数 1100011 除以二级制数 101：

1. 1100011 – 1010000 = 10011(其中二进制 1010000 = 5 乘 2 的 4 次幂)；
2. 10011 – 1010 = 1001 ( 其中二进制 1010 = 5 乘 2 的 1 次幂)；
3. 1001 – 101 = 100( 其中二进制 101 = 5 乘 2 的 0 次幂)；
4. 得到商为 2^4+2^1+2^0 = 16+2+1=19(^代表次幂)，余数为二进制 100 = 4。

1.1 硬件实现原理

对于 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 位即为商。

1.2 verilog HDL 代码及仿真

除法及取余算法代码：

/*  
* module:div_rill  
* file name:div_rill.v  
* syn:yes  
* author:network  
* modify:sunev
* date:2020-11-28  
*/  
  
module div_rill  
(  
input[31:0] a,   
input[31:0] b,  
  
output reg [31:0] yshang,  
output reg [31:0] yyushu  
);  
  
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  
    temp_a = {32'h00000000,tempa};  
    temp_b = {tempb,32'h00000000};   
    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];  
end  
  
endmodule  
  
/*************** EOF ******************/  

testbench 代码：

/*  
* module:div_rill_tb  
* file name:div_rill_tb.v  
* syn:no  
* author:sunev
* date:2020-11-28  
*/  
  
  
`timescale 1ns/1ns  
  
module div_rill_tb;  
  
reg [31:0] a;  
reg [31:0] b;  
wire [31:0] yshang;  
wire [31:0] yyushu;  
  
initial  
begin  
    #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_rill DIV_RILL  
(  
.a (a),  
.b (b),  
  
.yshang (yshang),  
.yyushu (yyushu)  
);  
  
endmodule  
/******** EOF ******************/ 

仿真结果：

1.3 改进

将组合逻辑改成时序逻辑，并修改位宽，这里采用了 16 位的数据，所以商和余数用了 16 个 clk 实现。

verilog HDL 代码：

/*  
* module:div_rill  
* file name:div_rill.v  
* author:sunev  
* date:2020-11-28
*/ 
  
module div_rill
(  
	clk,
	rst_n,
	i,
	a,   
	b,  
	temp_a,
	temp_b,
	yshang,  
	yyushu  
);  

input clk;
input rst_n;
input [15:0] a;
input [15:0] b;
output [15:0] yshang;
output [15:0] yyushu;

//for simulation
output [7:0] i;
output [31:0] temp_a, temp_b;

reg [15:0] yshang;
reg [15:0] yyushu;

wire [15:0] tempa, tempb;  
reg [31:0] temp_a, temp_b;  

assign tempa = a;
assign tempb = b;

reg [7:0] i;  
  
always @(posedge clk or negedge rst_n)  
begin
	if(!rst_n)
	begin
		i <= 8'd0;
		temp_a <= 16'h0;  
		temp_b <= 16'h0;  
		yshang <= 16'h0;  
		yyushu <= 16'h0; 
	end
	else case(i)
	8'd0:
	begin
		i = i + 1'b1;
		temp_a = {16'h0000,tempa};  
		temp_b = {tempb,16'h0000};   
	end
	8'd1:
	begin
		i = i + 1'b1;
		temp_a = {temp_a[30:0],1'b0};  
		if(temp_a[31:16] >= tempb)  
			temp_a = temp_a - temp_b + 1'b1;  
		else  
			temp_a = temp_a; 	
	end
	8'd17:
	begin
		i = 8'd17;
		yshang <= temp_a[15:0];  
		yyushu <= temp_a[31:16]; 
	end
	default:
	begin
		i = i + 1'b1;
		temp_a = {temp_a[30:0],1'b0};  
		if(temp_a[31:16] >= tempb)  
			temp_a = temp_a - temp_b + 1'b1;  
		else  
			temp_a = temp_a; 	
	end
	endcase
end  
  
endmodule  
  
/*************** EOF ******************/  

testbench 代码：

/*  
* module:div_rill_tb  
* file name:div_rill_tb.v
* author:sunev  
* date:2020-11-28
*/  
  
  
`timescale 1ns/1ns  
  
module div_rill_tb();  
  
reg [15:0] a;  
reg [15:0] b;  
wire [15:0] yshang;  
wire [15:0] yyushu;  

reg clk;
reg rst_n;

initial  
begin  
    #0  clk = 0;
        rst_n = 0;
		  a = 16'haabb;  
        b = 16'hcd;  
		  
    #5  rst_n = 1;
end  

always #10 clk = ~clk;

wire [7:0] i;
wire [31:0] temp_a, temp_b;  

div_rill u1
(
	.clk(clk),
	.rst_n(rst_n),
	.i(i),
	.a (a),  
	.b (b),  
	.temp_a(temp_a), 
	.temp_b(temp_b),
	.yshang (yshang),  
	.yyushu (yyushu)  
);  
  
endmodule  

/******** EOF ******************/  

do 代码：

vlib work
vmap work work
vlog -novopt -incr -work work "div_rill_tb.v"
vlog -novopt -incr -work work "div_rill.v"
vsim -novopt work.div_rill_tb -t 1ns 
add wave -noupdate /div_rill_tb/rst_n
add wave -noupdate /div_rill_tb/clk
add wave -noupdate /div_rill_tb/i
add wave -noupdate /div_rill_tb/a
add wave -noupdate /div_rill_tb/b
add wave -noupdate /div_rill_tb/temp_a
add wave -noupdate /div_rill_tb/temp_b
add wave -noupdate /div_rill_tb/yshang
add wave -noupdate /div_rill_tb/yyushu

run 1000

仿真结果：

最后将开发项目中的除法和取余运算修改之后的资源占用情况如下图所示：

1.4 算法推倒

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

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

画个简单的图：

扫码关注尚为网微信公众号