Build a Computer from NAND Gates

Part 1: Hardware Foundations

What if I told you that everything your computer does, from browsing the web to running AI models, can be built from a single type of logic gate? It sounds almost magical, but it's true. The NAND gate is functionally complete, meaning any computation can be expressed using only NAND gates.

In this three-part series, we'll build a complete computer from scratch:

• Part 1 (this post): Boolean logic, arithmetic circuits, and memory
• Part 2: Machine language and CPU architecture
• Part 3: Building an assembler

By the end, you'll understand how transistors become programs. Let's start with the most important gate in computing.

The NAND gate: one gate to rule them all

NAND stands for "NOT AND". It outputs the opposite of what an AND gate would output. Here's the key insight: any logic function can be built using only NAND gates.

This property, called functional completeness, is why NAND gates are the foundation of digital circuits. Try toggling the inputs below to see how NAND behaves:

Notice that NAND outputs 0 only when both inputs are 1. In every other case, it outputs 1. This behavior might seem arbitrary, but it's the key to building everything else.

Why NAND?

In the 1960s, engineers discovered that NAND gates were easier to manufacture with transistors than other gates. A single NAND gate requires only 4 transistors, while building NOT, AND, and OR separately would require more.

But here's the beautiful part: we don't need those other gates as primitives. We can build them all from NAND.

Building other gates from NAND

Let's construct the fundamental logic gates using only NAND. Click through each gate to see how it works:

Here's the insight behind each construction:

NOT (Inverter): Connect both NAND inputs to the same wire. Since NAND(a, a) = NOT(a AND a) = NOT(a), we get inversion.

AND: First NAND the inputs to get NOT(a AND b), then invert the result with another NAND to get a AND b.

OR: By De Morgan's law, a OR b = NOT(NOT(a) AND NOT(b)). Invert each input, then NAND the results.

XOR: This one requires four NAND gates arranged cleverly. XOR outputs 1 when inputs differ (essential for arithmetic).

Boolean arithmetic: adding with logic

Now that we can build any logic gate, let's do something useful: binary addition.

The half adder

Adding two 1-bit numbers can give us either 0, 1, or 2. In binary:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 10 (that's "2" in binary, so we need a carry bit!)

A half adder computes the sum and carry of two bits:

Look at the pattern: the sum is an XOR of the inputs (different = 1), and the carry is an AND (both 1 = carry).

The full adder

But what about that carry? When adding multi-bit numbers, we need to accept a carry from the previous bit position. The full adder adds three bits: a, b, and the carry-in.

A full adder is just two half adders chained together, with an OR to combine the carries.

The 16-bit adder

Chain 16 full adders together, and you can add two 16-bit numbers! The carry ripples from bit 0 up to bit 15, which is why this is called a ripple-carry adder.

Watch the animation to see how the carry propagates through each bit position. This ripple effect is the reason addition takes time. The more bits, the longer the carry chain.

Note: Real computers use faster adder designs like carry-lookahead adders that predict carries in parallel, but the principle is the same.

The ALU: the brain's calculator

The Arithmetic Logic Unit (ALU) is the computational core of any CPU. It performs arithmetic (add, subtract) and logical (AND, OR, NOT) operations based on control signals.

Our ALU has 6 control bits that select from 18 different operations:

Each operation is computed by manipulating the inputs before and after the core add/and operation:

• zx, nx: Zero or negate the x input
• zy, ny: Zero or negate the y input
• f: Choose between ADD or AND
• no: Negate the output

The output flags tell us if the result is zero (zr) or negative (ng), which is useful for conditional jumps in programs.

This single chip can compute any arithmetic or logical function we need. Combined with memory, it forms the heart of a computer.

Memory: storing bits over time

So far, our circuits are combinational. Their outputs depend only on current inputs. But computers need to remember values. For that, we need sequential circuits that can store state.

The 1-bit register

A register stores a value until we explicitly change it. The key component is a D flip-flop, which captures its input on the rising edge of a clock signal.

When load=1, the register captures the input value on the next clock tick. When load=0, the register keeps its current value, ignoring the input.

The clock signal synchronizes all memory operations. This is why CPUs have clock speeds. Each tick is one opportunity to read or write memory.

RAM: random access memory

A single register is useful, but we need many storage locations. RAM (Random Access Memory) provides this by combining:

• A decoder that selects one register based on an address
• Multiple registers, only one of which is active at a time

The "random access" part means we can read or write any address in the same amount of time, unlike a tape where you'd have to wind to the right position.

Building larger RAM

RAM units are built hierarchically:

• RAM8: 8 registers, 3-bit address
• RAM64: 8 RAM8 units, 6-bit address
• RAM512: 8 RAM64 units, 9-bit address
• ...and so on

The address is split: upper bits select which sub-unit, lower bits select within that unit. This recursive structure scales to any size.

What we've built

In this part, we constructed:

1. Logic gates (NOT, AND, OR, XOR) from NAND
2. Adders (half, full, 16-bit) for binary arithmetic
3. An ALU that computes 18 different operations
4. Registers and RAM for storing data

These are the building blocks of any computer. We now have:

• A way to compute (ALU)
• A way to remember (RAM)

What's missing? A way to control these components, to decide which operations to perform and when. That's where machine language comes in.

In Part 2, we'll design a CPU that reads instructions from memory and executes them, completing our computer architecture.

---

This post is part of a 3-part series on building a computer from first principles.