FPGA实现4位二进制除法器：移位相减算法详解

1. 项目概述

在数字电路设计中，除法运算一直是一个相对复杂的操作。与加法、乘法相比，除法运算需要更多的硬件资源和计算步骤。今天我要分享的是一个基于FPGA实现的4位无符号二进制除法器，它采用经典的移位相减算法，能够快速计算出两个4位二进制数相除的商和余数。

这个设计特别适合用于嵌入式系统、数字信号处理等对硬件资源要求较高的场景。整个电路采用纯组合逻辑实现，延迟低、结构简单，可以直接集成到更大的数字系统中。使用Altera Cyclone IV FPGA开发板实现，通过拨码开关输入被除数和除数，LED显示计算结果，非常直观。

提示：虽然这个设计是针对4位二进制数的，但理解了核心原理后，可以很容易扩展到8位、16位甚至更高位宽的除法器。

2. 设计原理与算法解析

2.1 二进制除法基础

在数字电路中实现除法运算，最常用的方法就是移位相减算法。这个算法的核心思想与我们手工做长除法非常相似，都是通过不断地比较、移位和减法来逐步求出商和余数。

对于4位无符号二进制数，被除数A的范围是0~15（0000~1111），除数B的范围是1~15（0001~1111）。当除数为0时，电路会给出错误标志。商Q的范围是0~15，余数R的范围是0到B-1。

2.2 移位相减算法详解

算法具体步骤如下：

1. 初始化阶段：

   • 余数寄存器R清零（R=0000）
   • 商寄存器Q清零（Q=0000）

2. 迭代计算阶段（共4次迭代，对应4位被除数）：

   • 将余数R左移1位，空出最低位
   • 将被除数的当前最高位填入R的最低位
   • 比较R和除数B：
     • 如果R ≥ B，则执行R = R - B，并在Q的对应位置1
     • 否则，Q的对应位置0

3. 结果输出阶段：

   • 4次迭代完成后，Q中存储的就是商，R中存储的就是余数

让我们通过一个具体例子来理解这个过程：

示例：计算8 ÷ 2（二进制：1000 ÷ 0010）

• 初始状态：R=0000，Q=0000
• 第1位处理（1）：
  • R左移：0000 → 0000
  • 填入被除数位1：R=0001
  • 比较：0001 < 0010 → Q=0000，R=0001
• 第2位处理（0）：
  • R左移：0001 → 0010
  • 填入被除数位0：R=0010
  • 比较：0010 ≥ 0010 → R=0000，Q=0100
• 第3位处理（0）：
  • R左移：0000 → 0000
  • 填入被除数位0：R=0000
  • 比较：0000 < 0010 → Q=0100，R=0000
• 第4位处理（0）：
  • R左移：0000 → 0000
  • 填入被除数位0：R=0000
  • 比较：0000 < 0010 → Q=0100，R=0000
• 最终结果：商Q=0100（4），余数R=0000（0）

这个例子完美验证了我们的算法设计。通过这种逐步移位和比较的方式，我们可以在硬件上高效地实现除法运算。

3. 硬件设计与FPGA实现

3.1 硬件平台选择

本设计选用Altera Cyclone IV EP4CE6F17C8 FPGA作为硬件平台。这款FPGA具有6272个逻辑单元，对于4位除法器这样的简单设计来说资源绰绰有余。选择这款芯片主要基于以下考虑：

1. 性价比高：Cyclone IV系列是Altera的中低端FPGA，价格适中
2. 开发环境成熟：可以使用Quartus II进行开发和综合
3. IO资源充足：足够支持我们的输入输出需求

3.2 硬件接口设计

系统需要以下硬件接口：

1. 输入部分：

   • 8位拨码开关：低4位（SW3~SW0）用于输入被除数A，高4位（SW7~SW4）用于输入除数B
   • 每个开关对应一个二进制位，ON状态表示1，OFF状态表示0

2. 输出部分：

   • 8位LED：低4位（D3~D0）显示商Q，高4位（D7~D4）显示余数R
   • 额外1位LED（D8）作为错误指示，当除数为0时点亮

3. FPGA引脚分配：

3.3 硬件连接注意事项

在实际硬件连接时，有几个关键点需要注意：

1. 上拉/下拉电阻：拨码开关的输出端需要适当的上拉或下拉电阻，确保在开关断开时能保持稳定的逻辑电平
2. LED限流电阻：每个LED都需要串联限流电阻，通常220Ω-1kΩ之间，具体值取决于LED的特性和所需亮度
3. 电源滤波：FPGA的电源引脚附近应放置适当的去耦电容，通常每个电源引脚配一个0.1μF的陶瓷电容

注意：在连接拨码开关和LED时，务必确认FPGA的IO电压等级（通常是3.3V）与外设兼容，避免损坏器件。

4. Verilog HDL实现

4.1 除法器核心模块

下面是4位除法器的Verilog HDL实现代码。这个模块采用纯组合逻辑设计，输入变化后立即计算输出结果。

verilog复制module divider_4bit (
    input [3:0] A,      // 被除数（4位无符号）
    input [3:0] B,      // 除数（4位无符号）
    output reg [3:0] Q, // 商（4位）
    output reg [3:0] R, // 余数（4位）
    output reg error    // 错误标志（除数为0时置1）
);

// 组合逻辑实现除法算法
always @(*) begin
    if (B == 4'd0) begin  // 除数为0，报错
        Q = 4'd0;
        R = 4'd0;
        error = 1'b1;
    end else begin
        error = 1'b0;
        R = 4'd0;  // 初始化余数为0
        Q = 4'd0;  // 初始化商为0
        
        // 逐位处理被除数（从高位到低位，共4位）
        for (int i = 3; i >= 0; i = i - 1) begin
            // 1. 余数左移1位，空出最低位
            R = R << 1;
            // 2. 填入被除数当前位（A的第i位）
            R[0] = A[i];
            // 3. 比较余数与除数，够减则减并记录商1
            if (R >= B) begin
                R = R - B;
                Q[i] = 1'b1;  // 商的第i位（对应被除数第i位）置1
            end else begin
                Q[i] = 1'b0;  // 商的第i位置0
            end
        end
    end
end

endmodule

4.2 顶层模块设计

顶层模块负责将除法器核心模块与实际的硬件接口连接起来：

verilog复制module top_divider (
    input [7:0] SW,      // 拨码开关（低4位A，高4位B）
    output [7:0] LED,    // LED（低4位Q，高4位R）
    output ERROR_LED     // 错误指示灯
);

// 信号拆分
wire [3:0] A = SW[3:0];  // 被除数（拨码开关SW3~SW0）
wire [3:0] B = SW[7:4];  // 除数（拨码开关SW7~SW4）
wire [3:0] Q, R;
wire error;

// 实例化除法器
divider_4bit u_divider (
    .A(A),
    .B(B),
    .Q(Q),
    .R(R),
    .error(error)
);

// 输出分配
assign LED[3:0] = Q;      // 商→LED D3~D0
assign LED[7:4] = R;      // 余数→LED D7~D4
assign ERROR_LED = error; // 错误标志→LED D8

endmodule

4.3 代码解析与优化技巧

1. 组合逻辑设计：

   • 使用always @(*)块实现纯组合逻辑
   • 输入变化时立即计算输出，延迟低
   • 但可能产生较大的组合逻辑路径

2. 除零处理：

   • 在算法开始前首先检查除数是否为0
   • 如果除数为0，立即设置错误标志并输出全0结果

3. 循环展开：

   • 使用for循环处理4位被除数
   • 综合器会自动展开循环，生成对应的硬件电路

4. 资源优化：

   • 可以添加(* optimize_power *)等综合指令，指导工具优化设计
   • 对于更复杂的除法器，可以考虑流水线设计提高性能

提示：在Quartus中综合时，可以设置"Optimization Technique"为"Balanced"或"Performance"，根据需求平衡资源使用和速度。

5. 关键问题与解决方案

5.1 除数为零的处理

问题描述：
在数学中，除数为零是无定义的操作。在硬件实现中，如果不处理这种情况，可能会导致不可预测的行为或硬件错误。

解决方案：

• 在Verilog代码中优先检查除数B是否为0
• 如果B==0，立即设置错误标志error=1，并输出Q=0、R=0
• 通过一个专用的LED（D8）指示错误状态

实现代码：

verilog复制if (B == 4'd0) begin  // 除数为0，报错
    Q = 4'd0;
    R = 4'd0;
    error = 1'b1;
end

5.2 组合逻辑延迟问题

问题描述：
纯组合逻辑设计虽然延迟低，但随着位宽增加，组合逻辑路径会变长，可能导致：

1. 输出出现毛刺（glitch）
2. 最大工作频率下降
3. 时序难以满足

解决方案：

1. 寄存器打拍：在输出端添加一级寄存器，用时钟同步输出

   verilog复制always @(posedge clk) begin
       Q_reg <= Q;
       R_reg <= R;
       error_reg <= error;
   end
   

2. 流水线设计：将除法过程分成多个阶段，每个时钟周期完成一部分工作
3. 时序约束：在Quartus中设置适当的时序约束，指导综合工具优化关键路径

5.3 无符号数范围限制

问题描述：
4位无符号数的范围是0~15，在设计时需要确保：

1. 余数R必须小于除数B
2. 商Q不能超过15
3. 被除数A和除数B的输入范围正确

解决方案：

• 通过算法保证余数R < B（这是移位相减算法的固有特性）
• 输入范围通过硬件限制（拨码开关只有4位）
• 在代码中添加断言(assertion)进行验证：

  verilog复制assert property (B != 0 || (Q == 0 && R == 0 && error));
  assert property (B == 0 || R < B);
  

6. 测试与验证方法

6.1 测试用例设计

为了全面验证除法器的功能，我们设计了以下测试用例：

6.2 硬件测试步骤

1. 准备工作：

   • 连接FPGA开发板与电源
   • 确保所有拨码开关和LED已正确连接
   • 下载编译好的程序到FPGA

2. 测试流程：

   • 设置被除数A：通过SW3~SW0设置4位二进制值
   • 设置除数B：通过SW7~SW4设置4位二进制值
   • 观察输出：
     • LED D3~D0显示商Q
     • LED D7~D4显示余数R
     • LED D8显示错误标志（除数为0时亮起）

3. 测试记录：

   • 对每个测试案例，记录实际输出与预期是否一致
   • 特别关注边界情况：A=0、A=15、B=1、B=15、B=0等

6.3 仿真测试

除了硬件测试，我们还可以使用ModelSim等工具进行仿真测试：

verilog复制module tb_divider;
    reg [3:0] A, B;
    wire [3:0] Q, R;
    wire error;
    
    divider_4bit uut (A, B, Q, R, error);
    
    initial begin
        // 测试案例1：8 ÷ 2 = 4余0
        A = 4'b1000; B = 4'b0010; #10;
        
        // 测试案例2：9 ÷ 2 = 4余1
        A = 4'b1001; B = 4'b0010; #10;
        
        // 测试案例3：15 ÷ 3 = 5余0
        A = 4'b1111; B = 4'b0011; #10;
        
        // 测试案例4：除数为0
        A = 4'b0010; B = 4'b0000; #10;
        
        $finish;
    end
endmodule

7. 优化与扩展方向

7.1 时序逻辑实现

虽然组合逻辑实现简单直接，但在某些场景下，时序逻辑实现可能更有优势：

优点：

1. 资源利用率更高（特别是位宽较大时）
2. 时序更容易满足
3. 功耗可能更低

实现代码片段：

verilog复制// 时序逻辑除法器（4周期）
reg [3:0] A_reg, B_reg;
reg [1:0] state;  // 状态机：0-初始化，1-迭代，2-完成
reg [1:0] bit_counter; // 位计数器

always @(posedge clk) begin
    case (state)
        0: begin  // 初始化
            A_reg <= A; 
            B_reg <= B; 
            R <= 0; 
            Q <= 0; 
            bit_counter <= 3;
            state <= 1;
        end
        1: begin  // 迭代
            R <= (R << 1) | A_reg[bit_counter];
            if (R >= B_reg) begin
                R <= R - B_reg;
                Q[bit_counter] <= 1'b1;
            end else begin
                Q[bit_counter] <= 1'b0;
            end
            
            if (bit_counter == 0)
                state <= 2;
            else
                bit_counter <= bit_counter - 1;
        end
        2: state <= 2;  // 保持结果
    endcase
end

7.2 有符号数扩展

当前设计仅支持无符号数，可以扩展为有符号数除法器：

实现步骤：

1. 增加符号位处理：
   • 被除数和除数各增加1位符号位
   • 结果的符号由被除数和除数的符号决定（同号为正，异号为负）
2. 取绝对值运算：
   • 在计算前，先取被除数和除数的绝对值
   • 使用无符号除法器计算
3. 结果处理：
   • 根据原始符号位调整商和余数的符号
   • 特别注意余数的符号应与被除数相同

代码修改点：

verilog复制// 符号处理
wire A_sign = A[4];
wire B_sign = B[4];
wire [3:0] A_abs = A_sign ? -A : A;
wire [3:0] B_abs = B_sign ? -B : B;
wire Q_sign = A_sign ^ B_sign;
wire R_sign = A_sign;

// 调用无符号除法器
divider_4bit u_divider (
    .A(A_abs),
    .B(B_abs),
    .Q(Q_abs),
    .R(R_abs),
    .error(error)
);

// 结果符号处理
assign Q = Q_sign ? -Q_abs : Q_abs;
assign R = R_sign ? -R_abs : R_abs;

7.3 性能优化技巧

1. 流水线设计：

   • 将除法过程分成多个阶段
   • 每个时钟周期完成一部分工作
   • 可以提高吞吐量，适合高速应用

2. 查找表辅助：

   • 对于高位宽除法，可以使用小的查找表加速计算
   • 例如预先计算并存储一些中间结果

3. 进位保留加法器：

   • 在减法操作中使用进位保留加法器
   • 可以减少关键路径延迟

4. 位宽扩展：

   • 可以轻松扩展到8位、16位或更高位宽
   • 只需增加寄存器的位宽和迭代次数

8. 应用场景与实用建议

8.1 典型应用场景

这个4位除法器虽然简单，但在许多场景中都有实用价值：

1. 嵌入式系统：

   • 资源受限的微控制器
   • 需要硬件加速的除法运算

2. 数字信号处理：

   • 滤波器系数计算
   • 信号归一化处理

3. 教育实验：

   • 数字逻辑设计教学
   • FPGA开发入门实践

4. 自定义处理器：

   • 作为ALU的除法单元
   • RISC-V等开源处理器的扩展指令

8.2 实用建议

1. 资源利用监控：

   • 在Quartus编译后，查看资源使用报告
   • 确保逻辑单元、寄存器等资源利用率合理

2. 时序分析：

   • 使用TimeQuest进行时序分析
   • 确保关键路径满足时序要求

3. 功耗考虑：

   • 对于电池供电设备，考虑使用时序逻辑降低功耗
   • 在不需要高速运算时，可以降低时钟频率

4. 验证方法：

   • 结合仿真和硬件测试
   • 使用自动化测试脚本提高验证效率

5. 扩展思路：

   • 尝试实现恢复式除法、非恢复式除法等不同算法
   • 比较不同算法在资源使用和性能上的差异

在实际项目中，我经常发现简单的组合逻辑设计就能满足大多数低性能需求，但当系统频率提高或位宽增加时，时序逻辑或流水线设计就变得必要了。一个实用的技巧是先用组合逻辑实现功能验证，然后再根据需要逐步引入时序元素进行优化。