Nand2Tetris 是由希伯来大学的两位教授 Noam Nisan 和 Shimon Schocken 在 Coursera 上开设的在线课程（网络课程）。课程全称叫做：依据基本原理构建现代计算机：从与非门到俄罗斯方块（基于项目的课程），其主要内容与计算机组成原理、操作系统等科目的关联性较大，但课程的受众群体也不止局限于专业人士，且课程的实践性很强，对深入理解理论知识很有帮助。
Introduction
第一周包含两个章节（一般情况下，一周一个）：Introduction 和 Boolean Functions and Gate Logic。
顾名思义，Introduction 是对本课程的说明，Boolean Functions and Gate Logic 才是第一周的真正的学习内容。
通过 Introduction 可以知道大体的学习路线是从基本的逻辑门单元开始，自下而上的学习如何构建计算机，继而构建出能在这台计算机上运行的程序，也即：Nand -> Hack -> Tetris。
另外，对于购买了课程的同学而言，这章节会有一个编程作业，用来练习如何在 Coursera 上提交作业。但如果你是旁听生（auditor），那么可以忽略掉。
Boolean Functions and Gate Logic
这部分内容属于计算机系统结构底层中的底层，课程从一个小小门逻辑电路开始讲起（当然不会讲与物理相关的内容，这也是老师让大家不要过分在意的地方），逐步介绍各种不同的逻辑电路，并自行构造具有一定复杂性的复合逻辑门电路。
Unit 1.1 Boolean Logic
本小节主要介绍了三种基本的逻辑门（Logic gate）：与（And）、或（Or）和非（Not），并举例说明了与之对应的基本运算方法和规律。
三种逻辑门的真值表（Truth table）如下：
And：
$$\begin{array}{cc|c}
x & y & And \\
\hline
0 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 0 \\
1 & 1 & 1 \\
\end{array}$$
Or：
$$\begin{array}{cc|c}
x & y & Or \\
\hline
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 1 & 1 \\
\end{array}$$
Not：
$$\begin{array}{c|c}
x & Not \\
\hline
0 & 0 \\
1 & 0 \\
\end{array}$$
运算规律：
- 交换律（Commutative Law）
- x and y = y and x
- x or y = y or x
- 结合律（Associative Law）
- x and (y and z) = (x and y) and z
- x or (y or z) = (x or y) or z
- 分配律（Distributive Law）
- x and (y or z) = (x and y) or (x and z)
- x or (y and z) = (x or y) and (x or z)
- 德摩根律（De Morgan Law）
- not (x and y) = (not x) or (not y)
- not (x or y) = (not x) and (not y)
以上基本内容说不定就会用到，记录下。
Unit 1.2 Boolean Functions Synthesis
本小节主要讲了三点：
- 如何根据真值表来反向构造布尔函数
- 介绍了一个结论：任意布尔函数都能被与或非三种运算表示（Any Boolean function can be represented using an expression containing AND, OR and NOT operations.）
- 接下来会用与非门（Nand）来构建其他逻辑门
Unit 1.3 Logic gates
本小节着重在说明一个问题，即：这门课程不会从物理层面深究这种逻辑门是怎样实现的，但是会探讨如何利用基础逻辑门来构建复合逻辑门。另外，还介绍了在这个课程中会见到的一些描述用语。
PS：God bless their souls. 感觉像是在嘲讽呢（笑）。
Unit 1.4 Hardware Description Language
本小节主要在说明硬件描述语言（后面会简称 HDL）的语法规则，不多，建议直接自己看老师提供的手册，并试着写下代码，有了一定的感性认识后，再来听，可能会收获多一点。
Unit 1.5 Hardware Simulation
本小节主要在讲如何使用课程提供的硬件模拟器和一些注意事项。
Unit 1.6 Multi Bit Buses
本小节主要在说明多位（bit）逻辑门在本课程所用的 HDL 中的用法，并顺便大致的说明了一下总线的含义，对后面构造位逻辑单元有一定帮助，特别是有 HDL 代码的地方，对后面的作业很有帮助。
Unit 1.7 Project 1 Overview
本小节主要在介绍第一周的作业以及这周作业对于后续课程的意义。不得不说，国内老师从来不会跟你讲作业的意义，最多给你讲讲错题。
扯远了，每周作业包括三个部分：代码源文件（.hdl）、测试脚本（.tst）和比对文件（.cmp）（其实就是程序正确的运行结果），每一个小作业（就是你要实现的每一个小芯片）都包含这三个文件。好消息是测试脚本跟正确答案老师都准备好了，坏消息是代码得自己写（其实也不算坏消息，本就是分内之事，笑），下面我们来完成这周的作业。
PS：有一点要注意，下面这些逻辑门实现的方式不唯一，这也是老师一再强调的东西。
Not
Nand 是我们在这个课程中可以直接使用的基本逻辑门，可以直接使用，Not 是我们要完成的第一个芯片，所以我们直接使用一个二元的与非门来实现一个一元的非门（The implementation of a unary Not gate from a binary Nand gate is simple.）。
一元非门只有两种情况，二元与非门有四种情况，那么我们直接用与非门的其中两种情况来表示非门即可，代码如下：1
2
3
4
5
6
7CHIP Not {
IN in;
OUT out;
PARTS:
Nand(a=in, b=true, out=out);
}
And
一开始思考如何实现 And 时，有点无从下手的感觉后来，想了一会，想到了两种方法：
- 使用 2 个 Nand
- 使用 1 个 Nand，在使用 1 个 Not
1 | CHIP And { |
Or
实现 And 之后，此时我们可以使用上面实现好了的逻辑门来帮助实现 Or。
1 | CHIP Or { |
Xor
异或运算有点特殊，同样还是用已经实现过的逻辑门来实现。1
2
3
4
5
6
7
8
9CHIP Xor {
IN a, b;
OUT out;
PARTS:
Or(a=a, b=b, out=c);
Nand(a=a, b=b, out=d);
And(a=c, b=d, out=out);
}
Mux
Mux 全称 Multiplexor，即多路复用器（大概是这个意思吧），这个东西应该是通信专业同学研究的东西，有三个输入：a，b 和 sel。规则就是根据 sel 的值来确定输出 a 还是 b，sel 有点像是校验码之类的东西吧。
粗略分析一下，Mux 有八种情况，我们先观察一下它的真值表。
$$\begin{array}{ccc|c}
a & b & sel & Mux \\
\hline
0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 \\
\end{array}$$
Mux 的结果中有 4 个值为真，仔细回想一下老师在 1.2 讲的有关反向构造布尔函数的知识，首先先列出所有真值的表达式，也就是上表中的第 3、4、6、8 行，可得：
- 第 3 行：a and (not b) and (not sel)
- 第 4 行：a and b and (not sel)
- 第 6 行：not a and b and sel
- 第 8 行：a and b and sel
继而我们可以得到 Mux 的布尔函数式子：(a and (not b) and (not sel)) or (a and b and (not sel)) or ((not a) and b and sel) or (a and b and sel)。汗，真长，不过先不管，我们直接按照这个函数来写代码，可以得到以下代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
Not(in=b, out=notb);
Not(in=sel, out=notsel);
Not(in=a, out=nota);
And(a=a, b=notb, out=u1);
And(a=u1, b=notsel, out=u2);
And(a=a, b=b, out=v1);
And(a=v1, b=notsel, out=v2);
And(a=nota, b=b, out=w1);
And(a=w1, b=sel, out=w2);
And(a=a, b=b, out=x1);
And(a=x1, b=sel, out=x2);
Or(a=u2, b=v2, out=y1);
Or(a=y1, b=w2, out=y2);
Or(a=y2, b=x2, out=out);
}
测试后结果是正确的，不过这显然不够老师说的 elegant（笑），我们来把布尔函数式根据运算规则化简一下，可得：(a and (not sel)) or (b and sel)，从而可得：1
2
3
4
5
6
7
8
9
10CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
Not(in=sel, out=notsel);
And(a=a, b=notsel, out=u);
And(a=b, b=sel, out=v);
Or(a=u, b=v, out=out);
}
测试后结果依然正确，说明化简是正确的。
另外，通过上面的计算过程和老师的讲解，我们可以得到反向构造布尔函数时的几个要点：
- 选取结果序列中真值或假值较少的一方，上面的 Mux 中真假值都是 4 个，任取即可
- 用每一个值写出的式子必须保证其中的每一子项皆为真或假，比如以上面第 3 行为例，a、not b 和 not sel 的值都是 1
- 单个式子的每一子项要进行 and 运算，而每个式子之间则用 or 运算
PS：有关逻辑式子化简的问题，应该属于离散数学的知识。
DMux
DMux，Demultiplexor，即解复用器，与 Mux 是一对，二者的功能也正好相反，但 DMux 的特殊性在于它有两个输出。我们还是按照上面的思路来构建，先看一下 DMux 的真值表
$$\begin{array}{c|cc}
sel & a & b \\
\hline
0 & in & 0 \\
1 & 0 & in \\
\end{array}$$
这是老师提供的资料上的真值表，好像不是很易于分析问题，那我们把详细的真值表整理出来：
$$\begin{array}{cc|cc}
sel & in & a & b \\
\hline
0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 \\
\end{array}$$
这样，我们在分析这个问题时，就可以单独考虑如何利用 sel 和 in 分别得到 a、b 这两列值，代码如下：1
2
3
4
5
6
7
8
9
10
11CHIP DMux {
IN in, sel;
OUT a, b;
PARTS:
Not(in=in, out=notin);
Or(a=sel, b=notin, out=v1);
Not(in=v1, out=a);
And(a=sel, b=in, out=b);
}
Not16
多位逻辑门是老师在 1.6 讲过的内容，构造的基本思想就是每一位都用一个逻辑门来计算，组合在一起就可以了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22CHIP Not16 {
IN in[16];
OUT out[16];
PARTS:
Not(in=in[0], out=out[0]);
Not(in=in[1], out=out[1]);
Not(in=in[2], out=out[2]);
Not(in=in[3], out=out[3]);
Not(in=in[4], out=out[4]);
Not(in=in[5], out=out[5]);
Not(in=in[6], out=out[6]);
Not(in=in[7], out=out[7]);
Not(in=in[8], out=out[8]);
Not(in=in[9], out=out[9]);
Not(in=in[10], out=out[10]);
Not(in=in[11], out=out[11]);
Not(in=in[12], out=out[12]);
Not(in=in[13], out=out[13]);
Not(in=in[14], out=out[14]);
Not(in=in[15], out=out[15]);
}
And16
1 | CHIP And16 { |
Or16
1 | CHIP Or16 { |
Mux16
1 | CHIP Mux16 { |
Or8Way
1 | CHIP Or8Way { |
Mux4Way16
4 路 Mux16 使用三个 Mux16 即可完成，可能会有人问为什么要先让 a 和 c 先通过一次 Mux16。因为 sel bits 是从右往左读的，若 a 和 b 先通过一次 Mux16，当 sel[1]=0 时，就无法得到正确的输出结果了（sel[0]=0，就输出 a，sel[0]=1，就输出 b，但第一次通过 Mux16 后已经过滤掉 a 或 b 了）。1
2
3
4
5
6
7
8
9CHIP Mux4Way16 {
IN a[16], b[16], c[16], d[16], sel[2];
OUT out[16];
PARTS:
Mux16(a=a, b=c, sel=sel[1], out=v1);
Mux16(a=b, b=d, sel=sel[1], out=v2);
Mux16(a=v1, b=v2, sel=sel[0], out=out);
}
Mux8Way16
在 Mux4Way16 的基础上构造就行了，注意一下这里的语法。1
2
3
4
5
6
7
8
9
10
11CHIP Mux8Way16 {
IN a[16], b[16], c[16], d[16],
e[16], f[16], g[16], h[16],
sel[3];
OUT out[16];
PARTS:
Mux4Way16(a=a, b=c, c=e, d=g, sel=sel[1..2], out=v1);
Mux4Way16(a=b, b=d, c=f, d=h, sel=sel[1..2], out=v2);
Mux16(a=v1, b=v2, sel=sel[0], out=out);
}
DMux4Way
先用 sel[1] 来区分 a、b 和 c、d 两组，再用 sel[0] 在组内分别区分 a、b 和 c、d。1
2
3
4
5
6
7
8
9CHIP DMux4Way {
IN in, sel[2];
OUT a, b, c, d;
PARTS:
DMux(in=in, sel=sel[1], a=u1, b=u2);
DMux(in=u1, sel=sel[0], a=a, b=b);
DMux(in=u2, sel=sel[0], a=c, b=d);
}
DMux8Way
在 DMux4Way 的基础上构建就行，思路是完全一致的。1
2
3
4
5
6
7
8
9
10
11CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;
PARTS:
DMux4Way(in=in, sel=sel[1..2], a=u1, b=u2, c=u3, d=u4);
DMux(in=u1, sel=sel[0], a=a, b=b);
DMux(in=u2, sel=sel[0], a=c, b=d);
DMux(in=u3, sel=sel[0], a=e, b=f);
DMux(in=u4, sel=sel[0], a=g, b=h);
}
Unit 1.8 Perspectives
本小节主要老师们回答学生在论坛区提出的一些典型问题，这次主要回答了 3 个问题：
- 能否不用 Nand 而是用其他的基本逻辑门来构建一个计算机？
- 答案是 yes，这里我们不深究具体原因。
- Nand gate 的具体工作原理
- 老师用电路图讲了一下，当然，这是电气工程师该干的活，就不具体讨论了
- 工业坏境下使用的 HDL 语言与课程使用的 HDL 语言有何差别
- 工业环境用的肯定功能更加强大，效率更高，学习的时间较长；而本课程的 HDL 语言只是为了满足教学使用，所以功能性会弱很多，但易于学习，且足够满足本课程的所有需要
本周内容过于底层，估计不少人觉得无聊，不过还好不是太难。当然，可能会有第一次使用这样的 HDL 语言和硬件模拟器而不熟悉的问题，不过老师提供的手册和视频的讲解帮助还是很大的。个人感觉老师给的手册如果能更详细一点，用例再多一点就更好了（主要还是自己太懒，笑）。
