当前位置：首页 > news >正文

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

news 2025/7/4 12:07:09

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-ingenvar i;generatefor(i=0; i<WIDTH; i=i+1) begin : adder_chainfull_adder fa (.a(a[i]),.b(b[i]),.cin(carry[i]),.sum(sum[i]),.cout(carry[i+1]));endendgenerateassign cout = carry[WIDTH];  // MSB carry-out
endmodulemodule 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 carryfor(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: 0b0111vector<bool> b = {0,1,1,0}; // LSB first: 0b0110vector<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个门(异或+与或)
延迟优化	不适用，本质是串行结构