行波进位加法器 (Carry-Propagate Adder)

发布于:2025-07-04 ⋅ 阅读:(12) ⋅ 点赞:(0)

目录

1. 原理

2. 结构

3. 公式

4. 应用

5. 延时分析

6. RTL 代码 (Verilog)

7. C++ 模拟代码

8. 特点总结


1. 原理

Carry-Propagate Adder (CPA),也称为行波进位加法器 (Ripple Carry Adder, RCA),是最基本的加法器结构。其核心原理是:

  • 将多个全加器(Full Adder)串联
  • 进位信号从最低位(LSB)向最高位(MSB)逐级传播
  • 每个全加器的进位输出(Cout)直接连接到下一级的进位输入(Cin)
  • 最低位的Cin通常为0

2. 结构


假设现有被加数 A = 5 和 加数 B = 7, 那么 A + B 如果用 CPA 的算法来实现的话, 假设他的内部结构是由 Full adder 组成, 那么它的结构将是:

当然, 我们在上一篇文章《半加器和全加器》中了解到 Full Adder 可以是由两个 Half Adder
组成或者是由三个与门, 一个或门和一个异或门组成, 那么电路图将会是:

3. 公式

对于n位加法器(0为最低位):

  • 第 i 个和位S_i = A_i \bigoplus B_i \bigoplus C_i
  • 第 i+1 个进位C_{i+1} = (A_i \cdot B_i) + ((A_i \bigoplus B_i) \cdot C_i)
  • 初始进位C_0 = 0
  • 最终进位C_{out} = C_n

假设上面的例子 A + B 的例子, A = 5, B = 7, 那么他们连个数值在 机器中的二进制表示为:A = 0101, B = 0111。

令  g_i = A _i \cdot B_i , p_i = A_i \bigoplus B_i

S_0 = p_0 \bigoplus C_0 

S_1 = p_1 \bigoplus C_1 

S_2 = p_2 \bigoplus C_2

S_3 = p_3 \bigoplus C_3

C_1 = g_0 + p_0C_0

C_2 = g_1 + p_1C_1 = g_1 + p_1g_0 + p_1p_0g_0C_0 

C_3 = g_2 + p_2C_2 = g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0g_0C_0

C_4 = g_3 + p_3C_3 = g_3 + p_3g_2 + p_3p_2g_1 + p_3p_2p_1g_0 + p_3p_2p_1p_0g_0C_0

可以看到在每个表达式中,每个全加器阶段的输出进位仅取决于初始输入进位(C_i),该阶段的 g 和 p 函数,以及前面阶段的 g 和 p 函数。由于每个 g 和 p 函数都可以用全加器的 A 和 B 输入来表示,所有输出进位都可以立即获得(除了门延迟),而不需要等待进位在所有阶段中传播,然后才能获得最终结果。因此,前瞻进位技术加速了加法过程。

4. 应用

  • 低功耗设计:结构简单,功耗较低
  • 小面积实现:门数量最少
  • 教学工具:理解加法器基本原理
  • 非关键路径电路:对速度要求不高的场景
  • ASIC/FPGA基础组件:作为更复杂加法器的构建块

5. 延时分析

延时主要来自进位传播链:

  • 关键路径C_0 \rightarrow FA_0 \rightarrow C_1 \rightarrow FA_1 \rightarrow ... \rightarrow FA_{n-1} \rightarrow C_n
  • 每级延迟T_{FA} (全加器延迟)
  • 总延迟T_{total} = n \times T_{FA}
  • 和位延迟:最低位 S_0 延迟为 T_{FA},最高位 S_n 延迟为 n \times T_{FA}
  • 进位传播延迟O(n),线性增长

6. RTL 代码 (Verilog)

module ripple_carry_adder #(parameter WIDTH=4) (
    input  [WIDTH-1:0] a, b,
    output [WIDTH-1:0] sum,
    output cout
);
    wire [WIDTH:0] carry;
    assign carry[0] = 1'b0;  // LSB carry-in
    
    genvar i;
    generate
        for(i=0; i<WIDTH; i=i+1) begin : adder_chain
            full_adder fa (
                .a(a[i]),
                .b(b[i]),
                .cin(carry[i]),
                .sum(sum[i]),
                .cout(carry[i+1])
            );
        end
    endgenerate
    
    assign cout = carry[WIDTH];  // MSB carry-out
endmodule

module full_adder(
    input  a, b, cin,
    output sum, cout
);
    assign sum  = a ^ b ^ cin;
    assign cout = (a & b) | ((a ^ b) & cin);
endmodule

7. C++ 模拟代码

#include <iostream>
#include <vector>
using namespace std;
// 全加器单元模拟
void full_adder(bool a, bool b, bool cin, bool& sum, bool& cout) {
    sum = a ^ b ^ cin;
    cout = (a & b) | ((a ^ b) & cin);
}

// 行波进位加法器
vector<bool> ripple_carry_adder(const vector<bool>& a, 
                               const vector<bool>& b) {
    size_t n = a.size();
    vector<bool> sum(n);
    vector<bool> carry(n+1, false); // carry[0] = LSB carry
    
    for(size_t i = 0; i < n; ++i) {
        full_adder(a[i], b[i], carry[i], sum[i], carry[i+1]);
    }
    
    cout << "Final carry: " << carry[n] << endl;
    return sum;
}

// 打印二进制数 (MSB first)
void print_binary(const vector<bool>& bits) {
    for(int i = bits.size()-1; i >= 0; --i) {
        cout << bits[i];
    }
}

int main() {
    // 4位加法示例: 7 + 6 = 13 (0111 + 0110 = 1101)
    vector<bool> a = {1,1,1,0}; // LSB first: 0b0111
    vector<bool> b = {0,1,1,0}; // LSB first: 0b0110
    
    vector<bool> sum = ripple_carry_adder(a, b);
    
    cout << "A: "; print_binary(a); cout << " (7)" << endl;
    cout << "B: "; print_binary(b); cout << " (6)" << endl;
    cout << "Sum: "; print_binary(sum); cout << " (13)" << endl;
    
    return 0;
}

输出示例

Final carry: 0
A: 0111 (7)
B: 0110 (6)
Sum: 1101 (13)


 

8. 特点总结

特性 说明
优点 结构简单、面积小、功耗低
缺点 延迟随位数线性增加(O(n))
适用场景 低位数加法(≤8位)、非关键路径
关键路径 进位传播链(Cin→Cout)
门数 每个位2个门(异或+与或)
延迟优化 不适用,本质是串行结构

行波进位加法器是数字电路中最基础的加法器实现,虽然速度较慢,但其简单性和低功耗特性使其在特定场景仍有重要应用价值。在实际工程中,高位加法通常采用超前进位加法器(Carry-Lookahead Adder)等更高效结构。