加法器进阶：让进位早点到
更新时间：2026-09-12。本文是「集成电路大类 · 芯片设计」**进阶层（intermediate）**数字逻辑基础第二十五篇。加法器与算术电路给了全加器和行波进位的直觉，这一篇正面回答那个决定 ALU 频率的问题——n 位加法的进位，到底能算多快。
本文要回答的问题
- 行波进位为什么慢？什么是生成 G、传播 P？
- 超前进位 CLA 怎样绕开逐位等待，用两级门直接算进位？它为什么在高位宽又变贵？
- 进位选择、进位跳过分别用什么「投机取巧」缩短进位路径？
- 并行前缀加法器（Kogge-Stone/Brent-Kung）为什么只要 log(n) 级？它们的布线/面积差在哪？
- 实际综合器怎么在这些结构里选，写 RTL 要注意什么？
一、病根：进位是一条贯穿全宽的链
全加器的和与进位是：sᵢ = aᵢ⊕bᵢ⊕cᵢ，cᵢ₊₁ = aᵢbᵢ + (aᵢ⊕bᵢ)cᵢ。关键在第二式：第 i 位的进位输出依赖第 i 位的进位输入。行波进位（RCA）把全加器串起来，c₀→c₁→…→cₙ，最坏进位要穿过 n 级门，延迟 O(n)。所有高性能加法器都在做同一件事：斩断这条串行依赖，让高位进位不必等低位一位位传上来。
先定义两个贯穿全文的位级信号：
- 生成（generate）
Gᵢ = aᵢ·bᵢ：这一位自己就产生进位（两数都为 1，不管 cᵢ 是多少）； - 传播（propagate）
Pᵢ = aᵢ⊕bᵢ：这一位把输入进位原样传到输出（恰有一个 1，cᵢ₊₁ = cᵢ）。
于是进位式干净地写成 cᵢ₊₁ = Gᵢ + Pᵢ·cᵢ。和也可写成 sᵢ = Pᵢ ⊕ cᵢ。注意 P 有时也用 aᵢ+bᵢ（为配合块运算），定义随结构微调，物理含义不变。
二、超前进位 CLA：把递推展开成两级门
把 cᵢ₊₁ = Gᵢ + Pᵢcᵢ 逐层代入展开：
c1 = G0 + P0·c0
c2 = G1 + P1·G0 + P1·P0·c0
c3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·c0
c4 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·c0读法很直观：c4=1 当且仅当「第 3 位生成」或「第 3 位传播且第 2 位生成」……或「低 4 位全部传播把 c0 一路传上来」。这些都是只含 G/P 和 c0 的两级与—或表达式！因此所有进位原则上可用两级门同时算出，和再经一级异或得到——延迟从 O(n) 降到 O(1)（与位宽无关的常数级逻辑深度）。
代价藏在扇入和扇出里：最高位的与项有 n 个输入、或项有 n 项，门的扇入和布线随位宽暴涨，物理上根本做不到理想两级。工程做法是分块 CLA：用 4 位 CLA 单元（如 74x283），块内超前进位，块间再用一层「块生成/块传播」做二级先行（74x182 先行扩展器），在扇入和速度间折中。
三、进位选择：赌一把，用 MUX 选结果
**进位选择加法器（carry-select, CSA）**换个思路投机。把加法切成几块（如低 4 位、中 4 位、高 4 位）。低位块正常算；相邻高位块不等进位传来，而是用两套加法器并行假设：一套假设块的输入进位是 0、一套假设是 1，两套结果同时算好；等真正的低位进位一到，用一排 2:1 MUX（进位当选择端）选正确的那套和。
进位一到，高位结果已经摆在 MUX 输入端，只需穿 MUX 而非整块加法器，等待时间大幅缩短。代价是高位块要双倍加法器（面积/功耗换速度）。优化：块尺寸不必相等——进位要逐块传来，越靠后的块等得越久、可以越做越大，让「等待时间」和「块计算时间」大致相等，经典取递增尺寸 1/2/3/4… 或近似等延迟分组，以最少总面积满足目标延迟。
四、进位跳过：给进位开一条旁路
进位跳过/进位旁路加法器（carry-skip/bypass）观察到一个事实：若一个块内所有位都传播（P_block = P0·P1·…·Pk），那么块输出进位就等于块输入进位——进位根本不必进块里逐级穿，直接**旁路（bypass）**过去。于是：
- 正常情况下进位在块内行波（块内 RCA）；
- 每块加一个多路器：当块传播信号
P_block有效，让输入进位直接跳过本块； - 最坏路径变成：在首块内穿到某个生成点、再经各级旁路 MUX 跳过中间块、再进入末块，约
块延迟 + (块数)·MUX + 块延迟，比纯行波短得多。
它比进位选择省器件（不用双加法器，只需每块一个传播与门 + 一只 MUX），是面积/速度的良好折中；高位宽时再用多级旁路（skip 之上再 skip）逼近对数延迟。
五、并行前缀：把进位计算化成 log(n) 级网络
最优雅的现代高性能结构是并行前缀加法器（parallel-prefix），它把 G/P 思想推广为一种可结合的「块运算」。定义块（前缀）运算 ∙，把相邻两段的生成/传播合并：
(G₁,P₁) ∙ (G₀,P₀) = (G₁ + P₁·G₀, P₁·P₀)含义：合并段会生成进位，当「右段生成」或「左段传播且右段生成」；合并段整体传播，当两段都传播。这个运算满足结合律，所以从最右端 c0 开始，对每一位求「从位 0 到位 i 的前缀合并结果」(G*ᵢ, P*ᵢ)，就能一步得到每位进位 cᵢ₊₁ = G*ᵢ + P*ᵢ·c0。问题于是变成经典的并行前缀求和——n 个元素用结合运算求所有前缀，可用 log₂(n) 级的树形网络完成（和 CLA 树、Wallace 压缩同一种对数思想）。三种著名布线：
| 网络 | 逻辑级数 | 布线/节点数 | 特点 |
|---|---|---|---|
| Kogge-Stone | log n（最少，最快） | 节点最多、扇出小但全局长线多 | 速度最高、布线拥塞/功耗大，宽位宽高频 ALU 常用 |
| Brent-Kung | 2log−1（稍多） | 节点最少、布线规则 | 面积小、功耗低，代价是深一两级 |
| Sklansky | log n | 节点中等，但扇出指数增长 | 条件折中，大扇出使单级变慢 |
结构上分三步：①位级 Gᵢ=aᵢbᵢ, Pᵢ=aᵢ⊕bᵢ；②前缀网络（log 级 ∙ 运算）算出每位 G*ᵢ、得进位；③sᵢ=Pᵢ⊕cᵢ 收尾。现代 CPU 宽加法器基本都在这一族里按频率/面积/布线选点。
六、工程视角：你几乎不用手搭，但要会读
写 RTL 时 assign s = a + b; 综合器会根据目标频率、位宽、单元库延迟自动在 RCA/CLA/carry-select/前缀结构间挑选——约束松选省面积的 RCA，约束紧自动推断前缀或进位选择。你能做的关键决策是：
- 位宽匹配：不必要的超宽加法平白加长进位链，按需要截/扩位（见 乘法器位宽、定点数）；
- 别在加法前后塞无关组合把进位链和别的逻辑串成更长关键路径；
- 懂得读报告：时序报告里加法关键路径常标注进位沿（carry chain），FPGA 上会映射成专用快速进位链（carry8 级联），此时手搓 CLA 反而更差——要用工具原生
+； - 理解结构选择的物理根因：一切加法器优化都是在「逻辑深度、扇入扇出、布线长度、面积/功耗」四个维度做权衡，前缀网络用面积和布线换 log 深度，进位选择用双份硬件换 MUX 延迟，跳过用旁路 MUX 换最坏路径。
这也是数据通路优化的通用母题，和 乘法器压缩树、流水线切关键路径一脉相承：先找到那条最长的依赖链（这里是进位），再用并行展开、投机预选、旁路捷径、对数树四把刀子去削它。
与现有篇目的衔接
总结
一句话总结：行波进位慢在进位必须逐级穿过 n 个全加器、延迟 O(n)，高性能加法器都在让高位进位早到；引入生成 Gᵢ=aᵢbᵢ（自己产生进位）和传播 Pᵢ=aᵢ⊕bᵢ（透传进位）后，超前进位 CLA 把进位递推式逐层展开成只含 G/P/c0 的两级与或式，所有进位几乎同时算出、逻辑深度 O(1)，代价是高位宽扇入扇出和布线爆炸，故实际用 4 位块加分块先行；进位选择加法器让高位块用两套加法器分别假设进位 0/1 并行算好，真进位一到仅用 MUX 选结果，以双份硬件换等待时间并按 1/2/3/4 递增分块省面积；进位跳过用「整块全传播则输入进位旁路」的 MUX 捷径，让最坏路径缩短为进块+跨块 MUX+出块，是省器件的折中；并行前缀加法器把 (G,P) 的合并定义成满足结合律的块运算，从而用 log(n) 级树形网络求所有前缀进位，Kogge-Stone 级数最少最快但全局长线和节点最多、Brent-Kung 节点最省布线规则但深一两级、Sklansky 折中但扇出大；实际写 s=a+b 时综合器按频率/位宽/库自动选结构，FPGA 上应让工具映射专用进位链而非手写 CLA，工程师要做的是位宽匹配、不把无关逻辑串进进位链、读懂时序报告里的 carry path——贯穿始终的是在逻辑深度、扇入扇出、布线、面积功耗间权衡，用并行展开、投机预选、旁路捷径、对数树四把刀削短那条最长依赖链。