Nand2Tetris1 Flashcards
1
Q
Software hierarchy
A
High level language Compiler VMCode VMTranslator LowLevelCode Assembler
2
Q
Hardware hierarchy
A
Computer architecture Digital design CPU, RAM, chipset Gate logic Elementary logic gates Electrical engineering
3
Q
Fill the missing:
Nand -> {1} -> Elementary Logic gates -> {2} -> CPU, RAM, Chipset -> {3} -> Computer architecture
A
1) Combinational logic
2) Combinational and sequential logic
3) Digital design
4
Q
x AND y
A
x y O(utput) 0 0 0 0 1 0 1 0 0 1 1 1
5
Q
x OR y
A
x y O 0 0 0 0 1 1 1 0 1 1 1 1
6
Q
NOT(x)
A
x O
0 1
1 0
7
Q
Для любой булевой функции можно сопоставить
A
таблицу истинности
8
Q
Boolean Identitites
A
Commutative law: (x AND y) = (y AND x) (x OR y) = (y OR x) Associative law: (x AND (y AND z)) = ((x AND y) AND z) (x OR (y OR z)) = ((x OR y) OR z) Distributive law: (x AND (y OR z)) = (x AND y) OR (x AND z) (x OR (y AND z)) = (x OR y) AND (x OR z) Demorgan Laws: NOT(x AND y) = NOT(x) OR NOT(y) NOT(x OR y) = NOT(x) AND NOT(y) Idempotent law: NOT(x) AND NOT(x) = NOT(x) NOT(x) OR NOT(x) = NOT(x) Double negation law: NOT(NOT(x)) = x
9
Q
Truth table to boolean expression
A
0 0 0 1 (NOT(x) AND NOT(y) AND NOT(z))
0 0 1 0
0 1 0 1 (NOT(x) AND y AND NOT(z))
0 1 1 0
1 0 0 1 (x AND NOT(y) AND NOT(z))
1 0 1 0
1 1 0 0
1 1 1 0
——————————————————————–
(NOT(x) AND NOT(y) AND NOT(z)) OR (NOT(x) AND y AND NOT(z)) OR (x AND NOT(y) AND NOT(z))
Нахождение самого короткого сокращения этой формулы это NP-проблема
10
Q
Any boolean function can be represented using an expression containing
A
NAND function x y NAND 0 0 1 0 1 1 1 0 1 1 1 0 proof every expression could be represented by two functions AND, NOT 1) NOT(x) = (x NAND x) 2) (x AND y) = NOT(x AND y) (x NAND y) = NOT(x AND y)
11
Q
Gate Logic
A
A technique for implementing Boolean functions using logic gates
12
Q
Logic Gates divides to:
A
Elementary(Nand, And, Or, Not…)
Composite(Mux, Adder,…)
13
Q
Gate interface
A
Describest what chip is doing
14
Q
Gate implementation
A
How is gate(chip) actually constructed - it may be many different implementations
15
Q
Что такое мультиплексор
A
Есть два входа(a и b) и один селектор(sel) if(sel == 0) out = a else out = b
16
Q
Что такое демультиплексор
A
есть вход in, и селектор sel
if(sel == 0)
{a, b} = {in, 0}
else
{a, b} = {0, in}
17
Q
Project 1 chips list
A
Elementary logic gates: And, Or, Not, Xor, Mux, Dmux 16-bit variants: Not16, Or16, And16, Mux16 Multiway-variants: Or8Way, Mux4Way16, Mux8Way16, DMux4Way, DMux8Way
18
Q
Как превратить Nand в And
A
Нужно скормить Nand x, y, и потом другому Nand то что вышло из первого
19
Q
Как превратить Nand в Not
A
x NAND x
20
Q
x OR y в терминах NOT и AND
A
NOT(NOT(x) AND NOT(y))
21
Q
mux
A
CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
Not(in=sel, out=notSel);
And(a=notSel, b=a, out=SX2);
And(a=sel, b=b, out=SX1);
Or(a=SX2, b=SX1, out=out);
}
22
Q
dmux
A
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);
}
23
Q
Mux4Way16
A
CHIP Mux4Way16 {
IN a[16], b[16], c[16], d[16], sel[2];
OUT out[16];
PARTS: 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); }
24
Q
Mux8Way16
A
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: 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=outEFGH); Mux16(a=outABCD, b=outEFGH, sel=sel[2], out=out); }
25
DMux4Way
CHIP DMux4Way {
IN in, sel[2];
OUT a, b, c, d;
PARTS:
DMux(in=in, sel=sel[1], a=outAB, b=outCD);
DMux(in=outAB, sel=sel[0], a=a, b=b);
DMux(in=outCD, sel=sel[0], a=c, b=d);
}
26
DMux8Way
CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;
PARTS:
DMux(in=in, sel=sel[2], a=outABCD, b=outEFGH);
DMux4Way(in=outABCD, sel=sel[0..1], a=a, b=b, c=c, d=d);
DMux4Way(in=outEFGH, sel=sel[0..1], a=e, b=f, c=g, d=h);
}
27
N bits - how many posibilities
2^N posibilities
28
Maximum with k-bits
2^k-1
29
Half adder what do
adds two bits
30
Full adder what do
adds three bits
31
Adder what do
adds two numbers
32
Half adder truth table
```
a b sum carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
```
33
Full adder truth table
```
a b c sum carry
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
a b out
0 1 0
0 1 1
0 1 1
1 1 1
```
34
2's complement system
Represent negative number -x using the positive number: 2^n - x
Positive numbers in range: 0 ... 2^(n-1) - 1
Negative numbers in range: -1 ... -2^(n-1)
for example:
if n == 4 bits and number is 5(0101):
16-5=11(1011)
```
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 -8 (8)
1001 -7 (9)
1010 -6 (10)
1011 -5 (11)
1100 -4 (12)
1101 -3 (13)
1110 -2 (14)
1111 -1 (15)
```
35
Substraction idea
```
2^n - x = 1 + (2^n-1) - x
(2^n-1) = 11111111
(2^n-1) - x:
1 1 1 1 1 1 1 1
1 01 1 0 0 1 1
-----------------
0 1001 1 0 0
```
36
To add 1
flip the bits from right to left, stopping the first time 0 is flipped to 1
37
Von neumann architecture
input -> ComputerSystem(input -> CPU(ALU, control) -> output
38
ALU
Arithmetic logic unit
The ALU computes a function on two inputs, and outputs the result
input1 -> A
input2 -> L -> output
function-> U
function one out of a family of pre-defined arithmetic and logical functions
39
Hack ALU
```
zx nx zy ny f no
| | | | | |
x -> -> out
y ->
| |
zr no
```
```
if(zx) x = 0
if(nx) x = !x
if(zy) y = 0
if(ny) y = !y
if(f) out=x+y else out=x&y
if(no) out = !out
```
which function to compute is set by six 1-bit inputs
computes one out of family of 18 functions
0, 1, -1, x, y, !x, !y, -x, -y, x+1, y+1, x-1, y-1, x+y, x-y, y-x, x&y, x|y
if(out == 0) then zr = 1 else zr = 0
if(out < 0) then ng = 1 else ng = 0
40
Project2 chips
HalfAdder, FullAdder, Add16, Inc16, ALU
41
HalfAdder HDL
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);
}
42
FullAdder HDL
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=b, b=c, sum=sum1, carry=carry1);
Xor(a=a, b=sum1, out=sum);
Or(a=sum1, b=carry1, out=sumcarry);
Mux(a=carry1, b=sumcarry, sel=a, out=carry);
}
43
Add16
CHIP Add16 {
IN a[16], b[16];
OUT out[16];
PARTS:
FullAdder(a=false,b=a[0],c=b[0],sum=out[0],carry=c1);
FullAdder(a=c1,b=a[1],c=b[1], sum=out[1], carry=c2);
FullAdder(a=c2,b=a[2],c=b[2], sum=out[2], carry=c3);
FullAdder(a=c3,b=a[3],c=b[3], sum=out[3], carry=c4);
FullAdder(a=c4,b=a[4],c=b[4], sum=out[4], carry=c5);
FullAdder(a=c5,b=a[5],c=b[5], sum=out[5], carry=c6);
FullAdder(a=c6,b=a[6],c=b[6], sum=out[6], carry=c7);
FullAdder(a=c7,b=a[7],c=b[7], sum=out[7], carry=c8);
FullAdder(a=c8,b=a[8],c=b[8], sum=out[8], carry=c9);
FullAdder(a=c9,b=a[9],c=b[9], sum=out[9], carry=c10);
FullAdder(a=c10,b=a[10],c=b[10], sum=out[10], carry=c11);
FullAdder(a=c11,b=a[11],c=b[11], sum=out[11], carry=c12);
FullAdder(a=c12,b=a[12],c=b[12], sum=out[12], carry=c13);
FullAdder(a=c13,b=a[13],c=b[13], sum=out[13], carry=c14);
FullAdder(a=c14,b=a[14],c=b[14], sum=out[14], carry=c15);
FullAdder(a=c15,b=a[15],c=b[15], sum=out[15], carry=c16);
}
44
Inc16
CHIP Inc16 {
IN in[16];
OUT out[16];
PARTS:
Add16(a[0..15]=in[0..15], b[0]=true, b[1..15]=false, out=out);
}
45
ALU hdl
```
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=zxOut);
Not16(in=zxOut,out=nxOut);
Mux16(a=zxOut, b=nxOut, sel=nx, out=zxnxOut);
Mux16(a=y, b=false, sel=zy, out=zyOut);
Not16(in=zyOut,out=nyOut);
Mux16(a=zyOut, b=nyOut, sel=ny, out=zynyOut);
And16(a=zxnxOut, b=zynyOut, out=xAndY);
Add16(a=zxnxOut, b=zynyOut, out=xPlusY);
Mux16(a=xAndY, b=xPlusY, sel=f, out=result);
Not16(in=result,out=notResult);
Mux16(a=result, b=notResult, sel=no, out[0..7]=finalResultFirst, out[8..14]=finalResultSecond, out[15]=finalResultLast);
Or8Way(in=finalResultFirst,out=abcdefgh);
Or8Way(in[0..6]=finalResultSecond,in[7]=finalResultLast, out=ijklmnop);
Or(a=abcdefgh, b=ijklmnop, out=zrInverse);
Not(in=zrInverse, out=zr);
And16(a=true, b[0..7]=finalResultFirst, b[8..14]=finalResultSecond, b[15] = finalResultLast, out=out);
And(a=finalResultLast,b=true, out=ng);
}
46
Flip-flop
Gates that can flip between two states
47
The clocked data flip flop
out[t] = in[t-1]
48
How to realize flip-flop using Nand
1) create a loop achieving an "un-locked" flip-flip
| 2) isolation across time steps using a "master-slave" setup
49
memory unit components
1) in[16]
2) load
3) address[3]
50
formula of count of bit to address register
k = log n
| 2
51
why random access memory
cause irrespective of the RAM size, every register can be accessed at the same time - instantenenously
52
counter abstraction
```
in[16], load, inc, reset, out[16]
if(reset[t] == 1) out[t+1] = 0
else if (load[t] == 1) out[t+1] = in[t]
else if(int[t] == 1) out[t+1] = out[t] + 1
else out[t+1] = out[t]
```
53
Project 3 chips
Bit, Register, RAM8, RAM64, RAM512, RAM4K, RAM16K, PC
54
Bit hdl
CHIP Bit {
IN in, load;
OUT out;
PARTS:
Mux(a=dffout, b=in, sel=load, out=preout);
DFF(in=preout, out=dffout, out=out);
}
55
Register hdl
CHIP Register {
IN in[16], load;
OUT out[16];
```
PARTS:
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]);
}
```
56
RAM8 hdl
CHIP RAM8 {
IN in[16], load, address[3];
OUT out[16];
PARTS:
DMux8Way(in=load, sel=address, a=load0, b=load1, c=load2, d=load3, e=load4, f=load5, g=load6, h=load7);
Register(in=in, load=load0, out=out0);
Register(in=in, load=load1, out=out1);
Register(in=in, load=load2, out=out2);
Register(in=in, load=load3, out=out3);
Register(in=in, load=load4, out=out4);
Register(in=in, load=load5, out=out5);
Register(in=in, load=load6, out=out6);
Register(in=in, load=load7, out=out7);
Mux8Way16(a=out0,b=out1,c=out2,d=out3,e=out4,f=out5,g=out6,h=out7,sel=address, out=out);
}
57
RAM64 hdl
CHIP RAM64 {
IN in[16], load, address[6];
OUT out[16];
PARTS:
DMux8Way(in=load, sel=address[0..2], a=load0, b=load1, c=load2, d=load3, e=load4, f=load5, g=load6, h=load7);
RAM8(in=in, load=load0, address=address[3..5], out=out0);
RAM8(in=in, load=load1, address=address[3..5], out=out1);
RAM8(in=in, load=load2, address=address[3..5], out=out2);
RAM8(in=in, load=load3, address=address[3..5], out=out3);
RAM8(in=in, load=load4, address=address[3..5], out=out4);
RAM8(in=in, load=load5, address=address[3..5], out=out5);
RAM8(in=in, load=load6, address=address[3..5], out=out6);
RAM8(in=in, load=load7, address=address[3..5], out=out7);
Mux8Way16(a=out0,b=out1,c=out2,d=out3,e=out4,f=out5,g=out6,h=out7,sel=address[0..2], out=out);
}
58
PC hdl
CHIP PC {
IN in[16],load,inc,reset;
OUT out[16];
PARTS:
Inc16(in = feedback, out = pc);
Mux16(a = feedback, b = pc, sel = inc, out = w0);
Mux16(a = w0, b = in, sel = load, out = w1);
Mux16(a = w1, b = false, sel = reset, out = cout);
Register(in = cout, load = true, out = out, out = feedback);
}
59
RAM512 hdl
CHIP RAM512 {
IN in[16], load, address[9];
OUT out[16];
PARTS:
DMux8Way(in=load, sel=address[0..2], a=load0, b=load1, c=load2, d=load3, e=load4, f=load5, g=load6, h=load7);
RAM64(in=in, load=load0, address=address[3..8], out=out0);
RAM64(in=in, load=load1, address=address[3..8], out=out1);
RAM64(in=in, load=load2, address=address[3..8], out=out2);
RAM64(in=in, load=load3, address=address[3..8], out=out3);
RAM64(in=in, load=load4, address=address[3..8], out=out4);
RAM64(in=in, load=load5, address=address[3..8], out=out5);
RAM64(in=in, load=load6, address=address[3..8], out=out6);
RAM64(in=in, load=load7, address=address[3..8], out=out7);
Mux8Way16(a=out0,b=out1,c=out2,d=out3,e=out4,f=out5,g=out6,h=out7,sel=address[0..2], out=out);
}
60
RAM4K hdl
CHIP RAM4K {
IN in[16], load, address[12];
OUT out[16];
PARTS:
DMux8Way(in=load, sel=address[0..2], a=load0, b=load1, c=load2, d=load3, e=load4, f=load5, g=load6, h=load7);
RAM512(in=in, load=load0, address=address[3..11], out=out0);
RAM512(in=in, load=load1, address=address[3..11], out=out1);
RAM512(in=in, load=load2, address=address[3..11], out=out2);
RAM512(in=in, load=load3, address=address[3..11], out=out3);
RAM512(in=in, load=load4, address=address[3..11], out=out4);
RAM512(in=in, load=load5, address=address[3..11], out=out5);
RAM512(in=in, load=load6, address=address[3..11], out=out6);
RAM512(in=in, load=load7, address=address[3..11], out=out7);
Mux8Way16(a=out0,b=out1,c=out2,d=out3,e=out4,f=out5,g=out6,h=out7,sel=address[0..2], out=out);
}
61
RAM16K hdl
CHIP RAM16K {
IN in[16], load, address[14];
OUT out[16];
PARTS:
DMux4Way(in=load, sel=address[0..1], a=load0, b=load1, c=load2, d=load3);
RAM4K(in=in, load=load0, address=address[2..13], out=out0);
RAM4K(in=in, load=load1, address=address[2..13], out=out1);
RAM4K(in=in, load=load2, address=address[2..13], out=out2);
RAM4K(in=in, load=load3, address=address[2..13], out=out3);
Mux4Way16(a=out0,b=out1,c=out2,d=out3, sel=address[0..1], out=out);
}
62
same hardware may can run many different programs
| Theory hypothesis is {1}, Practice is {2}
1) Universal turing machine
| 2) Von Neumann architecture
63
What was von Neumann’s contribution on top of Turing’s ideas?
He formulated a practical architecture for a general computing machine.
64
Machine operations. Usually what correspond to what's implemented in Hardware
- Arithmetic operations(Add,Sub)
- Logical operations(And, Or, Xor)
- Flow control(goto instruction X, if C then goto instruction Y)
65
Accessing a memory location is expensive:
- need to supply a long address
- getting the memory contents into the CPU takes time
Solution
Memory Hierarchy:
- registers
- cache
- main memory
- disk
66
Addressing modes
- register: ADD R1, R2 => R2 = R2+R!
- direct: ADD R1, M[200] => Mem[200] = Mem[200]+R1
- indirect: ADD R1, @A => Mem[A] = Mem[A]+R1
- Immediate: ADD 73, R1 => R1 = R1+73
67
What kind of computer is HACK
16-bit machine
-(data out)->
instructions(ROM) -> CPU data memory(RAM)
-(data in) ->
68
A 16-bit machine consists of
- data memory(RAM) : sequence of 16-bit register
- instructions memory(ROM) : sequence of 16-bit register
- CPU : performs 16-bit instructions
- instruction bus / data bus / address buses
69
Hack machine language
Recognizes 3 type of registers:
- D holds a 16-bit value
- A holds a 16-bit value
- M represents the 16-bit RAM register addressed by A
16-bit A-instructions
16-bit C-instructions
70
the A-instruction
```
Syntax: @value
Semantics:
Set the A register to value
Side effect - RAM[A] becomes the selected RAM register
Usage:
@100 // A=100
M=-1 // RAM[100] = -1
```
71
The C-instruction
Syntax: dest = comp ; jump
where comp = 0, 1, -1, D, A, !D, !A, -D, -A, D+1, A+1, D-1, A-1, D+A, D-A, A-D, D&A, D|A, M, !M, -M, M+1, M-1, D+M, D-M, M-D, D&M, D|M
dest = null, M, D, MD, A, AM, AD, AMD (M refers to RAM[A]
jump = null, JGT, JEQ, JGE, JLT, JNE, JLE, JMP
if(comp jump 0) jump to execute the instruction in ROM[A]
Semantics:
Compute the value of comp
Stores the value in dest
if the boolean expression (comp jump 0) is true, jumps to execute the instruction, stored in ROM[A]
Example:
// Set D register to -1
D=-1
// set RAM[100] to the value of D register minus 1
@100
M=D-1
// if (D-1==0) jump to execute the instruction stored in ROM[56]
@56
D-1;JEQ
72
The C-instruction: symbolic and binary syntax
```
dest = comp ; jump
111 a c1 c2 c3 c4 c5 c6 d1 d2 d3 j1 j2 j3
0 jump
JEQ 0 1 0 if out = 0 jump
JGE 0 1 1 if out >= 0 jump
JLT 1 0 0 if out < 0 jump
JNE 1 0 1 if out != 0 jump
JLE 1 1 0 if out <= 0 jump
JMP 1 1 1 unconditional jump
```
73
Screen memory map
a designated memory area( in RAM for example), dedicated to manage a display unit. A physical display is continuously refreshed from it
74
Screen memory map in HACK
Display unit - 256 by 512 b/w. Started at 16384 and ended at 16384 + 8192. Every bit represented by a pixel
0 ... 511 - first row on display. SCREEN CHIP!
75
To set pixel(on/off)
1 word = Screen[32*row + col/16] using Screen chip directly
or word = RAM[16384 + 32*row + col/16] using RAM
2. set the (col % 16)th bit of word to 0 or 1
3. Commit word to the RAM
76
Keyboard memory map
a single register (16bit). When a key is pressed on a keyboard, the key's scan code appears in the keyboard memory map. RAM[24576]
77
The hack assembly builtin symbols
R0 - 0 ... R15 - 15. For example @R0, @R5. Virtual registers, SCREEN - 16384, KBD - 24576, SP - 0, LCL - 1, ARG - 2, THIS - 3, THAT - 4
78
The project 4 programs
Mult: a program performing R2 = R0 * R1,
Fill: when a keyboard pressed - fill all display with black
