编码：二进制加法器

1 前言

  本文是基于《编码》、《穿越计算机的迷雾》两部著作进行读后整理的记录性博客。对书中较为重要的内容进行归纳整理进行二次创作，略去了繁琐的讲述细节，力求简明扼要。

---

编码：一种由若干符号和规则组成的系统，用来向计算机表述指令。

2 正文

2.1 二进制加法器

  加法是算术运算中最基本的运算，因此如果想搭建一台计算机（这也正是这两本书所隐含的内容），那么首先就要造出可以计算两个数的和的器件。

  本文中我们将基于前文介绍的开关、灯泡、导线、电池、逻辑门等这些简单的元件搭建一个二进制加法器。这个加法器完全用于二进制数的计算，而且没有现代加法器那么便利。你不能使用键盘来给出需要相加的两个数，相反所要用到的是一排开关。计算结果是通过一排灯泡来显示的，而非以数字的形式来显示。但是，这个加法器确实可以将两个数相加，其方法与计算机计算加法的方式非常相似。

  在开始构建二进制加法器之前，我们先来回顾一下我们小学学习的十进制加法的运算规则。在实际做加法的时候，要将被加数和加数从右边对齐，而开始计算的时候，也同样是从最右边的那一列开始。

十进制加法示意图

  首先是 5+7，“5 加 7 等于 2，进 1”，得到结果 “2”，并向左产生一个进位。现在左边只剩下“1”了，因为这一列只有它自己，所以通常是直接拽下来，作为结果的一部分。但是别忘了，这一列上还趴着一个进位。所以，我们还要再 “1加1等于2” 来得到这一列的结果 “2”。至此，我们已经完成了这道加法题，结果是 22。

  通过对十进制加法规则的回顾，我们了解了加法的运算规则。二进制和十进制类似，加法的计算方式和十进制一样，但需要注意的是由于进制的不同，两者之间还是存在细微的差别。类比于十进制，二进制加法时，需要知道：1 加 1 等于 0，进 1。和十进制加法一样，二进制情况下两个要加起来的数先是右对齐，然后从最右边的列开始计算。

二进制加法示意图

  任何一个二进制数都是由一个以上的比特组成的，是一个比特串。为了突出组成它的每个比特，一个二进制数可以表示成：

  在这里， 都是单个的比特，是这个二进制数的每一位。让我们来看看，随便两个二进制数相加时会怎样，比如：

  它们可以是任意两个数。照惯例，要先把它们右对齐，叠在一起，如下图所示。

两个二进制数相加

  因为最先相加的是最右边那一列，即 和 ，所以这里没有从其他列来的进位，属于单纯的两个比特相加。如下图所示，这里有 4 种可能的情况。

最右侧比特位相加

  接着我们考虑右侧第二列的情况，这一列与前面一列不同，它可能会接受到来自前一位（最右侧）的进位，这样这一列实际上就是三个比特相加。如果最右边一列产生了进位，那么这一列实际上是另外 4 种可能，如下图所示。

存在进位时的相加情况

  结合上述讨论结果，就得到了二进制加法在这一列上做加法时，所有可能出现的情形，共 8 种。而且我们需要明确如果产生进位，这个进位必定是 1。

  既然加法都是按列进行的，而且每一列的计算过程都一样，那么完全可以设计一个电路来完成每一列的相加过程，如下图所示。

全加器示意图

  在图中， 和 分别是来自被加数和加数的一个比特，它们位于同一列上； 是来自右边一列的进位； 是本列产生的进位； 是本列的 “和”。为了表明这个电路的用途，我们在图的中间加了一个符号 “∑”。

  在这里我们先略去电路的内部构造，我们直接结合相加时的情况构思出上述一个设备，这个设备能够接受来自前一列的进位并将二进制加法中每一列的相加计算出结果，输出该列向下一列的进位和计算结果。

半加器
半加器仅仅是把来自被加数和加数的两个比特加起来，产生一个 “和” 以及一个进位，并不考虑从其他列来的进位。全加器则不然，它真正实现了二进制加法中每一列的加法过程，所以它才叫做 “全加器”。

  有了全加器，解决了二进制加法过程中每一列的计算问题，那么，我们可以搞一大堆全加器，根据被加数和加数的比特数，把它们串联起来组成一个完整的加法电路，下图显示了这一过程。

由 3 个全加器组成的 3 比特加法机

  观察上述加法机可以发现 3 比特位的加法机结果是 4 比特，即四个输出结果。可以看出，第一个（左下角那个）全加器的进位输入端没有使用，意思是 “没有进位输入”，或者 “从后面来的进位是0”。其余的全加器，它们的进位输入端都和前一个全加器的进位输出端相连，意思是 “前面的，你产生进位了吗？如果有，我得加上它”。 是最后一个全加器产生的进位，由于这是最后一个全加器，所以它的进位也是最终结果的一部分。

  构思设计完成后，我们在结合前文已知的知识来进行具体实现。我们再来分析一下二进制加法中一列加在一起的情况：

  观察进位结果表时我们不难发现它与我们与门的输出结果时一样的。因此我们利用与门可以计算两个二进制数加法的进位。

  观察加法结果表时，我们发现加法结果表和或门相似，除了右下角的结果。与非门同样和我们想要的结果很相似，除了左上角的结果。

加法结果表	或门	与非门

  那么我们可以结合两个逻辑门的特点实现加法结果表，我们将或门和与非门连接到相同的输入上，如下图所示。

  下表总结了或门和与非门的输出，并将其与我们想要的结果进行了对比。

  注意，我们想要的是 1，那么这种情况只有在或门和与非门的输出都为 1 时才会出现。这表明两个输出端可以通过一个与门连接到一起。而这也就是我们想要的结果。

  实际上这个电路有个专门的名称，叫做异或门，简写为 XOR。之所以称为异或门是因为若想其输出结果为 1，要么仅让输入 A 为 1，要么仅让输入 B 为 1，两输入端都为 1 则输出为 0。们可以使用一个电气工程师所采用的特定电气符号来表示异或门，如下图所示。

异或门

  异或门在输入端比或门多出了一条曲线，除此之外它看上去和或门非常相像。异或门的特征如下表所示。

同或门
只有当两个输入相同的时候，其输出才为1。同或门所给出的输出刚好与异或门相反，因此同或门的符号和异或门相同，但在输出端多了个小圆圈。

  两个二进制数相加的结果是由异或门的输出给出的，而进位位是由与门的输出给出的。因此我们可以将与门和异或门连在一起来计算两个二进制数（即 A 和 B）的和。

  结合我们前文介绍的半加器，可以发现上述组合即为我们的半加器，不考虑前一位的进位，只考虑这一列相加的结果以及向下一位的进位。半加器没有做到将之前一次的加法可能产生的进位位纳入下一次运算。

半加器

  在二进制加法计算时，我们只能将半加器用于最右面一列的相加，对于从右面算起的第二列，由于进位位的存在，实际上需要将三个二进制数相加，而随后每一列的加法都是这样的。随后的每一列二进制数相加都需要将进位位算进来。

  为了对三个二进制数进行加法运算，我们需要将两个半加器和一个或门做如下连接。从而使得半加器能够实现对任意比特位的相加。我们选取二进制加法时的中间的比特位相加的场景，在这种情况下，相加时需要考虑下一位的进位，这一列相加的结果以及该列向下一列的进位情况。

  先略去中间的电路情况，观察输入和输出情况，输入 A 和输入 B 即为该列的两个比特位的值，进位输入即为上一列向这一列的进位。最后输出即为这一列的加和结果以及该列向下一位的进位。

示例

  先看输入 A 和输入 B 的半加器，在这个半加器中先不考虑上一列向这一列的进位直接将这一列的比特位加起来，得到这两个比特位的计算结果以及进位。之后我们便利用第二个半加器将上一列向这一列的进位（即进位输入）和这一列的加和结果相加，得到最终的加和输出以及进位，最后将两个半加器的进位利用或门得到最终的进位输出。两个半加器的进位输出又被输入到一个或门中。你可能会觉得，这里还需要一个半加器，这当然是可行的。但是如果你了解了所有的可能性之后，你会发现，两个半加器的进位输出是不会同时为 1 的，那么两个半加器的进位在其他情况下的结果和或门相同。当然采用异或门也能达到相同的效果，因为或门除了在输入都为1的时候以外，其他情况下结果和异或门结果相同。

  下图是结合上述过程进行演示的示例计算过程的拆解图：

计算过程

  为了避免重复地画上面的那个图，我们用以下形式来替代上图中的一堆符号，它也即我们前面想要实现的全加器（Full Adder）。

全加器

  构建二进制加法器的时候我们可以将多个全加器连接起来，每个全加器的进位输出都作为下一个全加器的进位输入。

  下面是画成一个盒子的完整的 8 位二进制加法器，输入标记为 和 ，输出标记为 。

8 位二进制加法器

  一旦你搭建起了 8 位二进制加法器，你就可以再搭建另外一个加法器。把它们级联起来就可以很容易地扩展出一个 16 位加法器。

16 位加法器

3 小结

  编码：二进制加法器篇总结了利用前文介绍的简单电子器件创建的二进制加法器的实现。为了精简内容删减了部分较为详细的书写，仅作为整理总结。