The Beginning

The Not Gate

Recently I have started working on a project called Nand2Tetris. The idea of the project is to build a computer from first principles all the way to an OS that runs a Tetris clone. The course is totally open source and free to audit. Thanks to Noam Nisan and Shimon Schocken for all their hard work in putting this course together.

In the very first(technically second) project you are commissioned to build 16 basic logic gates. As someone who is fairly new to programming in general but especially to this bare metal low level implementation it took some time to get used to this new way of thinking. Let’s look at one of the very first gates that you must build, the “Not” gate. Which in its essence is simple enough to understand. When passed a zero you should return a one, and when passed a one you should return a zero. Simple enough right? Well there is one catch. At least it was a catch for me. There are no handy logic crutches that I had grown so used to by using higher level languages. Based on previous experience I would have approached this problem with some logic that looked like this:

if(x==1)
{
return 0;
}else
{
return 1;
}

The only thing you are given is the magical “Nand” gate with which to build the rest of the computer.

What exactly is a “Nand” gate?

Well it’s not an “And” gate that’s for sure (A bad computer joke). Basically it has two inputs and one output. If the two inputs are one it spits out a zero. Otherwise the output is always one. With each logic gate that you build there is an associated “truth table” that helps to describe what the expected behavior of the chip is. The ability to construct a truth table is unique to binary because in general a number can range from negative infinity to positive infinity, but since we are dealing with strictly zeros and ones it gives us the ability to quickly write out every possible input and output in a small digestible table called a truth table. The truth table of a Nand gate is as follows.

 NAND TRUTH TABLE
| a | b | out |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

As you can see from looking at this table it truly is not an “And” gate . An “And” gate returns one if and only if both inputs are one. While a Nand gate does the opposite. So given that one chip with that specific behavior we now need construct the “Not” chip.

A Quick Word about HDL

Before I explain this anymore I have to say a word or two about how we go about describing the implementation details of chips in this Nand2Tetris course. The folks who put together this course were nice enough to define a language called HDL or Hardware Description Language that can be used for describing chips. This language is extraordinarily simple and efficient. The actual language isn’t very hard to grasp at all and can be almost completely understood in about 30 minutes. By the way, if you decide to do this course you can download the required software which will have these handy “stub” files to help you on your quest to Nand your way to the top. These stub files look like this

CHIP Not {
IN in;
OUT out;
PARTS:
//Define implementation here

Most importantly, this interface affords us a simple API to start working with and defining chips. If you think of the “in” and “out” variables as if they were wires it might help you wrap your mind around this. First, you have the CHIP section which defines what “wires” are going in and out of the chip. Then, the PARTS section is the place where we are supposed to supply our code. Which is going to be some combination of chips which when “wired” together supplies the desired outcome.It turns out we can define this chip in one line with our handy dandy Nand chip. The actual fully designed “Not” chip in HDL file looks like this:

CHIP Not {
IN in;
OUT out;

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

What just happened? Well lets look at the Nand truth table and compare it with the truth table we expect to see from a not chip and we will see it is actually simpler than we thought. If you look closely at the Nand table you’ll see the answer was right in front of us the whole time.

 NAND TRUTH TABLE 
| a | b | out |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

We just need to feed the input into the Nand chip twice to get the desired result because if you feed two ones into a Nand chip you are going to get a zero. Whereas when you feed two zeros into a Nand chip you will get a one viola! The elusive “Not” chip. One down 15 more to go!

Leave a Comment