全加器
复习
- 从真值表到逻辑表达式：能从真值表写出逻辑表达式，再据此搭出电路
- 常见复杂逻辑门：异或、同或和多路选择器等复杂逻辑门能由基本门组合而成
- 半加器：半加器用异或门算和、与门算进位，完成两个一位二进制数相加
TL;DR
- 全加器可以处理三个输入：两个加数和一个进位
- 全加器由两个半加器和一个或门组成
- 1 个 1 位全加器可以串联用来构建多位加法器，实现任意位数的二进制加法
正文
上一章我们设计了半加器，可以完成两个一位二进制数的加法。但是在计算多位二进制数时，我们发现半加器不能处理来自低位的进位。
比如计算 11 + 01：
1 1 (3)
+ 0 1 (1)
-------
1 0 0 (4)
从右往左计算：
- 最低位：1 + 1 = 10₂，需要进位
- 次低位：1 + 0 + 1（来自低位的进位）= 10₂
我们需要一个能处理三个输入的全加器。
加法器的真值表
全加器有三个输入：两个加数（A 和 B）和一个进位输入（Cin，Carry in），两个输出：和（Sum）和进位输出（Cout，Carry out）。为了方便观察，将几个中间值也纳入真值表里：
- A + B 的第一个和 S1、第一个进位 C1
- S1 + Cin 的第二个进位 C2
- S1 + Cin 的和直接作为最终和（Sum）输出了，所以不是中间值。
带中间值的真值表如下：
| A | B | S1 | C1 | Cin | C2 | Sum | Cout |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
不带中间值的真值表如下：
| A | B | Cin | Sum | 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 |
全加器的构成
仔细观察上述真值表，可以看出最终的进位输出 Cout 就是两个中间进位的或：只要 C1 和 C2 中有一个为 1，就代表最终有进位。
我们可以用两个半加器和一个或门来构建全加器：
-
第一个半加器：
- 输入：A 和 B
- 输出：第一个和（S1）和第一个进位（C1）
-
第二个半加器：
- 输入：第一个和（S1）和进位输入（Cin）
- 输出：最终和（Sum）和第二个进位（C2）
-
或门：
- 输入：两个半加器的进位（C1 和 C2）
- 输出：最终进位（Cout）
或者我们也可以直接用前面讲过的“从真值表写表达式”的方法，根据真值表书写表达式，再化简，再拼接基础逻辑门，效果等同。为方便书写，下面用 C 表示 Cin。
- 找出所有输出为真（即输出为 1）的输入组合
去除中间值，输出为 1 的真值表（Sum）：
| A | B | Cin | Sum |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
去除中间值，输出为 1 的真值表（Cout）：
| A | B | Cin | Cout |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
- 将这些输入组合用 “或” 连接（也即 + 号），输入组合的个数取决于输出为真的组合个数
每一行先按 A、B、C 的顺序写成一个与项。
- 针对每一个输入组合，如果有输入项为 0，就将该输入项取反
Sum = A̅B̅C + A̅BC̅ + AB̅C̅ + ABC
Cout = A̅BC + AB̅C + ABC̅ + ABC
化简后，Sum 就是三个输入的异或，Cout 则表示三个输入中至少有两个为 1：
Sum = A ⊕ B ⊕ C
Cout = AB + AC + BC
多位加法器
有了全加器，我们就可以构建多位加法器了。
将多位加法问题泛化：计算 A₃A₂A₁A₀ + B₃B₂B₁B₀（一个字母代表一个比特位）。产生 4 个子问题：A₃ + B₃，A₂ + B₂，A₁ + B₁，A₀ + B₀。因为不知道哪个问题会产生进位，所以均需要加上进位构成全加器。
比如 4 位加法器。从上往下，每一位都用一个全加器，前一个全加器的进位输出连接到下一个全加器的进位输入。注意，图中的低位在左边，高位在右边。
这种加法器叫做串行进位加法器（Ripple Carry Adder，简称 RCA，也称行波进位加法器）。
如果需要计算 8 位，将加法器扩展成 8 位的样子即可，16、32、64 位同理。如果最高位（即二进制最左边的那一位）产生进位，代表超出了此计算机的数据范围。这里简单丢弃，后续再处理。
思考题 1
我们已经可以做加法了，那减法呢？
效率？
需要说明的是，将全加器直接串联起来构成的串行进位加法器， 尤其懒惰和低效 。现代电子所用的加法器，经过优化，速度更快。 但无论如何，我们已经拥有加法器了。
本指南侧重如何构成加法器 ，不涉及加法器的优化，所以之后提到加法器时，默认已经过优化，效率比此章设计的加法器要高。
思考题 2
由于进位未知但不可缺少，每个全加器都要等待低位的进位，所以效率极低。
如果每个全加器耗时 0.1 秒，那么 8 位将耗时 0.8 秒。而现代 PC 基本都是 64 位，意味着做一次加法需要 6.4 秒。
有什么办法能优化这种速度吗？
小结
知识点
- 一位全加器
- 串行进位加法器或行波进位加法器：RCA
参考资料
- Wikipedia(zh)：全加器：全加器的详细工作原理
- Wikipedia(zh)：二进制：二进制的基本概念
思考题答案（仅供参考）
思考题 1
减法实际上就是加上负数（或者加上这个数的相反数）。现在问题来到了怎样再计算机中表示负数。负数在计算机中用“补码”表示。可以用“补码”和加法器来实现减法。比如计算 A - B，可以先求 B 的补码（反码加1），然后用 A 加上 B 的补码。这是下一章要讨论的内容。
思考题 2
可以使用超前进位加法器（也称并行进位加法器）。分析依赖关系之后，可以将进位从串联改为并联，能一定程度上提高效率。但当规模特别大时，此加法器会导致晶体管或逻辑门的数量指数级上升。需要数字电路知识。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪