从恢复余数法到非恢复余数法：Verilog除法器的核心算法实现与优化

1. 从手算到硬件：为什么除法器这么“难搞”？

很多刚接触数字电路设计的朋友，可能会觉得除法器和加法器、乘法器差不多，不就是个运算嘛，用Verilog写个“/”操作符不就完事了？我刚开始也是这么想的，直到第一次在FPGA上跑一个包含除法的项目，时序报告一片飘红，资源占用高得吓人，我才意识到事情没那么简单。计算机，或者说我们的FPGA，做加减乘可以很“豪横”，直接调用底层DSP单元或者构建并行结构，但一到除法，往往就得“精打细算”，采用迭代的方式一步步来。

这背后的原因，得从除法的本质说起。你可以把除法想象成一种“试探性”的减法。比如你算13除以4，你的大脑会快速估算：4的3倍是12，小于13，4倍是16又太大了，所以商是3，余数是1。这个“快速估算”对人脑来说容易，但对只认识0和1的硬件来说，它没法一眼看出倍数关系。硬件最擅长的是“比较”和“移位”。所以，硬件实现除法的经典思路，就是模拟我们小学学过的“竖式除法”，只不过把十进制换成了二进制。二进制只有0和1，每一步的“试探”就变成了一个二选一的问题：当前的部分余数够不够减去除数？够，商就上1，然后做减法；不够，商就上0，然后进行下一步。

这就是恢复余数法最朴素的思想。它非常直观，完全复刻了手算过程，是理解除法器硬件实现的绝佳起点。但它的“恢复”二字，也暗示了它的效率瓶颈——如果某一步试探后发现不够减（即余数减去除数为负），那么这次减法就是无效的，需要把余数“恢复”到减之前的状态，然后再进行下一步操作。这个过程就像你走路试探一个水坑，踩下去发现很深，你得把脚收回来，换个地方再试。多出来的这个“收脚”动作，在硬件上就意味着额外的时钟周期和逻辑判断。

所以，当我们用Verilog去实现一个除法器时，面临的第一个抉择就是：是选择容易理解但稍慢的恢复余数法，还是选择需要绕点弯子但更高效的非恢复余数法？这不仅仅是选一个算法，更是对设计目标（是追求极致的吞吐量，还是优先考虑代码的可读性和验证成本？）的权衡。接下来，我就带你亲手“踩”一遍这两个算法的坑，看看它们的Verilog代码到底长什么样，以及我们怎么才能让它们跑得更快、用得更省。

2. 恢复余数法：像教小学生一样设计硬件

让我们先搞定最基础的恢复余数法。我建议你先别急着看代码，拿张纸笔，跟我一起手算一个二进制除法：1100（十进制12）除以0101（十进制5）。这个过程会让你对后续的硬件操作有肌肉记忆。

第一步：对齐。我们把被除数1100放在一个临时寄存器里，我们叫它Remainder（余数寄存器）。除数0101放在另一个寄存器Divisor里。手算时，我们会把除数右移，去和被除数的不同位对齐。在硬件里，我们通常反其道而行之：我们把被除数左移，这样能空出低位来存放商。所以，我们初始化一个Dividend（被除数）寄存器为{4‘b0， 1100}，也就是0000_1100。商寄存器Quotient初始为0。

第二步：迭代“试探-比较-恢复”。我们需要循环（被除数位数）次，这里是4次。

1. 将{Remainder， Dividend}整体左移1位。现在Remainder是0001，Dividend是1000，Quotient左移后低位空出。
2. 用当前的Remainder去减Divisor（0101），得到一个试探结果Trial_Rem = Remainder - Divisor。
3. 关键判断来了：如果Trial_Rem >= 0（即没有发生借位，或者Trial_Rem的最高位不是1），说明够减。那么，我们就把Remainder更新为这个Trial_Rem（0001 - 0101为负，显然不够）。等等，这里不够！所以进入另一个分支。
4. 因为Trial_Rem < 0，说明这一步“踩深了”。那么商Quotient的新低位就上0。并且，余数需要“恢复”到减之前的状态，也就是保持Remainder为0001不变。
5. 进入下一次循环。左移后{Remainder， Dividend}变成0011_0000。Remainder现在是0011（3），减Divisor（5）？还是负。所以商上0，余数恢复为0011。
6. 再左移，{Remainder， Dividend}为0110_0000。Remainder=6，减5等于1，终于够减了！所以，商上1，Remainder更新为1（0001）。
7. 最后一次左移，{Remainder， Dividend}为0010_0000。Remainder=2，减5不够，商上0，余数恢复为2。

循环结束。最终，Quotient里存的就是商0010（十进制2），Remainder里存的就是余数0010（十进制2）。12除以5，商2余2，完全正确。

看明白这个过程，Verilog代码就呼之欲出了。它的核心就是一个状态机或者一个计数器控制的循环：

// 恢复余数法核心迭代部分伪代码 always @(posedge clk) begin if (start) begin // 初始化：被除数左移，余数寄存器清零或装入被除数高位 Rem <= {WIDTH{1'b0}}; Div_temp <= Divisor << (WIDTH-1); // 除数左移对齐 Quotient <= {WIDTH{1'b0}}; cnt <= 0; state <= CALC; end else if (state == CALC && cnt < WIDTH) begin // 1. 余数和被除数整体左移一位 {Rem, Dividend} <= {Rem, Dividend} << 1; // 2. 试探性减法 Trial_Rem = Rem - Div_temp; // 3. 判断并恢复 if (Trial_Rem >= 0) begin Rem <= Trial_Rem; // 够减，更新余数 Quotient <= {Quotient[WIDTH-2:0], 1'b1}; // 商上1 end else begin // Rem 保持不变（即恢复） Quotient <= {Quotient[WIDTH-2:0], 1'b0}; // 商上0 end // 4. 除数右移一位（为下一次比较做准备） Div_temp <= Div_temp >> 1; cnt <= cnt + 1; end else if (cnt == WIDTH) begin // 计算完成，输出结果 valid <= 1'b1; state <= IDLE; end end

这段代码虽然简化了，但骨架已经在了。你可以清晰地看到那个“试探-比较-恢复”的循环。实测下来，对于一个N位的除法，恢复余数法需要大约N个时钟周期来完成，但最坏情况下（几乎每一步都不够减），因为每次不够减都要“恢复”，实际的有效操作周期利用率并不高。这就是它的性能瓶颈。

3. 非恢复余数法：一次“踩坑”也不浪费的智慧

既然恢复余数法的痛点在于“恢复”这个多余动作，那有没有办法不恢复呢？非恢复余数法（也叫不恢复余数法）给出了一个非常巧妙的答案。它的核心思想是：如果这一步试探减法得到的是负数（不够减），我们不仅不恢复它，反而在下一步操作中把它“利用”起来。

怎么利用？规则变了：

1. 如果当前余数Rem>= 0，那么商上1，下一步计算Rem = (Rem << 1) - Divisor。
2. 如果当前余数Rem< 0，那么商上0，下一步计算Rem = (Rem << 1) + Divisor。

注意，这里比较的对象是上一步运算后的余数，而不是试探性减法的结果。它取消了单独的“试探-恢复”步骤，把判断和下一步的操作合并了。我举个例子，还是算12除以5，我们用非恢复余数法走一遍，你会发现它的精妙之处。

初始化：Rem = 0，Divisor = 5(0101)，被除数Dividend = 12(1100)，我们先装入高位。

1. 第一步：Rem = 0， 大于等于0。商上1。计算新余数：Rem = (0 << 1) - 5 = -5。注意，这里直接得到了一个负的余数-5。
2. 第二步：Rem = -5， 小于0。商上0。计算新余数：Rem = (-5 << 1) + 5 = -10 + 5 = -5。等等，怎么还是-5？别急，我们同时要把被除数位挪进来。实际上，完整的操作是{Rem， Dividend}左移后，再加上或减去除数。为了更清晰，我们结合被除数来看一个典型的硬件迭代步骤：

在硬件实现中，我们通常维护一个{Rem， Dividend}的组合寄存器。每一步：

• 如果Rem >= 0：整体左移1位，然后Rem = Rem - Divisor。
• 如果Rem < 0：整体左移1位，然后Rem = Rem + Divisor。

商则由每一步Rem的符号位决定（Rem>=0则商1，否则商0）。这样走完N步后，我们得到的余数可能还是负数。所以最后需要一步“恢复”：如果最终余数为负，则需要加上除数，得到正确的正余数，同时商需要调整（通常是最低位减1）。不过，在很多只关心商的应用里，这最后一步甚至可以省略。

// 非恢复余数法核心迭代部分伪代码 always @(posedge clk) begin if (start) begin // 初始化，注意余数寄存器初始为0 Rem <= 0; Div_temp <= Divisor; Dvd_temp <= Dividend; // 被除数 Quotient <= 0; cnt <= 0; state <= CALC; end else if (state == CALC && cnt < WIDTH) begin // 根据当前余数的正负决定操作 if (Rem >= 0) begin // 余数为正，商上1，下一步做减法 {Rem, Dvd_temp} <= {Rem, Dvd_temp} << 1; Rem <= (Rem << 1) - Div_temp; Quotient <= {Quotient[WIDTH-2:0], 1'b1}; end else begin // 余数为负，商上0，下一步做加法 {Rem, Dvd_temp} <= {Rem, Dvd_temp} << 1; Rem <= (Rem << 1) + Div_temp; Quotient <= {Quotient[WIDTH-2:0], 1'b0}; end cnt <= cnt + 1; end else if (cnt == WIDTH) begin // 迭代结束，处理最终余数（恢复） if (Rem < 0) begin Rem <= Rem + Div_temp; // 恢复正余数 // 商可能需要调整，这里简化处理 end valid <= 1'b1; state <= IDLE; end end

非恢复余数法每一步都是“有效”操作，没有原地踏步的“恢复”动作。因此，对于一个N位的除法，它稳定地需要N个时钟周期，性能是可预测的。而且，它的操作非常规整，只有加法和减法，非常适合用流水线进行优化。

4. Verilog实现对比与深度优化实战

理解了原理，我们把两种算法用真正的Verilog RTL代码实现，并放到一起对比。我们设计一个16位无符号整数除法器，看看细节。

恢复余数法关键模块设计要点：

• 需要一个work_flag信号标志计算进行中。
• 需要一个计数器cnt控制迭代次数（0到15）。
• 初始化时，需要把除数左移（N-1）位与被除数高位对齐。
• 在迭代中，比较的是当前余数和当前除数（右移后的）。
• 输出前，需要处理商和余数的位宽与符号（本例先讨论无符号）。

非恢复余数法关键模块设计要点：

• 同样需要work_flag和计数器cnt。
• 初始化时，余数寄存器置0，除数保持原值。
• 迭代中，判断的是上一周期产生的余数的正负（符号位），来决定本周期是加还是减。
• 最后一步需要判断并可能进行余数恢复。

我直接给出一个经过仿真测试的非恢复余数法核心部分代码，并附上关键注释：

module divider_nr #( parameter WIDTH = 16 )( input wire clk, input wire rst_n, input wire start, // 启动信号 input wire [WIDTH-1:0] dividend, input wire [WIDTH-1:0] divisor, output reg [WIDTH-1:0] quotient, output reg [WIDTH-1:0] remainder, output reg valid ); reg [WIDTH:0] rem_r; // 余数寄存器，宽度为WIDTH+1，用于存储符号位 reg [WIDTH-1:0] dvd_r; // 被除数移位寄存器 reg [WIDTH-1:0] div_r; // 除数寄存器 reg [4:0] cnt; // 迭代计数器，0-15 reg calc_en; always @(posedge clk or negedge rst_n) begin if (!rst_n) begin calc_en <= 1'b0; rem_r <= 0; dvd_r <= 0; div_r <= 0; quotient <= 0; valid <= 1'b0; cnt <= 0; end else begin if (start && !calc_en) begin // 初始化阶段 calc_en <= 1'b1; rem_r <= 0; dvd_r <= dividend; div_r <= divisor; quotient <= 0; cnt <= 0; valid <= 1'b0; end else if (calc_en) begin // 迭代计算阶段 if (cnt < WIDTH) begin // 根据上一周期余数的符号决定操作 if (!rem_r[WIDTH]) begin // 余数为正 (MSB为0) // {余数， 被除数} 整体左移1位 {rem_r, dvd_r} <= {rem_r[WIDTH-1:0], dvd_r, 1'b0}; // 新余数 = (旧余数左移后的高WIDTH+1位) - 除数 // 注意：rem_r此时已经左移，其高WIDTH+1位就是新的被减数 rem_r <= {rem_r[WIDTH-1:0], dvd_r[WIDTH-1]} - {1'b0, div_r}; quotient <= {quotient[WIDTH-2:0], 1'b1}; // 商上1 end else begin // 余数为负 (MSB为1) {rem_r, dvd_r} <= {rem_r[WIDTH-1:0], dvd_r, 1'b0}; rem_r <= {rem_r[WIDTH-1:0], dvd_r[WIDTH-1]} + {1'b0, div_r}; quotient <= {quotient[WIDTH-2:0], 1'b0}; // 商上0 end cnt <= cnt + 1; end else begin // 迭代结束，处理最终余数 calc_en <= 1'b0; if (rem_r[WIDTH]) begin // 如果最终余数为负 remainder <= rem_r[WIDTH-1:0] + div_r; // 恢复余数 // 商需要修正：这里简化，实际可能需要根据算法微调 end else begin remainder <= rem_r[WIDTH-1:0]; end valid <= 1'b1; end end else begin valid <= 1'b0; end end end endmodule

性能与资源对比：

我们可以从几个维度来对比这两种用Verilog实现的算法：

从表格可以清晰看出，非恢复余数法在性能和优化潜力上具有明显优势。尤其是在FPGA上，我们可以利用其规整的迭代结构，将其展开成多级流水线。

深度优化技巧：流水线化非恢复余数法

非恢复余数法的每一步迭代几乎完全相同，只是输入依赖于上一步的余数符号。这正是流水线的绝佳应用场景。我们可以把N次迭代展开成N级流水线。

// 流水线级1 stage1_rem = (rem_i >= 0) ? ((rem_i << 1) - divisor) : ((rem_i << 1) + divisor); stage1_quotient_bit = (rem_i >= 0) ? 1'b1 : 1'b0; // 将 stage1_rem 和 stage1_quotient_bit 寄存，送入下一级 // 流水线级2 // 使用 stage1_rem 的符号位决定本级的加/减...

这样，虽然单个除法结果的延迟还是N个周期，但是吞吐量可以达到每个时钟周期输出一个结果（初始化后），极大地提升了数据吞吐能力，非常适合需要连续进行大量除法运算的场合，比如信号处理中的滤波器系数更新。

选择策略建议：

• 如果你是学生，或者项目对除法性能要求不高，且需要快速验证功能，我建议先从恢复余数法开始。它的逻辑和手算对应关系强，出错了也容易定位。网上很多教程代码也是基于这个，方便对照。
• 如果你的设计对时序要求严格，或者需要较高的吞吐率，那么非恢复余数法是更好的选择。花点时间理解它的原理，写出代码后，其稳定性和可优化性会给你带来回报。
• 如果面积（资源）极其紧张，且速度要求不高，甚至可以尝试更慢但更省资源的“循环减法”法（纯软件思维），但在FPGA中这不常见。
• 最省事但可能最“贵”的方法：直接使用FPGA厂商提供的DSP块或专用IP核（如Xilinx的divider generator）。这些IP核经过高度优化，可能采用了查表、高位宽乘法逆近似等更高级的方法（如Radix-4， SRT算法），能实现单周期或极少周期的延迟。但代价是可能占用宝贵的DSP资源，或者有固定的位宽限制。在项目初期，用IP核快速搭建原型是完全可行的。

最后，关于有符号数（补码）和小数（定点数）的处理，其核心在于预处理和后处理。对于有符号数，在计算前取绝对值转换为无符号数计算，最后根据被除数和除数的符号位异或来决定商的符号，余数的符号则与被除数相同。对于定点小数，你可以将其视为整数除以一个缩放因子（例如，Q4.12格式的数，实际是整数除以2^12），或者直接在迭代算法中理解小数点的位置——本质上，算法完全通用，只是你解释结果的方式不同。我在实际项目中处理传感器数据转换时，就经常用到定点数除法，关键是要想清楚你的数据范围和精度需求，然后在初始化时做好位宽的扩展和移位对齐，避免计算过程中溢出或精度丢失。