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

1. 从手算到硬件为什么除法器这么“难搞”很多刚接触数字电路设计的朋友可能会觉得除法器和加法器、乘法器差不多不就是个运算嘛用Verilog写个“/”操作符不就完事了我刚开始也是这么想的直到第一次在FPGA上跑一个包含除法的项目时序报告一片飘红资源占用高得吓人我才意识到事情没那么简单。计算机或者说我们的FPGA做加减乘可以很“豪横”直接调用底层DSP单元或者构建并行结构但一到除法往往就得“精打细算”采用迭代的方式一步步来。这背后的原因得从除法的本质说起。你可以把除法想象成一种“试探性”的减法。比如你算13除以4你的大脑会快速估算4的3倍是12小于134倍是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次。将{Remainder Dividend}整体左移1位。现在Remainder是0001Dividend是1000Quotient左移后低位空出。用当前的Remainder去减Divisor0101得到一个试探结果Trial_Rem Remainder - Divisor。关键判断来了如果Trial_Rem 0即没有发生借位或者Trial_Rem的最高位不是1说明够减。那么我们就把Remainder更新为这个Trial_Rem0001 - 0101为负显然不够。等等这里不够所以进入另一个分支。因为Trial_Rem 0说明这一步“踩深了”。那么商Quotient的新低位就上0。并且余数需要“恢复”到减之前的状态也就是保持Remainder为0001不变。进入下一次循环。左移后{Remainder Dividend}变成0011_0000。Remainder现在是00113减Divisor5还是负。所以商上0余数恢复为0011。再左移{Remainder Dividend}为0110_0000。Remainder6减5等于1终于够减了所以商上1Remainder更新为10001。最后一次左移{Remainder Dividend}为0010_0000。Remainder2减5不够商上0余数恢复为2。循环结束。最终Quotient里存的就是商0010十进制2Remainder里存的就是余数0010十进制2。12除以5商2余2完全正确。看明白这个过程Verilog代码就呼之欲出了。它的核心就是一个状态机或者一个计数器控制的循环// 恢复余数法核心迭代部分伪代码 always (posedge clk) begin if (start) begin // 初始化被除数左移余数寄存器清零或装入被除数高位 Rem {WIDTH{1b0}}; Div_temp Divisor (WIDTH-1); // 除数左移对齐 Quotient {WIDTH{1b0}}; 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], 1b1}; // 商上1 end else begin // Rem 保持不变即恢复 Quotient {Quotient[WIDTH-2:0], 1b0}; // 商上0 end // 4. 除数右移一位为下一次比较做准备 Div_temp Div_temp 1; cnt cnt 1; end else if (cnt WIDTH) begin // 计算完成输出结果 valid 1b1; state IDLE; end end这段代码虽然简化了但骨架已经在了。你可以清晰地看到那个“试探-比较-恢复”的循环。实测下来对于一个N位的除法恢复余数法需要大约N个时钟周期来完成但最坏情况下几乎每一步都不够减因为每次不够减都要“恢复”实际的有效操作周期利用率并不高。这就是它的性能瓶颈。3. 非恢复余数法一次“踩坑”也不浪费的智慧既然恢复余数法的痛点在于“恢复”这个多余动作那有没有办法不恢复呢非恢复余数法也叫不恢复余数法给出了一个非常巧妙的答案。它的核心思想是如果这一步试探减法得到的是负数不够减我们不仅不恢复它反而在下一步操作中把它“利用”起来。怎么利用规则变了如果当前余数Rem 0那么商上1下一步计算Rem (Rem 1) - Divisor。如果当前余数Rem 0那么商上0下一步计算Rem (Rem 1) Divisor。注意这里比较的对象是上一步运算后的余数而不是试探性减法的结果。它取消了单独的“试探-恢复”步骤把判断和下一步的操作合并了。我举个例子还是算12除以5我们用非恢复余数法走一遍你会发现它的精妙之处。初始化Rem 0Divisor 5(0101)被除数Dividend 12(1100)我们先装入高位。第一步Rem 0 大于等于0。商上1。计算新余数Rem (0 1) - 5 -5。注意这里直接得到了一个负的余数-5。第二步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的符号位决定Rem0则商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], 1b1}; end else begin // 余数为负商上0下一步做加法 {Rem, Dvd_temp} {Rem, Dvd_temp} 1; Rem (Rem 1) Div_temp; Quotient {Quotient[WIDTH-2:0], 1b0}; end cnt cnt 1; end else if (cnt WIDTH) begin // 迭代结束处理最终余数恢复 if (Rem 0) begin Rem Rem Div_temp; // 恢复正余数 // 商可能需要调整这里简化处理 end valid 1b1; 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; // 余数寄存器宽度为WIDTH1用于存储符号位 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 1b0; rem_r 0; dvd_r 0; div_r 0; quotient 0; valid 1b0; cnt 0; end else begin if (start !calc_en) begin // 初始化阶段 calc_en 1b1; rem_r 0; dvd_r dividend; div_r divisor; quotient 0; cnt 0; valid 1b0; 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, 1b0}; // 新余数 (旧余数左移后的高WIDTH1位) - 除数 // 注意rem_r此时已经左移其高WIDTH1位就是新的被减数 rem_r {rem_r[WIDTH-1:0], dvd_r[WIDTH-1]} - {1b0, div_r}; quotient {quotient[WIDTH-2:0], 1b1}; // 商上1 end else begin // 余数为负 (MSB为1) {rem_r, dvd_r} {rem_r[WIDTH-1:0], dvd_r, 1b0}; rem_r {rem_r[WIDTH-1:0], dvd_r[WIDTH-1]} {1b0, div_r}; quotient {quotient[WIDTH-2:0], 1b0}; // 商上0 end cnt cnt 1; end else begin // 迭代结束处理最终余数 calc_en 1b0; if (rem_r[WIDTH]) begin // 如果最终余数为负 remainder rem_r[WIDTH-1:0] div_r; // 恢复余数 // 商需要修正这里简化实际可能需要根据算法微调 end else begin remainder rem_r[WIDTH-1:0]; end valid 1b1; end end else begin valid 1b0; end end end endmodule性能与资源对比我们可以从几个维度来对比这两种用Verilog实现的算法特性维度恢复余数法非恢复余数法核心操作比较 - 条件减法 - 可能恢复条件加法/减法无恢复单周期操作数1次比较1次减法可能1次加法恢复1次加法或1次减法总时钟周期N位N最坏到 2N理论上界稳定的 N1含最后恢复关键路径比较器 减法器 多路选择器加法器/减法器 多路选择器FPGA资源占用通常需要更多的控制逻辑和MUX控制逻辑更规整易于优化代码可读性更直观易于理解和调试需要理解“负余数”概念稍绕优化潜力较低恢复操作是固有开销高极易流水线化从表格可以清晰看出非恢复余数法在性能和优化潜力上具有明显优势。尤其是在FPGA上我们可以利用其规整的迭代结构将其展开成多级流水线。深度优化技巧流水线化非恢复余数法非恢复余数法的每一步迭代几乎完全相同只是输入依赖于上一步的余数符号。这正是流水线的绝佳应用场景。我们可以把N次迭代展开成N级流水线。// 流水线级1 stage1_rem (rem_i 0) ? ((rem_i 1) - divisor) : ((rem_i 1) divisor); stage1_quotient_bit (rem_i 0) ? 1b1 : 1b0; // 将 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或者直接在迭代算法中理解小数点的位置——本质上算法完全通用只是你解释结果的方式不同。我在实际项目中处理传感器数据转换时就经常用到定点数除法关键是要想清楚你的数据范围和精度需求然后在初始化时做好位宽的扩展和移位对齐避免计算过程中溢出或精度丢失。