☰
Verilog手写除法器:从恢复余数法到可综合状态机设计
2026/10/20 18:15:16 网站建设 项目流程

第一次在自己写的模块里放一个除法器的时候,我以为把/这个符号丢给综合工具就完事了。后来看到资源报告和时序报告才明白,事情没那么简单——除法不像乘法那样有现成的硬件加速,想要一个可控的除法器,还是得自己动手。

这篇文章想聊的就是这件事:在 Verilog 里从一个除法器的原理开始,到状态机的设计、可综合代码的落地,再到完整仿真验证的整个套路。适合刚把 Verilog 语法学完、准备接触真实数字设计问题的同学,也适合做过一些简单模块、想搞清楚除法器内部结构的开发者。下面所有代码都是我实际跑过的,直接抄作业也能用,但更建议跟着思路走一遍,这样遇到位宽溢出、除零这类坑的时候,你才知道问题出在哪。

1. 为什么除法在FPGA里总是绕不开的坑

1.1 综合工具对/运算符的真实处理

很多第一次接触 FPGA 的同学会有个错觉:Verilog 里写了a / b,综合工具就会自动生成一个能用的除法器。这话说对了一半,但代价没有写出来。

综合工具处理除法时,通常会走两条路。一条是把变量除法转换成一个组合逻辑网络,这种形式会让 LUT 消耗非常夸张,而且随着位宽增加,组合路径上的延迟几乎是指数级别的增长。另一条路是调用片内的除法 IP 核,这确实能解决问题,但会产生两个新的约束:你的工程必须配置好这个 IP,而且它的时序行为、握手协议都受 IP 提供的模式限制。真正想掌控时钟节拍、面积和吞吐率的时候,手写一个寄存器级除法器往往是更可靠的选择。

另一个常见误解是:综合工具对除法的优化能力很强。它确实在“被除数是常数”的场景下表现不错,能把除法优化成乘法和移位的组合,比如计算x / 8会被等价成x >> 3,几乎不占什么逻辑。可一旦除数是变量,尤其是无符号变量,情况就完全不同了。我的经验是,在项目早期就确认清楚除法器的需求形式:是固定被除数、固定除数,还是完全随机的变量除法。固定场景可以靠常数优化逃课,随机场景就得老老实实设计一个迭代结构。

1.2 组合展开与周期迭代:面积和时序的取舍

写除法器之前,先要决定用组合逻辑一把算完,还是用状态机分多个周期迭代算完。

组合除法器的思路很简单:把除法的每一步展开成并联结构,用比较器和减法器一层层搭。比如 8 位无符号除法,如果直接用组合方式做,最直观的办法是生成 8 个试减单元,每个单元处理一位商,然后再串接起来。但这种结构有一个明显的问题:后一级的输入依赖前一级的余数结果,本质上是一条很长的组合链路。仿真的时候看不出毛病,一上板子做时序分析,数字往往很难看。

周期迭代的思路相反:只保留一套减法器和移位寄存器,每个时钟周期处理一位商,用计数器控制次数。代价是延迟变大,8 位除法需要 8 个周期才能算出结果,但面积和组合路径都非常可控,时序收敛要容易得多。对于大多数通用嵌入式场景,几个周期的延迟通常是可以接受的。

两种路线的取舍,我一般用一个简单的表格来权衡:

方案面积组合延迟延迟周期适用场景
组合展开很高随位宽暴涨0 周期位宽小、时钟频率低
周期迭代低稳定N 周期通用、时序敏感
IP 核厂商优化看配置可配置不想维护逻辑

手写周期迭代并不是要取代 IP 核,而是让你在面对“除法器到底占用多少资源、多少周期”这一类问题时,心里有底。后面我讲的恢复余数法,就是周期迭代里最经典、最适合作为入门理解的一种实现。

2. 恢复余数除法:把竖式运算翻译成状态机

2.1 二进制竖式的核心逻辑

恢复余数法是从手算二进制除法演变过来的。小学学的十进制竖式,每一步都先看当前余数和被除数下一位拼起来的数够不够减除数,够就上商 1,不够就上商 0。二进制里因为只有 0 和 1,判断更简单:够减就是 1,不够就是 0。

放到硬件里,“够不够减”就变成了一个减法器和一个符号位判断。把被除数从最高位开始逐位移入余数寄存器,每次移动后拿余数寄存器减去除数,如果结果非负,说明够减,商位写 1,余数寄存器更新为减法结果;如果结果为负,说明不够减,商位写 0,余数寄存器保持不变。

这就是所谓的“恢复”两个字的意思:减完发现是负数,就相当于把这次减法“撤销”回去,恢复到减法之前的状态,再进入下一位的运算。传统教材里的实现会真的做一个加法把余数加回来,但在工程上我们不需要这么麻烦,用多路选择器直接选择不回写减法结果就行,既省了一个加法器,又节省了一个周期。

2.2 恢复余数法的迭代过程

用一句话概括流程:每个时钟周期,从被除数当前最高位开始取 1 位,把余数寄存器左移一位并把这 1 位补到低位,然后做一次试减,根据试减结果产生当前位的商。

这里最容易出错的地方,是余数寄存器的位宽。设想 8 位被除数a、8 位除数b,余数寄存器只开 8 位是不够的。因为左移之后余数可能变成 9 位,减法比较时也可能出现最高位的借位,必须多留 1 位来保存这个符号信息。所以我实现的时候,余数寄存器R一定声明成[W:0],也就是W+1位宽。

完整迭代过程可以拆成四步:

  1. 取被除数当前最高位,余数寄存器左移一位,把该位填入低位。
  2. 对更新后的余数执行R - b。
  3. 若结果最高位为 0,说明没有借位、够减,商位置 1,余数更新为R - b。
  4. 若结果最高位为 1,说明借位、不够减,商位置 0,余数保持左移后的值不变。

重复W次后,商寄存器里就是完整的商,余数寄存器的低W位就是真正的余数。

2.3 数据通路与位宽设计

有了上面的流程,硬件的数据通路就很清晰了:一个W+1位的余数寄存器R,一个W位的被除数移位寄存器a_shift,一个W位的商寄存器Q,外加一个W位的减法器。

还有一个常被忽略的细节:什么时候把被除数的哪一位放进余数寄存器。我的做法是先把整个被除数锁存到a_shift,每个周期取它的最高位,然后整体左移。这样写非常直观,而且最后一位用完时,移位寄存器已经全部移空,不需要额外维护一个位指针。

商寄存器的更新方式也值得说一下。我用的是“商寄存器左移,新生成的商位从最低位进入”这种写法,比如Q <= {Q[W-2:0], ~borrow}。刚开始容易不理解,因为手工推导时商是从最高位开始产生的,但移位寄存器的结果恰好相反:第一次产生的商位虽然写在了最低位,但经过后续多次左移后,它会自动到达最高位,第二次的商位到达次高位,最终结果正好和期望的二进制顺序一致。这个顺序问题我犯过不止一次,索性在这里记一笔,省得以后再看代码发呆。

3. Verilog落地实现:一个参数化的可综合模块

3.1 模块端口与时序约定

我实现的模块叫divu,主打无符号除法,位宽通过parameter W参数化。对外接口采用最朴素的握手形式:start高电平启动,计算完成后done输出一个高电平脉冲,quotient和remainder在done有效的同一个周期内更新。

这种握手方式虽然不是当前最流行的 valid/ready 流控,但非常好理解,也特别适合小模块内部使用。如果后续要接入流水线,再把它改成 AXI-Stream 风格也很容易。端口列表如下:

  • clk/rst_n:时钟与异步复位。
  • start:启动信号,高有效。在空闲状态下拉起start,模块会锁存被除数和除数。
  • dividend:被除数a,W位。
  • divisor:除数b,W位。
  • quotient:商q,W位。
  • remainder:余数r,W位。
  • done:完成脉冲,高电平持续一个时钟周期。

整个模块共需要W个计算周期,再加上启动锁存和输出锁存,总共W + 2个周期输出有效结果。对于 8 位除法来说,就是 10 个时钟周期出一次结果。

3.2 关键代码:状态机、移位、试减

下面这段代码就是完整的 8/16/32 位通用无符号除法器核心部分,我用W参数做成了可配置宽度。

module divu #( parameter W = 8 ) ( input wire clk, input wire rst_n, input wire start, input wire [W-1:0] dividend, input wire [W-1:0] divisor, output reg [W-1:0] quotient, output reg [W-1:0] remainder, output reg done ); localparam IDLE = 2'b00; localparam COMP = 2'b01; localparam FINISH = 2'b10; reg [1:0] state; reg [W-1:0] a_shift; reg [W-1:0] b_reg; reg [W:0] R; reg [W-1:0] Q; reg [$clog2(W+1)-1:0] cnt; wire [W:0] shiftedR = {R[W-1:0], a_shift[W-1]}; wire [W:0] diff = shiftedR - {1'b0, b_reg}; wire borrow = diff[W]; always @(posedge clk or negedge rst_n) begin if (!rst_n) begin state <= IDLE; done <= 1'b0; quotient <= {W{1'b0}}; remainder <= {W{1'b0}}; end else begin case (state) IDLE: begin done <= 1'b0; if (start) begin a_shift <= dividend; b_reg <= divisor; R <= {W+1{1'b0}}; Q <= {W{1'b0}}; cnt <= W; state <= COMP; end end COMP: begin if (cnt == 1) begin // 最后一次迭代,不需要再移位被除数 R <= borrow ? shiftedR : diff; Q <= {Q[W-2:0], ~borrow}; state <= FINISH; end else begin R <= borrow ? shiftedR : diff; Q <= {Q[W-2:0], ~borrow}; a_shift <= a_shift << 1; cnt <= cnt - 1'b1; end end FINISH: begin done <= 1'b1; quotient <= Q; remainder <= R[W-1:0]; state <= IDLE; end endcase end end endmodule

这段代码里最值得注意的就是shiftedR和diff这两个 wire。shiftedR先把余数寄存器的低W位左移一位,再把被除数的当前最高位补到最低位;diff用W+1位宽度做减法,最高位diff[W]就是借位标志。

当借位为 1 时,select 结果返回shiftedR,等于“撤销”了这次减法;当借位为 0 时,返回diff,余数更新为试减成功的值。这样就把传统恢复余数法两拍才能完成的操作压缩到了一拍,综合出来的面积也更小。

3.3 可综合写法里的几个坑

这段代码踩过的坑有两个,一个和位宽有关,一个和状态机有关。

位宽是最容易翻车的地方。shiftedR、diff、R三者宽度不一致,综合工具要么报警,要么直接扩展位宽,表面上能用,但波形里会出现 X 态。我的原则是:涉及到余数和减法的中间变量,一律显式写成W+1位,不要依赖综合工具自动补零。

状态机的坑在于done信号的产生时机。如果在COMP状态的最后一拍直接让done为 1,那quotient和remainder还停留在旧值,外部模块一拍到done就取数据,容易取到上一轮的旧结果。所以我在COMP完成后先进入FINISH状态,到这个状态的上升沿统一锁存Q和R[W-1:0]到输出端口,同时拉起done。下一拍回到IDLE,done又被拉低,正好形成一个单周期脉冲。

还有一个容易被忽略的细节:cnt的宽度不能拍脑袋写成$clog2(W),因为当W=8时,初始值 8 需要 4 位才能表示,$clog2(8)只有 3 位,存 8 会溢出。正确写法是$clog2(W+1)。

4. 仿真验证:从正确波形到边界用例的完整套路

4.1 测试平台的握手脉冲设计

写测试平台时,最容易犯的错误是把start拉高以后立刻送数据、立刻等待结果,而忘记start至少要保持一个时钟周期,且被除数和除数必须提前稳定。

我的测试平台一般是自己封装一个run_case任务,先在时钟上升沿之前准备好数据,然后拉高start一个周期,再用wait(done)等待完成脉冲。这样写的好处是把“驱动信号”和“检测结果”分离,后面增加用例时只需要追加一行调用,不用重复拷贝时序逻辑。

一个典型测试平台的骨架大概是这样的:

module tb_divu; reg clk = 0; reg rst_n = 0; reg start = 0; reg [7:0] A, B; wire [7:0] q, r; wire done; integer error_cnt = 0; divu #(.W(8)) u_dut ( .clk (clk), .rst_n (rst_n), .start (start), .dividend (A), .divisor (B), .quotient (q), .remainder(r), .done (done) ); always #5 clk = ~clk; initial begin rst_n = 0; #20 rst_n = 1; run_case(8'd100, 8'd7, 8'd14, 8'd2); run_case(8'd255, 8'd15, 8'd17, 8'd0); run_case(8'd0, 8'd9, 8'd0, 8'd0); run_case(8'd255, 8'd1, 8'd255, 8'd0); run_case(8'd128, 8'd2, 8'd64, 8'd0); if (error_cnt == 0) $display("ALL TESTS PASSED"); else $display("FAIL: %0d errors", error_cnt); $finish; end task run_case( input [7:0] a_in, input [7:0] b_in, input [7:0] exp_q, input [7:0] exp_r ); begin @(posedge clk); A <= a_in; B <= b_in; start <= 1'b1; @(posedge clk); start <= 1'b0; wait(done == 1'b1); if (q !== exp_q || r !== exp_r) begin error_cnt = error_cnt + 1; $display("FAIL: a=%0d b=%0d q=%0d/%0d r=%0d/%0d", a_in, b_in, q, exp_q, r, exp_r); end end endtask endmodule

4.2 测试用例与期望值对照

测试用例不能只挑几个“看起来正常”的数,至少要把下面这几类覆盖进去。

用例期望商期望余数设计意图
100 / 7142普通组合,商余数都非零
255 / 15170被除数和除数都是最大值附近
0 / 900被除数为零
255 / 12550除数最小,商可能最大
128 / 2640商为 2 的幂,验证移位协作
200 / 3662随机组合,防止只测到某种巧合

这些用例里,最容易出问题的是 255 / 1。因为商会写到最高位全 1,如果商寄存器位宽设计有问题,或者移位顺序搞反了,波形里会出现明显错误。我的经验是,先把这类“极端但合法”的用例跑通,再回过头做随机回归,这样定位问题会快很多。

另外,不要把除零测试当作正常用例来加。无符号除法的数学定义里,除零是没有意义的。这个模块在除零时会行为异常:余数寄存器一直因为减法失败而保留原值,最终余数等于被除数,商则为 0。这不属于错误,但也谈不上正确结果。实际工程里应该在模块外部或者内部增加除零判断,最好提前在状态机里加一个异常通道,或者干脆模块外部拦截divisor == 0的输入。

4.3 随机向量回归与除零处理

只靠人工列出的几条用例,很难把迭代过程的每一个分支都覆盖到。我习惯再补一段随机回归:生成多组无符号随机数,用系统函数$random产生a和b,同时在一段阻塞代码里直接用 Verilog 的暂存变量计算期望值。

仿真代码可以这样写:

for (int i = 0; i < 1000; i++) begin A = $random % 256; B = ($random % 255) + 1; // 避免除零 @(posedge clk); start = 1; @(posedge clk); start = 0; wait(done == 1); if (q !== A / B || r !== A % B) error_cnt++; end

用A / B和A % B作为参考模型,看起来有点“用 Verilog 验证 Verilog”的味道,但对于纯组合逻辑这种简单参考模型,完全够用。随机向量的意义在于:人工用例总能照顾到常见的边界,而随机向量能抓到那些你以为没问题、实际上移位次序差一位的隐蔽 bug。

除零的问题,在随机回归里我用ba + 1来刻意避开,因为这是一个“未定义输入”。工程上我更推荐在模块内部加一个input_is_zero输出,或者用busy信号把除零状态锁定住,不要让异常结果一路跑到下游模块里去。

5. 回到工程:时钟数、面积与替代方案

5.1 恢复法的延迟细账

把上面 8 位除法器放进综合工具后,资源消耗通常非常低:一个减法器、一组寄存器、几个多路选择器,LUT 占用大概只有几十个,这对很多资源紧张的 FPGA 项目来说很香。但代价就是延迟固定为W + 2个时钟周期。

这个延迟在很多算法加速场景里是不能接受的。比如你要对一长串定点数做连续除法,每个结果之间只隔一个周期,那这个串行恢复余数法就完全不够用,因为第一笔除法还没完成,第二笔数据已经到了。

所以我的建议是:不要一上来就默认选择某个除法结构,先看数据流节奏。如果除法是偶发事件,恢复余数法最合适;如果是连续流水,就得上流水线或并行实例化方案。

5.2 流水线化与连续除法的选择

要让除法器支持连续输入,最直接的办法是开多个计算单元,把不同数据的计算过程重叠起来。比如 8 位除法需要 8 个计算周期,那我就可以摆 8 个独立计算单元,每个周期接收一个新的被除数,延迟仍然接近 8 拍,但吞吐率变成了每周期一个结果。

代价是面积直接乘以 8,资源紧张时不一定付得起。另一种思路是给单个迭代单元插入流水寄存器,把每个时钟周期内的组合路径切短,这种做法吞吐率不会提升,但最高工作频率会上去,适合时钟已经很紧张的项目。

如果你不介意付出一些逻辑资源,还可以把除法器做成组合逻辑的“单拍版本”,用面积换吞吐。8 位以下的除法器用组合展开问题不大,16 位以上就要非常小心时序了。

5.3 非恢复余数法和2的幂特判

恢复余数法虽然好懂,但工业上更常见的还有非恢复余数法。它的核心区别是:试减失败时,不需要把余数恢复回去,而是保留负数余数,下一轮改做加法。这样做的好处是每个周期仍然是固定一次加法或减法,但省掉了恢复操作的额外周期,流水线实现起来更整齐。

非恢复余数法在实现上比恢复法稍微绕一点,因为余数可能是负数,位权处理要额外谨慎。但对于 16 位、32 位宽的场景,它能明显比恢复法更高效,也更容易被工具优化成高速流水的结构。

还有一个经常被忽略的捷径:除数是 2 的幂时,除法本质上就是右移。所以在除法器入口加一个判断,如果除数刚好是1 << k,直接输出dividend >> k,余数就是低k位。这个优化对特定应用非常有效,比如图像处理里常见的除以 16、除以 64,等于白送一个时钟周期和一堆门电路。

无论是恢复余数法还是非恢复余数法,最关键的工程原则都是同一句话:先看数据流,再选架构。延迟、面积、吞吐率这三者不可能同时完美,你得知道自己的系统最缺什么。

我自己的体会是,手写除法器最大的收获不在那几行 Verilog 代码,而在你真正理解了“把一个算法变成硬件状态机”的思考过程。回头再看综合工具生成的除法 IP 配置界面,那些延迟选项、吞吐率选项和面积选项,你会第一次觉得它们不再是黑盒里蹦出来的参数,而是能算清楚、能推明白的账。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询