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.）。

一元非门只有两种情况，二元与非门有四种情况，那么我们直接用与非门的其中两种情况来表示非门即可，代码如下：

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    Nand(a=in, b=true, out=out);
}

And

一开始思考如何实现 And 时，有点无从下手的感觉后来，想了一会，想到了两种方法：

使用 2 个 Nand
使用 1 个 Nand，在使用 1 个 Not

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    /* method 1: use 2 Nand
    Nand(a=a, b=b, out=c);
    Nand(a=c, b=true, out=out);
    */
    /* method 2: use Nand and Not */
    Nand(a=a, b=b, out=c);
    Not(in=c, out=out);
}

Or

实现 And 之后，此时我们可以使用上面实现好了的逻辑门来帮助实现 Or。

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=nota, b=notb, out=e);
    Not(in=e, out=out);
}

Xor

异或运算有点特殊，同样还是用已经实现过的逻辑门来实现。

CHIP 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)。汗，真长，不过先不管，我们直接按照这个函数来写代码，可以得到以下代码：

CHIP 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)，从而可得：

CHIP 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);
}

测试后结果依然正确，说明化简是正确的。

为什么要使用上面的方法来构造布尔函数？因为此时我们能用的逻辑门已经不仅仅只有 Nand，还有先前已经构造好了的 And、Not、Or、Xor，这些都可以直接拿来用了，那还费脑子死想干嘛呢。当然了，这也是老师强调过的思想。

另外，通过上面的计算过程和老师的讲解，我们可以得到反向构造布尔函数时的几个要点：

选取结果序列中真值或假值较少的一方，上面的 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 这两列值，代码如下：

CHIP 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 讲过的内容，构造的基本思想就是每一位都用一个逻辑门来计算，组合在一起就可以了。

CHIP 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

CHIP And16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    And(a=a[0], b=b[0], out=out[0]);
    And(a=a[1], b=b[1], out=out[1]);
    And(a=a[2], b=b[2], out=out[2]);
    And(a=a[3], b=b[3], out=out[3]);
    And(a=a[4], b=b[4], out=out[4]);
    And(a=a[5], b=b[5], out=out[5]);
    And(a=a[6], b=b[6], out=out[6]);
    And(a=a[7], b=b[7], out=out[7]);
    And(a=a[8], b=b[8], out=out[8]);
    And(a=a[9], b=b[9], out=out[9]);
    And(a=a[10], b=b[10], out=out[10]);
    And(a=a[11], b=b[11], out=out[11]);
    And(a=a[12], b=b[12], out=out[12]);
    And(a=a[13], b=b[13], out=out[13]);
    And(a=a[14], b=b[14], out=out[14]);
    And(a=a[15], b=b[15], out=out[15]);
}

Or16

CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    Or(a=a[0], b=b[0], out=out[0]);
    Or(a=a[1], b=b[1], out=out[1]);
    Or(a=a[2], b=b[2], out=out[2]);
    Or(a=a[3], b=b[3], out=out[3]);
    Or(a=a[4], b=b[4], out=out[4]);
    Or(a=a[5], b=b[5], out=out[5]);
    Or(a=a[6], b=b[6], out=out[6]);
    Or(a=a[7], b=b[7], out=out[7]);
    Or(a=a[8], b=b[8], out=out[8]);
    Or(a=a[9], b=b[9], out=out[9]);
    Or(a=a[10], b=b[10], out=out[10]);
    Or(a=a[11], b=b[11], out=out[11]);
    Or(a=a[12], b=b[12], out=out[12]);
    Or(a=a[13], b=b[13], out=out[13]);
    Or(a=a[14], b=b[14], out=out[14]);
    Or(a=a[15], b=b[15], out=out[15]);
}

Mux16

CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:
    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}

Or8Way

CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:
    Or(a=in[0], b=in[1], out=v1);
    Or(a=v1, b=in[2], out=v2);
    Or(a=v2, b=in[3], out=v3);
    Or(a=v3, b=in[4], out=v4);
    Or(a=v4, b=in[5], out=v5);
    Or(a=v5, b=in[6], out=v6);
    Or(a=v6, b=in[7], out=out);
}

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 了）。

CHIP 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 的基础上构造就行了，注意一下这里的语法。

CHIP 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。

CHIP 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 的基础上构建就行，思路是完全一致的。

CHIP 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 语言和硬件模拟器而不熟悉的问题，不过老师提供的手册和视频的讲解帮助还是很大的。个人感觉老师给的手册如果能更详细一点，用例再多一点就更好了（主要还是自己太懒，笑）。

bachzart's Blog

Nand2Tetris_Part1_01