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
