The question:
Have you ever wondered how something in a computer really works? When looking at the function:
printf("Hello World!");Have you ever found yourself questioning what printf is really doing? You might know that this function is used to print the defined characters on the screen that’s the “What” and that’s all you need to know to use it. However how is the function printing those characters on the screen? Again you might know that at a lower level it’s a wrapper for a system call which triggers a software interrupt and causes the CPU to execute the instructions needed to accomplish the task at hand. But how is the CPU itself working? That’s the “How” of the question.
Enter Nand2Tetris:
The project Nand2Tetris is aimed at developing an understanding of different levels of abstractions present in computers from hardware to software. The project takes a hands on approach where you start from a lower abstraction level and move on to the higher abstraction level. Creating Composite Logic Gates from Elementary Logic Gates to CPU & RAM to Computer Architecture to the Assembler and so until you reach the abstraction level of a high-level language. The project is based on a book The Elements of Computing Systems: Building a Modern Computer from First Principles and is designed by the authors of the book.
Project Structure:
The project is split into 2 parts. In the first part you start with a single logic gate “NAND” and design the hardware on which you will be running your software later on. The second part is focused on developing software to run on the hardware designed previously. The project is divided into sub projects. For the entire week you’ll gain the knowledge required to complete the upcoming weekly project.
The First week:
So we all have have heard that computers run on 0’s and 1’s, but how so? This is where boolean logic and logic gates come in.
Boolean Logic (Analogy):
Think you and your friend are sitting together you both can either raise your hand (1) or put it down (0). Now when you both raise your hand together you’ll get an apple as a reward, however if one of you does not raises his hand or none of your raise your hand none of you would get the reward. This is boolean logic in a nutshell where you create logic based on two possibilities.
Logic Gates:
Logic gates are devices use to perform boolean logic operations on 0’s and 1’s. There are many different logic gates such as: AND, NAND, OR, XOR etc. For example: When you input 1 and 0 in an AND gate the output will be 0 the logic gate is utilizing boolean logic to perform the desired operation. We can use truth tables to map the inputs and outputs of a logic gate to understand it’s functionality. This is the truth table of the AND gate:
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Notice this truth table follows the apple analogy mentioned above.
A logic gate can also be represented visually. AND gate and be represented as such:
Boolean Expression:
Now we can understand what is a boolean expression? Simply put it defines the inputs and the logic operation to be performed on the defined inputs. A boolean expression of the AND gate would be expressed as the following:
A AND B = OUT
Now that we know what a logic gate is we can look at different types of logic gates. So the main distinction is between 2 types:
Elementary Logic Gates and Composite Logic Gates:
Elementary Logic Gates (Basic):
AND, OR, XOR, NOT, NAND, NOR and XNOR
Gates which are created by combining Elementary Logic Gates are called Composite Logic Gates eg: MUX, DMUX etc.
So talking about combining gates. Did you know that you could create every logic gate composite/elementary just using the NAND gate?
Let’s give it a try here’s the truth table of AND and NAND gate:
AND:
| A | B | Out |
|---|---|---|
| 0 | 1 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
NAND:
| A | B | Out |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Analyzing the truth tables we can figure out that these gates are reverse of each other. So in order to make an AND gate from a NAND gate we need to somehow reverse the output. We can accomplish these using the NOT gate
NOT:
| A | Out |
|---|---|
| 1 | 0 |
| 0 | 1 |
We can now create an expression to turn a NAND gate into a NOT gate and get an AND gate:
((A NAND B) Out NAND Out)
Testing the expression:
Let: A = 1, B = 0:
= ((1 NAND 0) Out NAND Out)
= (1 NAND 1)
= 0
If we look at the truth table for the AND gate we can see that if A = 1 and B = 0 the output should be 0.
Synthesizing Expressions:
You might be asking: How can we derive an expression from truth table for a logic gate?
Well you need to “synthesize” an expression. First you should have access to the AND and OR gates. Then you can AND the inputs where 1 is to be returned and NOT them if needed to get a 1 output and repeat the process for every 1 output that exists in the truth table finally you can OR all the expressions you created. This might sound confusing at first, but I’ll provide an example to explain the process:
I’ll create the XOR gate using the defined process:
| A | B | Out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
So we can observe the second and third outputs in the truth tables are 1s. Now we can create an expression using the above process to synthesize an expression: ((NOT A) AND B) OR (A AND (NOT B))
A critical thing to remember is not to rely on this process without understanding how it works. As there will come times that you might need to tweak the process to fit a use case or leave it all together. When such time arrives you would have trouble doing things without using the process so make sure to understand it and think about how it works and why it works.
HDL:
We’ve discussed about boolean logic and how it works. But how can we implement a logic gate? In real life we would have physical chips for these gates which we can use, however we in the NAND2Tetris project we’ll be using software to implement these chips by using a simplified version of a language called HDL. HDL (Hardware Descriptive Language) is used to define logic of circuits using software. This is how the AND gate we created previously would be implemented in HDL:
CHIP And {
IN a, b;
OUT out;
PARTS:
Nand (a=a , b=b , out=temp );
Not (in=temp , out=out );
}(Note: I had already created a NOT gate using NAND gate previously instead of re-defining the gate every time we want to use it we can simply create it once and use it when need. That’s our first abstraction here!)
You can learn about the HDL’s syntax from the book (HDL Survival Guide) provided in the project material:
https://github.com/krolft/nand2tetris/blob/master/manuals/HDL Survival Guide.pdf
Interesting things to try:
In the first week’s project you have to create 15 gates from from just using the NAND gate. I won’t be creating them here as that would just be spoiling the project for you. Instead I’ll leave you with the few things that I found interesting when creating those gates myself.
- If you have a perform NOT operation on A, B and feed them to an AND gate should the output be the same if you feed A, B to a NAND gate which is just the reverse of the AND gate? Think about about your answer and then try to prove it by processing all four possibilities from both of the defined gate sets. (You might be surprised by the answer)
- Create some challenges for yourself to develop your logic thinking. For example: Using the same expression how can you get a different output for:
| 0 | 1 |
and
| 1 | 0 |
Conclusion:
This was just the first week of the project and it was packed with interesting learnings. We can now proceed to ask further questions: Now that we know how to create create expressions and understand boolean logic how does that fit into the bigger picture? How does the CPU utilizes boolean logic? Finally, if you have made it this far that means you are interested in learning more about this topic, so I would highly encourage you to get started with the NAND2Tetris project as the project covers things in much more detail then this blog and concepts such as: Optimizing the synthesized expressions etc.