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