第一次用半加器搭多位加法器的人,几乎都会踩同一个坑。做两位加法,第一版用了两个半加器,一位一位算。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。
| A | B | S 本位和 | C 进位 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
写成表达式,S 等于 A 异或 B,C 等于 A 与 B。异或负责「相同为 0、不同为 1」,刚好对应本位和;与门负责「两个都为 1 才进位」。两个门就能搭出来,简单得让人以为多位加法也不过如此。
问题就在「没有第三个输入」。多位加法里,除了本位的两个加数,还要接收低一位传上来的进位。半加器没有这个入口,所以它只能算最低位,或者只能用在不需要进位的场合。拿它级联,低位的进位要么被丢掉,要么被硬接成另一个加数,结果都会错。
全加器:三个输入,两个输出
全加器,full adder,在半加器的基础上多了一个进位输入 Cin,输出仍然只有本位和 S 与进位 Cout。三个输入一共八种组合,真值表如下。注意输出为 1 的行:S 在输入有奇数个 1 时为 1,Cout 在至少两个输入为 1 时为 1。
| A | B | Cin | S | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
表达式是:S 等于 A 异或 B 再异或 Cin;Cout 等于 A 与 B,或上(A 异或 B)与 Cin。前一项管「两个加数本身就进位」,后一项管「一个加数加进位才进位」。两个项或起来,覆盖了所有至少两个输入为 1 的情况。
从图上看,全加器比半加器多了第二个异或和第二个与门,多出来的部分就是为进位输入服务的。这个结构有一个好处:进位路径和求和路径分开走,求和走两级异或,进位走一级与加一级或。多条全加器级联时,和可以各自算,进位必须一位一位传,速度瓶颈自然落在进位链上。
行波进位:把四位串起来
把四个全加器串起来,最低位的进位输入接 0,低一位的进位输出接高一位的进位输入,最高位的进位输出就是整个加法器的进位 C4。四个本位和拼成 S3 到 S0,就是四位和。这种结构叫行波进位加法器,英文 ripple carry adder,进位像波浪一样从低位传到高位。
行波进位的优点是结构规整、面积小、每一位完全一样,写代码或画原理图都很省事。缺点是进位必须串行传递: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 + 8 | 16,超出 0 到 15 | 负八加负八,超出范围 | C4 为 1,溢出为 1 |
| 7 + 1 | 8,没有超出 0 到 15 | 正七加一得正八,超出负八到正七 | C4 为 0,溢出为 1 |
| 15 + 1 | 16,超出 0 到 15 | 负一加一得零,没有溢出 | C4 为 1,溢出为 0 |
| 7 - 3 | 4,没有借位 | 正七减三得正四 | 进位 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 位 | 8 | 6 | 不明显 |
| 8 位 | 16 | 8 | 约两倍 |
| 16 位 | 32 | 10 | 三倍多 |
| 32 位 | 64 | 12 | 五倍多 |
| 64 位 | 128 | 14 | 约九倍 |
这张表也说明了为什么低位宽时行波进位仍然常见:四位、八位差距不大,面积和布线简单反而更划算。位宽一上去,进位链就成为关键路径,这时候多花的门才值得。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,会看到加法器只是运算器的一部分,选择器、逻辑单元和标志逻辑都要一起考虑。
今天就能验证的五个练习
- 用纸笔写出全加器的八行真值表,再用布尔代数从真值表推出 S 和 Cout 的表达式,确认和本文一致。
- 用 Python 实现四位行波进位,穷举 0 到 15 的所有组合,验证和等于整数加法的低四位,并统计进位为 1 的组合有多少组。
- 用同一段代码做减法:把 B 取反、Cin 接 1,验证 7 减 3 得 4、3 减 7 得负四的位模式,并解释进位为什么是 0。
- 画出四位超前进位的 G、P 信号和 C1 到 C4 的表达式,数一数每个进位最多经过几级门,再和行波进位比。
- 找一颗 74LS283 或 74HC283 的手册,把它的进位输入、进位输出和级联方式抄下来,说明两片级联成八位时哪根线接到哪根线。
收束:加法器是运算器的骨架
半加器只会算两个一位数,全加器多了进位输入,四个全加器串起来就是行波进位。行波进位慢在进位要排队,超前进位用生成和传播把进位提前算出来,并行前缀再把进位做成树。无符号看进位,有符号看溢出,减法靠取反加一,这三件事把加法器的边界划清楚了。
但加法器只能算加法,真正的运算器还要做与、或、异或、比较、移位,还要输出零、进位、符号、溢出几个标志。下一篇把这些部件拼成 ALU:加法器负责算术,逻辑单元负责位运算,选择器负责选结果,控制信号负责选操作。这一篇的进位和选择器,到那里会再出现一次。