A5 组合逻辑

上回你用继电器搭出了一整套逻辑门——与、或、非、异或。发小对你的 3-8 解码器佩服得不行。现在你打算再挑战一件更刺激的事：让电路自己会算加法。

计算机的所有算术，归根结底都是加法。

谁还不会加法呢？但你一想到要让一堆灯泡和开关自己算出 13 + 9，就觉得这事没那么简单。先从最简单的开始——两个 1 位数的加法。

两张似曾相识的表

二进制只有 0 和 1，所以加法表比十进制简单太多了。两个 1 位相加，一共只有四种情况：

你盯着这两列看了半天，突然一拍大腿——这两列，怎么这么眼熟？

• 进位列：只有 A、B 都为 1 时才是 1。这不就是上一章的 AND（与门）吗？
• 和列：A、B 不同 时才是 1，相同 时是 0。这正是你刚发明的 XOR（异或门）。

半加器：会算一半的加法器

你把 XOR 和 AND 接上 A、B 两个输入。下面这个是真的能动的——试试点 A、B 两个开关，看电流怎么传：

但这玩意儿有个毛病：它只认 A 和 B 两个输入，不接受别人传来的进位。可你做多位加法时，每一位都得接收右边那位传来的进位啊。

所以这个只能算"一半"的加法器，你给它取名叫 半加器（Half Adder）——意思是只加了一半，剩下的一半被"鸽"了。

全加器：把进位也加进来

既然半加器只加了一半，那"半半得全"。你拿来两个半加器，把第一个的和位接到第二个的输入，再让第二个也接收外部进位 Cin，最后用 OR 门把两次产生的进位合起来——这就是 全加器（Full Adder）：

Sum = (A XOR B) XOR Cin ｜ Cout = (A AND B) OR ((A XOR B) AND Cin)

你来试试：让加法器跑起来

下面这个加法器已经搭好了 4 个全加器，串成一条链。输入两个二进制数（只填 0 和 1），看进位怎么一位一位往左传：

把全加器串起来：纹波进位

要做多位加法，就把全加器一个接一个串起来——低位的进位输出，直接接到高位的进位输入。下面是 4 位纹波进位加法器，拨开关试试进位怎么逐级"涟漪"：

进位从 bit0 一路传到 bit3，像水波纹一样向高位"涟漪"——所以这种加法器叫 纹波进位加法器（Ripple Carry Adder）。

以 13 + 9（1101 + 1001）为例：

位0: 1+1        = 0，进位 1
位1: 0+0+进位1   = 1，进位 0
位2: 1+0+进位0   = 1，进位 0
位3: 1+1+进位0   = 0，进位 1 ← 最终溢出

结果 10110 = 22。

进位的麻烦：它得一位一位等

到这里你发现一个闹心的问题。看上面那个链：位 1 必须等位 0 算完、把进位传过来，才能开始算；位 2 得等位 1……位 3 得等位 2。

这个延迟不是小问题。CPU 一个时钟周期可能就几百皮秒，如果一次加法要等进位从头传到尾，那 64 位 CPU 的加法指令会慢得没法用。纹波进位的延迟随位数线性增长，这是个会拖垮性能的坑。

你和发小对着这条长长的进位链犯愁：能不能别一位一位等？

超前进位：别等了，提前算

你盯着真值表看了半天，突然想到一个事：每一位到底进不进位，其实不完全取决于前一位。

拆开看一位全加器的进位输出 Cout，它由两部分相或而成：

Cout = (A AND B)  OR  ((A XOR B) AND Cin)

这两项各有名字，是超前进位的核心：

• 生成（Generate，G = A AND B）：A 和 B 都是 1，那么这一位自己就会产生进位，不管 Cin 是什么。
• 传播（Propagate，P = A XOR B）：A、B 不同时，这一位会把收到的进位 Cin 原样传出去。

能。把展开式一层层代入，你会发现每一位的进位都可以写成"几个 G、P 的与或式"。比如：

C1 = G0 + P0·C0          （只看第 0 位）
C2 = G1 + P1·G0 + P1·P0·C0   （前两位的 G、P）
C3 = G2 + P2·G1 + P2·P1·G0 + P2·P1·P0·C0   （前三位）

每一级进位都是一组 G、P 的组合，只要门足够多，所有进位可以同一时刻算出来。这就是 超前进位器（Carry-Lookahead Adder，CLA）。

代价是：位越高，公式越长、需要的门越多（电路面积和门延迟都会涨）。所以现实里的 CPU 用的是"分组超前进位"——每 4 位一组用 CLA，组之间再级联，既不是纯纹波也不是纯 CLA，是两者折中。

直观感受：纹波 vs 超前，差多少？

拖动下面的滑块选位数，看看两种加法器的进位延迟差几个数量级（假设每级门延迟 0.1ns）：

套娃，然后抽象

有了全加器，你就可以继续套娃——把全加器一个接一个串起来：

全加器 → 全全加器 → 全全全加器 → 全全全全加器 → 全全全全全全全全加器

"全全全全全全全全加法器"这个名字太长了，所以你干脆叫它：8 位加法器。两个 8 位加法器级联，又能算 16 位。

为了不让父母发现你没写作业而是在摸鱼，也为了省事，你决定把这一堆电路藏进一个盒子里，只露出输入和输出——这种把复杂集合体藏进简单包装里的做法，叫做 抽象（Abstraction），也叫封装。

把刚才那 4 位纹波进位加法器封进一个盒子，只留 A、B 两组输入开关和 Sum 输出灯，就成了一个 ADD4 黑盒。拨 A/B 开关，灯照样逐级亮起——你不必再关心里面那一堆全加器和进位链：

同理，8 个全加器串起来封进盒子，就是 ADD8。两个 8 位加法器级联，又能算 16 位。盒子越套越大，但你看到的接口始终只有"输入 → 输出"：

抽象，果然是人类智慧进步的阶梯。

从一个"通/断"的开关，到能做加法的电路，你已经走完了从信号到算术的整条路。但加法器只会算——它不会记。算完就忘，下一次还得从头来。怎么让电路记住上一次的结果？下一章，我们让输出绕回来，接回输入。