From NAND to a 6502

Any digital logic can be built from one kind of gate, the NAND. Real chips aren’t designed that way, but it’s the simplest place to start.

A NAND gate outputs 0 when both its inputs are 1, and 1 the rest of the time. Every other gate can be made out of NANDs, and everything further down this page is made out of those gates.

Here are the basic gates, each built from NANDs. Click a switch to flip an input.

Wiring a few of those gates together gives you circuits that do arithmetic, starting with adding two bits.

Everything so far has been combinational, meaning the outputs depend only on what the inputs are right now. A computer also has to remember things, and for that a circuit needs feedback, with its output wired back into its own input.

Circuits that remember usually change only when a clock ticks, so everything updates in step. The Tick button below advances the clock by one cycle.

A counter is a register that adds one to itself on every tick. Bit 0 flips every time, bit 1 flips when bit 0 is 1, and bit 2 flips when bits 0 and 1 are both 1. The AND gates that work this out are a carry chain, the same as in the adders.

Click Tick a few times, or Auto to let it run. The LEDs count up in binary from 0000 to 1111 (15), then wrap back to 0000.

A CPU’s program counter is a counter like this one. It steps through memory one address at a time while the CPU fetches instructions. The 6502’s is 16 bits wide, and it can also be loaded with a new address, which is how jumps and branches work.

One full adder handles one column of a sum. To add whole numbers, connect the carry-out of each full adder to the carry-in of the next, the way you carry a 1 when adding by hand. Four in a row add two numbers from 0 to 15.

This is a ripple-carry adder, since the carry works its way up from the lowest bit to the highest. The 6502’s adder is 8 bits wide. Its addresses are 16 bits, so it adds them in two halves, and when the low half carries into the high half the instruction takes one extra clock cycle.

Set the A switches (a3–a0) to 0011 (3) and the B switches to 0101 (5). The sum LEDs should read 1000 (8).

A CPU needs more than addition. It also needs AND, OR and XOR. The arithmetic logic unit (ALU) works out all of them at once and uses a multiplexer to pass on the one the current instruction asked for.

Here is one bit of an ALU: a full adder and an AND, an OR and an XOR gate, all fed the same inputs. The two op switches choose the output: 00 is ADD, 01 AND, 10 OR and 11 XOR.

Put eight of these side by side, with the carry running between the adders, and you have most of the 6502’s ALU. The real one can also shift and do decimal arithmetic. When the CPU decodes an instruction, part of what it decides is which op to send the ALU.

Registers hold a handful of values. Programs need thousands of bytes, each at its own address, and that’s what RAM is for. Put an address in and the byte stored there comes out.

In this RAM, reading happens straight away and writing waits for a tick. Change addr and data_out follows. To write, set addr and data_in, turn we (write enable) on, and click Tick. Then turn we off and change the address to read it back.

Write 42 to address 1 and 7 to address 2, then switch between the two addresses to read them back. The 6502 computer at the end of this post has 2,048 bytes of RAM instead of 256, wired up the same way.

The MOS 6502 came out in 1975 and ended up in the Apple II, the Commodore 64 and the NES. It has about 3,500 transistors. Its ALU is 8 bits wide and its program counter 16, and it understands 56 instructions, which come in 151 variants once you count the different ways they can address memory.

Below is a small 6502 computer: the CPU, 2 KB of RAM, a ROM, and a console that prints any byte written to address $F000. It isn’t built out of the gates above. Its blocks are written to do the same jobs as the real chip’s, and that skips the part this page hasn’t covered yet: how an instruction gets decoded into the signals that drive everything else. The CPU is laid out like the real chip’s block diagram, with the same program counter, ALU, registers and internal buses. The wiring inside each block is simpler than the real chip’s, but on every clock cycle it reads or writes the same address and data as a real 6502, including the extra reads the real chip makes along the way. I checked this against Tom Harte’s tests, 1.5 million single instructions recorded cycle by cycle, and Klaus Dormann’s functional and decimal-mode test programs, and it passes both.

The programs in the ROM are written in C and compiled with cc65, a C compiler for the 6502. Press Run to start one. You can also edit the code and compile your own, and the compiler runs in your browser too. There’s no operating system on this computer, so when a program calls printf the C library hands each character to a few lines of startup code, which store it at $F000 for the console to show.