FPGA二进制除法器设计：从算法原理到Verilog实现与优化

1. 项目概述：在FPGA中实现二进制除法

在数字电路设计领域，尤其是在现场可编程门阵列（FPGA）中实现数学运算，除法器一直是一个颇具挑战性的课题。与加法、减法乃至乘法相比，除法运算在硬件实现上要复杂得多，它涉及到迭代、比较、移位和状态控制，稍有不慎就会在资源消耗、运算速度和精度之间失衡。我之前在专栏中断言要结束关于二进制数学的讨论，但回头一想，如果缺少了对二进制除法，特别是定点数除法的深入探讨，这个系列就像缺了最后一块拼图，不够完整。所以，我决定食言一次，专门用这篇长文来聊聊如何在FPGA里“驯服”除法运算。

这篇文章的核心，是拆解二进制除法的硬件实现原理，并提供一个清晰、可复现的设计路径。我们将从最基础的“长除法”算法讲起，这是理解一切除法器设计的基石。然后，我们会直面将算法映射到硬件时遇到的核心难题：如何高效地对齐操作数？如何管理中间状态？如何处理余数和精度？最后，我会分享几种主流的硬件除法器架构，包括恢复余数法、不恢复余数法（SRT算法），并简要探讨更高级的迭代方法（如牛顿-拉弗森法）的应用场景与权衡。无论你是正在学习数字逻辑的学生，还是需要在实际项目中实现除法功能的工程师，这篇文章都将提供从理论到实践的完整视角，并附上我踩过的一些坑和总结出的实用技巧。

2. 二进制除法基础与硬件化挑战

2.1 重温“长除法”：从十进制到二进制的思维转换

我们首先回归到小学课堂，用十进制长除法来计算136除以3。这个过程看似简单，却蕴含了除法算法的所有核心步骤：对齐、试商、乘减、移位。我们将被除数136写在里面，除数3写在外面。从被除数的最高位开始，我们问：3能除1几次？答案是0次。于是，我们“拉下”下一位，形成13，再问：3能除13几次？答案是4次。我们将商4写在对应的位上，然后用3乘以4得到12，从13中减去12得到1。接着，再拉下最后一位6，形成16，继续这个过程，得到商5，余数为1。

现在，让我们把这两个数转换成二进制。136的二进制是10001000，3的二进制是11。二进制长除法的过程在逻辑上与十进制完全一致，但由于二进制每一位只有0或1两种状态，试商的过程被极大地简化了。我们不再需要“猜测”商是几，只需要做一个简单的比较：当前的部分余数是否大于或等于除数？如果是，商位就是1，并执行减法；如果不是，商位就是0。然后，将除数右移一位（相当于除以2），与新的部分余数继续比较。

这个二进制流程可以提炼为以下几步：

1. 对齐：将除数的最高有效位与被除数的最高有效位对齐。
2. 初始化：将所有商位预设为0。
3. 比较与减：如果当前对齐下的被除数（或部分余数）大于等于除数，则将对应位置的商位置1，并从被除数中减去除数。
4. 移位：将除数右移一位。
5. 循环：重复步骤3和4，直到除数被移到最低位或我们得到了足够多的商位。
6. 结束：最后的被除数（或部分余数）就是余数。

注意：这里的“对齐”在硬件实现中是一个关键且耗资源的操作。在软件或心算中，我们一眼就能看出最高位在哪，但在硬件里，我们需要通过电路来检测和移动。

2.2 硬件实现的核心矛盾与设计考量

将上述算法直接翻译成硬件，我们会立刻撞上几堵墙。这些矛盾点正是设计高效除法器的关键所在。

2.2.1 操作数对齐：速度与面积的权衡

算法要求“对齐最高有效位”。在硬件中，如何找到这个“最高有效位”？最直接的方法是使用一个桶形移位器，将除数左移，直到它的最高位与被除数的最高位对齐。但这需要多个时钟周期（对于N位数，最多需要N个周期来逐位试探对齐），速度慢。另一种方法是使用一个巨大的多路选择器（MUX）树，根据前导零检测器的结果，在一个周期内完成对齐。这种方法速度快，但消耗的查找表（LUT）和布线资源会随着位宽呈指数级增长，面积大。

在实际FPGA设计中，这通常是一个权衡。对于速度要求不高的应用，可以采用多周期移位对齐。对于高性能计算单元，可能会采用基于前导零计数器和多路选择器的组合逻辑路径，在一个周期内完成，但这会显著增加关键路径的延迟和资源占用。我的经验是，在FPGA中，除非位宽很小（比如小于16位），否则纯组合逻辑对齐的成本往往过高，多周期方案更为常见。

2.2.2 商位生成与精度控制

二进制除法中，商位非0即1，这简化了逻辑。但我们需要一个寄存器来逐位收集这些商位。通常的做法是，在每次比较-减法循环后，将生成的商位（0或1）移位存入一个商寄存器。这里的一个细节是，商寄存器的初始化宽度需要与期望的商位宽一致，包括可能的整数和小数部分。

对于定点数除法，我们还需要明确结果的表示格式。例如，进行Q8.8格式（8位整数，8位小数）的除法，我们需要预先确定输出是保持Q8.8格式，还是会产生溢出？通常，为了保留精度，我们可能会进行被除数的扩展。例如，计算A/B（均为Q8.8），一个常见的技巧是将被除数A左移N位（N为期望的小数位数），然后进行整数除法，得到的结果就包含了小数部分。这本质上是在硬件中模拟了“拉下”更多位（包括虚拟的小数点后的0）的过程。

2.2.3 余数处理与舍入

除法运算结束后，我们得到一个商和一个余数。在整数除法中，余数可能直接被丢弃或用于模运算。在定点数或需要更高精度的场合，余数至关重要。我们可以选择：

• 截断：直接丢弃余数，这是最简单但精度最低的方法。
• 舍入：根据余数的大小决定是否对商进行加1。例如，如果余数大于或等于除数的一半，则商加1。这需要在硬件中增加一个比较器和一个加法器。
• 保留余数：将余数作为输出的一部分，用于后续计算。

在FPGA中实现舍入，会增加额外的逻辑和潜在的关键路径。是否值得，完全取决于应用对精度的要求。在许多信号处理或控制应用中，简单的截断可能就足够了，而在金融或高精度科学计算中，舍入则是必须的。

3. 主流硬件除法器架构详解

理解了基础挑战后，我们来看几种具体的硬件实现架构。它们都是在“比较-减法-移位”这个核心循环上的不同变体，旨在优化速度、面积或两者。

3.1 恢复余数除法器

这是最直观、最接近我们手算长除法的方法。其基本单元是一个减法器、一个比较器（或利用减法器的符号位）和几个寄存器。操作流程如下：

1. 初始化：将被除数加载到余数寄存器，除数加载到除数寄存器，商寄存器清零。将除数左移，使其最高位与被除数最高位对齐（或在循环中动态移位）。
2. 循环（对于每一位商）： a.试探减法：用当前余数减去除数。 b.判断：如果结果为正或零（即余数≥除数），则商位置1，并将减法结果更新为新的余数。 c.恢复：如果结果为负（即余数<除数），则商位置0，并且恢复原来的余数（即不做更新，或者将减法的结果再加回除数，恢复原值）。 d.移位：将除数右移一位，为下一位计算做准备。同时，将商寄存器左移一位，为接收下一位商腾出位置。

设计要点与坑点：

• 恢复操作是性能瓶颈：每次试探减法后，如果结果为负，需要一次加法操作来恢复余数。这增加了一个时钟周期（如果在一个周期内完成判断和恢复，则增加了组合逻辑延迟）和额外的硬件（加法器）。
• 资源利用：需要一套完整的加减法器。现代FPGA通常有专用的DSP Slice，里面包含预加器和乘法器，可以高效地实现加减法，但需要合理配置。
• 我的实操心得：在早期项目中使用恢复余数法时，我试图在一个状态机周期内完成“减-判断-恢复/更新”全套操作，导致关键路径过长，时序难以收敛。后来将其拆分为两个时钟周期（一个周期做减法并判断，下一个周期根据判断结果选择更新余数或恢复），虽然吞吐量减半，但时序变得非常稳健，在100MHz时钟下轻松实现。对于FPGA设计，有时用 latency（延迟）换 timing（时序）是值得的。

3.2 不恢复余数除法器

不恢复余数除法器，也称为SRT除法器（以Sweeney， Robertson和Tocher的名字命名），是对恢复余数法的重大改进。它的核心思想是：既然我们总是要移位除数，那么当余数为负时，我们何不将负的余数保留下来，然后在下一步中，加上移位后的除数（而不是减去）？

算法流程如下：

1. 初始化同恢复余数法。
2. 循环（对于每一位商）： a.根据余数符号判断： * 如果当前余数 ≥ 0，商位置1，下一步计算：新余数 = 2 * (旧余数 - 除数)。 * 如果当前余数 < 0，商位置0（或-1，在某种编码下），下一步计算：新余数 = 2 * (旧余数 + 除数)。 b. 左移余数寄存器（相当于乘以2），然后加上或减去除数（根据上一步的商位决定）。

优势分析：

• 消除了恢复操作：无论余数是正是负，都进行统一的“移位后加/减”操作，流程规整，控制逻辑简单。
• 更高的潜在速度：因为步骤固定，没有条件分支导致的流水线停顿，更容易实现高时钟频率或进行流水线化。
• 商位编码：标准的SRT算法可以使用{-1, 0, 1}的商位集，这允许在某些情况下一次迭代产生多位商，进一步加速运算，但这会显著增加查找表的复杂度。

实现注意事项：

• 余数寄存器需要有符号表示能力（通常用二进制补码）。
• 初始对齐和最终商的计算（将{-1, 0, 1}的商位序列转换为标准二进制）需要额外的逻辑。
• 对于FPGA，不恢复余数法的规整性使得它非常适合于用流水线实现。你可以将每一位商的生成拆分成一个流水线级，每级都做同样的“移位-加/减”操作，只是输入数据不同，从而实现每个时钟周期输出一个商位的高吞吐量设计。

3.3 基于乘法的迭代方法简介

当FPGA中集成了高性能的硬件乘法器（如DSP48单元）时，另一种强大的思路是利用乘法来逼近除法。其代表是牛顿-拉弗森迭代法。

核心思想是：计算Y = A / B，可以转化为计算Y = A * (1/B)。因此，问题转化为求除数B的倒数R = 1/B。牛顿-拉弗森法为求解方程f(x) = 1/x - B = 0提供了迭代公式：X_{n+1} = X_n * (2 - B * X_n)

操作步骤：

1. 初始估计：需要一个倒数1/B的粗略估计值X_0。这通常通过一个小型的查找表实现，根据B的最高几位比特来索引。
2. 迭代精化：使用上述公式进行迭代。每次迭代都需要两次乘法和一次减法。
3. 乘法：得到倒数的精确估计R后，最后计算Y = A * R。

优势与局限：

• 优势：收敛速度极快（二次收敛）。如果初始估计有k位精度，一次迭代后能达到约2k位精度。对于32位或64位精度，通常只需要2-3次迭代。当硬件乘法器速度快且资源充足时，这种方法的总延迟可能远低于串行的移位-减法除法器。
• 局限：
  • 依赖乘法器：没有快速乘法器的情况下，此法无优势。
  • 初始估计：需要ROM来存储倒数查找表，增加了资源消耗。
  • 定点数处理复杂：对于任意格式的定点数，需要仔细处理缩放因子，以确保迭代过程中的数据不会溢出或下溢，这增加了设计的复杂性。相比之下，整数或浮点数格式更为规整。
  • 非单调性：由于是迭代逼近，其最坏情况下的延迟是固定的，但不如基于减法的除法器那样确定（后者延迟严格由位宽决定）。

提示：在今天的许多高性能FPGA应用中，尤其是涉及浮点运算时，牛顿-拉弗森法及其变种（如Goldschmidt算法）是除法器实现的首选，因为它们能充分利用DSP硬核，达到很高的吞吐量和能效比。

4. Verilog实现示例与关键代码解析

理论说得再多，不如一段代码来得实在。这里我将展示一个简单的、基于恢复余数法的整数除法器Verilog实现，并逐段解析其中的设计要点和容易出错的地方。我们假设实现一个16位被除数除以8位除数，得到8位商和8位余数的无符号整数除法器。

module divider_restoring ( input wire clk, input wire rst_n, input wire start, // 启动信号，高电平有效 input wire [15:0] dividend, // 被除数 input wire [7:0] divisor, // 除数 output reg [7:0] quotient, // 商 output reg [7:0] remainder, // 余数 output reg done // 运算完成标志 ); // 状态机定义 localparam S_IDLE = 2'b00; localparam S_SHIFT = 2'b01; localparam S_SUB = 2'b10; localparam S_RESTORE = 2'b11; reg [1:0] state, next_state; reg [15:0] reg_rem; // 内部余数寄存器，宽度为被除数宽度 reg [7:0] reg_div; // 除数寄存器 reg [3:0] bit_cnt; // 位计数器，因为要生成8位商，所以计数0-7 // 状态机时序逻辑 always @(posedge clk or negedge rst_n) begin if (!rst_n) begin state <= S_IDLE; reg_rem <= 16'b0; reg_div <= 8'b0; quotient <= 8'b0; remainder <= 8'b0; bit_cnt <= 4'b0; done <= 1'b0; end else begin state <= next_state; case (state) S_IDLE: begin if (start) begin reg_rem <= dividend; // 加载被除数 reg_div <= divisor; // 加载除数 quotient <= 8'b0; bit_cnt <= 4'd7; // 从最高位开始，共8位 done <= 1'b0; end end S_SHIFT: begin // 将余数寄存器左移一位，为新的商位腾出空间 reg_rem <= {reg_rem[14:0], 1'b0}; end S_SUB: begin // 试探减法：当前余数的高位部分减去除数 // 注意：我们比较的是 reg_rem[15:8] 和 reg_div，因为 divisor 是8位 // 这模拟了除数与被除数高位对齐的过程 if (reg_rem[15:8] >= reg_div) begin // 够减，商位置1，更新余数高位 quotient[bit_cnt] <= 1'b1; reg_rem[15:8] <= reg_rem[15:8] - reg_div; end // 如果不够减，商位在初始化时就是0，保持即可，余数部分不变（等待后续恢复或进入下一轮） end S_RESTORE: begin // 在恢复余数法中，如果上一步不够减，理论上需要恢复余数。 // 但注意：在我们的流程中，S_SUB状态只执行减法判断和更新。 // 如果不够减，我们实际上没有修改reg_rem[15:8]（因为没执行减法）。 // 所以，这里不需要真正的“加回来”操作。这是一个常见的优化/简化。 // 更严格的做法是在S_SUB中，如果不够减，执行一次减法，然后在S_RESTORE中加回来。 // 我们这里采用“只减成功情况”的简化流程。 // 因此，S_RESTORE状态主要进行计数和状态转移判断。 if (bit_cnt == 4'b0) begin done <= 1'b1; remainder <= reg_rem[15:8]; // 最终余数是余数寄存器的高8位 end else begin bit_cnt <= bit_cnt - 1'b1; end end endcase end end // 状态机组合逻辑（下一状态逻辑） always @(*) begin next_state = state; case (state) S_IDLE: begin if (start) next_state = S_SHIFT; end S_SHIFT: begin next_state = S_SUB; end S_SUB: begin next_state = S_RESTORE; end S_RESTORE: begin if (bit_cnt == 4'b0) begin next_state = S_IDLE; end else begin next_state = S_SHIFT; end end endcase end endmodule

代码解析与关键点：

1. 状态机设计：这是时序逻辑的核心。S_SHIFT、S_SUB、S_RESTORE三个状态构成了处理一位商的循环。bit_cnt控制循环8次。
2. 对齐的隐含处理：代码中没有显式的“对齐最高位”操作。这是因为我们固定了除数为8位，被除数为16位。算法通过每次迭代将reg_rem左移一位，并总是用reg_rem的高8位（[15:8]）与整个除数reg_div比较，这隐式地实现了除数的“右移”效果。这是一种非常经典且高效的硬件实现技巧。
3. “恢复”的简化：在严格的恢复余数法中，如果试探减法结果为负，需要将减去的除数加回来以恢复原余数。在上面的代码中，我们做了一个优化：只有在够减（余数高位≥除数）时，才执行减法并更新余数寄存器；如果不够减，则根本不执行减法操作，余数寄存器保持原样。这等价于“先减，发现为负，再加回来”，但节省了一次加法操作。这是可行的，因为我们的判断（reg_rem[15:8] >= reg_div）发生在减法操作之前（通过比较器）。
4. 资源与时序：这个设计需要一个16位寄存器（reg_rem）、一个8位比较器、一个8位减法器和一个简单的状态机。它需要8个循环（每个商位一个循环）来完成一次除法。如果时钟频率为100MHz，那么完成一次除法大约需要80ns的延迟。吞吐量是每8个周期一次运算。
5. 扩展为定点数：如果要支持Qm.n格式的定点数除法，通常的做法是将被除数左移n位（扩展小数位），然后将其视为整数进行上述除法运算。得到的结果（商）就自然包含了n位小数。例如，计算Q8.8格式的A除以B，可以将A左移8位（变成16位整数），然后除以B（8位整数），得到的16位结果中，高8位是商的整数部分，低8位是商的小数部分。

5. 实战调试、优化与常见问题排查

即使有了清晰的算法和代码，在FPGA上实现除法器时仍然会遇到各种实际问题。下面是我在多个项目中总结出的经验、调试技巧和常见坑点。

5.1 功能仿真与边界条件测试

在烧录到板子之前，充分的仿真至关重要。除了常规的随机测试，必须重点测试以下边界情况：

• 除数为0：这是最危险的错误。硬件除法器没有软件中的异常抛出机制。如果除数为0，比较器可能产生全1的结果，导致后续状态混乱或产生极大的商值。必须在设计中加入除零检查。如果检测到除数为0，可以设置一个标志位，并输出一个预设的最大值或让商和余数保持为0。

  // 在IDLE状态或数据加载时检查 if (divisor == 8'b0) begin divide_by_zero <= 1'b1; quotient <= 8'hFF; // 或根据协议设定其他值 // 跳过计算，直接进入完成状态 end

• 被除数小于除数：商应为0，余数等于被除数。确保你的算法在这种情况下能正确工作，商寄存器全部为0，余数寄存器正确保留被除数。
• 被除数等于除数：商应为1，余数为0。
• 被除数远大于除数：确保商不会溢出。在我们的例子中，16位被除数除以8位除数，最大商是255（8‘hFF），这正好是8位能表示的最大值。如果被除数更大，比如用16位除以4位，商可能需要更多位宽。设计时必须根据输入范围确定输出位宽，防止溢出。
• 负数（如果支持）：如果设计有符号除法，需要额外测试正负组合，并确保商的符号处理和余数的定义（总是与被除数同号或总是为正）符合你的系统要求。

5.2 时序收敛与性能优化

除法器通常位于关键数据路径上，其时序性能直接影响系统频率。

• 关键路径分析：在恢复余数法示例中，关键路径很可能在S_SUB状态。这条路径包括：从reg_rem[15:8]到比较器，比较器输出控制商位写入和选择减法器操作，减法器结果写回reg_rem[15:8]。如果位宽增加，比较器和减法器的延迟会显著增长。
• 流水线化：这是提高吞吐量的最有效方法。可以将每一位商的生成流程拆解成多级流水线。例如，将“移位”、“比较”、“减法/恢复”分别放在不同的流水线级中。这样，虽然完成第一次除法结果的延迟（Latency）增加了，但系统可以每个时钟周期都开始一次新的除法运算（吞吐量提高）。对于不恢复余数法，由于其步骤规整，流水线化更加自然。
• 使用FPGA专用资源：对于比较和减法操作，如果位宽较大，可以尝试使用FPGA的DSP Slice。虽然DSP主要针对乘法优化，但其内部的预加器、模式检测器和快速进位链也可以用于加速宽位加减法和比较。需要查阅厂商手册（如Xilinx的UG579或Intel的文献）来了解如何有效映射。
• 寄存器平衡：在关键路径中间插入寄存器（流水线寄存器），可以打破长组合逻辑链，提高时钟频率。这需要修改状态机，将原本一个状态内完成的操作拆分到两个或多个时钟周期内完成。

5.3 资源利用与面积优化

对于资源受限的FPGA，需要优化除法器面积。

• 选择合适算法：恢复余数法最简单，但迭代次数多。不恢复余数法逻辑稍复杂，但迭代流程规整。对于非常小的位宽（如小于8位），恢复余数法可能面积更小。对于中等位宽，需要综合评估。
• 位宽裁剪：仔细分析实际应用所需的数据范围。如果被除数和除数的有效位宽远小于寄存器位宽，可以考虑动态检测前导零，只对有效部分进行计算，这能减少迭代次数和逻辑规模。
• 共享硬件：如果系统中有多个需要除法但不同时使用的模块，可以考虑时分复用同一个除法器硬件单元，通过一个仲裁器来调度请求。这能显著节省资源，但会增加访问延迟和设计复杂性。
• 查找表与迭代结合：对于精度要求不极高的场合，可以考虑使用小容量的查找表（LUT）来提供除数的近似倒数，然后结合一次牛顿-拉弗森迭代来获得可接受的结果。这比纯迭代法需要的ROM小，比串行减法法速度快。

5.4 常见问题速查表

问题现象	可能原因	排查思路与解决方案
商的结果完全错误（如全0或全1）	状态机未正确启动或卡在某个状态；除数为0未处理。	1. 仿真查看start信号、状态机state和bit_cnt的变化。 2. 检查除零检测逻辑及其对状态机的影响。 3. 确认复位后所有寄存器处于已知状态。
商的结果比预期小1	比较或减法逻辑有误，可能在边界条件下（如相等时）判断出错。	1. 重点测试“被除数等于除数”的情况。 2. 检查比较运算符（>=还是>），确保包含等于的情况。 3. 查看减法器是否因为溢出处理导致错误。
余数不正确	余数更新逻辑错误；移位操作覆盖了错误的数据。	1. 仿真时追踪reg_rem寄存器在每次S_SUB和S_SHIFT后的值。 2. 确认在“不够减”时，余数寄存器是否正确保持原值（未执行减法）。 3. 检查最终余数赋值是否正确（是取reg_rem的全部还是高部分）。
时序报告显示建立时间违例	组合逻辑路径过长（关键路径在比较器、减法器、多路选择器链路上）。	1. 查看时序报告，定位关键路径的具体模块和信号。 2. 考虑插入流水线寄存器，将关键路径打断。 3. 使用寄存器输出（output reg）而不是组合逻辑输出。 4. 如果使用DSP，确保其配置已优化时序。
资源使用率异常高	算法选择不当；位宽过大；存在未优化的冗余逻辑。	1. 综合后查看资源报告，哪个模块（比较器、减法器、多路选择器）消耗最多。 2. 考虑使用更节省资源的算法（如对于小位宽，恢复余数法可能更优）。 3. 检查代码中是否有可以被共享的公共子表达式。
在高速时钟下结果不稳定	关键路径存在亚稳态；时钟偏移严重。	1. 降低时钟频率测试，如果问题消失，则是时序问题。 2. 加强时序约束，特别是输入数据到寄存器的路径。 3. 对start、dividend、divisor等异步输入信号进行同步处理（打两拍）。

最后，分享一个我个人的深刻体会：在FPGA中设计数学运算单元，没有“最好”的方案，只有“最合适”的方案。你需要根据项目的具体约束（时钟频率、吞吐量、延迟、资源面积、精度）来做出选择。一个在高速数据中心卡上表现优异的基于牛顿-拉弗森法的浮点除法器，如果放到一个低功耗的传感器节点MCU的软核里，将是灾难性的。理解每种算法的本质、开销和适用场景，比单纯追求性能指标更重要。对于大多数嵌入式场景，一个经过精心优化、时序收敛的串行移位-减法除法器，往往是可靠而务实的选择。在动手写代码之前，花时间在纸上画一画数据流和状态图，把边界条件和异常处理想清楚，这能节省你大量的调试时间。