Verilog整数除法算法

在verilog语言设计时，我们经常使用verilog 语法实现一些算术运送。比如 a = a + 1; b= 256- c; c = n*m; d= f/k ; 等等。一般情况下。 + 、- 运算占用逻辑比较少，使用IP核或者使用verilog 语法实现相关的电路，整个工程都可以跑到比较高的速度。（具体算法实现的延时，根据不同芯片有所不同）。乘法操作一般是通过IP核来实现的，当然使用verilog 语法也是可以实现的。但是通过verilog 语法实现会占用大量的逻辑，同时逻辑电路延迟也是比较长的。

使用verilog 语法实现乘法的好处是：

可以移植到任何一个平台上，比如xilinx的代码移植到altera 芯片上。
不像使用乘法IP，受到fpga DSP 数量的限制。

缺点是：

使用verilog 语法 * 产生大量逻辑电路，综合后时序不是很高。

所以乘法算法通常是将数据分成若干个8421 系数进行组合，通过移位和加法运算来实现。

举例：c = n * 13 = n * (8 + 4 + 1) = n << 3 + n <<2 + n;

1 除法算法实现的方法

除法的verilog实现比较复杂。一般来说可以通过一下几种方法：

1）分母是常数，可以将 d = f/k 变换为 d = f * 1/k 。如果k为常数，可以提前将1/k 计算出来，然后实现乘法操作即可。

2）分母是常数，并且分母是2的整数幂，可以通过逻辑右移实现。例如 d = f/8; d = f >> 3;

3）分子，分母都是变量，可以使用IP 核来实现，xilinx ，altera 都有相应的IP 核。缺点是一颗芯片中的IP 核（DSP）数量有限。

4）分子，分母都是变量，如果程序不着急使用除法的输出结果（商数，余数），可以通过减法算法实现。举例：d = f/k ; d = f -k -k -k ….. -k 。直到结果为0 或者是结果小于k。只要计算一下做几次减法，就可以得到商数和余数了。

5）分子，分母都是变量，通过竖式方式实现（long division）。这种方法和小学学习的竖式除法方法类似。

2 竖式除法算法原理

首先，我们看一下10进制下的除法运算：

8634/23 = 375 + R9

图1

2进制下的除法竖式算法为

8634/23 = 375 + R9

图2

3 verilog 算法

表1

m	n	quotient	解释（蓝色部分为商）
0000_0000_0001_0111	0000_0000_0000_0000		divisor << 16
0000_0000_0000_0000	0010_0001_1011_1010	0000_0000_0000_0000	{16’h0000, dividend}，初始化
0000_0000_0000_0000	0100_0011_0111_0100	0000_0000_0000_0000	被除数+ 商数整行左移一位
0000_0000_0000_0000	1000_0110_1110_1000	0000_0000_0000_0000	被除数+ 商数整行左移一位
0000_0000_0000_0001	0000_1101_1101_0000	0000_0000_0000_0000	被除数+ 商数整行左移一位
0000_0000_0000_0010	0001_1011_1010_0000	0000_0000_0000_0000	被除数+ 商数整行左移一位
0000_0000_0000_0100	0011_0111_0100_0000	0000_0000_0000_0000	被除数+ 商数整行左移一位
0000_0000_0000_1000	0110_1110_1000_0000	0000_0000_0000_0000	被除数+ 商数整行左移一位
0000_0000_0001_0000	1101_1101_0000_0000	0000_0000_0000_0000	被除数+ 商数整行左移一位
0000_0000_0010_0001	1011_1010_0000_0000	0000_0000_0000_0001	被除数+ 商数整行左移一位
0000_0000_0000_1010	1011_1010_0000_0000	0000_0000_0000_0001	10_0001 > 1_0111，当前行{m , n} – (divisor << 16)
0000_0000_0001_0101	0111_0100_0000_0000	0000_0000_0000_0010	被除数+ 商数整行左移一位
0000_0000_0010_1010	1110_1000_0000_0000	0000_0000_0000_0101	被除数+ 商数整行左移一位
0000_0000_0001_0011	1110_1000_0000_0000	0000_0000_0000_0101	10_1010 > 1_0111，当前行{m , n} – (divisor << 16)
0000_0000_0010_0111	1101_0000_0000_0000	0000_0000_0000_1011	被除数+ 商数整行左移一位
0000_0000_0001_0000	1101_0000_0000_0000	0000_0000_0000_1011	10_0111 > 1_0111，当前行{m , n} – (divisor << 16)
0000_0000_0010_0001	1010_0000_0000_0000	0000_0000_0001_0111	被除数+ 商数整行左移一位
0000_0000_0000_1010	1010_0000_0000_0000	0000_0000_0001_0111	10_0001 > 1_0111，当前行{m , n} – (divisor << 16)
0000_0000_0001_0101	0100_0000_0000_0000	0000_0000_0010_1110	被除数+ 商数整行左移一位
0000_0000_0010_1010	1000_0000_0000_0000	0000_0000_0101_1101	被除数+ 商数整行左移一位
0000_0000_0001_0011	1000_0000_0000_0000	0000_0000_0101_1101	10_1010 > 1_0111，当前行{m , n} – (divisor << 16)
0000_0000_0010_0111	0000_0000_0000_0000	0000_0000_1011_1011	被除数+ 商数整行左移一位
0000_0000_0001_0000	0000_0000_0000_0000	0000_0000_1011_1011	10_0111 > 1_0111，当前行{m , n} – (divisor << 16)
0000_0000_0010_0000	0000_0000_0000_0000	0000_0001_0111_0111	被除数+ 商数整行左移一位
0000_0000_0000_1001	0000_0000_0000_0000	0000_0001_0111_0111	10_0000 > 1_0111，当前行{m , n} – (divisor << 16)
			1001 余数

如表1 所示： 8634/23 = 375 + R9

1）首先将 8634 之前扩展 16bit 0。 {16’h0000, 8634} = {16’b0000_0000_0000_0000, 16’b0010_0001_1011_1010} = {m,n}

2）将23 之后扩展16bit 0。{23,16’h0000} = {16’b0000_0000_0001_0111, 16’b0000_0000_0000_0000}

3）{m,n, quotient} << 1；

if(m >= 23) {m,n} = {m,n} – {23,16’h0000}; 商 quotient[0] = 1’b1;

在状态3 连续执行16 次，跳转到状态4

4）m 为余数， quotient 为商数。

整个算法就是根据竖式除法以2进制方式操作，最后得到相应的商数和余数。

4 verilog 算法优化

从表1中，我们可以看出，每次左移操作中，n 补上0， quotient 保留的是商数。实际上可以不使用quotient这个变量，每次一位操作时，将商补齐在n的最后一位即可。这样就可以省出16bit 的寄存器。

算法如下：

1）首先将 8634 之前扩展 16bit 0。 {16’h0000, 8634} = {16’b0000_0000_0000_0000, 16’b0010_0001_1011_1010} = {m,n}

2）将23 之后扩展16bit 0。{23,16’h0000} = {16’b0000_0000_0001_0111, 16’b0000_0000_0000_0000}

3）{m,n} << 1；

if(m >= 23) {m,n} = {m,n} – {23,16’h0000}; 商 n[0] = 1’b1;

在状态3 连续执行16 次，跳转到状态4

4）m 为余数， n 为商数。

Verilog 代码：

`timescale 1ns / 1ps
module int_div_core
#(
    parameter DATA_WID = 8,
    parameter SIM_DEBUG = "FALSE"
)
(
    input  clk,
    
    input  [DATA_WID- 1:0] dividend,
    input  [DATA_WID- 1:0] divisor,
    input  div_valid,
    
    output [DATA_WID- 1:0] dbg_quot,
    output [DATA_WID- 1:0] dbg_rem,
    output reg dbg_rest_rdy = 0,

    output [DATA_WID- 1:0] quotient,
    output [DATA_WID- 1:0] remainder,
    output result_ready,

    input  rst
);

//========================================================================= 

reg [DATA_WID*2 -1:0] tmp_op;
reg [DATA_WID*2 -1:0] tmp_divisor;
reg [$clog2(DATA_WID):0] i;
reg done_r;
always @ (posedge clk or posedge rst)
if(rst) begin
    i = 0;
    tmp_op = 0;
    tmp_divisor = 0;
end
else
begin 
    i = 0;
    if(div_valid) 
    begin
        if(i == 0) 
        begin
            tmp_op = {{DATA_WID{1'b0}}, dividend};
            tmp_divisor = { divisor, {DATA_WID{1'b0}}}; 
        end
        
        for (i = 0; i < DATA_WID; i = i + 1)
        begin
            tmp_op = tmp_op << 1;
            if(tmp_op >= tmp_divisor) tmp_op = (tmp_op - tmp_divisor) | 1'b1;
            else tmp_op = tmp_op;
        end
        done_r = 1;
    end
    else done_r = 0;
end
 
assign remainder = tmp_op[DATA_WID*2 -1:DATA_WID];
assign quotient  = tmp_op[DATA_WID- 1:0];

assign result_ready = done_r;


//========================================================================= 
reg [DATA_WID- 1:0] quot = 0;
reg [DATA_WID- 1:0] rem = 0;
always @ (posedge clk or posedge rst)
if(rst)
begin
    dbg_rest_rdy <= 0;
end
else
begin
    dbg_rest_rdy <= 0;
    if(div_valid)
    begin
        quot <= dividend/divisor;
        rem <= dividend%divisor;
        dbg_rest_rdy <= 1;
    end
end
//========================================================================= 
 
assign dbg_quot = quot;
assign dbg_rem = rem;

endmodule

整个代码分为两个部分， dbg_quot, dbg_rem 用于verilog 验证，这里直接使用的是verilog 语法实现。 quotient， remainder 是算法实现的除法器。目前使用阻塞赋值的方式实现，掌握算法后，可以很容易的通过状态机方式实现。这样就可以提高综合时序了。（缺点是需要多个clock后，才能得到除法结果）。

思考问题：如何实现有符号的整数除法器设计呢？

Quartus 工程代码：

[content_control]

int_division.zip

[/content_control]

Verilog整数除法算法

1 除法算法实现的方法

2 竖式除法算法原理

3 verilog 算法

4 verilog 算法优化

1 Comment

发表回复取消回复

近期评论

Verilog整数除法算法

1 除法 算法实现的方法

2 竖式除法算法原理

3 verilog 算法

4 verilog 算法优化

1 Comment

发表回复 取消回复

相关链接

近期评论

1 除法算法实现的方法

发表回复取消回复