加法器
复习
- 第二章:知道了计算机由输入设备、存储器、运算器和输出设备组成,这个体系目前还在沿用
- 第三章:了解了计算机使用二进制(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 国际许可协议进行许可。
封面图
设计师 | 南国微雪