Nand to Tetris 0

Chapter 1 - Boolean Logic

Such simple things, and we make of them something so complex it defeats us, Almost. John Ashbery (1927–2017)

所有的电子设备都由芯片驱动，而各式各样的芯片虽然外形和功能都大不相同，但其内部都是由一些基本的逻辑门组成的。常见的逻辑门有：Nand, And, Or, Not, Xor, Mux, DMux… 而这些逻辑门都可由 NAnd 门组合而成。在「Nand2Tetris」中，我们将从 NAnd 门开始，逐步构建出一个完整的计算机。在这一章里，我们的任务是组装出这些常见的逻辑门。

先介绍 Nand 门

Nand 门计算两个输入的逻辑与后取反的结果，即：$nand(A, B) = \overline{AB}$，Nand 门的真值表如下：

A	B	nand(A, B)
0	0	1
0	1	1
1	0	1
1	1	0

先试试最简单的 Not 门

Not 门计算一个输入取反后的结果，由于我们已知 $AA = A$，就有 $\overline{A} = \overline{AA} = nand(A, A)$ 。于是可以这样实现 Not 门：

CHIP Not {
    IN in;
    OUT out;

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

再试试 And 门、 Or 门和 Xor 门

同样我们可以推出这样两个式子：

\begin{align*} & and(A, B) = AB = \overline{\overline{AB}} = not(nand(A, B))\\ & or(A, B) = A + B = \overline{\overline{A}\times\overline{B}} = nand(not(A), not(B))\\ & xor(A, B) = \overline{A}B + A\overline{B} = \overline{AB}\times (A + B) = and(nand(A, B), or(A, B)) \end{align*}

然后按照式子实现 And 门、 Or 门和 Xor 门：

CHIP And {
    IN a, b;
    OUT out;

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

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:
    Not(in= a, out= na);
    Not(in= b, out= nb);
    Nand(a= na, b= nb, out= out);
}

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    Nand(a= a, b= b, out= nand);
    Or(a= a, b= b, out= or);
    And(a= nand, b= or, out= out);
}

然后是 Mux 门和 DMux 门

相较于前面几个门，这两个逻辑门的作用更像是一种选择器（我感觉前几个门更像是一种运算器）。Mux 门的作用是根据「选择信号」选择「输入信号」中的一个输出，而 DMux 门的作用是根据「选择信号」将「输入信号」分为两个输出：

\begin{align*} & mux(A, B, sel) = \begin{cases} A& sel = 0\\ B& sel = 1 \end{cases} \\ & dmux(in, sel) = \begin{cases} (in, 0)& sel = 0\\ (0, in)& sel = 1 \end{cases} \end{align*}

对于这种比较复杂的式子，如果无法一眼看出逻辑表达式，其实可以考虑通过列真值表加卡诺图化简的方式处理。这里我们先列出 Mux 门的真值表：

A	B	sel	mux(sel, A, B)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

然后得出 $mux(A, B, sel) = \overline{sel}\times A + sel\times B$ 。

类似的办法也能得到 $dmux(in, sel) = (in\times\overline{sel}, in\times sel)$ 。

最后是多位逻辑门和多路逻辑门！

在现代的计算机中，我们通常不会单独操作一个二进制位，而是直接操作一个二进制组。比如我们平时说的 32/64 位机器，就是指它们的处理器一次可以处理 32/64 个二进制位。而且在「Nand2Tetris」中我们要实现的计算机是 16 位的，所以我们要对应地实现一些多位的逻辑门和多路逻辑门。

And16、Or16、Mux16 等等这几个逻辑门的作用就是把 16 位对应 And/Or/Mux/… 在一起，所以你只要写很多类似 And(a= a[i], b= b[i], out= out[i]); 的代码就行了（不过由于 n2t 用的教学语言十分简陋，你可能需要通过别的程序来生成一下代码）。

然后多路逻辑门（以 DMux_Way）为例，只要用类似递归的思路去组合，用 DMux 去组合出 DMux4Way、用 DMux4Way 去组合 DMux8Way … 下面以 DMux8Way 的代码为例：

CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;

    PARTS:
    DMux(in= in, sel= sel[2], a= t0, b= t1);
    DMux4Way(in= t0, sel= sel[0..1], a= a, b= b, c= c, d= d);
    DMux4Way(in= t1, sel= sel[0..1], a= e, b= f, c= g, d= h);
}

Chapter 2 - Boolean Arithmetic

Counting is the religion of this generation, its hope and salvation. Gertrude Stein (1874–1946)

第二章的主题会从第一章的布尔运算转到我们日常生活中更常见的的算数运算，我们会用第一章中实现的芯片来实现半加器、全加器和增值器（incrementer），最后来组装出算数逻辑单元（ALU）。

二进制表示数的内容在网上已经有很多资料了，这里就全部略去。

首先向我们走来的是——半加器！

半加器的作用是将两个二进制位相加，并返回它们的和（sum）和它们的进位（carry）。我们去分析一下它的真值表：

A	B	sum	carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

可以发现：

\begin{align*} & sum = A \oplus B \\ & carry = AB \end{align*}

转换成代码即是：

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b
        carry;  // Left bit of a + b

    PARTS:
    Xor(a= a, b= b, out= sum);
    And(a= a, b= b, out= carry);
}

全加器，顾名思义就是两个半加器

全加器在半加器的基础上考虑了来自上一位的进位。也就是说，全加器会计算三个二进制位的和与进位。实现上只要把先把两个二进制位用半加器连接起来，再把产生的和与第三个二进制位连接起来，而整个全加器的进位则是两个进位的或：

CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    PARTS:
    HalfAdder(a= a, b= b, sum= s, carry= t);
    HalfAdder(a= s, b= c, sum= sum, carry= u);
    Or(a= t, b= u, out= carry);
}

未完待续