The Power of NAND
What's NAND?
NAND is one of the most basic logic gates. So first I need to explain what the logic gate is.
A logic gate is a sort of a calculator that accepts one or more input and produces one or more output where both input and output values are either 0 or 1. Let's take a look at one of the simplest logic gates: AND.
As you can see it takes two inputs (a) and (b), then produce one output (out). Because each (a) and (b) can be either 0 or 1, there are 4 variations of input combination as shown in the table below. The output of an AND gate will be 1 only when both (a) and (b) are 1.
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Let's take a look at another example: OR gate.
Again, it receives two inputs and produces one output. The output of the OR gate is 0 when both (a) and (b) are 0, otherwise 1. This is the truth table of the OR gate.
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Now let's get back to the initial question: What is NAND?
Like AND and OR gates, NAND is also a logic gate that receives two inputs and produces one output.
The output of NAND gate is just an opposite of AND output: When either (a) or (b) is 1 or both of them are 0, the output is 1. More simply put, the output is 0 only when both (a) and (b) are 1.
| a | b | out |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Not very complicated, right?
Now how would it be possible to build a "computer" like the one you're reading this post with with this tiny device?
How to Build a Computer with NAND
The steps are like this:
- build elementary logic gates such as AND, OR, and Multiplexer with NAND
- build components needed to compose CPU such as ALU (Arithmetic Logic Unit) and RAM (Random Access Memories) with elementary logic gates
- build a CPU with these components
An essential fact that makes these steps possible is that any logic gates can be constructed by combining only NAND gates. Let's take a look at an example.
There are three NAND gates in this combined logic gate and it still has two inputs and one output. The branching lines from (a) and (b) mean that input (a) and (b) are connected to multiple gates. Please take a moment to think how the truth table of this logic gate would look like.
This is the answer.
| a | b | out |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
As you can see, it's identical to the AND gate; we successfully made an AND gate only with NAND gates.
What about this one?
As you may have guessed, it's an OR gate implemented with NAND gates.
The truth tables we've seen so far were quite simple: two inputs and one output, but it can be very complex in real life. However, it is known that no matter how complex the truth table is, it can be realised by combining only NAND gates. This characteristic of NAND is called functional completeness.
Because so called CPU and any other components needed to build a computer are just a very complex version of logic gates, all the necessary components to build a computer are constructed only with NANDs.
Of course tons of arduous work needs to be done on top of this to turn it into a full-fledged computer we use today, however, they are all about how to make use of this tiny yet powerful device.
"The Elements of Computing Systems"
Let me introduce a book which I learned this fact from at the end of the story.
In the previous post I said I'm going to work on the "CPU Experiment". However, I didn't know what exactly I should work on or how to kick off the project. After some intensive search on the internet, I came across this book titled "The Elements of Computing Systems".
The book was written by Dr. Noam Nisan and Dr. Shimon Schocken, and was first published in 2005 as a computer science textbook to teach their students how the black-boxed computer systems actually look inside.
The key concept of the book is "NAND to Tetris": The idea that any general-purpose computers are made in a same way that
- (1) they are built from NAND as an elementary logic gate, and
- (2) they are programmed to run any applications such as Tetris game.
And then there is a word to between them meaning the book provides readers a hands-on experience of building a Tetris (general-purpose computer) starting from NAND (an elementary logic gate).
It turned out that not only is this book a perfect introduction to the low-level systems but also it was a perfect timing for me to read. Most importantly, it helped me understand what exactly I'm trying to learn.
I can't wait to see what comes out of this journey. Stay tuned…