---
tags: nand2tetris
---
# From Nand to Tetris 學習筆記
[TOC]
# 0. Introduction
這門課會從最底層開始建構，最底層是指邏輯閘，從 nand 閘開始，建構出基本元件，然後從全加器、 ALU 、暫存器 一路向上建構出 CPU 與整台電腦。
此課程的API
# 1. Boolean functions ans logic gate
:::success
習題順序為
1. Not
1. And
1. Or
1. Xor
1. Mux
1. DMux
1. Not16
1. And16
1. Or16
1. Mux16
1. Or8Way
1. Mux4Way16
1. Mux8Way16
1. DMux4Way
1. DMux8Way
:::
接下來會以比較經典的邏輯閘應用當作展示，首先先複習布林代數
## 布林代數複習
## Not
```c=
/**
* Not gate:
* out = not in
*/
CHIP Not {
IN in;
OUT out;
PARTS:
// Put your code here:
Nand(a=in, b=in, out=out);
}
```
## Mux and DMux
```c=
/**
* 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=a, b=notSel, out=sela);
And(a=b, b=sel, out=selb);
Or(a=sela, b=selb, out=out);
}
```
```c=
/**
* Demultiplexor:
* {a, b} = {in, 0} if sel == 0
* {0, in} if sel == 1
*/
CHIP DMux {
IN in, sel;
OUT a, b;
PARTS:
Not(in=sel, out=notSel);
And(a=notSel, b=in, out=a);
And(a=sel, b=in, out=b);
}
```
## Or8Way
```c=
/**
* 8-way Or:
* out = (in[0] or in[1] or ... or in[7])
*/
CHIP Or8Way {
IN in[8];
OUT out;
PARTS:
// Put your code here:
Or(a=in[0], b=in[1], out=out01);
Or(a=in[2], b=in[3], out=out23);
Or(a=in[4], b=in[5], out=out45);
Or(a=in[6], b=in[7], out=out67);
Or(a=out01, b=out23, out=out0123);
Or(a=out45, b=out67, out=out4567);
Or(a=out0123, b=out4567, out=out);
}
```
## Mux4Way16
```c=
/**
* 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=outab);
Mux16(a=c, b=d, sel=sel[0], out=outcd);
Mux16(a=outab, b=outcd, sel=sel[1], out=out);
}
```
## Mux8Way16
```c=
/**
* 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=outabcd);
Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=outdefg);
Mux16(a=outabcd, b=outdefg, sel=sel[2], out=out);
}
```
# 2. Boolean arithmetic and the ALU
:::success
習題順序為：
1. HalfAdder
1. FullAdder
1. Add16
1. Inc16
1. ALU
:::
## Adder
## 半加器
```c=
/**
* Computes the sum of two bits.
*/
CHIP HalfAdder {
IN a, b; // 1-bit inputs
OUT sum, // Right bit of a + b
carry; // Left bit of a + b
PARTS:
// Put you code here:
Xor(a=a, b=b, out=sum);
And(a=a, b=b, out=carry);
}
```
## 全加器
```c=
/**
* Computes the sum of three bits.
*/
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:
// Put you code here:
Xor(a=a, b=b, out=aXorb);
Xor(a=aXorb, b=c, out=sum);
And(a=a, b=b, out=aAndb);
And(a=b, b=c, out=bAndc);
And(a=c, b=a, out=cAnda);
Or(a=aAndb, b=bAndc, out=aAndbOrbAndc);
Or(a=aAndbOrbAndc, b=cAnda, out=carry);
}
```
```c=
/**
* Computes the sum of three bits.
*/
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:
// Put you code here:
HalfAdder(a=a, b=b, sum=sumab, carry=carryab);
HalfAdder(a=sumab, b=c, sum=sum, carry=carryabc);
Or(a=carryab, b=carryabc, out=carry);
}
```
## Add16
```c=
/**
* Adds two 16-bit values.
* The most significant carry bit is ignored.
*/
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
// Put you code here:
HalfAdder (a=a[0], b=b[0], sum=out[0], carry=carry1);
FullAdder (a=a[1], b=b[1], c=carry1 , sum=out[1], carry=carry2);
FullAdder (a=a[2], b=b[2], c=carry2 , sum=out[2], carry=carry3);
FullAdder (a=a[3], b=b[3], c=carry3 , sum=out[3], carry=carry4);
FullAdder (a=a[4], b=b[4], c=carry4 , sum=out[4], carry=carry5);
FullAdder (a=a[5], b=b[5], c=carry5 , sum=out[5], carry=carry6);
FullAdder (a=a[6], b=b[6], c=carry6 , sum=out[6], carry=carry7);
FullAdder (a=a[7], b=b[7], c=carry7 , sum=out[7], carry=carry8);
FullAdder (a=a[8], b=b[8], c=carry8 , sum=out[8], carry=carry9);
FullAdder (a=a[9], b=b[9], c=carry9 , sum=out[9], carry=carry10);
FullAdder (a=a[10], b=b[10], c=carry10 , sum=out[10], carry=carry11);
FullAdder (a=a[11], b=b[11], c=carry11 , sum=out[11], carry=carry12);
FullAdder (a=a[12], b=b[12], c=carry12 , sum=out[12], carry=carry13);
FullAdder (a=a[13], b=b[13], c=carry13 , sum=out[13], carry=carry14);
FullAdder (a=a[14], b=b[14], c=carry14 , sum=out[14], carry=carry15);
FullAdder (a=a[15], b=b[15], c=carry15 , sum=out[15], carry=carry16);
}
```
## Inc16
```c=
/**
* 16-bit incrementer:
* out = in + 1 (arithmetic addition)
*/
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
// Put you code here:
Add16(a=in, b[0]=true, out=out);
}
```
## ALU
> 假設我們要計算y-x，我們可以設定control bits得到結果
```c=
/**
* The ALU (Arithmetic Logic Unit).
* Computes one of the following functions:
* x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
* x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs,
* according to 6 input bits denoted zx,nx,zy,ny,f,no.
* In addition, the ALU computes two 1-bit outputs:
* if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
* if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.
*/
// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0 // 16-bit constant
// if (nx == 1) set x = !x // bitwise not
// if (zy == 1) set y = 0 // 16-bit constant
// if (ny == 1) set y = !y // bitwise not
// if (f == 1) set out = x + y // integer 2's complement addition
// if (f == 0) set out = x & y // bitwise and
// if (no == 1) set out = !out // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1
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:
Mux16 (a=x, b=false, sel=zx, out=maybeZeroedX);
Mux16 (a=y, b=false, sel=zy, out=maybeZeroedY);
Not16 (in=maybeZeroedX, out=negX);
Not16 (in=maybeZeroedY, out=negY);
Mux16 (a=maybeZeroedX, b=negX, sel=nx, out=transformedX);
Mux16 (a=maybeZeroedY, b=negY, sel=ny, out=transformedY);
Add16 (a=transformedX, b=transformedY, out=sum);
And16 (a=transformedX, b=transformedY, out=and);
Mux16 (a=and, b=sum, sel=f, out=output);
Not16 (in=output, out=negatedOutput);
Mux16 (a=output, b=negatedOutput, sel=no, out=out, out[15]=ng, out[0..7]=firstHalfOut, out[8..15]=secondHalfOut);
Or8Way (in=firstHalfOut, out=firstOr);
Or8Way (in=secondHalfOut, out=secondOr);
Or (a=firstOr, b=secondOr, out=or16Way);
Not (in=or16Way, out=zr);
}
```
# 3. Memory
:::success
習題順序為：
1. 1 bit register
1. 16-bit register
1. RAM8（16-bit / 8-register memory）
1. RAM64
1. RAM512
1. RAM4K
1. RAM16K
1. PC（Program Counter）
:::
## 邏輯電路種類
## 正反器（Flip-Flop）
## 時脈（Clock）
## 拴鎖（Latch）
沒有時脈控制信號的正反器稱為「拴鎖（Latch）」，由於無時脈控制不容易同步，每級會產生延遲容易發生錯誤。
## RS正反器
## D型正反器
## 1 bit register
```c=
/**
* 1-bit register:
* If load[t] == 1 then out[t+1] = in[t]
* else out does not change (out[t+1] = out[t])
*/
CHIP Bit {
IN in, load;
OUT out;
PARTS:
// Put your code here:
Mux(a=dffout, b=in, sel=load, out=muxout);
DFF(in=muxout, out=dffout);
Or(a=dffout, b=dffout, out=out);
}
```
## 16-bit register
```c=
/**
* 16-bit register:
* If load[t] == 1 then out[t+1] = in[t]
* else out does not change
*/
CHIP Register {
IN in[16], load;
OUT out[16];
PARTS:
// Put your code here:
Bit(in=in[0], load=load, out=out[0]);
Bit(in=in[1], load=load, out=out[1]);
Bit(in=in[2], load=load, out=out[2]);
Bit(in=in[3], load=load, out=out[3]);
Bit(in=in[4], load=load, out=out[4]);
Bit(in=in[5], load=load, out=out[5]);
Bit(in=in[6], load=load, out=out[6]);
Bit(in=in[7], load=load, out=out[7]);
Bit(in=in[8], load=load, out=out[8]);
Bit(in=in[9], load=load, out=out[9]);
Bit(in=in[10], load=load, out=out[10]);
Bit(in=in[11], load=load, out=out[11]);
Bit(in=in[12], load=load, out=out[12]);
Bit(in=in[13], load=load, out=out[13]);
Bit(in=in[14], load=load, out=out[14]);
Bit(in=in[15], load=load, out=out[15]);
}
```
## RAM
:::info
記憶體容量複習
:::
```c=
/**
* Memory of 8 registers, each 16 bit-wide. Out holds the value
* stored at the memory location specified by address. If load==1, then
* the in value is loaded into the memory location specified by address
* (the loaded value will be emitted to out from the next time step onward).
*/
CHIP RAM8 {
IN in[16], load, address[3];
OUT out[16];
PARTS:
// Put your code here:
DMux8Way(in=load, sel=address, a=loada, b=loadb, c=loadc, d=loadd, e=loade, f=loadf, g=loadg, h=loadh);
Register(in=in, load=loada, out=outa);
Register(in=in, load=loadb, out=outb);
Register(in=in, load=loadc, out=outc);
Register(in=in, load=loadd, out=outd);
Register(in=in, load=loade, out=oute);
Register(in=in, load=loadf, out=outf);
Register(in=in, load=loadg, out=outg);
Register(in=in, load=loadh, out=outh);
Mux8Way16(a=outa, b=outb, c=outc, d=outd, e=oute, f=outf, g=outg, h=outh, sel=address, out=out);
}
```
```c=
/**
* Memory of 64 registers, each 16 bit-wide. Out holds the value
* stored at the memory location specified by address. If load==1, then
* the in value is loaded into the memory location specified by address
* (the loaded value will be emitted to out from the next time step onward).
*/
CHIP RAM64 {
IN in[16], load, address[6];
OUT out[16];
PARTS:
// Put your code here:
// 0..2 - low bits select the register, 3..5 select the bank (one of RAM8 chips)
DMux8Way(in=load, sel=address[3..5],
a=sel0,
b=sel1,
c=sel2,
d=sel3,
e=sel4,
f=sel5,
g=sel6,
h=sel7
);
RAM8(in=in, load=sel0, address=address[0..2], out=r0);
RAM8(in=in, load=sel1, address=address[0..2], out=r1);
RAM8(in=in, load=sel2, address=address[0..2], out=r2);
RAM8(in=in, load=sel3, address=address[0..2], out=r3);
RAM8(in=in, load=sel4, address=address[0..2], out=r4);
RAM8(in=in, load=sel5, address=address[0..2], out=r5);
RAM8(in=in, load=sel6, address=address[0..2], out=r6);
RAM8(in=in, load=sel7, address=address[0..2], out=r7);
Mux8Way16(
a=r0,
b=r1,
c=r2,
d=r3,
e=r4,
f=r5,
g=r6,
h=r7,
sel=address[3..5],
out=out);
}
```
## 16 bit Program counter
```c=
/**
* A 16-bit counter with load and reset control bits.
* if (reset[t] == 1) out[t+1] = 0
* else if (load[t] == 1) out[t+1] = in[t]
* else if (inc[t] == 1) out[t+1] = out[t] + 1 (integer addition)
* else out[t+1] = out[t]
*/
CHIP PC {
IN in[16],load,inc,reset;
OUT out[16];
PARTS:
// Put your code here:
Inc16(in=regOutput, out=regOutputInc);
Mux16(a=regOutput, b=regOutputInc, sel=inc, out=out1);
Mux16(a=out1, b=in, sel=load, out=out2);
Mux16(a=out2, b=false, sel=reset, out=regInput);
// load == load OR inc OR reset !!!
Or(a=load, b=inc, out=loadOrInc);
Or(a=loadOrInc, b=reset, out=loadOrIncOrReset);
Register(in=regInput, load=loadOrIncOrReset, out=regOutput);
Or16(a=regOutput, b=regOutput, out=out); // dummy OR gate for output
}
```
# 4. Machine language
## Computer architecture
## Hack Instruction Set
### Branching
### Variables
### Labels
## Low Level Programming
### Basic
### Iterative
### Pointer
### Array
## C instructions
## I/O
### Output
### Input
## Mult.asm & Fill.asm
{%youtube aC-IeMoZN4M%}
Sign in with Wallet
Connect another wallet