Nand2Tetris_Part1_02

Posted on | Edited on | In ,
| 6.6k | 55 mins.

本周的主题是 Boolean Arithmetic and the ALU Roadmap，旨在介绍如何构建加法器（adder）和算术逻辑单元（Arithmetic Logic Unit，ALU），学习路线依然还是从简单到复杂。

Unit 2.1 Binary Numbers

本小节主要在说明二进制与十进制的一些联系，粗略介绍了一下进制转换的过程，但没有说明具体的方法。学过一门编程语言课的同学，肯定对这些都已经很熟悉；没学过的，老师讲的也很清晰。

Unit 2.2 Binary Addition

本小节主要在介绍二进制加法规则，本质上与十进制是一样的。但由于二进制算术存在位数（bits）的限制，所以会产生溢出（overflow）的问题，老师暂时没有讲具体的解决办法，只说明了，在计算机内是会直接忽略掉的，但是使用者必须知道溢出了。
接着，又由易到难的介绍了三种加法器，并大致说明了一下构造的方法，这也是本周的作业之一。

Unit 2.3 Negative Numbers

前面介绍的规则都是与正数相关的，而本小节主要在介绍在计算机中如何表示负数，老师主要介绍了两种表示方法：

  1. 用最前面的 1 位（1 bit）代表符号，为 0，则为正数，为 1，则为负数，二者绝对值相等。这样表示会有一个问题，那就是会产生正 0 和 负 0，这样在做加、减法时会产生问题，所以舍弃了这种方法
  2. 用 $2^N + (-x) = 2^N - x$ 来表示负数，其中 -x 就是要表示的负数，这样表示后就没有负 0 了，且在做加、减法时也是完全正确的。

说点题外话，上面的几小节内容对应了组成原理中有关数的表示部分，提到的一些方法，其实就是原码、补码（radix complement）和反码的概念，可能是老师为了照顾非计算机专业的学生，一点没提这些东西，也有可能是国外讲课的风格导致了老师不会硬讲这些概念性的东西吧。

Unit 2.4 Arithmetic Logic Unit

本小节主要在介绍后面要构建的计算机 Hack 的 ALU 是如何构建的。
首先是对此 ALU 的基本介绍，包括其输入、输出、控制位（control bits），注意其控制位有两类，有 6 个算是功能控制位，剩下两个是输出控制位，且并没有说明输出控制位存在的意义。
接着，说明了如何使用硬件模拟器来使用模拟 ALU 的一些功能，在这一块，如果对 ALU 的运算过程不清楚可以使用内置的（built-in）ALU 来熟悉一下过程。
最后，举例验证了 ALU 能逐一实现所要求功能的可靠性，但老师没有介绍具体的原理，想了解就得自己看资料了。
还剩下的最后一点是在说明 Hack ALU 的优点，通俗来讲其实就是一点：易于学习。

Unit 2.5 Project 2 Overview

本小节主要在介绍这周的作业，并给出了一些提示信息。
尽管在第一周已经实现了很多 chips，但是老师建议不要使用自己实现的 chips，直接使用软件自带（built-in）的 chips，原因是为了避免软件可能会产生的卡顿等情况。
下面我们就来开始完成这周的作业。

HalfAdder

按照老师给的提示，直接用 Xor 和 And 来实现就完事了。

1
2
3
4
5
6
7
8
9
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);
}

FullAdder

1
2
3
4
5
6
7
8
9
10
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=s1, carry=v1);
    HalfAdder(a=s1, b=c, sum=sum, carry=v2);
    Or(a=v1, b=v2, out=carry);
}

Add16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:
    HalfAdder(a=a[0], b=b[0], sum=out[0], carry=c1);
    FullAdder(a=a[1], b=b[1], c=c1, sum=out[1], carry=c2);
    FullAdder(a=a[2], b=b[2], c=c2, sum=out[2], carry=c3);
    FullAdder(a=a[3], b=b[3], c=c3, sum=out[3], carry=c4);
    FullAdder(a=a[4], b=b[4], c=c4, sum=out[4], carry=c5);
    FullAdder(a=a[5], b=b[5], c=c5, sum=out[5], carry=c6);
    FullAdder(a=a[6], b=b[6], c=c6, sum=out[6], carry=c7);
    FullAdder(a=a[7], b=b[7], c=c7, sum=out[7], carry=c8);
    FullAdder(a=a[8], b=b[8], c=c8, sum=out[8], carry=c9);
    FullAdder(a=a[9], b=b[9], c=c9, sum=out[9], carry=c10);
    FullAdder(a=a[10], b=b[10], c=c10, sum=out[10], carry=c11);
    FullAdder(a=a[11], b=b[11], c=c11, sum=out[11], carry=c12);
    FullAdder(a=a[12], b=b[12], c=c12, sum=out[12], carry=c13);
    FullAdder(a=a[13], b=b[13], c=c13, sum=out[13], carry=c14);
    FullAdder(a=a[14], b=b[14], c=c14, sum=out[14], carry=c15);
    FullAdder(a=a[15], b=b[15], c=c15, sum=out[15], carry=c16);
}

Inc16

1
2
3
4
5
6
7
CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:
   	Add16(a=in, b[0]=true, out=out);
}

ALU_nostat

按照老师所给资料上的提示，我们先不去考虑 ng 和 zr 这两个输出控制位，直接考虑输出即可。那我们先得构造出能根据 zx 和 nx 这两个控制位来选择性输出的逻辑电路，当然，这个逻辑电路总线宽度是 16 位的。
结果硬想了好一会儿，没想出来。后来意识到，这个问题本质上其实就是在思考如何在没有条件编程语句的情况下构造出条件逻辑。
胡乱的写了些代码，发现语法都不通，但脑子里始终想的都是：在现有的可使用的逻辑电路里，好像没有可以用于条件选择的啊？
过了两天，又回来思考这个问题，突然发现，Mux 这种东西不是根据 sel bit 来选择性输出的吗？突然想到自己之前的想法：这东西应该是通信专业同学研究的东西吧...
好吧，自己一开始就把正确的思考方向给抛到九霄云外去了，真是搬起石头砸自己的脚，想的我真是辛苦...
扯远了，有了上面的思路后，这个问题其实就很容易了，直接看下面代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
CHIP ALU {
    IN  
        x[16], y[16],  // 16-bit inputs        
        zx, // zero the x input?
        nx, // negate the x input?
        zy, // zero the y input?
        ny, // negate the y input?
        f,  // compute out = x + y (if 1) or x & y (if 0)
        no; // negate the out output?

    OUT 
        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    PARTS:
        //zx nx
        Mux16(a=x, b=false, sel=zx, out=x1);
        Not16(in=x1, out=x2);
        Mux16(a=x1, b=x2, sel=nx, out=x3);
        //zy ny
        Mux16(a=y, b=false, sel=zy, out=y1);
        Not16(in=y1, out=y2);
        Mux16(a=y1, b=y2, sel=ny, out=y3);
        //f
        Add16(a=x3, b=y3, out=z1);
        And16(a=x3, b=y3, out=z2);
        Mux16(a=z2, b=z1, sel=f, out=z3);
        //no
        Not16(in=z3, out=z4);
        Mux16(a=z3, b=z4, sel=no, out=out);
}

ALU

完成上面的任务后，接下来我们需要考虑的问题就是如何得到 zr 和 ng 的正确结果。
按照前面的课程内容，我们已经知道负数的最高位 bit 是 1，所以 ng 就很容易得到了。但是 zr 就不是那么易得了，原因在于 0 的二进制最高位与普通正数的二进制最高位一样，都是 0 ，所以无法轻易的区分。这里好像又回到了我们在之前碰到的问题：如何在没有判断编程语句的情况下构造出判断逻辑呢？
注意到 0 先取反再自增加 1 后，得到的二进制序列最高位与原序列最高位一致（溢出的 bit 舍弃），而其他的数由此过程得到的两个序列的最高位必然一个是 1，另一个是 0。如此一来，问题就解决了。
当然了，要想得到 zr，最快的办法其实就是让最后的结果序列按位取或（Or）运算，采用之前构造的 Or8Way 这个逻辑电路，试了下，好像总是语法有问题...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
CHIP ALU {
    IN  
        x[16], y[16],  // 16-bit inputs        
        zx, // zero the x input?
        nx, // negate the x input?
        zy, // zero the y input?
        ny, // negate the y input?
        f,  // compute out = x + y (if 1) or x & y (if 0)
        no; // negate the out output?

    OUT 
        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    PARTS:
        //zx nx
        Mux16(a=x, b=false, sel=zx, out=x1);
        Not16(in=x1, out=x2);
        Mux16(a=x1, b=x2, sel=nx, out=x3);
        //zy ny
        Mux16(a=y, b=false, sel=zy, out=y1);
        Not16(in=y1, out=y2);
        Mux16(a=y1, b=y2, sel=ny, out=y3);
        //f
        Add16(a=x3, b=y3, out=z1);
        And16(a=x3, b=y3, out=z2);
        Mux16(a=z2, b=z1, sel=f, out=z3);
        //no zr ng
        Not16(in=z3, out=z4);
        Mux16(a=z3, b=z4, sel=no, out=z5);

        Not16(in=z5, out=z6);
        Inc16(in=z6, out=z7);
        Or16(a=z5, b=z7, out[15]=z8);
        Not(in=z8, out=zr);
        
        And16(a=z5, b=true, out[15]=ng);
        Mux16(a=z3, b=z4, sel=no, out=out);
}

Unit 2.6 Perspectives

这周的问题主要有 4 个：

  1. 目前所构建的大约 20 种逻辑电路，是否都是标准的？
    • 问这个问题的人口中的标准应该是相对于工业界而言的，老师的回答很直接，除了用于学习的 ALU，其他都是标准的。其实仔细一想，太底层的东西，反而没有多种构建方法，大家用的其实都是那一套。
  2. 目前实现的 ALU 为何不能提供乘法或除法？
    • 因为课程中实现的 ALU 过于简单，只是为了学习使用。但你依然可以自己去实现乘法或除法，这取决于开发者是否需要给它添加这个功能。
  3. 课程中的 ALU 是否高效？
    • 课程中设计的大多数逻辑电路都是高效的，但有一种仍然可以改进的更高效，那就是——Adder。目前它“低效”的原因在于，其内部实现是由多个全加器“串”起来的，所以二进制比特流的流动存在一定的延迟。
  4. 为何建议学生使用 built-in chips？
    • 第一，使用 built-in chips 会更加高效；第二是因为可以避免一些未知的错误，而这些错误可能是由模拟器的 bug 导致的，也就是说这并不是你的代码有问题；第三，模拟器并不高效，使用自己构建的 chips 可能会进一步降低效率。

这周内容的难点在于如何构建 ALU，可见在没有高级语言的帮助下，如果想要在底层实现一些复杂逻辑，还是挺费脑子的。
另外，还有一块知识老师没有强调，就是根据逻辑运算来构造实际运算，也就是 ALU 这样设计的背后原理，这部分内容可能又跟电学有点关系吧...

Buy me a coffee ? :)
0%