跳到正文
半导体开放世界

加法器与进位传播

Adders and Carry Propagation

把位权、产生传播与输入进位对齐，比较串行、旁路和选择结构如何组织同一算术依赖。

进阶出处 2 本教材
报告问题

速览

约 1 分钟

多位加法的难点不是写出一个加号，而是把低位进位及时而正确地送到需要它的和位。

系统理解

约 2 分钟

本页使用异或传播约定，将本位操作数先变成G与P，再按进位依赖形成结果。串行、旁路和选择结构改变等待和预计算的分工，却必须保持相同位权及接口语义。逻辑拓扑估算只提供候选，最终延迟还取决于负载、尺寸与布线。

在数字逻辑和综合基础上专门分析算术依赖，再进入并行前缀，区别于逻辑努力的通用门尺寸模型。

关键参数

关键参数
参数单位含义
位宽与位号—明确输入进位、和位及输出进位的位权
传播定义—本页P为Ai与Bi异或，G为两者与
组宽和候选开销—在旁路及选择结构中共同影响等待与资源

常见误区

  • OR传播信号可不加区分地用于XOR求和。
  • 只计算最高进位就得到了全部和。
  • 更复杂的进位结构一定比短位宽串行加法快。

工程深入

12 条结论 · 1 道例题

算术位权与PG约定

定义

全加器同时输出本位和与高一位的进位

全加器把两个同位操作数和输入进位相加，和位保持本位权重，输出进位具有两倍位权。将这些位片级联后，前一位进位成为后一位的输入，形成多位加法的依赖。12

成立条件 讨论普通二进制无冗余进位传播加法。；本页低位编号从0开始，c0为外部进位输入。

机制

进位产生由本位操作数决定而不等待输入进位

当本位两个操作数均为1时，这一位自身已经产生输出进位；该事实可提前计算，不必等低位进位到达。高速加法器利用这种与输入进位独立的预处理信息改变依赖组织。12

成立条件 Gi=Ai∧Bi。；预先得到Gi不等于已经得到全部和位。

边界

本页以异或定义传播信号

本页约定Pi=Ai⊕Bi，因此产生与传播互斥，最终和可直接用Pi与输入进位异或。有些电路以Ai∨Bi参与进位网络，这也能实现进位递推，但不能直接把这个或信号用于最终求和的异或输入。12

成立条件 所有组传播均延续本页的异或约定。；∧、∨、⊕分别表示与、或、异或，不是普通实数乘加。

公式

进位递推与求和必须使用同一套位号

输入进位ci与本位Gi、Pi给出下一位进位ci+1，而本位和si使用当前输入ci。把ci+1误接入本位求和会改变算术功能，即使进位网络本身计算正确也不例外。12

ci+1=Gi∨(Pi∧ci),si=Pi⊕cic_{i+1}=G_i\lor(P_i\land c_i),\qquad s_i=P_i\oplus c_i
ci+1 = Gi ∨ (Pi ∧ ci)；si = Pi ⊕ ci
ci、ci+1
本位输入与下一位输入进位，单位 1
Gi、Pi
本位产生与异或传播信号，单位 1
si
本位和，单位 1

成立条件 Pi=Ai⊕Bi，Gi=Ai∧Bi，i从0至N−1。；所有量为单比特逻辑值。

例题：动手算一次教学假设，可复算

以4位无符号数A=1011、B=0110及c0=1验证逐位进位，输出保留进位。

已知

  1. 从最低位到最高位：(A0,B0)=(1,0)，(A1,B1)=(1,1)，(A2,B2)=(0,1)，(A3,B3)=(1,0)。
  2. A=11，B=6，c0=1。

步骤

  1. (P0,P1,P2,P3)=(1,0,1,1)；(G0,G1,G2,G3)=(0,1,0,0)，先按异或和与计算本位传播与产生。
  2. (c1,c2,c3,c4)=(1,1,1,1)，依次应用ci+1=Gi∨(Pi∧ci)。
  3. (s0,s1,s2,s3)=(0,1,0,0)，每一位使用输入进位ci而不是输出进位ci+1。
  4. c4s3s2s1s0 = 10010₂ = 18₁₀ = 11+6+1，连同最高进位核验完整位权。
结果 4位和为0010，输出进位为1；完整无符号结果为18。

截断为4位后只保留低4位，最高进位须按接口另行保留。

不能外推到 这是有限位宽算术验证，不给出物理电路延迟；不把无符号进位当作有符号溢出标志。

边界

进位取消位切断低位进位的影响

当Ai和Bi均为0时，Gi和Pi都为0，该位的输出进位固定为0。低位输入进位可以影响这一位的和，却不能再经过这一位改变更高位进位。12

成立条件 沿用异或传播约定。；取消描述进位依赖，不表示该全加器的所有输出都不随输入变化。

时序依赖与候选结构

机制

最终求和需要保留每一位的输入进位

只计算最高输出进位不够形成整个结果字，因为中间和位仍各自依赖相应的低位前缀进位。进位网络和最终异或层应分开核对，尤其不能把一个全局进位直接广播为所有和位的输入。12

成立条件 每一位的操作数和传播信号均已对应正确位号。；前缀加法器节点继续处理如何并行形成全部前缀。

边界

最坏进位链由可激活的传播模式决定

串行进位的长路径需要低位变化产生或改变进位，并由中间位持续传播。只测试随机几个加法结果，或只观察平均进位长度，都不能据此排除一条能到达最高有效和位的最坏输入模式。12

成立条件 最坏路径仍要核对当前结构中的可激活输入与所观察输出。；不把教材示例的具体位型直接套用到位宽和Cin不同的接口。

边界

串行级数随位宽增长不等于固定每位物理延迟

同类串行位片的进位依赖长度随位数增加，可用逐级门延迟建立一阶估算；实际总时间还取决于扇出、尺寸、连线和各输入到达时刻。因此线性逻辑链是拓扑描述，不是无需表征的纳秒规格。12

成立条件 模型内比较保持位片类型及负载假设明确。；不将逻辑级数与logical-effort模型或STA最终结果混为一项。

机制

旁路进位在整组可传播时跳过组内串行链

若一组每一位都传播输入进位，组传播信号为真，旁路选择路径可直接把组输入进位送向下一组；否则应采用该组实际计算出的进位。旁路硬件自身也有传播延迟与负载，不能视为零时间跨越。12

成立条件 组传播为该组所有Pi的逻辑与。；首尾组的串行路径与旁路选择形成共同关键路径。

机制

进位选择用两种预计算换取迟到进位的选择路径

进位选择结构可同时计算组输入进位假设为0和1的候选结果，再由实际输入进位选择正确结果。它减少了进位到来后尚需完成的计算，但增加候选逻辑与选择网络的资源开销。12

成立条件 候选结果来自相同操作数和不同进位假设。；不把两组候选都当作有效输出或两次实际加法事务。

机制

可变组长旨在平衡预计算与选择信号到达

在后续选择信号更晚到达时，某些组内预计算可使用更长位组而不立即延长最终关键路径。组长应按真实到达、负载和选择开销设计，而不是机械使用所有组一样宽或照搬平方根级数结论。12

成立条件 教材平方根趋势来自单位或近似门延迟模型。；较大扇出可能需要缓冲，改变理想分组的优势。

关联

选择加法结构要同时交回算术与物理验证

比较串行、旁路、选择和前缀候选时，应在相同位宽、输入到达、输出负载和实现条件下验证结果字及进位，再核对实际时序与资源。结构更复杂不等于必然更快，低位宽时额外控制逻辑可能没有收益。12

成立条件 功能等价检查、库映射和物理时序各自承担不同验证任务。；不重复综合节点的通用流程，只限定算术候选之间可比的接口条件。

出处

2 本教材 · 24 处引用
  1. 1

    CMOS超大规模集成电路设计（第4版）

    查看这个来源 →
  2. 2

    数字集成电路：电路、系统与设计（第2版）

    Jan M. Rabaey, Anantha Chandrakasan, Borivoje Nikolić

    查看这个来源 →