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的二进制是100010003的二进制是11。二进制长除法的过程在逻辑上与十进制完全一致但由于二进制每一位只有0或1两种状态试商的过程被极大地简化了。我们不再需要“猜测”商是几只需要做一个简单的比较当前的部分余数是否大于或等于除数如果是商位就是1并执行减法如果不是商位就是0。然后将除数右移一位相当于除以2与新的部分余数继续比较。这个二进制流程可以提炼为以下几步对齐将除数的最高有效位与被除数的最高有效位对齐。初始化将所有商位预设为0。比较与减如果当前对齐下的被除数或部分余数大于等于除数则将对应位置的商位置1并从被除数中减去除数。移位将除数右移一位。循环重复步骤3和4直到除数被移到最低位或我们得到了足够多的商位。结束最后的被除数或部分余数就是余数。注意这里的“对齐”在硬件实现中是一个关键且耗资源的操作。在软件或心算中我们一眼就能看出最高位在哪但在硬件里我们需要通过电路来检测和移动。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 恢复余数除法器这是最直观、最接近我们手算长除法的方法。其基本单元是一个减法器、一个比较器或利用减法器的符号位和几个寄存器。操作流程如下初始化将被除数加载到余数寄存器除数加载到除数寄存器商寄存器清零。将除数左移使其最高位与被除数最高位对齐或在循环中动态移位。循环对于每一位商 a.试探减法用当前余数减去除数。 b.判断如果结果为正或零即余数≥除数则商位置1并将减法结果更新为新的余数。 c.恢复如果结果为负即余数除数则商位置0并且恢复原来的余数即不做更新或者将减法的结果再加回除数恢复原值。 d.移位将除数右移一位为下一位计算做准备。同时将商寄存器左移一位为接收下一位商腾出位置。设计要点与坑点恢复操作是性能瓶颈每次试探减法后如果结果为负需要一次加法操作来恢复余数。这增加了一个时钟周期如果在一个周期内完成判断和恢复则增加了组合逻辑延迟和额外的硬件加法器。资源利用需要一套完整的加减法器。现代FPGA通常有专用的DSP Slice里面包含预加器和乘法器可以高效地实现加减法但需要合理配置。我的实操心得在早期项目中使用恢复余数法时我试图在一个状态机周期内完成“减-判断-恢复/更新”全套操作导致关键路径过长时序难以收敛。后来将其拆分为两个时钟周期一个周期做减法并判断下一个周期根据判断结果选择更新余数或恢复虽然吞吐量减半但时序变得非常稳健在100MHz时钟下轻松实现。对于FPGA设计有时用 latency延迟换 timing时序是值得的。3.2 不恢复余数除法器不恢复余数除法器也称为SRT除法器以Sweeney Robertson和Tocher的名字命名是对恢复余数法的重大改进。它的核心思想是既然我们总是要移位除数那么当余数为负时我们何不将负的余数保留下来然后在下一步中加上移位后的除数而不是减去算法流程如下初始化同恢复余数法。循环对于每一位商 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_{n1} X_n * (2 - B * X_n)操作步骤初始估计需要一个倒数1/B的粗略估计值X_0。这通常通过一个小型的查找表实现根据B的最高几位比特来索引。迭代精化使用上述公式进行迭代。每次迭代都需要两次乘法和一次减法。乘法得到倒数的精确估计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 2b00; localparam S_SHIFT 2b01; localparam S_SUB 2b10; localparam S_RESTORE 2b11; 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 16b0; reg_div 8b0; quotient 8b0; remainder 8b0; bit_cnt 4b0; done 1b0; end else begin state next_state; case (state) S_IDLE: begin if (start) begin reg_rem dividend; // 加载被除数 reg_div divisor; // 加载除数 quotient 8b0; bit_cnt 4d7; // 从最高位开始共8位 done 1b0; end end S_SHIFT: begin // 将余数寄存器左移一位为新的商位腾出空间 reg_rem {reg_rem[14:0], 1b0}; end S_SUB: begin // 试探减法当前余数的高位部分减去除数 // 注意我们比较的是 reg_rem[15:8] 和 reg_div因为 divisor 是8位 // 这模拟了除数与被除数高位对齐的过程 if (reg_rem[15:8] reg_div) begin // 够减商位置1更新余数高位 quotient[bit_cnt] 1b1; 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 4b0) begin done 1b1; remainder reg_rem[15:8]; // 最终余数是余数寄存器的高8位 end else begin bit_cnt bit_cnt - 1b1; 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 4b0) begin next_state S_IDLE; end else begin next_state S_SHIFT; end end endcase end endmodule代码解析与关键点状态机设计这是时序逻辑的核心。S_SHIFT、S_SUB、S_RESTORE三个状态构成了处理一位商的循环。bit_cnt控制循环8次。对齐的隐含处理代码中没有显式的“对齐最高位”操作。这是因为我们固定了除数为8位被除数为16位。算法通过每次迭代将reg_rem左移一位并总是用reg_rem的高8位[15:8]与整个除数reg_div比较这隐式地实现了除数的“右移”效果。这是一种非常经典且高效的硬件实现技巧。“恢复”的简化在严格的恢复余数法中如果试探减法结果为负需要将减去的除数加回来以恢复原余数。在上面的代码中我们做了一个优化只有在够减余数高位≥除数时才执行减法并更新余数寄存器如果不够减则根本不执行减法操作余数寄存器保持原样。这等价于“先减发现为负再加回来”但节省了一次加法操作。这是可行的因为我们的判断reg_rem[15:8] reg_div发生在减法操作之前通过比较器。资源与时序这个设计需要一个16位寄存器reg_rem、一个8位比较器、一个8位减法器和一个简单的状态机。它需要8个循环每个商位一个循环来完成一次除法。如果时钟频率为100MHz那么完成一次除法大约需要80ns的延迟。吞吐量是每8个周期一次运算。扩展为定点数如果要支持Qm.n格式的定点数除法通常的做法是将被除数左移n位扩展小数位然后将其视为整数进行上述除法运算。得到的结果商就自然包含了n位小数。例如计算Q8.8格式的A除以B可以将A左移8位变成16位整数然后除以B8位整数得到的16位结果中高8位是商的整数部分低8位是商的小数部分。5. 实战调试、优化与常见问题排查即使有了清晰的算法和代码在FPGA上实现除法器时仍然会遇到各种实际问题。下面是我在多个项目中总结出的经验、调试技巧和常见坑点。5.1 功能仿真与边界条件测试在烧录到板子之前充分的仿真至关重要。除了常规的随机测试必须重点测试以下边界情况除数为0这是最危险的错误。硬件除法器没有软件中的异常抛出机制。如果除数为0比较器可能产生全1的结果导致后续状态混乱或产生极大的商值。必须在设计中加入除零检查。如果检测到除数为0可以设置一个标志位并输出一个预设的最大值或让商和余数保持为0。// 在IDLE状态或数据加载时检查 if (divisor 8b0) begin divide_by_zero 1b1; quotient 8hFF; // 或根据协议设定其他值 // 跳过计算直接进入完成状态 end被除数小于除数商应为0余数等于被除数。确保你的算法在这种情况下能正确工作商寄存器全部为0余数寄存器正确保留被除数。被除数等于除数商应为1余数为0。被除数远大于除数确保商不会溢出。在我们的例子中16位被除数除以8位除数最大商是2558‘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的软核里将是灾难性的。理解每种算法的本质、开销和适用场景比单纯追求性能指标更重要。对于大多数嵌入式场景一个经过精心优化、时序收敛的串行移位-减法除法器往往是可靠而务实的选择。在动手写代码之前花时间在纸上画一画数据流和状态图把边界条件和异常处理想清楚这能节省你大量的调试时间。