8位全加器原理

读《编码-隐匿在计算机软硬件背后的语言》一书有感。 该书从日常生活沟通场景着手，谈到编码，然后由编码讲解了莫斯编码、布莱叶盲文的历史背景和原理，剖析了编码背后的含义，阐述了编码的重要性，进一步讲到了电报机，从电报机讲到继电器，然后由继电器讲到逻辑门，从逻辑门讲到加法器，从加法器讲到存储、总线、芯片、微处理器、计算机总线、操作系统等等，内容广泛而不失深度，从历史背景一步步讲到原理，一气呵成的感觉。 非常推荐这本书。

在高中，我们学到了电的一个重要特性即电的磁效应。 在一根铁棒上面缠绕足够多的导线，然后将导线连接在电池的正负两极，此时铁棒就会有磁性。 如下图

利用电的磁效应，我们可以做出继电器，一种将信号放大的装置。 如下图

在长距离的电报通信过程中，电流会随着路程的增大而衰减。此时就可以在中间布设一个或多个继电器将电信号传递下去（将一个微弱的电流信号变成一个更强的电信号）。

同时，利用继电器闭合或断开电路的特性。 我们也可以做出各种各样的逻辑电路（当然这其中有逻辑学的发展历程，可以阅读《编码》一书详细了解）。

在逻辑学中有以下几种逻辑条件及其结果，即

与门，一假及假，其真值表如下：

AND	0	1
0	0	0
1	0	1

或门，一真即真，其真值表如下：

OR	0	1
0	0	1
1	1	1

非门就比较简单了，输入0时为1 ，输入为1时为0，即取反。

与或非也就是高中所学的知识，但是当时没有与计算机联系起来。但其实就是这几种逻辑门极大的促进了计算机的发展。

制作一个全加器，从简单的情况入手。先只考虑一位二进制数的加法，两个二进制数分别取0和1时总共有四种情况，不同取值及对应的和如下表，A、B分别代表两个一位的二进制数：

A	B	SUM
0	0	0
0	1	1
1	0	1
1	1	10

可以看到表格中最后一个单元格数是10 （二进制表示），因为1+1=2导致二进制发生了进位。将进位信息添加到表格最后一列后，然后尝试从表格数据中寻找使用逻辑门电路的替换方法。

A	B	SUM	CARRY
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

从上述表格可以看到，每一行的进位信息和与门的真值表是一致的，故我们可以采用与门来表示进位信息。 但是通过比较发现，和的当前位的值无法直接使用上面的逻辑门电路来表示。 如何处理呢？

仔细分析表格中SUM列的数据，可以发现，SUM只有在A和B不同的时候才为1，这种情况可以使用异或门来模拟。（此处是了解了异或门之后才会知晓，书中是通过将与门与或门尝试组合得到的规律）

我们将与门和或门及其对应的非门每种取值情况列出，方便我们从中找到规律。

A	B	AND	OR	NAND（与非）	NOR（或非）
0	0	0	0	1	1
0	1	0	1	1	0
1	0	0	1	1	0
1	1	1	1	0	0

将AND、OR、NAND、NOR这几列尝试进行与或非的计算，发现将OR和NAND进行与计算，则可以达到想到的逻辑值，即两个值不同时，结果为1，相同时为0. （这种门也成为异或门，即两个值相异结果才为1，否则为0）

为了绘制这个加法器，先罗列一下各种逻辑门的绘图表示方式

与门的符号图如下：

或门的符号图如下：

非门的符号图如下：

非门

根据上面找到的规律，可以使用异或门来表示和的信息，使用与门来表示进位的信息。

绘制出电路符号图如下：

表示和的逻辑电路图

如上电路图的专有表示符号如下，后面用这种逻辑符号代替上面的异或电路图。

xor电路图符号

但是该加法器只能处理没有进位的两个二进制位，如果遇到了有进位信息的加法就无法工作了。所以该加法器也只成为半加器（与之对应的是全加器）。

在改进半加器之前，可以考虑一下，如何处理进位信息。 书中有一句话，让我印象深刻，即每一位上的二进制加法其实是三个数的加法（与原文可能略有出入）。 这三个中就包括了进位了。

这让我联想到了leetcode上一道题。摘录该题如下：

在此处摘录此题，是因为在解答该题时先设置了一个默认的进位为0，然后每个节点计算时都更新这个进位节点。

同时附上python版的解法，代码如下：

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        delta = 0

        dummy = ListNode(-1)
        head = dummy
        while l1 is not None or l2 is not None:
            a = 0 if l1 is None else l1.val
            b = 0 if l2 is None else l2.val
					
						// 从这里可以看出其实是三个数的加法
            total = a + b + delta
            delta = total // 10
            tmp = total % 10

            n = ListNode(tmp)
            head.next = n
            head = n

            if l1 is not None:
                l1 = l1.next

            if l2 is not None:
                l2 = l2.next

        if delta != 0:
            head.next = ListNode(delta)
        
        return dummy.next

有了这个思想，我们可以使用三个数相加来实现一个全加器。 既然一个半加器可以处理两个数的相加，那么可不可以将两个半加器连接起来实现一个全加器呢？经过尝试，可以尝试如下方式将两个半加器连接起来，然后通过列出真值表来验证其正确性。

一位的全加器

注意，在上面的电路图中，使用了一个或门来计算总体的进位信息。 可以这样理解，相当于是A和B

先进行计算，然后其结果在和进位计算，这两个计算过程中只可能有一个进位信号产生，故使用或门，只要两个计算中有一个进位产生，那么最终就输出进位信号。

列出A与B相加，带有进位信息的预期值如下表

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

通过核对真值表发现，该电路完全可以实现两个二进制相加的各种结果。

虽然这只能处理一位二进制的全加器，但是如果我们将8个全加器按如下方式连接起来，那么我们就实现了一个8为的全加器。

由于绘制繁琐，于是将上述的全加器进行一个抽象（在计算机领域经常使用抽象来屏蔽一些复杂的实现细节，这样便于学习）。

总体上看，全加器是一个有三个输入，两个输入的逻辑电路，简化如下（复制《编码》一书中的图）：

Full Adder

如上的全加器只能完整的处理一位二进制的加法，如果将多个全加器按照一定规则连接起来，那么就可以实现多位二进制的加法了。 如连接8个全加器，实现8位二进制的加法，如下图：

8位全加器

将输入A、B及输出的绘制方式改一下，即将输入A的线路放在一起，输入B的线路放在一起，同理加和的输出也放在一起，绘制后的电路图就如下：

抽象8位加法器

如果将8位输入A在进一步抽象，用一个线条表示8位输出。同理输入B及输出S，可以得到下列抽象的8位全加器表示图，如下：

8位全加器抽象表示图

至此，我们得到了在各种书籍上看到的8位全加器表示图了。 有了上面的理解后，以后在看到这样的全加器表示图就不会在陌生了并且疑惑了。它们的背后是简单的逻辑电路的各种组合，通过这种简单的组合达到我们的目的。