CS N2T

From Nand to Tetris: Project 01

Posted by KaiserTT's Blog on January 19, 2024

该系列博客用于记录 Coursera 课程 Build a Modern Computer from First Principles: From Nand to Tetris 中各个 Projects 的完整解答.

Project 1

Project 1 要求我们使用一个与非门(Nand)来实现其他 15 种逻辑门, 已实现的逻辑门可以在实现其他逻辑门时使用, 这 15 个逻辑门将用于后续更复杂的计算机组件的搭建.

课程推荐按以下顺序实现 15 种逻辑门:

image-20240119194056963

先来看看与非门(Nand)

\[in=a,b \quad out=\overline{ab}\]

非门(Not)

\[in = a \quad out=\overline{aa}=\overline{a}\] 
1
2
3
4
5
6
7
8

CHIP Not {
    IN in;
    OUT out;

    PARTS:
    // Put your code here:
    Nand(a=in, b=in, out=out);
}

与门(And)

\[in=a, b \quad out=\overline{\overline{ab}}=ab\] 
1
2
3
4
5
6
7
8
9

CHIP And {
    IN a, b;
    OUT out;

    PARTS:
    // Put your code here:
    Nand(a=a, b=b, out=nandOut);
    Not(in=nandOut, out=out);
}

或门(Or)

\[in=a,b \quad out=\overline{\overline{a}\overline{b}}=a+b\] 
1
2
3
4
5
6
7
8
9
10
11

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=o);
    Not(in=o, out=out);
}

异或门(Xor)

\[in=a,b \quad out=\overline{a}b+a\overline{b}\] 
1
2
3
4
5
6
7
8
9
10
11
12

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    // Put your code here:
    Not (in=a, out=nota);
    Not (in=b, out=notb);
    And (a=a, b=notb, out=aAndNotb);
    And (a=nota, b=b, out=notaAndb);
    Or  (a=aAndNotb, b=notaAndb, out=out);
}

多路选择器(Mux)

\[in=a,b,sel \quad out=bsel+a\overline{sel}\] 
1
2
3
4
5
6
7
8
9
10
11
12
13

CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:
    // Put your code here:
    Not(in=sel, out=notsel);

    And(a=b, b=sel, out=bAndsel);
    And(a=a, b=notsel, out=aAndnotsel);

    Or(a=aAndnotsel, b=bAndsel, out=out);
}

多路分解器(DMux)

\[in=in, sel\quad out=a,b\\ a=a\overline{sel},\quad b=bsel\] 
1
2
3
4
5
6
7
8
9
10

CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:
    // Put your code here:
    Not (in=sel, out=nots);
    And (a=nots, b=in, out=a);
    And (a=sel, b=in, out=b);
}

16 位非门(Not16)

16 位非门即对一个有 16 位的输入, 每个位都做一次非运算, 所以需要 16 个非门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

CHIP Not16 {
    IN in[16];
    OUT out[16];

    PARTS:
    // Put your code here:
    Nand(a=in[0], b=in[0], out=out[0]);
    Nand(a=in[1], b=in[1], out=out[1]);
    Nand(a=in[2], b=in[2], out=out[2]);
    Nand(a=in[3], b=in[3], out=out[3]);
    Nand(a=in[4], b=in[4], out=out[4]);
    Nand(a=in[5], b=in[5], out=out[5]);
    Nand(a=in[6], b=in[6], out=out[6]);
    Nand(a=in[7], b=in[7], out=out[7]);
    Nand(a=in[8], b=in[8], out=out[8]);
    Nand(a=in[9], b=in[9], out=out[9]);
    Nand(a=in[10], b=in[10], out=out[10]);
    Nand(a=in[11], b=in[11], out=out[11]);
    Nand(a=in[12], b=in[12], out=out[12]);
    Nand(a=in[13], b=in[13], out=out[13]);
    Nand(a=in[14], b=in[14], out=out[14]);
    Nand(a=in[15], b=in[15], out=out[15]);
}

16 位与门(Not16)

两个 16 位输入, 两个输入之间按位进行与运算, 需要 16 个与门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

    PARTS:
    // Put your code here:
    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]);
}

16 位或门(Not16)

两个 16 位输入, 两个输入之间按位进行或运算, 需要 16 个或门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

    PARTS:
    // Put your code here:
    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]);
}

16 位多路选择器(Mux16)

需要 16 个一位多路选择器 Mux

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

8 路或门(Or8Way)

该逻辑门作用是对一个 8 位的输入, 8 个位一起做一次或运算, 只要有一个位是 1 则输出为 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

    PARTS:
    // Put your code here:
    Or (a=in[0], b=in[1], out=t01);
    Or (a=t01, b=in[2], out=t02);
    Or (a=t02, b=in[3], out=t03);
    Or (a=t03, b=in[4], out=t04);
    Or (a=t04, b=in[5], out=t05);
    Or (a=t05, b=in[6], out=t06);
    Or (a=t06, b=in[7], out=out);
}

16 位 4 路多路选择器(Mux4Way16)

对于1 位 4 路多路选择器

1
2
3
4

out = a if sel == 00
      b if sel == 01
      c if sel == 10
      d if sel == 11
\[in=a,b,c,d,sel[2] \\ out =\overline{sel[0]sel[1]}a+\overline{sel[0]}sel[1]b+sel[0]\overline{sel[1]}c+sel[0]sel[1]d\]

观察以上式子, 其中 sel[0] 用于选择输出 a 与 b 其中一个, 同时选择输出 c 与 d 其中一个.

sel[1] 用于选择输出 sel[0] 选择得到的两个结果中的其中一个.

1
2
3
4
5
6
7
8
9
10

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=out1);
    Mux16(a=c, b=d, sel=sel[0], out=out2);
    Mux16(a=out1, b=out2, sel=sel[1], out=out);
}

16 位 8 路多路选择器(Mux4Way16)

对于 1 位 8 路选择器, sel[0] 和 sel[1] 可作为 4 路选择器的 sel[2]

1
2
3
4

out = a if sel == 000
      b if sel == 001
      etc.
      h if sel == 111

1
2
3
4
5
6
7
8
9
10
11
12

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=out1);
    Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=out2);
    Mux16(a=out1, b=out2, sel=sel[2], out=out);
}

4 路多路分解器(DMux4Way)

与 4 路选择器的实现方法类似

1
2
3
4

{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

1
2
3
4
5
6
7
8
9
10

CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:
    // Put your code here:
    DMux(in=in, sel=sel[0], a=out1, b=out2);
    DMux(in=out1, sel=sel[1], a=a, b=c);
    DMux(in=out2, sel=sel[1], a=b, b=d);
}

8 路多路分解器(DMux8Way)

1
2
3
4

 {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

1
2
3
4
5
6
7
8
9
10

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[2], a=out1, b=out2);
    DMux4Way(in=out1, sel=sel[0..1], a=a, b=b, c=c, d=d);
    DMux4Way(in=out2, sel=sel[0..1], a=e, b=f, c=g, d=h);
}
CATALOG
    FEATURED TAGS
    Blogs 机器学习 经济学 金融学 CS N2T 读书笔记
    FRIENDS