超前进位加法器：原理、层级结构与行波进位比较

超前进位加法器使用生成与传递信号重构进位计算。本文推导 4 位 CLA，并说明宽位设计采用层级结构的原因。

Denny

2026年5月7日阅读约需 8 分钟

Chalkboard feature illustration for “超前进位加法器：原理、层级结构与行波进位比较”

简述： 超前进位将串行递推式 $C_{i+1}=G_i+P_iC_i$ 改写为逐位和分组的生成/传递信号。小型平坦 CLA 可以直接从操作数表示多个进位。层级式和并行前缀版本以额外单元、扇出和布线为代价，将进位深度从线性降低到接近对数级。

4 位行波进位加法器很直观：串接四个全加器，并将每个 $C_{out}$ 接到下一个 $C_{in}$ 。其最坏情况进位依赖会随字宽增长。该路径是否满足时序取决于工艺、时钟目标、单元设计和周边数据通路；仅凭位宽并不能断言一种设计“不可接受”。

超前进位加法器（CLA）通过从可直接由操作数得到的中间信号推导进位表达式，来消除这种串行依赖。

行波进位的线性依赖

回顾全加器方程：

$S_i = A_i \oplus B_i \oplus C_i$ $C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

和 $S_i$ 依赖于 $C_i$ ，进位 $C_{i+1}$ 也依赖于 $C_i$ 。因此依赖链为 $C_0 \to C_1 \to C_2 \to \dots \to C_n$ 。若单级进位耗时为 $t_c$ ，最坏情况总加法时间近似为：

$T_{ripple} \approx n \cdot t_c + t_{sum}$

一阶依赖关系随字宽线性增长。绝对纳秒数需要指定实现，因此门延迟计数在这里仅适用于比较拓扑结构。这正是促使采用更快进位网络的传播延迟限制。

生成与传递

再看进位方程：

$C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

第一项 $A_i B_i$ 恰好在两个操作数位都为 1 时为真——此时第 $i$ 级无论 $C_i$ 输入什么，都会无条件产生进位输出。定义：

$G_i = A_i \cdot B_i$

这就是生成信号——第 $i$ 级自行生成一个进位。

第二项 $(A_i \oplus B_i) C_i$ 表示：若两个操作数位中恰有一个为 1，则到达 $C_i$ 的任何值都会直接传递过去。定义：

$P_i = A_i \oplus B_i$

这就是传递信号——第 $i$ 级将任何输入进位传到输出。

进位方程可简化为：

$C_{i+1} = G_i + P_i \cdot C_i$

该式只包含与门和或门所对应的基本运算，但组合后形成了可展开的递推关系。

展开进位递推式

将递推式代回自身。从已知的 $C_0$ 开始：

$C_1 = G_0 + P_0 C_0$

$C_2 = G_1 + P_1 C_1 = G_1 + P_1(G_0 + P_0 C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0$

$C_3 = G_2 + P_2 C_2 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$

规律很清晰。每个进位 $C_{i+1}$ 都是第 0 到 $i$ 级生成和传递信号的积之和。从逻辑上看，每个表达式只依赖 $G$ 、 $P$ 与 $C_0$ ，而非前一个全加器中已经完成的物理跃迁。从物理上看，宽乘积项及其布线仍需要有限的门、缓冲器和路由。

一个 4 位实例

计算 $A=1011_2$ （11）加 $B=0110_2$ （6），且 $C_0=0$ 。按最低有效位在前写出各位：

位 $i$	$A_i$	$B_i$	$P_i=A_i\oplus B_i$	$G_i=A_iB_i$	$C_i$	$S_i=P_i\oplus C_i$
0	1	0	1	0	0	1
1	1	1	0	1	0	0
2	0	1	1	0	1	0
3	1	0	1	0	1	0

由进位方程得到 $C_1=0$ 、 $C_2=1$ 、 $C_3=1$ 和 $C_4=1$ 。读出 $C_4S_3S_2S_1S_0$ ，得到预期的 $10001_2=17$ 。算术结果与行波进位相同；变化的只是进位网络拓扑。

分组生成与传递

对于从 $i$ 到 $j$ 的位组，定义组传递和组生成：

$P_{j:i}=P_jP_{j-1}\cdots P_i$

$G_{j:i}=G_j+P_jG_{j-1}+\cdots+P_jP_{j-1}\cdots P_{i+1}G_i$

则离开该组的进位为：

$C_{j+1}=G_{j:i}+P_{j:i}C_i$

两个相邻组可用同一运算组合：

(G_H,P_H)\circ(G_L,P_L) = (G_H+P_HG_L,\;P_HP_L)

这种结合性是层级式和并行前缀加法器的关键：先合并成对的组，再合并成对的对，形成树而非串行链。

4 位 CLA 架构

在布尔层面，平坦的 4 位 CLA 有三项功能：

生成/传递层。 $n$ 个与门在一个延迟内产生 $G_i = A_i B_i$ ； $n$ 个异或门在一个延迟内产生 $P_i = A_i \oplus B_i$ 。二者并行运行。
进位网络。 与或逻辑从展开公式计算 $C_1$ 至 $C_4$ 。在假想的无限扇入门下，这看似只有两级逻辑；真实单元库会分解宽项，因此深度与负载随位宽增加。
求和层。 $n$ 个异或门在一个延迟内产生 $S_i = P_i \oplus C_i$ 。（注意，一旦算出 $P_i$ ，就有 $S_i = A_i \oplus B_i \oplus C_i = P_i \oplus C_i$ 。）

对四位而言，这能比全加器单元链缩短进位路径。无限延展平坦方程并不实用，因此较大的 CLA 会引入分组。

4 位 CLA 方框图

A0,B0 ─┬──XOR ──P0 ──┐                           ┌──XOR ──S0
       └──AND ──G0 ──┤                           │
                       │┌───carry network ───┐ │
A1,B1 ─┬──XOR ──P1 ──┤   ││├──XOR ──S1
       └──AND ──G1 ──┤   │computes          ││
                       ├──>│C1, C2, C3, C4    │─┤
A2,B2 ─┬──XOR ──P2 ──┤   │from expanded     │├──XOR ──S2
       └──AND ──G2 ──┤   │││
                       ││carry expressions  ││
                       │└─────────────────────┘ │
A3,B3 ─┬──XOR ──P3 ──┤                           ├──XOR ──S3
       └──AND ──G3 ──┘                           │
                                                   └──────────C4
C0 ──────────────────────>┘

扇入、布线与隐藏成本

对 $C_4$ 而言，包含 $C_0$ 的最长平坦表达式含有一个五输入乘积项；对 $C_{16}$ ，对应项将含 17 个输入。标准单元库只提供有限扇入，而长导线和大负载都会增加时延。因此，按字面直接实现的平坦 CLA 即使布尔表达式层数较少，也难以有效扩展。

通常的解决方案是层级结构。将位分组——通常每组四位——先计算组 $G$ 和 $P$ ，再在下一层组合这些组。一个 16 位设计可使用四个 4 位组加上第二级超前进位。并行前缀加法器则在整棵树中应用结合性的组运算。

这种权衡无法由一张通用门数表概括：

架构	进位依赖	典型优势	典型成本
行波进位	线性	面积小、布线简单	最坏进位路径长
分块超前进位	层级式	速度/面积折中适中	局部逻辑和组布线更宽
选择进位	预先计算两种进位情形	判定路径更短	重复的求和硬件
并行前缀	树状	逻辑深度低	更多前缀单元、布线，有时扇出也高

实际延迟、面积和能耗必须在映射与物理实现之后测量。一个在抽象门级上获胜的拓扑，可能在拥塞、缓冲和负载被计入后落败。

超越 CLA：并行前缀加法器

超前进位思想可以进一步推广。递推式 $C_{i+1} = G_i + P_i C_i$ 在自定义运算符下具有结合性，因此可先成对合并相邻位置，再逐级合并为树。这便形成了并行前缀加法器家族：

Kogge–Stone——前缀深度低、逻辑扇出有界，但布线密集且前缀节点多。
Brent–Kung——前缀节点和布线较少，但深度较大。
Han-Carlson、Ladner-Fischer、Sklansky——在扇出、布线复杂度和深度间作出不同权衡。

量产加法器还可能混合前缀结构、使用稀疏结构，或在选定组周围布置选择进位逻辑。选择必须针对具体的时序、面积、功耗和布线预算；处理器的时钟频率本身并不能揭示其加法器拓扑。

在 DigiSim 中实现 CLA

4 位 CLA 可用基本元件构建：四个用于生成信号的与门、四个用于传递信号的异或门、实现上述方程的进位网络，以及四个用于求和的异或门。高层加法器和8 位加法器元件提供行为级抽象；除非元件文档明确说明，否则不能据此推断其内部架构。

比较拓扑时，可将四个全加器串成行波进位，并另建一个 4 位 CLA。首先验证全部操作数组合的功能等价性。若仿真器对逐门延迟进行了建模，可比较输入变化后的最晚稳定时间；若采用理想逻辑门模型，则应比较相关逻辑级数。理想波形不能预测硅实现的物理时序。

常见陷阱

忘记 $P_i$ 用的是 XOR 而不是 OR。 两种定义—— $P_i = A_i + B_i$ 或 $P_i = A_i \oplus B_i$ ——都能产生正确进位，因为 $A_i = B_i = 1$ 的情况已由 $G_i$ 覆盖。优先选 XOR 的原因是同一根线可馈入求和级： $S_i = P_i \oplus C_i$ 。若用 OR 定义 $P_i$ ，该复用便不成立，求和还需单独的 XOR。
低估扇入扩展。 包含 $C_0$ 时，平坦的 16 位展开式含有一个 17 文字项。实用的宽位设计会分解或分组逻辑。
假定 CLA 总是更快。 位宽较小时，行波实现可能在面积上胜出，且完全能满足时序。不存在与架构无关的交叉位宽。
混淆求和与进位的关键路径。 进位网络深度主导总延迟，但最后的求和 XOR 还增加一个门延迟。将延迟表述为“进位网络深度”是常见错误。

后续阅读与验证

继续阅读ALU 如何工作：从逻辑门构建算术逻辑单元，再阅读Booth 乘法器详解，了解另一种算术优化。

可打开带进位的全加器模板，串接四个实例形成行波进位加法器，并在逻辑分析仪上观察逐位进位传递；再按本文方程构建等效的 4 位 CLA，对两种电路的建模时延进行比较。缩短算术关键路径是高速 ALU 采用更复杂进位网络的重要原因之一。