简易加法器的实现

发表于 分类于 阅读次数：

作者：小牛呼噜噜 | https://xiaoniuhululu.com
计算机内功、JAVA底层、面试、职业成长相关资料等更多精彩文章在公众号「小牛呼噜噜」

普通人对CPU，第一印象是神秘高端，但又耳熟能详，因为常常能听到新闻中提到芯片慌，中国芯等等。CPU是芯片的一种，也是超大规模的集成电路的一种，我们每天非常熟悉的开、关灯的开关，其实就制造CPU的关键。这里我就不再解释了，感兴趣的，可以去看看上一篇文章聊聊开关和CPU之间故事。

给我足够多的开关，我就能制造出CPU出来，就是这个需要的数量非常庞大。

本文就具体看看开关是如何实现CPU中的计算单元之一加法器的。

半加器

半加器，指对两位二进制数实施加法操作的元器件。它具有2个输入端A和B,还有输出端S,进位数C

我们先来了解一下其真值表：

A B S C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

观察A、B与S,A、B与C的关系，我们很容易就找到他们之间的关系表达式：

有了表达式，我们发现AB可以通过异或门得到S,从而实现最简单的整数加法， 我们也就能画出其电路图了

我们将这个电路封装一下，模拟一下效果：

模拟的结果，和我们真值表中一致。

全加器

半加器能产生进位但是不能处理进位，这个时候全加器就应运而生了。它们本质上是一样的，半加器不能处理进位的原因是由于，当加数和被加数之和达到二位时，还需要再加上来自个位的进位信号，也就是说一共需要三个数进行相加，才能得到结果。也就是说将两个半加器和一个或门，就能组合成一个全加器。

全加器比半加器多一个接收进位的输入端，这样全加器每一次都要考虑来自低位的进位，而半加器不用考虑，直接把两个二进制数相加就行。

当输入3位数中，任意1位为1的话，不会触发进位，结果为1;任意2位为1的话，必有一个半加器进位，结果为2;当3位都是1个话，会触发2次进位，但由于有或门的存在，会保证最终只有一个进位，这也就保证了结果为3。
我们将这个电路封装一下，模拟一下效果：

行波进位加法器

现在的全加器，每次只能对一位(bit)进行操作，所能表示的信息太少了，如果我们想要对一个字节的信息进行加法操作怎么办？
由于1个字节=1个比特，我们只需将8个全加器串联即可，16,32,64位依次类推，只需串联对应数量的全加器即可。我们来看一个8位加法器的电路图：

8个全加器串联，将低位的输出和高位的进位输入相连即可,输入选择8位管脚的，并使用分线器，注意分线器箭头指向的方向表示低位。输入A和全加器的输入A端，高位和高位，低位和低位一一对应相连；输出也选择8位管脚，电路和输入雷同；最后再连接进位输入和进位输出。

真值表太大了，就不贴了，我们来模拟一下看看效果：

上图的计算过程，相当于
(0000 0001)2 + （0000 0001)2 =(0000 0011)2 =[2] =2
(0000 0011)2 + （0000 0001)2 = [3]+[1] =4
(1111 1111)2 + （0000 0001)2 = [255]+[1] =256

需要注意的是，这种串联全加器，在最低位，没有来自更右侧的进位了，我们让其进位输入始终是0即可。
在最高位的输出进位信号，不仅表示的是进位信号，还更是是否溢出的标志。当这里大家终于明白了计算机为什么能自动地识别加法结果是否溢出了：从硬件层面，当加法结果溢出时，电路就会产生溢出的信号，这也是我们现代计算机的判断溢出的原理，让笔者不进感叹真是玄妙啊！

但是这种串联式全加器，由于高位运算需要等待低位是否有进位，是有延迟的。加法器总体的速度等于加数的位数乘以单个全加器的速度,这种全加器也叫行波进位加法器(RCA)

关键路径和门延迟

那么我们一般如何对电路进行性能分析？

找出其中的最长路径，也就是找出所有的从输入到输出的电路连接中，经过的门数最多的那一条。所有的从输入到输出的电路连接中，经过的门数最多的一条路径（延迟最长的路径），也称为关键路径

输入信号进入到这块电路之后，在连接线上传递需要花时间，称为线延迟，经过各种门，需要花时间，称为门延迟

我们对电路进行性能分析时，主要关注门延迟。如果把每一个门延迟都记为T，首先在每个全加器内部，都要经过2T个延迟，还要加上最开始的这一个门延迟，对于四位的行波进位加法器，一共是9个门延迟，如果是N位的行波进位加法器，就是一共2N+1个门延迟。

比如对于8位的行波进位加法器，一共是17个门延迟，性能与如今的加法器差距有点大的，如今的加法器中，还使用了一种超前进位方式的电路。

超前进位加法器

由于行波进位加法器，最主要的问题是高位的运算必须等待低位的“进位输出信号”，造成延迟时间过大。

超前进位加法器（Carry-Lookahead Adder , CLA），比如一个4位的超前进位加法器，仍然由四个全加器构成，但是每个全加器的进位输入不是来自前一级的加法器，而是来自一个统一的超前进位逻辑。对于每一个进位，只需要三级门延迟就可以计算出来，然后进入到全加器中，最后一级全加器还需要1级门延迟才可以计算出对应的信号，因此对于超前进位加法器总的延迟时间为4个门延迟。

超前进位加法器的门延迟与加法的位宽度是没有关系的，但如果进一步拓宽加法器的位数，则电路变得非常非常复杂。

如果采用完全的超前进位，理想的总延迟时间为4级门延迟，实际上电路过于复杂，难以实现。通常的实现方法是采用多个小规模的超前进位加法器拼接而成一个较大的加法器，例如采用4个8位的超前进位加法器连接成32位加法器。

这里就不展开解释了，公式推导和电路图都比较复杂，感兴趣地，推荐阅读->加法器的优化

小结

本文的加法器，从基本电路>门电路>半加器>全加器>加法器,就像搭积木一样，分层封装。封装带来的好处是显而易见的，可以通过”简单的指令”来实现复杂的操作，但是避免不了的是 明明可以使用基础的电路就能实现操作，使用封装后的电路，虽然简单了，但需要更多的电路，速度也就变慢了。

性能和封装往往需要取舍， RISC 和 CISC 这样的复杂/精简 指令集孰优孰劣呢？

本文主要是通过逻辑电路实现不带符号的整数加法运算，那如果整数是带符号的加法运算，或者说减法运算逻辑电路该怎么实现呢？大家可以思考一下，我们后面再慢慢道来。

参考资料：
《深入理解计算机系统》
《编码：隐匿在计算机软硬件背后的语言》
《深入浅出计算机组成原理》
https://www.cnblogs.com/dreamingoutloudly/p/13138304.html
https://www.cnblogs.com/houhaibushihai/p/9266868.html
https://www.cnblogs.com/yiquwange/p/14988026.html

本篇文章到这里就结束啦，很感谢靓仔你能看到最后，如果觉得文章对你有帮助，别忘记关注我！
计算机内功、JAVA源码、职业成长、项目实战、面试相关资料等更多精彩文章在公众号「小牛呼噜噜」