Nand2Tetris1 Flashcards
Software hierarchy
High level language Compiler VMCode VMTranslator LowLevelCode Assembler
Hardware hierarchy
Computer architecture Digital design CPU, RAM, chipset Gate logic Elementary logic gates Electrical engineering
Fill the missing:
Nand -> {1} -> Elementary Logic gates -> {2} -> CPU, RAM, Chipset -> {3} -> Computer architecture
1) Combinational logic
2) Combinational and sequential logic
3) Digital design
x AND y
x y O(utput) 0 0 0 0 1 0 1 0 0 1 1 1
x OR y
x y O 0 0 0 0 1 1 1 0 1 1 1 1
NOT(x)
x O
0 1
1 0
Для любой булевой функции можно сопоставить
таблицу истинности
Boolean Identitites
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
Truth table to boolean expression
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-проблема
Any boolean function can be represented using an expression containing
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)
Gate Logic
A technique for implementing Boolean functions using logic gates
Logic Gates divides to:
Elementary(Nand, And, Or, Not…)
Composite(Mux, Adder,…)
Gate interface
Describest what chip is doing
Gate implementation
How is gate(chip) actually constructed - it may be many different implementations
Что такое мультиплексор
Есть два входа(a и b) и один селектор(sel) if(sel == 0) out = a else out = b
Что такое демультиплексор
есть вход in, и селектор sel
if(sel == 0)
{a, b} = {in, 0}
else
{a, b} = {0, in}Project 1 chips list
Elementary logic gates: And, Or, Not, Xor, Mux, Dmux 16-bit variants: Not16, Or16, And16, Mux16 Multiway-variants: Or8Way, Mux4Way16, Mux8Way16, DMux4Way, DMux8Way
Как превратить Nand в And
Нужно скормить Nand x, y, и потом другому Nand то что вышло из первого
Как превратить Nand в Not
x NAND x
x OR y в терминах NOT и AND
NOT(NOT(x) AND NOT(y))
mux
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);
}
dmux
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);
}
Mux4Way16
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); }
Mux8Way16
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); }
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); }
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); }
N bits - how many posibilities
2^N posibilities
Maximum with k-bits
2^k-1
Half adder what do
adds two bits
Full adder what do
adds three bits
Adder what do
adds two numbers
Half adder truth table
a b sum carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1
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
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)
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
To add 1
flip the bits from right to left, stopping the first time 0 is flipped to 1
Von neumann architecture
input -> ComputerSystem(input -> CPU(ALU, control) -> output
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
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
Project2 chips
HalfAdder, FullAdder, Add16, Inc16, ALU
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); }
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); }
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); }
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); }
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); }
Flip-flop
Gates that can flip between two states
The clocked data flip flop
out[t] = in[t-1]
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
memory unit components
1) in[16]
2) load
3) address[3]
formula of count of bit to address register
k = log n
2
why random access memory
cause irrespective of the RAM size, every register can be accessed at the same time - instantenenously
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]Project 3 chips
Bit, Register, RAM8, RAM64, RAM512, RAM4K, RAM16K, PC
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); }
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]);
}
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); }
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); }
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); }
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); }
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); }
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); }
same hardware may can run many different programs
Theory hypothesis is {1}, Practice is {2}
1) Universal turing machine
2) Von Neumann architecture
What was von Neumann’s contribution on top of Turing’s ideas?
He formulated a practical architecture for a general computing machine.
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)
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
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
What kind of computer is HACK
16-bit machine
-(data out)->
instructions(ROM) -> CPU data memory(RAM)
-(data in) ->
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
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
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
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
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
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
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!
To set pixel(on/off)
1 word = Screen[32row + col/16] using Screen chip directly
or word = RAM[16384 + 32row + col/16] using RAM
2. set the (col % 16)th bit of word to 0 or 1
3. Commit word to the RAM
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]
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
The project 4 programs
Mult: a program performing R2 = R0 * R1,
Fill: when a keyboard pressed - fill all display with black
