How You Can Build a Computer From a Single Gate

Most software engineers can't explain how their computer works.

Me included, I work as a backend developer but know nothing about the internals of my laptop.
In modern computer science we have so many layers of abstraction that you don't need to know what's underneath.
But knowing a thing or two about it will certainly make you a better developer.

And you can start by building your own computer from just a single logic gate.

Nand2Tetris

Nand2Tetris is a course by Noam Nisan and Shimon Schocken where you build a fully functional computer by starting with just one simple logic gate - the NAND gate.

The course is available for free on the website nand2tetris.org and it does not require any pre-existing knowledge about computers or programming (although it helps).
It's divided into two parts: Hardware and Software, and includes twelve projects.
In the first six projects you build the computer from scratch, and in projects 7 to 12 you build the software stack: a VM translator, a compiler, and a small OS.

The course is widely known as one of the best courses in computer science for understanding how things work on a low level.

Boolean Logic

The first project is about boolean logic. Build 15 different chips from a simple logic gate.

The documents (or videos) explain everything that is needed to solve this task:

• the theory of boolean logic
• the connection between boolean logic and electrical circuits
• an introduction to hardware description files and hardware simulation

You are provided with stub, comparison and test files for each gate. These files provide the necessary information on how the gate/chip
is supposed to work. The actual implementation is your part.

For the Xor gate for example, these are the stub and comparison file:

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/1/Xor.hdl
/**
 * Exclusive-or gate:
 * if ((a and Not(b)) or (Not(a) and b)) out = 1, else out = 0
 */
CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:
    //// Replace this comment with your code.
}

| a | b |out|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

The first gates like NOT, AND and XOR were straightforward, but Mux and DMux were a different story.

Routing

Mux and DMux broke my pattern.

While the simpler gates are all basic boolean arithmetic, Mux and DMux do not calculate anything.
The Mux takes two input signals (a and b) and a select signal.
Based on the select signal the output has either the value of a or b. The DMux does the opposite: it takes one input and routes it to one of two outputs based on the selector.

This is the truth table for the Mux:

| a | b |sel|out|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

The tricky part here is the shift in the pattern. NOT, AND, XOR all follow the principle of combining inputs and calculating a result. Routing needs a different pattern and requires you to shift your thinking.

Another challenge is the 4-Way and 8-Way Mux. I built them the same way as the Mux (but with a lot more code as you may imagine) first, before realizing that they can be built with just three Mux chips.
I discovered that you can use the divide and conquer pattern for both, software and hardware.

My Verdict of Project 1

In total the first project took me around five hours including going through the course material.

So far it's worth it to go through this course to deepen your knowledge of how computers work and eventually become a better software engineer.

The next project will be about building a calculator from logic gates.

Originally published on jasu.dev