第一次用半加器搭多位加法器的人,几乎都会踩同一个坑。做两位加法,第一版用了两个半加器,一位一位算。1 加 1 得 0,看起来「本位是 0、进位是 1」,可这个进位没地方去;2 加 1 得 1,也说不通。检查半天,问题不在接线,而在器件选错了:半加器只有两个输入,根本没有「低位进位」这个入口,用它搭多位加法器,低位的进位永远传不上来。

加法器是组合逻辑里最值得细看的一块。一位的加法只用一个异或、两个与、一个或就能搞定,难的是几十位怎么把进位一路传下去。行波进位最简单,但进位像排队一样从最低位传到最高位,位宽一大,延迟就线性增长;超前进位把进位提前算出来,用更多门换更短路径;并行前缀再进一步,把进位树做成对数深度。这三种结构,基本就是数字电路里「面积换速度」的活教材。

这篇从半加器讲到全加器,再讲到行波进位、超前进位和并行前缀,最后用 Python 穷举十六种输入组合、验证四位加法器的每一位和进位,顺便把有符号溢出讲清楚。文中的真值表、穷举结果和延迟模型是本机跑出来的;具体芯片的上板时序未在本机实测。

先看现象:8 加 8 得 0,进位去哪了

四位加法器算 8 加 8,结果是 0,进位输出却是 0。很多人第一反应是「溢出很正常」,但溢出不等于进位消失。8 加 8 的无符号结果是 16,四位装不下,正确行为应该是本位为 0、进位输出为 1。进位输出为 0,说明最高位的进位根本没有接到输出,或者接错了位。

再算 15 加 1,本位 0、进位 0,同样不对。最高位那一位的全加器其实已经产生了进位,只是设计者只把四位和接出来,忘了把第四位的进位也引到端口。这种错误在仿真里很容易被忽略,因为只看和的话,很多组数据都「碰巧」是对的;只有边界值,比如 8 加 8、15 加 1,才会露馅。

还有一种更隐蔽的情况:算 7 加 1 得 8,和是对的,但有人把它当成「有符号溢出」。七加一等于八,在四位有符号数里,八已经超出负八到正七的范围,确实是溢出;可如果把它当无符号数,八完全装得下,进位为 0。同一组位,解释方式不同,结论就不同。

半加器:只管本位,不管低位进位

半加器,half adder,做两个一位二进制数的加法,输出本位和 S 与进位 C。真值表只有四行:0 加 0 得 0 不进位,0 加 1 得 1 不进位,1 加 0 得 1 不进位,1 加 1 得 0 并向高位进 1。

ABS 本位和C 进位
0000
0110
1010
1101

写成表达式,S 等于 A 异或 B,C 等于 A 与 B。异或负责「相同为 0、不同为 1」,刚好对应本位和;与门负责「两个都为 1 才进位」。两个门就能搭出来,简单得让人以为多位加法也不过如此。

问题就在「没有第三个输入」。多位加法里,除了本位的两个加数,还要接收低一位传上来的进位。半加器没有这个入口,所以它只能算最低位,或者只能用在不需要进位的场合。拿它级联,低位的进位要么被丢掉,要么被硬接成另一个加数,结果都会错。

全加器:三个输入,两个输出

全加器,full adder,在半加器的基础上多了一个进位输入 Cin,输出仍然只有本位和 S 与进位 Cout。三个输入一共八种组合,真值表如下。注意输出为 1 的行:S 在输入有奇数个 1 时为 1,Cout 在至少两个输入为 1 时为 1。

ABCinSCout
00000
00110
01010
01101
10010
10101
11001
11111

表达式是:S 等于 A 异或 B 再异或 Cin;Cout 等于 A 与 B,或上(A 异或 B)与 Cin。前一项管「两个加数本身就进位」,后一项管「一个加数加进位才进位」。两个项或起来,覆盖了所有至少两个输入为 1 的情况。

全加器的门级结构:两个异或、两个与、一个或
A B Cin S Cout XOR XOR AND AND OR

从图上看,全加器比半加器多了第二个异或和第二个与门,多出来的部分就是为进位输入服务的。这个结构有一个好处:进位路径和求和路径分开走,求和走两级异或,进位走一级与加一级或。多条全加器级联时,和可以各自算,进位必须一位一位传,速度瓶颈自然落在进位链上。

行波进位:把四位串起来

把四个全加器串起来,最低位的进位输入接 0,低一位的进位输出接高一位的进位输入,最高位的进位输出就是整个加法器的进位 C4。四个本位和拼成 S3 到 S0,就是四位和。这种结构叫行波进位加法器,英文 ripple carry adder,进位像波浪一样从低位传到高位。

四位行波进位加法器:进位从 C0 一路传到 C4
C0 C4 FA0 FA1 FA2 FA3 S0 S1 S2 S3 A0 B0 A1 B1 A2 B2 A3 B3

行波进位的优点是结构规整、面积小、每一位完全一样,写代码或画原理图都很省事。缺点是进位必须串行传递:C1 要等第 0 位的进位算出来,C2 要等 C1,C3 要等 C2,C4 要等 C3。每一级进位大约要经过一个与门加一个或门的延迟,位宽 n 的加法器,最坏路径就是 n 倍的进位延迟。

四位还不明显,三十二位、六十四位就很致命。CPU 的主频往往由最慢的那条组合路径决定,而加法器经常就在这条路径上。行波进位的延迟随位宽线性增长,位宽翻倍,延迟也翻倍,这在高位宽处理器里是不可接受的。

实际芯片里,四位的加法器有现成型号,比如 74LS283、74HC283,内部已经做了进位优化,不是纯行波。多片级联时,低片的 C4 接高片的 C0,顺序不能反;如果接反,低位进位就传到了错误的方向,高位结果全错。级联时还要注意每片的进位输出极性,有些型号的进位是低有效。

进位、借位和溢出:同一个位,三种解释

无符号数看进位。四位无符号数最大是 15,两个数加起来超过 15,本位会回绕,进位 C4 为 1。比如 8 加 8 得 16,本位 0、进位 1;15 加 1 得 16,本位 0、进位 1。进位标志就是「有没有超出四位能表示的范围」。

有符号数看溢出。四位有符号数用补码表示,范围是负八到正七。最高位是符号位,0 表示非负,1 表示负数。两个正数相加得负数,或者两个负数相加得正数,就是溢出。检测方法是最高位的进位输入与进位输出异或:C3 异或 C4 为 1 表示溢出。这个信号和无符号进位 C4 不是一回事。

运算无符号解释有符号解释标志
8 + 816,超出 0 到 15负八加负八,超出范围C4 为 1,溢出为 1
7 + 18,没有超出 0 到 15正七加一得正八,超出负八到正七C4 为 0,溢出为 1
15 + 116,超出 0 到 15负一加一得零,没有溢出C4 为 1,溢出为 0
7 - 34,没有借位正七减三得正四进位 1,溢出 0
3 - 7借位,结果为负负四,在范围内进位 0,溢出 0

减法用加法器实现:A 减 B 等于 A 加 B 的按位取反再加 1。取反用异或门,每个 B 位和 1 异或就得到反码;加 1 就是把最低位的进位输入接 1。这样一套加法器加几个异或门,就能同时做加法和减法,代价是控制信号多了一根。补码的位级细节在位运算那一篇里讲得更细,这里只记住「取反加一」。这也是很多处理器里减法结果差一的原因:忘了那个加一。

超前进位:把进位提前算出来

行波进位慢,是因为每一位都要等前一位的进位。超前进位,carry lookahead,换了个思路:不等等,直接根据 A、B 算出「这一位会不会产生进位」和「这一位会不会传递进位」,再用两级逻辑把进位提前算出来。

定义两个信号。生成信号 G 等于 A 与 B,表示这一位自己就会产生进位,不管低位进不进来。传播信号 P 等于 A 异或 B,表示这一位本身不产生进位,但会把低位的进位传上去。有了这两个信号,第 i 位的进位可以写成:C(i+1) 等于 G(i) 或上 P(i) 与 C(i)。

把这个式子展开,四位块的进位就能写成只依赖 C0 的表达式:C1 等于 G0 或 P0C0;C2 等于 G1 或 P1G0 或 P1P0C0;C3 类似;C4 等于块生成 G* 或块传播 P* 与 C0。块生成是「块内自己产生进位」,块传播是「块内能把进位一路传过去」。这样 C1 到 C4 不用串行等待,可以并行算出来。

代价是门数增加,而且高位的与门扇入变大。四位的超前进位还能接受,八位、十六位直接展开,门数和扇入会爆炸。实际做法是分级:每四位一个超前进位块,块内并行算,块间再用一层超前进位把四个块的进位连起来。位宽再大就继续分层,形成一棵进位树。

并行前缀与进位选择:更快,但更贵

并行前缀加法器把「生成」和「传播」做成树。每一位先算出 G 和 P,然后两两合并:左边的块和右边的块合并后,新的生成等于右块生成,或右块传播与左块生成;新的传播等于两块传播相与。合并做 log2(n) 层,进位就能在 logarithmic 深度内算出来。Kogge-Stone 树深度最小、布线最多,Brent-Kung 树布线少、深度稍大,中间还有很多折中结构。

进位选择是另一种思路:把高位块算两遍,一遍假设低位进位是 0,一遍假设是 1,等低位进位到了,再用一个选择器选结果。面积差不多翻倍,但关键路径缩短,因为两遍计算可以并行。进位跳过则更轻量:如果一整块都处于传播状态,进位可以直接跳过这一块,不用逐位等。

下面这张表是简化延迟模型的对比,只算进位链的级数,不含求和和布线。行波进位按每位两级门延迟估算,并行前缀按 2 乘 log2(n) 加 2 估算。数字不是某个具体工艺的实测值,只用来看数量级差距。

位宽行波进位(门延迟)并行前缀(门延迟)差距
4 位86不明显
8 位168约两倍
16 位3210三倍多
32 位6412五倍多
64 位12814约九倍

这张表也说明了为什么低位宽时行波进位仍然常见:四位、八位差距不大,面积和布线简单反而更划算。位宽一上去,进位链就成为关键路径,这时候多花的门才值得。FPGA 里更特殊,综合工具会把加法映射到专用的进位链硬件,延迟和 LUT 实现完全不同,手写超前进位未必比直接写加号更快。

跑一遍:穷举四位加法器,验证和与溢出

下面这段 Python 用全加器的公式逐位模拟四位行波进位,穷举两个四位数的所有组合,比对整数加法的低四位结果,并统计不匹配的数量。然后找出有符号溢出的例子,最后打印简化延迟模型的对比。

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

def ripple4(a, b, cin=0):
    out, c = [], cin
    for i in range(4):
        s, c = full_adder((a >> i) & 1, (b >> i) & 1, c)
        out.append(s)
    return sum(out[i] << i for i in range(4)), c

bad = 0
for a in range(16):
    for b in range(16):
        s, cout = ripple4(a, b)
        if s != (a + b) & 0xF:
            bad += 1
print("pairs:", 16 * 16, "mismatches:", bad)
4-bit ripple adder checked pairs: 256
mismatches: 0
carry examples (a b sum carry):
   1 + 15 =  0, carry=1
   2 + 14 =  0, carry=1
   2 + 15 =  1, carry=1
   3 + 13 =  0, carry=1
   3 + 14 =  1, carry=1
   3 + 15 =  2, carry=1

signed overflow examples (a b raw sa sb sraw):
  1 7 8  1 7 -8
  2 6 8  2 6 -8
  2 7 9  2 7 -7
  3 5 8  3 5 -8
  3 6 9  3 6 -7
total signed overflow cases: 64

width | ripple gate delays (2n) | prefix depth (2*log2(n)+2)
    4 |                        8 |                      6
    8 |                       16 |                      8
   16 |                       32 |                     10
   32 |                       64 |                     12
   64 |                      128 |                     14

结果里,256 组输入没有一个和错误,说明四位求和本身的逻辑是对的;错误只会出在进位输出、位宽扩展和溢出判断上。有符号溢出一共 64 组,例子中 1 加 7 得 8,位模式是 1000,按有符号解释就是负八,正加正得负,典型溢出;但无符号看 1 加 7 等于 8,完全正常,进位也是 0。

现象对照:这些症状先查哪儿

加法器的故障往往不在「会不会加」,而在进位、位宽和符号解释。下面这张表按症状列,先定位再改电路或代码。

现象真实原因第一步查什么
低位结果对,高位结果错用半加器搭多位,低位进位没接进高位逐位检查全加器是否有三个输入,Cin 有没有接
8 加 8 得 0,进位标志也是 0最高位进位没引到输出,或标志接错位量 C4 和 carry 标志,确认连接关系
无符号结果对,有符号比较结果错把 C4 当溢出,或没做符号位判断查溢出逻辑是否为 C3 异或 C4
减法结果总是差一用了取反加一,但只取了反,没加一查减法时最低位 Cin 是否为 1
位宽加倍后主频明显下降行波进位链太长,关键路径在进位上看时序报告的最长路径,确认是否在进位链
手写超前进位后综合资源反而更多工具已自动优化,手写结构打乱了映射对比综合前后的资源和时序,别只看源码
两片四位加法器级联结果错进位输出接到下一片的进位输入时顺序或极性错量低片 C4 到高片 C0,逐位算一遍边界值
比较器偶尔误判加法器组合输出尚未稳定就被采样,毛刺进了比较看采样时刻是否在进位稳定之后,必要时打一拍

边界与代价

第一,加法器的面积和速度是一条曲线上的两个点。行波进位最省面积,但延迟线性增长;超前进位和并行前缀把延迟压到对数级,代价是门数、扇入和布线复杂度上升。没有哪种结构绝对更好,只有哪种更适合当前的位宽、工艺和频率目标。

第二,进位链的延迟只是加法器延迟的一部分。求和路径、输入缓冲、输出负载、布线都会贡献延迟。超前进位把进位算快了,如果求和异或链仍然很长,整体提升有限。时序优化要看整条路径,不能只盯进位。

第三,溢出标志不是进位标志。无符号运算关心 C4,有符号运算关心符号位溢出,两者不能混用。处理器通常同时提供进位、零、符号、溢出几个标志,软件按数据类型选对应的那一个。把 C4 当溢出,会在负加负、正加正这些边界上出错。

第四,位宽扩展要正确处理符号。无符号扩展直接在高位补 0;有符号扩展要复制符号位,否则负数会被当成大正数。加法器本身只认位,不认符号,符号解释是外围逻辑和软件的事。跨位宽运算时,先做扩展,再送加法器,顺序错了结果就错。

第五,FPGA 和 ASIC 的加法器实现差别很大。FPGA 有专用进位链,综合工具会把加号映射成快速进位结构,手写行波或超前进位反而可能更慢;ASIC 里则要自己权衡标准单元的面积和延迟。下一篇把这些模块拼成 ALU,会看到加法器只是运算器的一部分,选择器、逻辑单元和标志逻辑都要一起考虑。

今天就能验证的五个练习

  1. 用纸笔写出全加器的八行真值表,再用布尔代数从真值表推出 S 和 Cout 的表达式,确认和本文一致。
  2. 用 Python 实现四位行波进位,穷举 0 到 15 的所有组合,验证和等于整数加法的低四位,并统计进位为 1 的组合有多少组。
  3. 用同一段代码做减法:把 B 取反、Cin 接 1,验证 7 减 3 得 4、3 减 7 得负四的位模式,并解释进位为什么是 0。
  4. 画出四位超前进位的 G、P 信号和 C1 到 C4 的表达式,数一数每个进位最多经过几级门,再和行波进位比。
  5. 找一颗 74LS283 或 74HC283 的手册,把它的进位输入、进位输出和级联方式抄下来,说明两片级联成八位时哪根线接到哪根线。

收束:加法器是运算器的骨架

半加器只会算两个一位数,全加器多了进位输入,四个全加器串起来就是行波进位。行波进位慢在进位要排队,超前进位用生成和传播把进位提前算出来,并行前缀再把进位做成树。无符号看进位,有符号看溢出,减法靠取反加一,这三件事把加法器的边界划清楚了。

但加法器只能算加法,真正的运算器还要做与、或、异或、比较、移位,还要输出零、进位、符号、溢出几个标志。下一篇把这些部件拼成 ALU:加法器负责算术,逻辑单元负责位运算,选择器负责选结果,控制信号负责选操作。这一篇的进位和选择器,到那里会再出现一次。