nand2tetris—构建ALU

URL

type

status

date

slug

summary

Week0:课程简介和一些背景知识

一. nand2tetris 课程介绍

nand2tetris 即 from nand to tetris(to 和 2 的英文读音一致)，翻译过来就是从与非门到俄罗斯方块。这是一门由希伯来大学的两名教授开发的计算机基础知识课程。课程以项目驱动，从最基础的逻辑门开始，一步步构造一个完整的名为 Hack 的计算机系统，包括基础的硬件结构，还有软件层面的操作系统。我们甚至要构建一个名为 jack 的编程语言，用它来写操作系统，最后也是用它写一个俄罗斯方块小游戏在我们制造的这个计算机上运行。

通过这门课程，我们可以俯瞰整个计算机，拉通理解整个过程：从里面的每一个零件的协同运作，一直到能在屏幕上运行我们的应用程序。其中包含数字电路，计算机组成原理，操作系统，编译原理等等知识，但是都没有特别深入。这门课最大的价值是为我们展开了一幅计算机知识的地图，我们可以在学完整个课程后，选择自己喜欢的地方深入。另外课程提供的实验是这个课程的最大亮点，可以说这个实验就是课程本身，它提供了一种动手制造整个计算机的途经，让我们在实践中学习知识，尤为可贵。因此学习这门课程尽量要动手实践

本课程分为大的两部分，第一部分是硬件，第二部分是软件，自底向上的构建计算机系统。

二. 计算机的诞生

tips: 本小节为本人凭借兴趣了解的题外话，可以跳过

学习的过程中也在了解一些课余的知识，比如计算机是怎么诞生的？计算机为什么可以是计算机？

计算机发明的最主要目的便如名字所说：计算。为了计算我们向前甚至可以追溯到结绳记数，但这些“古典”的计算方式都和我们现在的通用计算机相去甚远。关于现代计算机的开端，我们可以放眼到 1936 年由图灵提出的图灵机模型。图灵机是一个抽象的概念，它抽象了人们使用纸笔运算的过程，为自动化的计算提供了可能。

想想我们用纸笔是怎么运算的？首先，我们肯定有解题的思路，或者说叫算法，其次我们的问题有一些初始的值。我们的计算过程就是通过我们的解题思路，不停的对这些值进行修改，直到改成目标答案。而图灵设想了一个自动化的机器来完成上述操作，具体如下：

什么是图灵机

如上图，这是一个经典的图灵机模型图。其中包含这几个部分：

一条无限长的纸带，纸带被划分成一个个小格子，每个格子只有三种状态（空和 1）

纸带上方的方盒子是一个读写头，可以在纸带上面按照格子移动，它可以做三种操作：

读取格子数据

编辑格子里的数据

向左或向右移动

横插在方盒子上的是图灵机当前的状态，图灵机可以有许多不同的状态。

方盒子上面的纸张是一些指令（也就是前文纸笔运算时的解题思路）。每条指令分为状态，和操作，控制读写头在指定状态执行指定操作。（状态可以由纸带上的数据和图灵机本身的状态共同决定）

图灵机初始的时候，会有一个状态，纸带上也有一些初始值。然后读写头根据当前状态对应的指令，做出编辑数据，移动，改变状态等操作。到了下一个状态，又执行对应的操作。这样一个状态一个状态的迭代，不停的修改纸带上的数据，到最终得到结果时，就让图灵机进入停机状态。

上面的过程描述很抽象，这里推荐个视频可以帮助理解：图灵机运作原理及示例

无论是否理解这个机器，至少我们知道，它能通过一些指令，用读写头在纸带上修修改改，而且过程是一步一步的，一条指令一串操作这样修改，最后得出结果。这为现代计算机的实现提供了方向，而且科学家们也证明了这个模型的可行性（具体可以学习计算理论和数理逻辑相关知识）。

我们要造一个计算机，首先得要有个东西装指令吧，还得有个东西能理解指令吧，还要能判断当前的状态；我们还要有个无限长的纸带，虽然不太现实，但至少得足够长吧；还要有个能在纸带上游走，对纸带数据进行增删改查的读写头吧；还有那个标记当前状态的玩意也得有吧。通过后面的学习，我们可以知道，现在目光所及的通用计算机几乎都是按照这个框架制造的。

下一章我们要学习布尔逻辑，这也是个划时代的玩意，它将概念上的形式逻辑落地成了硅片上的电路，用看得见摸得着的东西来呈现只有思维里和纸上符号才能表示的逻辑。计算时我们脑子里的解题思路，就有了一个被实体化的可能，图灵机的指令那块也有了实现的希望。事实上在布尔逻辑和电路的帮助下，我们能把各种信息数字化到芯片里，进行存储，读取和处理等等操作。正是这些伟大的思想和技术的综合作用，才带了如今非凡繁盛的互联网时代。

三. 学习环境和资料

学习这一套课程只需要有一台普通的电脑就行，win 和 linux 系统都可。然后需要下载的资料链接放下面：

课程视频教程 b 站：【高清-中字-公开课】依据基本原理构建现代计算机：从与非门到俄罗斯方块(点击观看)

课程官网：Nand2Tetris（点击进入）

课程配套软件和练习文件：网盘下载（提取码：2222）

课程配套书籍《计算机系统要素：从零开始构建现代计算机》：网盘下载（提取码：2222）

本人的环境是 Windows 系统，我自己学习的方式是以看书为主，然后有不懂的地方再去看视频，学完一章就直接动手实验。

Week1:布尔逻辑

一. 布尔代数

布尔逻辑是一套由乔治布尔于十九世纪中叶定义的逻辑系统。所谓逻辑，就是对正确推论的研究，如何根据一系列前提，推论出一个正确的结果。下面我们来看看布尔逻辑的内容。

首先我们知道一个命题，它不是真的，就是假的。假设有命题 a 为真，命题 b 也为真，那么有个命题 c 内容是 a 且 b，它是真的还是假的？我们可以感性的举个例子，如果“这个棒棒糖是甜的”是真命题，“这个棒棒糖是球形”也是真命题，那么“这个棒棒糖是甜的并且它是球形”也显然是真命题。我们可以发现，前提 a，b 是真的，那么 a 且 b 也是真的。我们把这种形式抽离出来，只要满足这个形式，不管内容是啥（不管 ab 是啥），它都成立。

这里的 “且” 是语言上表达的一种逻辑连接词，也可以叫 “与” 表示两者都满足；类似的还有 “或” ，a 或 b，其中至少一个为真就为真；还有 “非” ，这个字只作用于一个命题，而前两者连接两个命题，如果 a 是真的，那么非 a 就是假的，反之亦然。与，或，非组成了基础的三种逻辑连接词。所以可以抽象出来：

a 且 b：必须 a 和 b 都是真的这个命题才真

a 或 b：a 和 b 中至少一个是真的，这个命题就是真的

非 a：如果 a 是真的，那么这个命题是假的，a 是假的这个命题就是真的

布尔把 “真” 设为 1，把 “假” 设为 0。然后用上述连接词，1 或 0 为 1, 0 或 0 为 0, 1 或 1 为 1，等一下，这不和加法一样了吗只是 1+1 比较特殊，还是得 1。同样，对于 “与” 来说，就和乘法一样。而 “非”，无非是把 1 变为 0,0 变成 1。这些真真假假是可以像数字一样进行计算的！只是这里的数字只有 0 和 1（这很容易联想到二进制），而且没有进位，1+1 还是 1，我们称这种计算叫逻辑运算。由此，布尔代数诞生了。

一些逻辑运算规则：
或：1+1=1；1+0=1；0+0=0；有 1 为 1
且：1x1=1；1x0=0；0x0=0；有 0 则 0
非：1’=0；0’=1；唱反调

在布尔代数中，我们称这些连接词为布尔算子，就和普通代数中的加减乘除一样。与或非就是最基础的布尔算子。除了最基础的三个，我们还可以了解与非，就是先与再非；或非，先或再非；异或，连接两个命题，同真同假的话结果是假，只有真假不同结果才是真；同或，与异或相反，只有同真同假时结果才为真。普通的四则运算有一些交换律结合律之类的规律，还有些化简公式，布尔代数也不例外，如下图（不用刻意记住，需要时查找即可）。

布尔函数

在普通的代数中，我们不仅有 1+1 这种具体的式子，也有 x+y+2 这种带着未知量(变量)的式子，当 x 和 y 取不同的值时，就会得到不同的结果，这个式子只是表示一个计算的过程，我们可以称其为函数。布尔代数同样也有布尔函数，或者叫布尔表达式，只是其中的运算变成了逻辑运算，其中的变量只能取 0 或 1。函数体现了一种黑箱思想，我们的表达式的变量需要接收一些值，然后经过表达式的处理，得到一个结果。比如布尔表达式 (x+y)z’，需要接收三个具体的值分别给 xyz 三个变量，我们把表达式本身想象成一个黑盒子，用符号 f(x,y,z)表示，f 是盒子的名字，盒子上有三个入口分别叫 x,y,z，还有个出口出来运算结果。假设黑盒子内部可以自动化的处理。当我们把 1,1,0 这三个值扔进 x,y,z 这三个入口，那么盒子就可以产生出结果 1，因为内部运算(1+1)x0’的结果为 1，可以写为 f(1,1,0)=1。xyz 三个变量，每个变量只能取 0 或者 1 两个值，所以一共有 2 的 3 次方也就是 8 中取法，我们把所有的输入情况和对应结果找出来，并列成一张表，就成了真值表。

真值表反推函数表达式：

上面我们说了，函数就是一个黑盒子，给它输入，就一定会给一个固定的输出。反过来说，如果我们一开始不知道盒子里是啥呢？我们只知道有几个输入，还有对应输入应该是什么结果，换句话说就是只知道真值表！我们是否可以反推出盒子里的表达式呢？这也符合现实的很多情况，我们知道这个问题有哪些条件，我们也知道自己要什么结果，但是我们需要一个把条件变为结果的手段。这其实是可行的，我们先只关注输出为 1 的那些行，对于每一行，我们用与来连接 xyz。然后我们关注这一行 xyz 分别的取值，比如第三行 xyz 分别取 010，那么取 0 的那个字母就要进行非运算，第三行就写成 x’yz’。然后把输出为 1 的三行都这么处理，就能得到三个与连接的式子：x’yz’，xy’z’和 xyz’，接着把这三个式子用或连接，就成了 x’yz’+xy’z’+xyz’，这其实就是这个真值表的函数表达式了，最后用上面的计算规律化简就成了我们熟悉的(x+y)z’。我们可以得到化简过程中你可能会发现中途有好多种表达式，所以一个真值表可能对应不止一个黑盒子，我们通常选取最简单的那一个。另外你还可以发现，不管多复杂的真值表，只用与或非三种算子就能表示。

与非的妙用：

与非(nand)，(xy)’，是一个十分牛的算法，因为只用与非代替基础的三种算子：与或非。这用上面运算规律中的德摩根律很容易能求出。进而我们可以把任何表达式，都转化为只用与非这一种算子的表达式。这在之后构建硬件中起了非常大的作用，你也可以发现课程题目中的 nand 说的就是与非门，这是这门课程项目的最基础的元素。

与现实世界连接：

有了上面知识，我们就可以自己设计一个函数了，给这个函数喂一些 0 和 1，就能吐出想要的 0 和 1。但是这有什么用呢？上一章第二节我们谈到了图灵，他有个好朋友叫香农，香农在 1938 年的硕士论文《继电器与开关电路的符号分析》中将这些概念上的逻辑与物理世界连接，让这些理论的落地有了可能。香农是研究通讯的，他发现电从一点到另一点本身不是信息，而电的有无却可以是信息。比如我们了解的电报，通过电路开关以及开关的时间，就可以表示语言信息。而电路的开关引起了香农的注意，这电路一开一关两种状态，不是正好对应了布尔逻辑中的 1 和 0 两种状态吗？我们将信息转化为 0 和 1，然后用电路的开关去表示，我们还能用真值表设计“黑盒子”去处理这些信息，也就是说，我们能把逻辑放到看得见摸得着的电路板上了。

我们再回想一下上一章的图灵机，其中一个要考虑的点就是如何把我们的计算思路给存到机器里去，如何让机器去理解。现在看来，这一切都有了实现的可能。下一节逻辑门，我们将把理论落实，把抽象的与或非转化为具有物理实体的与门，非门，或门，还能会制造后面需要用到的一些门电路或者说芯片。你还会发现我们的门电路或者说芯片，就是给一堆输入的 0 和 1，然后输出特定的 0 和 1，设计门电路就是在设计布尔函数。

拓展：香农也是一位很有趣的科学家，这里有一部纪录片可以了解下：《香农传》

二. 门电路

从编码说起：

我们知道电脑里面就是一堆电路，稍微了解计算机的可能听说过，电脑只会二进制语言，只能读懂 0 和 1。但是我们玩电脑，可以看图片，听音乐，可以看视频，甚至在大型游戏中模拟了另外一个现实，你可以在一个空间中畅游互动。显然计算机表现出来的不只是 0 和 1，这都离不开编码的帮助。

像上一节说的电报，我们可以通过一些规则，把不是 0 和 1 的信息变成 0 和 1。比如我们规定字母 a 是 000，b 是 010，c 是 100，这样字母信息就变成了 0 和 1 的信息可以传入电脑中。向电脑输入字母应该是按键盘，安一个按钮可以输出一些 0 和 1 的信号，我们把这些信号变成 abc 字母规定的编号。比如按了 a 键，键盘输出 101101，然后我们把它转化为 000，这个过程就是编码。电脑怎么展示这些字母呢，首先它得有个屏幕，屏幕也是由 0 和 1 控制的，通过屏幕上有的地方通电发光，有的地方不通电变暗就能显示图案。很显然屏幕上面这么多发光点，控制屏幕的 0 和 1 是和字母不同的。也就是说我们需要一个翻译，来把字母的编码转化为屏幕可以显示的 0 和 1，然后控制屏幕怎么发光，这个过程就是译码。

上述过程我们可以猜想有两个东西，一个编码的东西，一个译码的东西，它们输入一些 0 和 1，吐出一些 0 和 1，这不就是上一节的布尔函数吗？通过编码译码，我们就可以把现实的信息数字化。当然上述例子极其粗糙，整个计算机系统是一个超级工程，肯定不会如此简单，后续我们也会学习更细节的东西。

在电路中实现逻辑

tips: 这一小点为拓展，稍微了解即可

所谓的逻辑门就是逻辑电路中最基本的组件，可以实现与或非这些操作的电路。

课程并没有要求我们去了解最基础的与非门电路是怎么实现的，我们前面说了，有了与非门，就可以实现所有的布尔函数。课程默认与非门是造好了的，我们拿来用便可，但我还是稍微了解了一下具体的实现。

一切要从发明大王爱迪生说起，爱迪生在捣鼓灯泡的过程中发现了爱迪生效应，而弗莱明通过爱迪生效应制造了二极管，一种可以单向通电的元器件。后来福雷斯特在二极管的基础上制造了三极管，三极管在二极管的基础上增加了第三个端，在第三端施加少量电压便可以使另外两端导通。

我们可以用符号来表示三极管，并用三极管来构建基本的逻辑门。

我们可以看到，这时候的三极管还是类似灯泡一样，烧的灯丝，我们称其为电子管。电子管体积巨大，功效奇高，而且寿命不长，所以用电子管构建的第一台计算机，也是体积庞大的功耗怪兽。后来利用半导体材料制造的晶体管横空出世，晶体管利用硅的特性来制造，体积小巧，功耗低，很快全面代替了电子管。后来人们发现，制造晶体管电路的材料可以被硅包办，为什么不直接把电路刻在一块硅片上呢？于是集成电路出现了，所有的元器件都是直接刻在硅片上，并且体积越来越小以至于到了纳米级别，数量越来越多到达千亿级别，让计算机真正成为了能握在掌心的超级工程。

晶体管的工艺也一直在更新，为了更加稳定更加高效。现在比较流行的是cmos制程，用 mos 管来代替三极管，实现更稳定的性能。

无论如何，我们的课程假设我们已经有了许多的与非门(nand)，你可以把它想象成一个小黑盒，盒子上有三根暴露的电线 abc，电线只有两种状态，可以是有电和没电，也可以是高电压和低电压。c 电线的状态总是(ab)’。我们将只用这些与非门来构造整个计算机。

用与非门构建基础的门电路

还记得学布尔函数时的黑盒思想吧，我们先来把这些基本的门变成带接口的盒子画出来：

这些其实就是逻辑门的电路符号。我们要实现一个门电路，其实就是求它的布尔表达式，有了这个表达式我们就可以根据表达式连接电路。下面以非门为例展示如何构建：

首先我们确定或门的输入和输出，它有一个输入 a,有一个输出 out。

我们知道 c=a+b,但是我们要化为全是与非门的形式，所以 out=(aa)’，也就是 a 和 a 本身与非一下

接下来就是按照式子画图：

有了非门，我们就可以把非门用在后面的逻辑门制造中，而不用考虑非门如何制造，同理我们可以画出其他几个基础逻辑门的电路图。

除了与或非异或，我们还需要两个特殊的逻辑门——multiplexor和demultiplexor，简称mux和dmux。

mux 的有三个接收端和一个输出端，三个接收端分别为 a,b,sel，输出端为 out，sel 可以选择让 out 输出的是 a 的值还是 b 的值。比如 a 为 0，b 为 1，当 sel 为 0 时，out 就输出 a 的值 0，当 sel 为 1 时就输出 b 的值为 1。

dmux 可以看做是 mux 的逆过程，dmux 有两个接收端，in 和 sel，两个输出端 a，b。sel 可以选择让 in 从 a 出来还是 b 出来，另一端一直为 0。比如说 in 输入一个 1，sel=0 时，a 就输出 1b 就输出 0，sel=1 时，a 就输出 0b 就输出 1。

以上两个电路比较复杂，不能像基本门电路一样直接写出表达式，所以我们采用真值表法来求出表达式

tips: 一定要自己动手推导下，从表达式的推算到电路图的绘制，这将极大的帮助理解

多位基本门和多通道逻辑门

在很多时候，我们需要同时把许多信号做相同的操作，或者说把一组信号当作一个整个信号进行处理。这时我们就需要多位逻辑门了，根据后面课程的需要，我们将要制作 16 位的与或非门和 mux，分别叫做 and16，or16，not16，mux16。以前输入的一个信号 a 变成了一组信号，我们可以用数组来表示：a[16]。举个例子：a[16]是 1111111111111111 一共十六个 1，我们的 not16 可以直接把这组信号变为 0000000000000000 十六个 0。要制作这样的多位门其实很简单，直接把 16 个一位的基础逻辑门拼起来装进一个大黑盒子就行了。

而多通道逻辑门主要说的是 mux 和 dmux，通过前面学习可以知道，mux 和 dmux 都可以用 sel 这个输入来控制 a 和 b 两个端。那么 sel 能否控制更多呢，比如控制 4 个或者 8 个端？要创造这样的门是有一定技巧的，我们先从 4 个端的 mux 看起，要用 sel 端来控制 4 个 16 位的信号，a[16]，b[16]，c[16]，d[16]。首先想到的是以前 sel 只有一位，不是 0 就是 1，这样只能控制两个信号。现在有了 4 个信号，我们可以把 4 个信号俩俩分组，sel 为 0 就选择 a[16]和 b[16]，sel 为 1 就选择 c[16]和 d[16]。可是 sel 只有一位啊，只能选择其中的两个，我们顺其自然就能想到再给 sel 来一位，就能从前一位选中的两个中选择一个，就实现了 4 选 1 啦。一个 mux16 可以从 2 个中选一个，所以要从 4 个中选 2 个就需要 2 个 mux16，他们的 sel 接同一个信号构成 1 位。从选中的两个中再选一个，又需要一个 mux，它的 sel 又是 1 位。所以要制造一个 mux4way16，需要 3 个 mux16。sel 就升级为了两位的 sel[2]，00，01，10，11 正好分别对应四个通道。

从上述推到中我们可以拓展，要从 n 个信号选择一个信号，我们需要k=log2 n个信号来控制，也就是说 k 个信号可以去选择n = 2^k 个信号。比如 16 是 2 的 4 次方，所以我们只用 4 个信号就能控制 16 个信号，因为 4 个 0 或 1 可以有 16 种组合。我们还能从二进制角度看待这一点，四位二进制数的最大值 1111 就是十进制的 16。知道这一点很重要，它在后续的编码译码中起了相当大的作用。

上面这段描述比较抽象，不理解可以结合下面的图来看，mux8way16 可以同理由 mux4way16 来构建。而 dmux4way 和 dmux8way 需要一点逆向思维，可以自行思考下：

还是老话，尽量自己动手画一画，印象深刻。

下一节我们将要学习用一种类似编程语言的东西来描述这些零件。我们将用代码描述这些零件，这样我们就可以在电脑上对这些零件进行模拟测试了（毕竟要用真家伙做这些电路也挺费事）。

三. 硬件描述语言 HDL

由于用实物做实验条件太难，而且不可控的因素很多，所以本课程采用软件模拟的方式进行，也就是说我们造的这台电脑是在我们自己的真电脑上运行的。所有的逻辑门都通过硬件描述语言 HDL 来创建。

什么是 HDL

通过上面的学习我们知道，一个逻辑门可以看成一个黑盒，黑盒外面有输入和输出接口，黑盒的里面有各种逻辑门电路。HDL 就是一种计算机语言，它可以用来描述这样一个逻辑门或者芯片。本课程使用的 HDL 是老师为课程设计的简化版本，和设计生产使用的 HDL 语言差距还是不小，但是也突出了其精髓。下面是用 HDL 语言描述的一个与门：

将这样一串代码写进一个文件中，文件的名字必须和芯片的名字一样，然后后缀为.hdl，比如上面这个芯片的名字就叫 and.hdl。接着就可以放进专门的软件里调试了。

第 0 章我们分享了课程需要的所有软件资源，打开课程配套软件 nand2tetris\tools\HardwareSimulator.bat(Linux 打开.sh 文件)，将上面的 and.hdl 导入进软件中，就可以对这个与门进行调试。

可以在设置输入那里输入想要的值，然后点一下计算输出的按钮，就能在展示输出里看到对应的输出。

我们可以手动输入每一种情况，看看输出正确与否，就能验证我们的设计是否正确。但是有的芯片输入的组合极多，手动输入效率实在太慢了，因此这个软件还可以导入另外两种后缀的文件 .tst 脚本文件和 .cmp 比较文件。.tst 文件可以通过导入脚本按钮导入，课程资料里提供了每个芯片需要的测试脚本，经过测试脚本测试后的芯片，会输出一个.out 文件，这个文件其实就是这个芯片的真值表。.cmp 文件是课程提供的正确芯片应该输出的真值表，我们可以比较自己输出的.out 文件和.cmp 文件是否一致。后面再来详细说说导入脚本的一些问题。

HDL 基本语法

通过上面的例子我们可以了解到，一个.hdl 文件就是一个芯片，而代码内容必须包含在如下的大括号里，这个结构规定了芯片的名字，而且必须和文件名字一致。内部分为两部分，一部分定义输入和输出，即黑盒外的接口；一部分定义内部的零件和电路，写在 PARTS：后面。

定义输入输出采用如下格式，IN 后面跟输入接口的名字，OUT 后面跟输出端口的名字，这个名字可以自定义，一般多个输入或者多个输出，我们定义为 a,b,c…，如果只有一个输入那么就叫 in，只有一个输出就叫 out。像 mux 和 dmux 这种有个选择的输入，我们就叫它 sel。一次定义多个接口，名字中间用逗号隔开，每一行分号结尾

如果有很多位的话，可以用数组的表示法，比如 a[16]，sel[2]，表示 16 位和 2 位的信号。

定义内部线路是重头戏，通过前两节的学习，我们知道内部线路也是许多逻辑门组成的。信号的流动过程大概是输入口->逻辑门输入->逻辑门输出->逻辑门输入->逻辑门输出->……->逻辑门输出->输出口。因此我们只用关注内部的逻辑门是怎么相互连接的。下面用 mux 举例，先再回顾下 mux 的电路图：

黑盒子里有四个逻辑门，一个非门，两个与门，一个或门。对于非门，它的输入是 sel，输出是给与门，我们就可以这样描述它not(in=sel,out=outa);，not 是非门的名字，也就是非门这个.hdl 文件的名字，in=sel 表示输入的是 sel。out=outa，我们要把非门的输出连接到与门，可以这样操作，先给输出的那条电线取个名字叫 outa，待会把那个与门的输入接到电线 outa 上就行了，我们称这样的中介一样的线叫做管线，多位的就叫总线。

四个零件都这样描述一下，就是下面的代码：

值得注意的是：软件中只有与非门(nand)是可以直接使用的，需要先自己用 nand 门构建与或非门，上述文件 mux.hdl 在运行时会去寻找同一目录下的 Not.hdl，and.hdl，or.hdl，而这些都是自己构建的，输入输出口都得和自己定义的吻合。(实际上软件内置所有基本门，门的名字和接口和书上一致)

还有一个问题是多位数据的传输，比如 a[16]这个信号，你可以想象一根电线里有 16 根小电线，给它们编个号，注意得从 0 开始，就是 0,1,2,3,4…14,15。当需要把前 8 个信号接到 outa 这个总线上时，我们可以这么写 a[0..7]=outa，outa 不用去规定有几位，它由输入的信号自动决定，后面保持不变。如果需要把多位信号中的一位输出到管线 b 上，可以这样写 a[2]=b，就是把 a 的 2 号电线(第三个信号)输出到 b 上。这里的 a[2]是在 PARTS 里的，表示信号的编号，而 a[2]在 IN 或 OUT 后面，则表示 a 有两位信号，和其他编程语言里数组的定义和取值差不多。

软件的脚本使用，个人认为还是视频更加直观，这里贴下链接：硬件调试软件的使用

下面补充一些脚本的注意事项，以 mux 的测试脚本为例，你可以通过修改脚本来做一些自定义的操作：

开工

现在我们的目标是把上一节计算并画图出来的门电路全部转化为 hdl 文件，并且都要通过软件的测试。书上为我们规定了文件名称，和输入输出接口的名称，需要动手的是 PARTS：后面的部分，打开文件夹nand2tetris\projects\01，找到里面的.hdl 文件用顺手的文本编辑器打开，然后为里面的 PARTS 部分填空吧！

我开始不知道老师给了模板，就自己新建文本文档写了，所有的文件名都整成了小写字母，还需要改脚本里的名字，直接用老师的模板方便很多。下面的参考代码只用关心 PARTS 部分就好。

下面是我的代码链接，已经全部通过测试脚本，你可以先自己动手做完，实在搞不懂再看答案。

链接：第一章实验结果

四.结语

本章节用与非门来构建了所有我们需要的基础逻辑门，实际上也可以只用或非门来构建，更可以综合使用各种与或非门来构建，可以自行去学习数字电路相关的课程。为了让教学更加友好，让我们忽略哪些繁琐的细节抓住主要知识，这个课程的设计并没有考虑效率问题，现实中的芯片设计中这些问题是非常重要的。一个电路中交叉线路的数量，基本门的数量，有许许多多的工程师和科学家去优化它们，以求更快的速度，更低的功耗和更低的成本，这些不是这门课的主要目的，我们可以在学完这门课程，再去自行探索。

Week2: 布尔运算

我们之前讲过，计算机实际上就是模仿我们人用纸笔计算的过程。人在用纸笔计算时，有个很重要的步骤就是“计算”，我们计算可以背乘法口诀表，可以列竖式计算，也可以使用其他工具，但是计算机应该怎么办呢？计算机里的信息都是 0 和 1 这样的电信号，我们很容易想到前面的逻辑运算，与或非这些运算都是只操作 0 和 1 的。不过只有逻辑运算还是不够，实际问题中有许多算数运算，比如要算个 150+50 等于 200，这用逻辑运算是走不通的，所以我们还要学习只有 0 和 1 的算数运算，即二进制。本章着重制造计算机的运算单元，它可以进行逻辑运算和算数运算。

一. 二进制和补码

二进制和十进制的转化

十进制我们很熟悉，就是满十进一，组成十进制体系的数字是从 0 到 9。二进制顾名思义就是满 2 进 1，因此二进制体系下数字只有 0 和 1 两个，就很符合我们之前学习的知识。用二进制计算 1+1，因为满 2 进 1，所以结果为 10，它等价于十进制的贰而非十进制的十。

二进制和十进制如何相互转化呢？从上面的例子可以看到 10 第二位的 1 是因为第一位满了 2 进上来的(最右边为第一位)，所以第二位的 1 表示的是 2 的 1 次方，同理第一位的 1 表示 2 的 0 次方即 1，第三位的 1 表示 2 的 2 次方，第 n 位的 1 表示 2 的 n-1 次方。所以用每一位的数字乘以这个 n-1 次方，再加起来，就是这个 n 位二进制数的十进制数，以 10011 举例：

通用公式：

十进制转二进制，我们可以用短除法来求，用十进制数不停的除以 2，会得到一系列的余数，最后的商作为最高位，后面余数倒序排列便是二进制数。

下图以 13 转化为二进制为例，最右边的便是余数，左边不停的除以 2，最后商 0 作为最高位，余数倒序排列，就是 01101 即 1101

二进制加法

二进制做加法，实际上和十进制一样，可以通过列竖式来求，只不过是满 2 进 1。值得注意的是，在计算机里存储的数字，都是固定的长度。比如一个计算机用 4 位存储数字，相加到第 4 位时可能会产生进位，答案就是 5 位，我们就说它溢出了，如果答案也是 4 位，那就是成功执行。也就是说计算机里二进制加法有两种结果，要不溢出，要不成功执行。

上图这样的竖式计算大家应该都不陌生，这是常用的纸笔计算方法。接下来我们的计算机做加法就是模仿这个流程，所以理解这种竖式计算法非常重要。

补码

假设有一个 4 位的计算机，即里面的数字都是 4 位的，所以最多可以表示从 0 到二进制 1111 个数，也就是 0 到 15 一共 16 个数。可是现实生活中有正数和负数，这该如何表示？毕竟只有 4 位，那么我们可以把这 16 个数一部分表示正数，一部分表示负数，就像之前学习多通道 mux 时的思想，可以拿出最高位，如果为 0 就是正数，如果为 1 就是负数，这样 16 个数就分成了 0xxx 和 1xxx 两类。1000 和 0000 都是 0，这样就就能表示从-7 到 7 的 15 个数。

我们称上述这种编码方式叫做原码表示法，可是原码表示法有个很大的缺点，就是符号必须单独处理，不能参与运算。有没有一种方法可以带着符号算呢？这就得看下面这种补码了，n 位数 x 补码表示如下：

这个公式就很好的体现了补码的本质，其实是一种模运算，就像钟表上按环形排列的数字，最小的数和最大的数首尾相接形成一个环。用原码表示的时候最大的正数 0111 也就是 7，如果带着最高位符号看的话，下一个数应该是 1000，但是因为我们把符号单独定义了，所以 7 过后不是最小的数-7，而是 0。补码表示法就很好的解决了这个问题，补码 0111 为 7，带着符号看下一个数 1000 就是最小的数-8。相当于把 0,1,2,3,4,5,6,7,-8,-7,-6,-5,-4,-3,-2,-1 依次对应到 0000 到 1111，实现了最大数和最小数的首尾相接。

观察上表可以发现一种转化为补码的简单方法。整数和 0 与原码表示一致，而负数可以取反加一，比如要计算-6 这个数的四位补码，先把 6 转化为二进制 0110，然后按位取反为 1001，再加 1，就是补码 1010。

为什么要用补码？用补码计算，你可以发现 3+(-6)=0011+1010=1101 也就是-3 的补码。我们可以带着符号计算了！这和模运算的性质有关，可以自行去了解下。既然我们能直接用加法计算正负数，那么减法就可以转化为加法！而乘法也就是许多加法的叠加，除法是乘法的逆运算，所以我们只需要一个加法电路就可以完成所有的四则运算。正是因为补码的这种特性，现代计算机几乎都是用补码来表示数字。

拓展：这里有个视频，通过倒推法来推导补码，可以加深理解：『教程』补码怎么来的？

二. 加法器

接下来就要让计算机学会做加法了。先从二进制数的竖式入手，模仿列竖式加法的思路来设计电路。

上面这个图展示了竖式运算的规律：

竖式一位一位进行相加

每一位都会产生进位(没有进位就算进位是 0)

最低两位计算时不考虑进位，从第二位开始的每一位都要考虑加上进位（每一位之间的关联就是这个进位）

因为计算机内数字的位数是恒定的，所以最高位的进位丢弃

按照上述规律，我们也可以按位设计这个电路，每个位的计算都由一个芯片单独处理。

半加器

先看最低位的加法，有两个输入：两个加数的最低位，有两个输出：结果和进位，已知输入输出就可以根据需要设计真值表，进而设计电路了，这样的电路我们称之为半加器。

上述便是半加器的真值表，通过观察我们可以发现，carry 进位其实就是与运算，而 sum 结果就是异或运算，因此可以直接给出 hdl 代码：

全加器

然后是从第二位开始的高位，因为要考虑加上进位，所以有三个输入：两个加数的对应位和一个进位，依旧有两个输出：进位和结果。这样的电路我们称之为全加器，真值表如下：

因为有三个变量不容易直接看出如何构建，我们可以根据真值表计算布尔表达式。这里也提供另一种思路，用两个半加器构建全加器(可能这就是为啥叫半加器和全加器的原因吧)。

三个变量相加，我们很自然的想到让其中两个输入一个半加器，然后输出的结果和第三个变量输入另一个半加器，按照半加器的原理，其实就是三个变量相异或，其结果也就是正确结果的最低位。两次半加器都有可能产生进位，只有三个变量中两个或三个为 1 才会有进位，所以两个半加器只要有进位 1，整个全加器都会有进位 1，只需要把两个半加器的进位端 carry 用或门连接即可，电路如下：

加法器

有了半加器和全加器，我们就有了计算每一位的手段，接下来就是把半加器和全加器组装起来，能够计算 16 位的二进制加法。根据前面竖式的规律，我们不难发现，连接这些半加器全加器的，是“进位”，因此我们可以把进位端连接起来，构成一个 16 位加法器。比如要把 a[16]和 b[16]相加，电路图如下：

就这样一步步把进位传递给下一个全加器，就实现了多位二进制数的按位加法计算。当然最后的进位 carry 可以不要。

拓展：这种加法器实际上效率很低，因为每一位计算需要先拿到前一位的进位，因此书中提到了有一种进位预测的技术，可以大大加速运算过程。通过查阅资料，我发现这种加法器在中文语境下叫超前进位加法器，这里找到一个视频，通过布尔代数运算求出超前进位加法器的布尔表达式：动画：如何深入理解超前进位加法器 [manim制作]，我们可以发现这种加法器把链式的结构转化为了一中扁平的结构，只需要少数几层的计算就能出结果，现代的加法器大多也用的这种

增量器

书中还要求我们设计构建一种叫增量器的芯片，它的作用是让一个 16 位二进制数加一，这在后续的计算机构建中有重要作用。我们只需将 16 位加法器中的一个数换成 000000000000001 就行了。

ALU 算术逻辑单元

ALU 可以说是整个计算机的核心部件，它负责做所有的运算操作。可以说 ALU 是一个多功能的运算器，不仅可以做算数运算，还可以做逻辑运算。由于 ALU 比较复杂，我们很难说去从头思考设计，所以我们先学习 ALU 需要满足哪些功能，然后再去构建它。幸运的是，ALU 所需要的所有部件我们之前都造好了，只需要根据需求拼装即可。

ALU 的需求十分复杂，但是不用慌，先来理清输入和输出。

我们可以看到 ALU 主要输入两个十六位二进制数，x 和 y，然后输出一个结果 out。这也体现了 ALU 的功能，就是输入两个数，然后进行一种运算，然后输出结果。而其它的这么多输入，都是用来控制做什么运算的。下面来理一下输入：

zx 和 zy：这两个控制输入是否置零，也就是对 x 和 y 单独进行处理。

nx 和 ny：这两个控制输入是否取反，也是对 x 和 y 的单独处理。

f：这一个输入控制做什么运算，这里有两种运算，and 和 add(相与和相加)。显然这里是把处理过后的 x 和 y 进行运算。

no：这个输入控制结果 out 是否取反，也就是对 and 或 add 的结果进行处理。

有了上述分析，我们就有了思路，先对 x 和 y 分别进行处理，怎么处理由 zx,zy,nx,ny 来决定（涉及到选择，一定要活用 mux 逻辑门）。处理好之后的 x 和 y 再交由 f 决定是做 add 运算还是 and 运算，我们可以先用加法器和 16 位与门把两个运算都做了，再用 mux 选择哪一个输出。最后处理输出，no 来决定是否用 16 位非门取反。

接下来看输出：

out[16]：就是最后 no 选择后的值

zr：判断 out 是不是为 0，一个比较好的方法是把每一位或起来，如果为 0 就是 0，此处需要两个 8 通道或门 Or8Way

ng：判断是不是小于零，前面学了补码知道最高位为 1 就是负数，所以直接把最高位连过来就成

下面是代码参考：

你可能会想，ALU 为什么这么设计呢，为什么 ALU 要先把 x 和 y 这么处理呢，为什么计算非要是 add 和 and 两种呢等等。你会发现我们的 ALU 除了两个数据，一共有 6 个控制信号的输入端，6 位也就是可以表示 64 种不同的操作。下表为我们展示了最重要的 18 种操作，他们都是有具体的意义的。你会惊叹人类的智慧，通过对信号进行提前处理，就能把 add 和 and 两种运算算转化为多种其他的运算。

开工

现在打开文件夹nand2tetris\projects\02，找到里面的.hdl 文件用顺手的文本编辑器打开，然后为里面的 PARTS 部分填空吧！

下面是我自己的工程链接：第二章实验结果

三.结语

本章中我们创造了一个功能强大的计算单元 ALU，但是它并不够强大，它还无法胜任除法，乘法，浮点数等运算。我们会在之后用软件的方式来实现这些运算（前面说过各种运算都是可以互相转化的）。因为本课程的设计原则是让 ALU 实现较少的功能，尽可能用软件拓展其他功能。