Nand2Tetris笔记 - Nand2Tetris week-1 - 《CS笔记👑》

作业顺序
与非门 Nand
- 与非门的真值表
非门 Not
或门 Or
数据选择器 Mux
数据分配器 DMux
16位-数据选择器 Mux16
4路16位数据选择器 Mux4Way16
8路16位数据选择器 Mux8Way16
4路数据分配器 DMux4Way
8路数据分配器 DMux8Way
- sub-bus问题
作业提交
总结

作业顺序

与非门 Nand

与非门是内置的，无需编写，可以直接使用，其他逻辑结构，在编写后才能使用。

A NAND B = NOT(A AND B)

与非门的真值表

a	b	out
0	0	1
0	1	1
1	0	1
1	1	0

其实只要构造出来其中一个常见的门（与或非），其他的都很容易推断出来。

非门 Not

非门只有一个输入，比较好猜想验证。

发现Nand两个输入相同时，会得到与输入端相反的结果。这就实现了非门。

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Not.hdl
/**
 * Not gate:
 * out = not in
 */
CHIP Not {
    IN in;
    OUT out;
    PARTS:
    // Put your code here:
    Nand(a=in, b=in, out=out);
}

或门 Or

采用德摩根律

A Or B = not(not(A) and not(B))

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Or.hdl
 /**
 * Or gate:
 * out = 1 if (a == 1 or b == 1)
 *       0 otherwise
 */
CHIP Or {
    IN a, b;
    OUT out;
    PARTS:
    // Put your code here:
    Not(in=a, out=nota);
    Not(in=b, out=notb);
    And(a=nota, b=notb, out=tmp);
    Not(in=tmp, out=out);
}

数据选择器 Mux

两个提示点

a or 0 = a和a and 1 = a

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux.hdl
/** 
 * Multiplexor:
 * out = a if sel == 0
 *       b otherwise
 */
CHIP Mux {
    IN a, b, sel;
    OUT out;
    PARTS:
    // Put your code here:
    Not(in=sel, out=notsel);
    And(a=notsel, b=a, out=w1);
    And(a=sel, b=b, out=w2);
    Or(a=w1, b=w2, out=out);
}

数据分配器 DMux

需要学会填充常数

a and 0 = 0和a and 1 = 1

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/DMux.hdl
/**
 * Demultiplexor:
 * {a, b} = {in, 0} if sel == 0
 *          {0, in} if sel == 1
 */
CHIP DMux {
    IN in, sel;
    OUT a, b;
    PARTS:
    // Put your code here:
    Not(in=sel, out=notsel);
    And(a=in, b=notsel, out=a);
    And(a=in, b=sel, out=b);
}

16位-数据选择器 Mux16

第二部分就是许多简单门的并行，都是直接重复调用前面写好的简单门，HDL没有loop，不能简写。

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux16.hdl
/**
 * 16-bit multiplexor: 
 * for i = 0..15 out[i] = a[i] if sel == 0 
 *                        b[i] if sel == 1
 */
CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];
    PARTS:
    // Put your code here:
    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]);
}

4路16位数据选择器 Mux4Way16

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux4Way16.hdl
/**
 * 4-way 16-bit multiplexor:
 * out = a if sel == 00
 *       b if sel == 01
 *       c if sel == 10
 *       d if sel == 11
 */
CHIP Mux4Way16 {
    IN a[16], b[16], c[16], d[16], sel[2];
    OUT out[16];
    PARTS:
    // Put your code here:
    Mux16(a=a, b=b, sel=sel[0], out=tmp1);
    Mux16(a=c, b=d, sel=sel[0], out=tmp2);
    Mux16(a=tmp1, b=tmp2, sel=sel[1], out=out);
}

8路16位数据选择器 Mux8Way16

调用上次的4路16位数据选择器，注意使用sub-bus时，中间是2个点，这个我点多了，没注意到这个错误。

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux8Way16.hdl
/**
 * 8-way 16-bit multiplexor:
 * out = a if sel == 000
 *       b if sel == 001
 *       etc.
 *       h if sel == 111
 */
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:
    // Put your code here:
    Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=tmp1);
    Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=tmp2);
    Mux16(a=tmp1, b=tmp2, sel=sel[2], out=out);
}

4路数据分配器 DMux4Way

这个我想了很久，也没有思路，还是查了别人的解法。类似从树的根开始递归遍历寻找in，需要剪掉的分支，直接赋予0，之后的递归全都是0了。

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/DMux4Way.hdl
/**
 * 4-way demultiplexor:
 * {a, b, c, d} = {in, 0, 0, 0} if sel == 00
 *                {0, in, 0, 0} if sel == 01
 *                {0, 0, in, 0} if sel == 10
 *                {0, 0, 0, in} if sel == 11
 */
CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;
    PARTS:
    // Put your code here:
    //Dmux可以理解为sel = 0, 把in赋给前面，否则赋值后面
    DMux(in=in, sel=sel[0], a=w1, b=w2); 
    //根据低位划分，低位符合的一组赋值为in，否则为0
    DMux(in=w1, sel=sel[1], a=a, b=c);
    DMux(in=w2, sel=sel[1], a=b, b=d);
}

8路数据分配器 DMux8Way

sub-bus问题

这个姑且强调一下，也是看了论坛好多人问这个问题，虽然我没犯这个错误。

下标问题，比如c语言的字串，数组都是从左往右，下标依次增大的；

而本课程的HDL下标是从左向右，依次减小的，类似计算机组成原理中的大端（Big-Endian）；

也因此，在递归处理8路数据分配器（拆成两个4路分配器）时，是从低位（右边）开始的，也就是调用时，几个参数是不连续的（这又类似低位交叉编址，误）

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/DMux8Way.hdl
/**
 * 8-way demultiplexor:
 * {a, b, c, d, e, f, g, h} = {in, 0, 0, 0, 0, 0, 0, 0} if sel == 000
 *                            {0, in, 0, 0, 0, 0, 0, 0} if sel == 001
 *                            etc.
 *                            {0, 0, 0, 0, 0, 0, 0, in} if sel == 111
 */
CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;
    PARTS:
    // Put your code here:
    DMux(in=in, sel=sel[0], a=w1, b=w2);
    DMux4Way(in=w1, sel=sel[1..2], a=a, b=c, c=e, d=g);
    DMux4Way(in=w2, sel=sel[1..2], a=b, b=d, c=f, d=h);
    //吐槽，这里类似低位交叉编址。。。
}

作业提交

总结

作业大约是从下午1点做到晚上8点，中间吃了2顿饭，去洗了一次澡，没思路就想看会手机。也算是大约和推荐的5h差不多吧。

回顾看一看代码量并不大，但是许多地方想写，会用自然语言或者c语言，但是并不能使用好HDL来写，确实有难度。

遇到不会的地方，想不懂的地方，也要去看看别人的思路。