indexpost archiveatom feed

2017-02-25

My copy of The Elements of Computing Systems came in the mail and I've been having a great time digging into the absolute fundamentals of programming. While I'm passingly familiar with some of the material, working the examples in the text has me finally feeling like I deeply understand the concepts.

## Gates

### Making a NAND

The text covers the basics of digital logic at a brisk pace, conceding the NAND gate to be the most fundamental aspect of its coverage. For the sake of completeness, I sketched out both creating a NAND from an AND/NOT pair, as well as the composition of the more basic gates from the "universal" NAND gate. Any further in creating these is an interesting, but distracting exercise with transistors -- which as the book states, are more the realm of electrical engineers than computer scientists.

So, how do you make a NAND gate? It's pretty simple, with NAND being the inversion (NOT) of the AND operation `¬(A·B)`

Annoyingly, the hardware simulator accompanying the book assumes `Nand.hdl` to be a built-in and doesn't allow you to shadow with your own, so it must be named something like `not-and.hdl`. More annoyingly still, a direct translation of the above, while sensible, doesn't work and instead requires two NOT gates to invert each pin of the AND chip. I haven't worked out why this is the case, but it seems to be strictly an issue with the tool itself. So instead the working `not-and.hdl` file looks like:

``````CHIP NotAnd {
IN a, b;
OUT out;

PARTS:
Not(in=a, out=a2);
Not(in=b, out=b2);
And(a=a2, b=b2, out=out);
}
``````

Because the NAND gate exhibits functional completeness the first interesting exercise is to re-implement those gates using only NAND.

pin A pin B output
0 0 1
0 1 1
1 0 1
1 1 0

#### NOT

If you squint just a bit at the truth table for the NAND gate, you'll notice that a NOT operation is emergent for two equivalent inputs. Consequently, all you have to do is wire both inputs together and you're done:

``````CHIP Not {
IN in;
OUT out;

PARTS:
Nand(a=in, b=in, out=out);
}
``````

#### AND

Without getting boring, you can imagine then how AND can be implemented by (re)inverting a NAND gate.

``````CHIP And {
IN a, b;
OUT out;

PARTS:
Nand(a=a, b=b, out=o);
Not(in=o, out=out);
}
``````

#### OR

Another obvious one, included for completeness sake - OR is the logical inversion of NAND, not much to it, really.

``````CHIP Or {
IN a, b;
OUT out;

PARTS:
Not(in=a, out=a2);
Not(in=b, out=b2);
Nand(a=a2, b=b2, out=out);
}
``````

#### XOR

XOR is an interesting one because it too exhibits functional completeness. It only clicked for me during the exercise that XOR is the same as `¬Equivalent`, which was a fun realization (from an implementation perspective).

``````CHIP Xor {
IN a, b;
OUT out;

PARTS:
Not(in=a, out=nota);
Not(in=b, out=notb);
And(a=na, b=b, out=c);
And(a=a, b=nb, out=d);
Or(a=c, b=d, out=out);
}
``````

Tremendously frustrating, the above implementation also doesn't work with the hardware simulator. It appears to be a known issue and possibly a result of a recent update. I'm hugely impressed at the amount of tooling that went into the book, but only a little disappointed to have found what look like so many bugs out of the gate. XOR is pretty simple to validate by hand: ( x · ¬y ) + ( ¬x · y )

I was most excited to dig into adders (and the yet-to-be-explored ALU), Forth has given me and appreciation for low-level programming, but some of the fundamentals still elude me. I can appreciate pointer-arithmetic, but I couldn't tell you exactly how a register works. In that vein, implementing a half-adder and full-adder (2-bit and 3-bit, respectively) using only basic logic gates is a sound footing on which to get started.