So, I've embarked on the journey of nand2tetris.
What is nand2tetris? It's basically a vertically-integrated course on computer science. Starting from 0s and 1s, we build up a whole simulated computer, build an operating system on top of it, build a compiler on top of that OS, and finally build a game on that whole tower.
It's quite a daunting task. How do we get started?
The Magic of NAND
In computers (or, at least in the computer that we're implementing), there is a single circuit that we basically use for everything. It's called NAND
. If you're familiar with boolean logic, it's defined something like this: NOT(A AND B))
.
The truth table for NAND
looks like this:
A B | OUTPUT
==============
0 0 | 1
0 1 | 1
1 0 | 1
1 1 | 0
While this may seem unimpressive, our NAND
gate includes behaviors in it such that we can create literally any other logic gate from some combination of just NAND
gates. We won't be getting into formal proofs, but we'll demonstrate how to build NOT
, AND
, and OR
from just NAND
. (taking NAND
as a given)
NOT
We'll start with NOT
, since it's the simplest operation. The secret to NOT
has to do with a property of AND
. Anything AND
itself simply outputs itself. Have a look: 0 AND 0
is 0
, and 1 AND 1
is 1
.
If we consider NAND
to be a combination of NOT
and AND
, a value NAND
itself will cancel out the AND
, leaving the NOT
operation. If we refer back to our truth table, 0 NAND 0
is 1
and 1 NAND 1
is 0
. So, NOT A
is A NAND A
Here's roughly what the logic gates look like. I'll represent NAND
as a box with N
written on it. If we've only got one input, we'll assume that it's hooked up to both inputs.
AND
Now that we've got a NOT
, it's pretty easy to get to AND
, for fairly self-evident reasons. A NOT
inverts a value, so NOT
ing a NOT
will cancel out the NOT
, leaving the original value. ~~0
outputs 0
, and ~~1
outputs 1
.
NAND
is NOT
applied to the result of an AND
, so if we cancel out the NOT
, we're left with the AND
operation. We've already built a NOT
, and can simply add it to the output of our NAND
The operation looks like this: (A NAND B) NAND (A NAND B)
, but it's easier to draw a diagram.
If we have AND
and NOT
, it won't be too hard to derive OR
.
OR
OR
can be built through DeMorgan's law, which I've been lucky enough to derive myself a few months ago. Basically, we can represent A OR B
as NOT ( NOT(A) AND NOT(B))
.
if our NOT
is A NAND A
and our AND
is made up of (A NAND B) NAND (A NAND B)
, we actually have enough to build an OR
by substituting them in for their relevant terms.
This will be a mess to start, but we'll simplify it.
First, let's replace our NOT
s, since they're simplest to do. NOT(A)
is A NAND A
and NOT(B)
is B NAND B
.
NOT( (A NAND A) AND (B NAND B) )
The overall NOT
will take its term (A NAND A) AND (B NAND B)
and NAND
it with itself as both inputs. It'll come out like this:
((A NAND A) AND (B NAND B)) NAND ((A NAND A) AND (B NAND B))
Now, AND
translates as follows: A AND B
= (A NAND B) NAND (A NAND B)
. If we make our substitution where A
= (A NAND B)
and B
= (B NAND B)
, this happens:
(((A NAND A) NAND (B NAND B)) NAND ((A NAND A) NAND (B NAND B))) NAND (((A NAND A) NAND (B NAND B)) NAND ((A NAND A) NAND (B NAND B)))
Which is, of course, completely unreadable. Let's represent it visually instead.
This is difficult to see in the written version of this logic gate implementation, but our last two NAND
s are simply acting as NOT
operators, flipping our output value, then flipping it back. We can simplify our logic gate by removing them, since ~~A
is just A
, no matter the value.
Now, if we walk backwards from our diagram, we can translate it back into a statement.
(A NAND A) NAND (B NAND B)
Not so bad.
We'll be building more complex systems in the future, but this is certainly a start!
Top comments (0)