From Nand to Tetris(Nand2tetris) Project 0 & Project 1
After about 50 days of work, I finally finished the Nand2tetris course Part 1 and Part 2 on Coursera. I have no background in computer science, and this was really challenging at some point. I really want to thank Shimon and Noam who created this course, which can give the high level programmers a better idea about how does the “blackbox” that they are coding to everyday work.
Project 0 was nothing, it’s just teaching the students how to submit their homeworks. Simple! just go to the folder that you saved your homework, and select all the files that you want to submit and right click, choose compress n items, then there will be something created called “Archive.zip”, rename it to be “projectN.zip”, and then you are good to go.
Project 1 is all about logic gates.
When talking about computers, it was actually only about zeros and ones.
We can use AND OR gates to create many other kind of gates, NAND for example. Nand will return the opposite value of AND. we are going to use NAND to create all the other gates.
How to describe “NOT x” using only NAND?
We can also create OR, XOR, and all the other interesting gates.
(For a XOR b, the gate will only return true if a is not equal to b.)
The next step is to use HDL(hardware description language) to describe the gates. But first of all, let there be NAND. We will create every gate with NAND only.
HDL is just a description about how the gate works.
CHIP Not { IN in; OUT out; PARTS: Nand(a=in, b=in, out=out);}
“CHIP Not” is giving this chip a name, after you created this chip, the hardware simulator will know that such “Not” gate is available, and if other gates call for “Not”, simulator will use this description.
“IN in” there will be one inputs, “in” can be seen as parameters of high level languages.
“OUT out” meaning “out” with be the output, it’s like the return value of a function.
“PARTS:” is the implementation of the gate, as we discussed before, we have Nand in our pocket, so we can utilize Nand to create Not, after some thinking we will get the conclusion that “Not x= x Nand x”, so we follow the standard styling of the HDL, and tell the hardware simulator how to yield the expected output. “Nand(a = in, b = in, out = out);”. Well, there are two “out”s in this description. The first out is the parameter name for Nand gate, the second out is the name of the output, which has to be the same as the name that we created in“OUT out”. In other words, if we write “OUT abcd” on line 3, we will have to change “out = out” to “out = abcd”, and in the future if we call Not gate in any other gates we will have to write:
Not(in=in, abcd=out);This is not recommended, we’d better respect those conventions.
The most difficult one is MUX, and this MUX gate is actually the most fundamental and important one in all gates. MUX takes in three inputs, a, b, and selector. If selector is 0, then output a, else, output b. How could we select using only a description language? Let’s first look at the truth table.
We can see that E4 and I4 are true only if b&sel is true. so the output is correlated with b & sel. which will give us a output of 00010001
Another observation is that F4, G4, H4 are the opposite of “sel”, but if we say the answer is only correlated with Not(sel), it’s not accurate, we can try to combine the result of not sel and b & sel, we can never yield the right output, so we have to look into something else — the correlation of “not sel” and “a”, Not(sel)&a will give us exactly 00001010. Then we can generate the expected answer by (b & sel | a & Not(sel)).
After we figured out Mux, everything else was pretty easy.
Or(b&sel, a&Not(sel)) 00010001 | 00001010 = 00011011CHIP Mux {
IN a, b, sel;
OUT out;
PARTS:
Not(in=sel, out=notSel);
And(a=sel, b=b, out=c1);
And(a=notSel, b=a, out=c2);
Or(a=c1, b=c2, out=out);
}CHIP Mux16 {
IN a[16], b[16], sel;
OUT out[16];
PARTS:
Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
...
...
Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}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=ab);
Mux16(a=c, b=d, sel=sel[0], out=cd);
Mux16(a=ab, b=cd, sel=sel[1], out=out);
}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=d, d=d, sel=sel[0..1], out=abcd);
Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=efgh);
Mux16(a=abcd, b=efgh, sel=sel[2], out=out);
}CHIP DMux {
IN in, sel;
OUT a, b;
PARTS:
Not(in=sel, out=notsel);
And(a=in, b=notsel, out=a);
And(a=in, b=sel, out=b);
}CHIP DMux4Way {
IN in, sel[2];
OUT a, b, c, d;
PARTS:
DMux(in=in, sel=sel[1], a=ab, b=cd);
DMux(in=ab, sel=sel[0], a=a, b=b);
DMux(in=cd, sel=sel[0], a=c, b=d);
}CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;
PARTS:
DMux(in=in, sel=sel[2], a=abcd, b=efgh);
DMux4Way(in=abcd, sel=sel[0..1], a=a, b=b, c=c, d=d);
DMux4Way(in=efgh, sel=sel[0..1], a=e, b=f, c=g, d=h);
}
It’s not as easy as I described when trying to figure out the relations, but finally we can understand. There are a lot of ways to solve it, but the best will be the one use the least gates, which means that it can return the output as fast as possible. In the hardware realm, efficiency matters.
But why do we need these mux dmux stuff? At this point, I don’t know. I was just following. And later I understood that this is about the RAM.
That’s all about project 0 and 1.
