本篇目标：

1.以异或门为例，理解从真值表到组合电路的构造；

2.以相等判断逻辑为例，理解电路的模块级抽象；

3.搭建2路复用器；

4.搭建n路复用器；

5.理解二进制数以及补码表示法；

6.搭建1比特全加器；

7.搭建n比特加法器；

8.搭建n比特减法器；

9搭建n比特大小判断逻辑；

10.搭建算术逻辑单元ALU。

在上一篇中，我们理解了与或非逻辑门，那是我们造物的起点，太重要了，梅开六度，再复习一遍：

在本篇中，我们就要开始带着这仨逻辑门开始奇妙冒险了。在冒险的旅途中，我们会使用一个小巧讨喜的软件Logisim，这是下载地址：https://sourceforge.net/projects/circuit/，欢迎读者下载安装这个软件。运行该软件需要安装Java环境，这个不难，读者简单搜索一下就可以搞定了。让我们一起实现文档中的各种奇妙电路吧（搓手手.jpg）！

1.以异或门为例，理解从真值表到组合电路的构造

我们首先要整一个新的逻辑门，叫异或门，它要求是这样的：

AB俩输入相同，则得到0

AB俩输入不同，则得到1

我们一般会简称为“同0异1”。仿照上一篇的做法，可以得到一个真值表：

我们这里要学一个小技巧，也就是用数学表达式把Y等于多少A多少B写出来。首先，不难注意到，Y在两种可能的情况下会等于1，也就是A0B1和A1B0这两个。那我们就用“|”连接，写成这个样子：

Y = (情况1: A=0而且B=1) | (情况2: A=0而且B=1)

对于这俩情况，我们也要用数学表达式写出来，俩case就写成乘法形式，用“&”连接，也就是这样：

Y = ((A=0) & (B=1)) | ((A=0) & (B=1))

最后一步，把等于0的情况替换成取反，也即“~”符号，等于1的不用管，直接写变量名就可以，最后我们得到了Y的布尔代数表达式：

Y = (~A & B) | (~A & B)

好嘞，有了这个表达式，我们就可以画电路啦！符号“~”就是非门，符号“&”就是与门，符号“|”就是或门，于是乎，我们就可以把上面得到的表达式变成这样：

最后在软件里面把各种组合试验一下，是否符合预期，符合一开始的要求（暗绿色的线就是0，亮绿色的线就是1）：

诶嘿，完美匹配真值表，完美符合要求。刚刚我们的这个流程：理解需求，写出真值表，得到数学表达式，根据表达式连接电路。这一套就是我们得到组合电路的基本操作，希望读者可以get到~

2.以相等判断逻辑为例，理解电路的模块级抽象

这一部分我们的目标是搭建一个用于相当判断的电路模块，该模块有俩输入，要求是这样的：

AB俩输入相等，就得到1

AB俩输入不相等，就得到0

AB俩输入都是5比特

前两个要求，稍微琢磨一下还是很简单的，也就是把异或门的结果取个反就可以了。但是我们的异或门输入都是1比特的，而这次相等判断的输入是5比特的。诶嘿好像也简单，AB每一个比特分别判断，最后用与门全部连起来就可以了呀。

如果5组对比都把异或逻辑摆一道，显然就很累，我们可以把异或逻辑放在一个框框里面，只关注输入输出，不关注内部实现细节。这就是电路的模块级抽象，其实也就是套娃，后面要经常用，希望读者可以get到。

进一步地，异或后面紧紧跟着一个非门，我们可以把它们捏一块，这个逻辑门也是有名字的，叫同或门，真值表和电路如下：

类似的，一堆两输入与门也可以捏一块，捏成一个大的，这样一来，我们刚刚的相等判断逻辑就变成这样了：

诶嘿，我们还可以再进一步，这一整个相等判断逻辑也可以捏一块嘛，套娃继续，就变成这样：

这部分的电路本身比较简单，主要是要向读者展示电路的模块级抽象，这其实也是理工科很常见的思维方式，通俗地说起来就是套娃加套娃。我们从一开始的Si元素电子排布到P型掺杂、再到二极管、CMOS管、以及逻辑门，也是抽象再抽象。这个思维方式很重要哦，手动画个重点~

3.搭建2路复用器

我们再来整一个小电路，熟练一下这部分的玩法。这个电路叫2路复用器，它的要求是这样的：

当选择信号S等于0，输出信号Y等于A

当选择信号S等于1，输出信号Y等于B

OK，老套路，上真值表，这次是三个输入，真值表有8行：

继续我们的套路，写出Y的表达式，共有四种情况，用“|”连接：

Y = ( S=0且A=1且B=0) | ( S=0且A=1且B=1) |

 ( S=1且A=0且B=1) | ( S=1且A=1且B=1)

继续变换，且的逻辑用“&”，等于0就换成“~”，于是乎：

Y = ( ~S & A & ~B) | ( ~S & A & B) | ( S & ~A & B) | ( S & A & B)

然后就是上电路，按照表达式的意思连接：

好勒，搞定，很漂亮。稍有不足的是，这个电路其实可以跟简单的。奥秘就在Y的数学表达式上，我们先观察这一部分：

( S & ~A & B) | ( S & A & B)

可以发现当S等于1且B也等于1的时候。A取反可以触发，A不取反也可以触发，诶，变量A搁着闹呢？我们就可以把它去掉，也即：

( S & B) | ( S & B)

那如果这样的话，或两个一样的也没啥意思，浪费了，不妨直接：

S & B

嗯嗯，很漂亮！同理，另一边的表达式也可以化简：

( ~S & A & ~B) | ( ~S & A & B) = ( ~S & A) | ( ~S & A) = ~S & A

哦吼，这样一来，Y的表达式就是：

Y = ( ~S & A) | ( S & B)

对应的电路就是：

测试一下，也是对的，好嘛，原来可以这么简单，布尔表达式的化简就是这么神奇。

4.搭建n路复用器

这部分我们搞一个进阶的，刚刚是2路复用，2选1，这次搞一个n路复用，n选1。要求就变成这样了：

当选择信号S等于0，输出信号Y等于A0

当选择信号S等于1，输出信号Y等于A1

当选择信号S等于2，输出信号Y等于A2

……

当选择信号S等于7，输出信号Y等于A7

……

那具体要怎么做的？直接上真值表，上表达式？那玩意有2的n次方行，如果n等于10，或者等于32什么的，怕不是要裂开……

或许我们可以先好好理解一下2路复用器的电路逻辑：

S是选择信号，也可以理解为了允许信号。中间两个与门可以理解为景区入口检票的。最后的或门很随便，不管事，随便过，它就是一个捏信号的玩意。我们可以注意到：S信号等于0，就是说给上面的通道打开，A来了就可以走，下面的通道被关咯，B不能过；反之也类似。

灵光一闪，那n路复用，我们就整n个与门，最后也是用或门捏起来。那些与门，每一个都留出一个端口给游客（输入信号），另一个端口听S信号指挥。如果S信号对上了，就允许游客过去。具体地说，怎么叫对上了？哦吼，我们刚刚造了相等判断的逻辑，用上：

测试一下，也是对的，很漂亮。但是因为这8个输入都是1比特的，稍微还差点意思，我们需要给它加个buff，把这8个输入都改成8比特的。这样一来，与门、或门的端口也需要是8比特输入。其实与或非的输入都可以是多比特的，也即每比特分别进行与、或、取反，然后再捏起来。上了这个buff之后，与门、或门另一个输入，也即相等判断逻辑的输出，也应该是8比特的。具体在电路上，可以直接使用位扩展，这个操作其实等价于这样：

最后看一下上了buff之后的8路复用器，内部长这样：

再进一步地，32路，每一个输入32比特，类比一下，应该也很好理解了，就是不停的连线连线，拉框框拉框框，最后就是这样啦：

5.理解二进制数以及补码表示法

二进制，相信大家都或多或少听说过，每位都只有0、1两个可能，进位逻辑就是“逢二进一”。其实在之前的文字中我也多少用了点。我觉得这个东西可以直接看下表。0到15这16个数，用二进制表示分别是这样的：

从0看到15，其实规律就已经很明显了，一个一个往上加1，如果已经有1了，那就进位。不难看出，如果有16的话，16的二进制编码应该是10000。于是有一个规律呼之欲出，2、4、8、16这种2的整数次幂，其二进制编码就是一个1，后面跟上若干0。是2的几次幂，那就几个0。例如8是2的三次幂，那就是1000。

再进一步地，一般正整数都可以用2的整数次幂凑一凑得到，例如12就是8加4，也就是2的3次幂加上2的2次幂，那它二进制编码就是1000和0100的叠加。

二进制数的加减运算和我们小学学的那个是类似的，排竖式去加就可以了，记得逢二进位，就像这样：

左边这个对应回十进制数，也就是7+5=12，没毛病；右边这个明明是13+5=18，怎么变成2了？是不是应该最高位进位呀，变成10010？

没错，理论上是应该最高位进位，但是实际上可以直接不管。我们提前好规定4比特运算，超过15就是溢出，不归我们电路管了。就像时间：晚上11点，再过俩小时，就是1点了。准确地说应该是次日1点，但是我们不管第几天，只在乎几点了，那么11+2就会得到1。换言之，对于4比特电路，我们默认接受15+1得到0，15+2得到1。

嗯，好吧，勉强接受这个设定，虽然一时看起来有点奇怪……

OK，现在有意思的问题来了，刚刚这些操作，都是正数呀，负数怎么办？也就是二进制数是如何表示符号的？也像我们平时写数字一个前面带上一个“-”吗？其实也可以，但是一般不这么干。二进制数表示符号一般用补码表示法。那啥是补码表示？-1、-2又应该是什么编码呢？来，直接上表：

-1的编码是1111、-2的编码是1110，从最大的编码倒回去减一、减一，直到1000这个编码减到了-8。

嗯，好吧，勉强接受这个设定...个鬼呀！看起来太奇怪了！为什么呀！

其实补码表示和上一个设定是要联系起来一块看的。想象这么一个表盘，11点了，再过两个小时，就是1点了，跨过了12点，也正常OK，可以理解。我们可以再抽象一下，把表盘上面的数之间的加法，看做是顺时针转动指针，11+2=1，对应的既可以是11点再过2小时，也可以是2点再过11小时，都是1点。

相应的，减法就是逆时针转动指针，6-3=3，6点倒回去三个格子就是3点；1-2=11，1点倒回两个格子就是11点。

有趣的事情发生了：我们注意到，每一个逆时针的操作，一定都等效于唯一的一个顺时针的操作。例如这个黑指针到红指针，6点到9点，既可以顺时针3格，也可以逆时针9格，也即在12个数的表盘中，加3与减9，这两个操作的效果是一样的。

同理，我们可以轻松理解，加6与减6也一样。于是乎，所有减法都可以用对应的加法代替，你想要减1，没问题，加11就是了，没毛病。诶嘿：

减9等价于加3

减6等价于加6

减1等价于加11

……

减3等价于加9

减11等价于加1

……

3与9我们称之为一对补数，同样1和11也是一对补数。这些一对一对的补数是什么规律呢？没错，他们的和都是12。那12有什么特别的吗？12是表盘的数字总量。

叮~是不是想到了什么，4比特二进制数，也可以看做一个表盘，只不过这个表盘上面有16个数。那么相应的，在这个表盘上的补数对，就应该还是和为16的，也即1与15、2与14、3与13等等。进一步地说，既然这种情况下，减1等价于加15、减2等价于加14……不如负1直接使用15的二进制编码表示、负2直接使用14的二进制编码表示……也即如果一个数是负的，那就用它的补数的编码来表示。这就是补码表示法：

此处留个小坑：补码表示法的绝妙之处，将在设计减法器的时候显现。

6.搭建1比特全加器

接下来我就要开始折腾二进制的运算器了，首先当然是加法器咯。我们先回顾一下二进制加法是怎么玩的：

这里我们需要一个抽象，也就是下图的长条虚线框，它叫做1比特全加器。其实这也就是在考虑1比特的加法：

这1比特的加法进行的时候，其实还有一个隐含的输入，就是低位给的进位信号，还有一个隐含的输出，就是交给高位的进位信号：

我们分别给这些信号都取好了名字，本位的俩输入就叫AB、本位的计算结果叫S，这个一般也叫本位和。还有进位输入和进位输入分别是Cin和Cout。根据二进制加法的基本规律，逢二进一，我们可以知道：

诶嘿想到了什么？没错，真值表。套路开始：

写表达式：

S = (~A & ~B & Cin) | (~A & B & ~Cin) | (A & ~B & ~Cin) | (A & B & Cin)

Cout = (~A & B & Cin) | (A & ~B & Cin) | (A & B & ~Cin) | (A & B & Cin)

画电路：

按照真值表测试一下，虽然没有错，但是这显然说不上漂亮。这主要还是因为表达式没有化简，来，继续套路，化简表达式。这里补充一下，本篇的第一个小点，异或运算，它的数学符号是“^”。也就是说：

A^B = (~A & B) | (A & ~B)

这个公式我现在要倒过来用，找到类似 (~A & B) | (A & ~B)的结构，把它们换成A^B。再补充一下，与、或运算是有分配率的，就是：

(A & B) | (C & B) = (A |C) & B

好勒，我们先用分配率处理一下S的表达式（注意&的优先级高于|）：

S = (~A & ~B & Cin) | (~A & B & ~Cin) | (A & ~B & ~Cin) | (A & B & Cin)

= (~A & B | A & ~B ) & ~Cin | (~A &~B | A & B) & Cin

= (A ^ B) & ~Cin | (~A &~B | A & B) & Cin

我们注意到异或运算的取反，同或，回忆一下它的真值表，注意到它的表达式就是：

~(A^B) = (~A & ~B) | (A & B)

诶，这个东西S的表达式里面有呀，那就继续化简：

S = (A ^ B) & ~Cin | (~A &~B | A & B) & Cin

= (A ^ B) & ~Cin | ~(A ^ B) & Cin

哦吼，异或的结构又出现了，继续化简：

S = A ^ B ^ Cin

Nice! 很漂亮，我们试试Cout是不是也能化简？观察Cout表达式后面两项(A & B & ~Cin) | (A & B & Cin)，也就是A为1、B为1的时候，Cin不是1可以触发、Cin是还是可以触发。Cin这个变量在摸鱼，给它抓起来！化简Cout表达式：

Cout = (~A & B & Cin) | (A & ~B & Cin) | (A & B & ~Cin) | (A & B & Cin)

= (~A & B & Cin) | (A & ~B & Cin) | (A & B)

我们注意到原式中有(A & B & Cin)，并且(A & B & Cin) | (A & B & Cin)和(A & B & Cin)的一样的，那就意味我们可以多来几个。为啥要多来几个呢？有好处的，往下看：

Cout = (~A & B & Cin) | (A & ~B & Cin) | (A & B) |(A & B & Cin)

观察第2项和第4项，(A & ~B & Cin)和(A & B & Cin)，诶，老套路，当A为1、Cin为1的时候，B不是0触发，B是0还触发，变量B在摸鱼，抓起来！化简：

Cout = (~A & B & Cin) | (A & B) | (A & Cin)

啊哈，发现了规律了吧！再来一个:

Cout = (~A & B & Cin) | (A & B) | (A & Cin) | (A & B & Cin)

观察第1项和第4项，(~A & B & Cin)和(A & B & Cin)，变量A在摸鱼，抓起来，最后得到：

Cout = (A & B) | (A & Cin) | (B & Cin)

S = A ^ B ^ Cin

我们根据新的表达式，画出新的电路图：

最后调整一下接口朝向，抽象封装一下：

7.搭建n比特加法器

加法只有1比特肯定是不够意思的，咱们刚刚整的1比特全加器，其实就是加法器内部的一部分。其实如果充分理解了1比特全加器的位置，搭建一个n比特的加法器，就很简单了。

只需要把它们一个一个头尾相连串起来就可以了。我们之前已经完成了封装，现在就可以直接上电路：

至于最低为的全加器的进位输入Cin，设置为常量0既可，最高位的进位输出额，直接丢掉就好了。最后，封装一下，当当当当，一个8比特加法器诞生了：

想要多少比特都可以哦，多连几个就是了~

8.搭建n比特减法器

有了加法，接下来整一个减法，就是很自然的思路咯。我们当然可以先设计一个一比特减法器，定义好输入输出，填真值表，写表达式，画电路图，这当然OK的。但是得益于我们先前介绍的补码表示法，减法器的实现其实可以非常美妙。我们不妨先复习一下补码表示法：

一个数如果是负的，那就用这个数的补数的编码来表示。减去一个数，就等于加上这个数的补数。补数的性质很不错呀，既如此，那么现在我们来探究一下，一个数的补数，要怎么求？

当我们规定数位是4比特的时候，每一个数和它的补数，加起来都是16。例如1和15、2和14等。对于二进制编码来说，也就是加起来得到0，例如0001和1111、0010和1110等。同时，我们不难发现，一个数和它的取反，这俩相加，永远是1111，而全1的编码，只要再加上一个1，就会得到0，也就是一个n比特的二进制数A，永远满足：

A + ~A + 1 = 0

既然A和(~A+1)的和永远是0，那就说明，A的补数就是(~A+1)，也就是说：

X - A = X + ~A + 1

我们发现，减法，可以变成一次取反和两次加法，取反简单，而加法刚刚已经实现了，那么我们的减法器就可以直接这样连接：

封装测试一下，没毛病，一个减法器，就这么漂亮地实现啦！

9.搭建n比特大小判断逻辑

最后一个器件啦，我们做一点点小扩展，搭建一个n比特的大小判断逻辑，要求是这样的：

如果A小于B，则输入Y等于1，否则，Y等于0

Emmmm，要怎么做呢？难道要上真值表，有点折磨呀……我们不妨再看看补码表示法，梅开三度了属于是：

我们注意到，右边都是小于0的数，它们的最高位都是1，左边都是不小于0的数，它们的最高位都是0。显然，右边的数肯定是小于左边的数，也就是说，最高位是1的数，小于最高位是0的数。诶嘿这个规律好诶，我们简单摆弄一下逻辑门就可以搞定了~

我们继续看，如果最高位一样的数，也就是在同一排的数，它们的次高位有没有这个规律呢？啊，次高位是1的数，大于次高位是0的数，坏了，规律没了，咋办呢？

诶，根据套路，我们现在搞这个，应该要把之前造的东西用上，小脑袋瓜一转~这不是有减法器嘛：

A < B 等价于 A - B < 0

小于0，只需要判断最高位是否是1既可，是1就小于0。Nice！可行，小结一下，我们的电路逻辑就是这样的：如果AB的高位异号，也就是AB不在同一排，那么A的高位是1，就是A小，Y直接输出1；如果AB的高位同号，也就是在同一排，那么查看A-B的差值，如果差值的高位是1，说明差值小于0，说明A小，Y也是输出1。直接上电路：

顺手再封装一下：

不妨再进一小步，那么如果我们要求这样呢：

如果A大于等于B，则输入Y等于1，否则，Y等于0

啊哈，这不就是倒过来嘛，简单，秒了，上电路，顺手封装：

其实这个电路还有点小毛病（比较大小要分有符号比较还是无符号比较的），但是这里作者偷懒了，不想写了，求原谅，直接下一个（

10.搭建算术逻辑单元ALU

到了本篇的最后一关啦，我们要把之前设计的器件都用起来，整一个稍微有用的电路，这个电路名字叫做算术逻辑单元，Arithmetic Logic Unit，一般简称ALU，它的设计要求是这样的：

当S = 0，输出Y = A & B

当S = 1，输出Y = A | B

当S = 2，输出Y = A ^ B

当S = 3，输出Y = A + B

当S = 4，输出Y = A - B

当S=5，若A = B，输入Y = 1，否则Y = 0

当S = 6，若A < B，输入Y = 1，否则Y = 0

当S = 7，若A >= B，输入Y = 1，否则Y = 0

诶，这其实就是一个大复用器，而且那些运算咱们都会了，只要分别计算，把每种结果都准备好，然后都丢给复用器的输入端，最后的输出根据S信号选择出来就可以了。思路清晰，开工：

其中，相等判断、小于判断和大于等于判断，这三个模块的输出是1比特的，所以需要扩展一下再进复用器，扩展也就是零扩展，说白了就是配上7比特的0，捏一块。最后再测试，封装，很完美~

预告一下，下一篇时序逻辑，很精彩哦~

扩展阅读：

（进位与溢出判断）

（超前进位加法器）

（Booth算法与Wallace树）

（写不动了，让我偷懒一下吧……）