More computer science from first principlies with NAND2Tetris! So yesterday I implemented AND, OR and NOT on paper and had fun just playing around with binary and Boolean algebra and logic gates. Today I’ll see how many more of these 15 chips I can implement.
Exclusive-Or (XOR), schmexclusive-schmor!
Implementing the XOR gate using AND, OR and NOT was super easy! I just wrote out the canonical representation of the desired truth table and bam, done!
Fun fact: I just learned that what this course calls “canonical representation” or canonical normal form is one of two variants, and the variant they teach is called “canonical disjunctive normal form” (CDNF) or “minterm canonical form”. (The other variant is called “canonical conjunctive normal form” (CCNF) or “maxterm canonical form”, but I don’t know what the difference is.)
Anyway, so I have one possible implementation of XOR, but is it the most efficient? How could I confirm that? More specifically, how could I convert the canonical form (NOT(x) AND Y) OR (X AND NOT(Y)) into a version that only uses NAND gates? I put that on hold for while and moved onto the next piece of the project.
My first multiplexer and three-input gates
So far, all the gates I’ve built only take two inputs. But a multiplexer (or mux for short) takes three inputs: two normal inputs and one “select” input, which determines which of the other two inputs to pass through as its output. I think of it as a forwarding device that just passes a certain bit through to the next gates. (I still never did completely figure out why exactly they’re useful, though.)
Anyhow, I got stuck on this question: how do you make a three-input gate out of nothing but two-input gates?
After some scribbling, I realized that for a set of three inputs, you have to break them down into every combination of two. For example, I need to think of XYZ as XY, XZ, YZ. This reminds me of the famous handshake problem – woohoo, combinatorics!
To come up with the actual implementation for a mux, I wrote out its truth table (which is much bigger than I’ve been used to up until this point!) and converted that into its canonical representation. But then I didn’t have any luck using Boolean algebra to reduce the expression into combinations of only two inputs. Clearly I need more practice, and I should probably review the basics of regular algebra too!
I tried another strategy: stare at the truth table until something jumps out at me. And it did! I saw a clear pattern involving only two inputs at a time, so I wrote that as a Boolean expression. Done! I can implement a mux with AND, OR and NOT gates.
How to make NANDs with De Morgan’s laws
With my first implementation of a mux complete, I circled back to my earlier question: how do I know if this is the most efficient implementation? And how can I write an expression that shows how to build a chip with nothing but NAND gates, the most primitive building block (at least for this course)?
This took me back to De Morgan’s laws, which I revisited yesterday but didn’t explore in any detail. Time to fix that!
I wrote them out on paper and then wrote the negations of the two laws, which involved lots of overbars representing double negatives.
On Wikipedia’s page on overlines I discovered a fun mnemonic device for De Morgan’s laws:
“Break the line, change the sign.”
I love that! And apparently in math the overbar/overline is called a vinculum, and there are also other notations for negation. That page also says that De Morgan’s laws can be thought of as a way to distribute negation. I like that.
After some more scribbling, I had a table of every conversion you can make with two variables using De Morgan’s laws and I realized that to write NAND as a Boolean expression, you just write NOT(X AND Y). So to turn an AND expression into a NAND expression, I can just negate it twice: X AND Y = NOT(NOT(X AND Y)). In other words, AND is just NAND with the output inverted.
To turn an OR expression into a NAND expression, I used an inverted form of one of De Morgan’s laws to show that X OR Y = NOT(NOT(X) AND NOT(Y)), which is a NAND gate with the two inputs inverted.
Hurray! Based on that, I figured out how to write any Boolean expression in terms of NAND gates and NOT gates (which I can build from a NAND gate, as I learned yesterday)! Success!
With this new trick up my sleeve, after playing with more Boolean algebra and writing lots of negatives and double negatives and triple negatives, I came up with a more efficient implementation for my XOR and mux gates! My original mux implementation would’ve required 13 NAND gates, and now I got it down to 7!
Demultiplexers and multiple outputs
Whereas a multiplexer passes along one of its inputs based on a “select bit” input, a demultiplexer does the opposite: based on the “select bit”, it passes a single input to one of its outputs.
The mux was my first gate with more than two inputs, and now the demux will be my first gate with more than one output! I wonder how this is supposed to work…
Ah, I see, it isn’t any more difficult to design something with multiple outputs; I just end the design with two gates and use both of their outputs instead of ending with a single gate like my other designs have.
The truth table looks different from what I’m used to, but I already see familiar patterns for each of the outputs! Yeah, this is an easy one; I’m just making two gates out of what I’ve already made. Done!
Learning summary (#TIL)
- I designed implementations of XOR, mux, and demux gates and then refined them into more efficient designs.
- I learned that there are two variants of canonical normal form.
- I learned how to use De Morgan’s laws to convert any Boolean expression into a composition of NAND and NOT gates, which allows me to make much more efficient gate designs!
New terms
- Vinculum, the name of an overline used in math notation.
- Canonical normal form and its variants: “canonical disjunctive normal form” (CDNF) or “minterm canonical form”, and “canonical conjunctive normal form” (CCNF) or “maxterm canonical form”.
Questions
- How do you confirm if you have the most efficient implementation for a given chip?
- What’s the difference between the two variants of canonical normal form?
Next steps
- Implement the next 9 chips required for the first NAND2Tetris project.
- Write up my implementations in HDL and test them with the hardware simulator.
Time breakdown
- Study time: 3 hours
- NAND2Tetris project 1 implementations: 1 hour 17 min
- Playing with Boolean algebra: 34 min
- Researching, thinking, writing: 1 hour 11 min
- Web dev work: 35 min