Build the smallest useful computer

Why two states?

A wire in a chip carries a voltage, and voltages are noisy. Neighbouring wires couple into each other, the supply ripples, and temperature drifts. If we tried to store ten different levels on one wire, a small disturbance could turn a 6 into a 7.

Digital logic avoids this by asking only one question of each wire: is it low or high? Any voltage in a wide "low" band counts as 0. Any voltage in a wide "high" band counts as 1. Voltages in the gap between the bands do not have a guaranteed 0-or-1 interpretation. A switching signal passes through this region, so a circuit that samples the signal must wait until it has settled into a valid band. Every gate also restores its output to a clean level, so noise doesn't pile up from one gate to the next: each stage regenerates a valid 0 or 1. (A chain of gates still adds delay, and every gate has loading and operating limits, so "regenerated" doesn't mean "free".)

Place value in base 2

A bit is one 0-or-1 position. One bit gives us two patterns; two bits give us four: 00, 01, 10, 11. Every added bit doubles the possibilities, so n bits have 2ⁿ patterns. The next question is what we want those patterns to mean.

If we read a pattern as an unsigned (nonnegative) number, its positions have weights 1, 2, 4, 8, and so on from right to left. Just as decimal 305 means 3 hundreds + 0 tens + 5 ones, binary 00101101 means 32 + 8 + 4 + 1 = 45. The positions holding 0 contribute nothing; find the four 1s in the figure and add their weights.

In hexadecimal, the digits after 9 are A through F, standing for 10 through 15. Split the byte into groups of four bits: 0010 is 2, and 1101 is 13, written D. Together they make 0x2D; the 0x prefix says the digits are hexadecimal. This is a shorter spelling of the same bits, not another value stored alongside them.

Same bits, many meanings

A bit pattern has no meaning by itself. As an unsigned number, 11111111 represents 255. Under two's complement—the signed-number encoding explained below—the same 8-bit pattern represents −1. The same byte could be eight on/off flags, part of a character encoding, or an instruction fetched from memory. The bits have not changed; the operation using them supplies the interpretation. For example, adding two bytes treats them as numbers, while fetching a byte into an instruction register treats some of its bits as an operation code. Click the bits below to see several readings of one pattern, plus its hexadecimal spelling.

Negative numbers: two's complement

How can the same 8 bits also represent negative numbers? In two's complement, the highest bit has weight −128 instead of +128; the other weights stay the same. Thus 11111111 means −128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = −1. A top bit of 0 still gives values 0 through 127; a top bit of 1 gives −128 through −1. The choice of signed or unsigned reading belongs to the operation, not to a hidden label inside the byte.

The wheel below assigns two sets of number labels to the same 16 bit patterns. Adding 1 advances to the next pattern under either reading. For example, adding 0001 to 1111 produces 1 0000; keeping four bits leaves 0000. This represents unsigned 15 + 1 wrapping to 0, or signed −1 + 1 producing 0. The circuit adds the bit patterns, so the same adder circuit works for signed and unsigned numbers. The interpretation determines whether the mathematical sum fits within the available range.

The same wraparound rule explains how to get the bit pattern for the negative of a value B. At each position, B and its flipped bit add to 1, so B plus its flipped pattern equals 1111. The flipped pattern therefore equals 1111 − B; adding 1 makes 10000 − B. Keep the low four bits and the result acts like −B.

For example, 5 is 0101. Flip to 1010 and add 1 to get 1011, which reads as −5. Thus subtraction can reuse addition: A − B = A + (flipped B) + 1, discarding any fifth bit. Lesson 2 will put this rule into an ALU.

The flip-and-add-one bit rule still works at the edge of the range, but the mathematical answer may not fit. An n-bit two's-complement number ranges from −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1: −8 to +7 in 4 bits. There's no +8, so flipping 1000 (−8) to 0111 and adding 1 yields 1000 again. The bits follow the rule; interpreting the result as +8 would be wrong because +8 has no 4-bit signed representation.

Carry and signed overflow are also different things. 0111 + 0001 = 1000 has no carry out of the top bit, yet as signed numbers 7 + 1 came out as −8: signed overflow without a carry. 1111 + 0001 = 1 0000 does carry out, which means the unsigned sum 15 + 1 didn't fit, but as signed numbers it's −1 + 1 = 0, a correct result despite the carry. Signed overflow happens when two operands of the same sign produce a result of the other sign.

Fixed width means arithmetic wraps around

An 8-bit register can hold only eight bits, so it cannot hold the unsigned number 300. If a calculation produces more bits, this machine keeps the low eight and drops the rest. In arithmetic terms, it keeps the remainder after division by 2⁸ = 256, also called the result modulo 256. Imagine a counter that goes from 255 back to 0 rather than gaining a ninth digit.

An address is not the value stored there

To run a program, we will soon need to ask both "which storage location?" and "what value is in it?" Those are different questions, even when the address and the stored value are both written as numbers.

Memory is a collection of numbered storage locations. The address selects a location; the contents are the bits found there. We write M[6] = 42 to mean "read address 6 and you get 42." It does not mean that 6 equals 42. This is abstract notation for now; Lesson 3 builds a circuit that stores and selects the values. In the picture below, a read of address 3 returns 6. What additional step would get us to 42?

Use the returned 6 as the address for a second read: M[6] = 42. We can write the two reads together as M[M[3]] = 42. The extra pair of brackets means another memory access, not a property of the number 6 itself. This previews pointers and indirect addressing; NIB-8's instructions later in this unit use their address field directly.

A machine's widths are separate design choices: how many bits a register holds, how many bits an address has, how long an instruction is, and how much storage one address names. For example, a 4-bit address can name 2⁴ = 16 locations whether each location holds one bit, one byte, or something else. The choices happen to match on some machines, which makes them easy to confuse:

Explain the difference between a bit pattern, an interpretation of it, an address, and the contents at that address, using an example of your own.

Lesson 1 gave us patterns that can stand for numbers. But writing 0111 + 0001 = 1000 on paper does not make any wires calculate it. We need a circuit that turns input bits into output bits. A combinational circuit does exactly that: its outputs depend only on its current inputs. Change an input and, after a short physical delay while the signals settle, the output changes too. It has no memory of earlier inputs.

Five gates on a bench

A gate is a tiny circuit (a handful of transistors) that computes one logical function. Set A = 1 and B = 1 in the bench below. OR lights up, but XOR does not; change B to 0 and both light up. The truth table highlights each combination as you try it.

These gates work on one bit at a time. To apply AND to two bytes, line up their bits and use an AND gate for each position: 00001100 AND 00001010 = 00001000. The 8's place is 1 in both inputs, so it is 1 in the result; all other positions give 0. This is a bitwise operation, different from treating the whole bytes as numbers and adding them.

The multiplexer: choosing a source

A multiplexer (mux) has several data inputs and a select input that picks which one passes through. In the demo, A stays 7 and B stays 12; changing S alone changes which value reaches the output. A processor uses the same choice when one input must receive values from different sources at different times. Later, for example, a mux will let our memory receive either the address of an instruction or the address of data.

Building addition: the full adder

Adding binary numbers column by column works like decimal addition: each column adds two digits and any carry from the column to its right. For example, 1 + 1 is binary 10: write 0 in this column and carry 1 into the next. If another 1 came in as a carry, 1 + 1 + 1 is 11: write 1 and carry 1.

A full adder handles one such column. It takes A, B and carry-in, then produces a sum bit and carry-out. The two outputs must account for the value of the three inputs: A + B + Cin = sum + 2 × Cout. Gates implement those outputs with these Boolean formulas:

sum = A ⊕ B ⊕ C_in     C_out = A·B + C_in·(A ⊕ B)

In these Boolean formulas, ⊕ means XOR, · means AND, and + means OR; that last + is not numerical addition. Read the carry formula in words: a carry comes out if both inputs are 1 (the column generates a carry), or if exactly one is 1 and a carry came in (the column propagates it). Toggle the inputs and follow the highlighted wires:

Chaining columns: the ripple-carry adder, and why it takes time

Connect four full adders so each carry-out feeds the next column's carry-in, starting with carry-in 0 at the rightmost column, and you can add 4-bit numbers. For 0111 + 0001, the rightmost 1 + 1 produces sum 0 and carry 1; the next two columns each have a 1 and pass that carry left, giving 1000. Gates aren't instantaneous: each takes a small propagation delay to respond, and each column may have to wait for its incoming carry. Set some bits, then press Watch it ripple:

The ALU: many operations, one chosen result

An adder solves one problem, but a program will need to choose among operations. An arithmetic logic unit (ALU) offers add, subtract, AND, OR and XOR. Try A = 23 and B = 19 below: ADD gives 42; SUB gives 4. The input values stay put. The operation-select signal determines which calculation's result reaches the output.

In this circuit, the bitwise units and one adder work in parallel, then an output mux makes that choice. The adder is shared: for subtraction, the select signal makes it calculate A + (NOT B) + 1, with the "+1" entering as its first carry-in. Choosing SUB therefore changes the adder's inputs and the mux selection. Real ALUs make different choices about sharing circuits and disabling unused work.

The demo's Z output is 1 when the chosen ALU result is zero. It is a combinational indication, not a value stored for later. Our NIB-8 machine in Lesson 4 does not have a saved zero flag: its JZ instruction checks whether the value already held in ACC is zero.

What we still can't do

Suppose the ALU has produced 42 and the next step needs that 42. Where will it find the value after we change the inputs for the next operation? The ALU doesn't keep its old answer; after the delay, its output changes with its inputs. We have built a calculator circuit, but a sequence of steps needs somewhere to hold each result. Lesson 3 adds that storage.

Point at each part of the ALU figure and say whether it computes, selects, or (so far, nothing) remembers.

Feedback makes memory

The missing storage begins with feedback: a circuit can use its own output to keep a value in place.

Not every loop of gates remembers anything useful, so take a specific one: two inverters, each feeding the other. If the right-hand node is 1, the lower inverter makes the left-hand node 0, and the upper inverter turns that 0 back into 1. The loop agrees with itself, so it stays that way. The opposite state (right 0, left 1) is just as self-consistent. Two stable states: one bit of storage.

The loop alone gives us no way to choose or change its value. It might settle in either state when powered on. To make useful storage, we need a way to write a chosen bit and then let the loop hold it. The mux from Lesson 2 provides exactly that choice.

While a latch is enabled, its output follows its input. Suppose a latch stores A and its input is computed as A + 1. The latch takes that incremented value, which feeds the adder and produces another increment. That next value can enter the latch while it is still enabled, allowing several updates during one enable interval. To take one step per clock cycle, we need storage that captures a value at an edge.

A flip-flop controls that timing by chaining two latches enabled on opposite halves of the clock. In this rising-edge design, the first follows D while the clock is low. At the rising edge it closes, and the second passes along the first latch's held value. Later changes to D cannot pass through until the next rising edge. From outside, the flip-flop captures D at the rising edge and holds its output for the rest of the cycle. Line up 8 flip-flops sharing one clock and you have an 8-bit register.

A register usually also has a write enable. When it's off, the register keeps its old value even though the clock keeps ticking. Look at how that's built: it's just the mux from Lesson 2, feeding the register's own output back in.

The synchronous model: register state updates at clock edges

We can now describe a clocked machine with a simple rhythm:

1. Between edges, combinational logic reads the current register values and computes the next values. Its outputs may change several times as signals propagate. For reliable capture, each register's input must settle before the edge and remain stable for the required interval around it.
2. At the edge, every enabled register captures its next value at the same instant.

Think of an edge as a single handoff. If A holds 3 and B holds 9, and the wiring says A ← A + B and B ← A, the logic computes next-A = 12 and next-B = 3 from the old pair. At the edge, the pair becomes (12, 3) together. B never sees the newly written 12 during that update. This rule lets us trace a whole machine without guessing which register changes "first."

Try it: registers read old values

Because all registers capture at the same instant, each next-value computation sees the old values of every register, never a half-updated mix. This is very different from lines of code running one after another. Pick a rule, predict the next values, then tick the clock:

Why the clock can't just go faster

The clock period is the time from one rising edge to the next. It must be long enough for the slowest path from one register, through logic, to another register to settle. That is the critical path. In the example below, the sending register takes 60 ps to produce its output, the logic takes 700 ps, and the receiving register needs the input stable 40 ps before the next edge. The period must therefore be at least 60 + 700 + 40 = 800 ps. A faster setting would not make the computation finish sooner; it would make the captured result unreliable.

A tiny addressed memory, built from registers

Lesson 1 used M[address] as if selecting a storage location were automatic. We can now build a four-word version from registers and the parts we already know. In the figure, we want to read word 1 while preparing to write 99 to word 2.

A read mux with four inputs uses the 2-bit read address 01 to pass register 1's value to read data. For writing, a decoder turns the write address 10 into four separate enable wires; only wire 2 is high. If the overall write enable is on, register 2 captures 99 at the next clock edge. The two addresses select different locations, so the read can return 42 while the write changes word 2.

Registers, memory, datapath, control

Both registers and memory hold bits. In a processor, a small set of named working registers is close to the arithmetic circuits, while a memory array offers locations selected by addresses. The four-word example and NIB-8's 16-word memory are intentionally tiny; practical main memories are vastly larger.

A register file may itself use a small number to select a register, so the distinction is not simply "numbers versus no numbers." The useful distinction for this course is the role: working registers are operands that CPU instructions can name directly; memory supplies many addressed locations reached through memory operations. Exact size, speed and number of simultaneous accesses depend on the machine.

We now have circuits that hold values and circuits that transform them. Together, registers, an ALU, muxes and memory form a datapath. Control logic chooses the ALU operation, mux inputs and write enables. So far those choices are built into a particular circuit, as with the counter above. Lesson 4 gives the same hardware a way to follow different sequences: instructions read from memory.

Describe any clocked machine as three things: its current state, the combinational logic that computes the next state, and the rule for when state changes (the clock edge and write enables).

The counter from Lesson 3 has state, but its wiring always tells it to do the same thing. Making it count down or stop at zero would require different control. A stored-program machine keeps those choices as numbers in memory. One fixed circuit fetches a number, decodes it, and performs the requested action; change the numbers and the circuit follows a different sequence.

Meet NIB-8

Our machine is small enough that its entire specification fits in one table. Keep an eye on two values in particular: PC chooses which instruction comes next, while ACC holds the working data that arithmetic changes.

On reset, NIB-8 starts with PC = 0, ACC = 0 and phase = fetch. Every instruction is one byte, split into two nibbles of four bits each. The upper nibble is the opcode, which chooses an action. The lower nibble usually supplies an address: a data location for LOAD, STORE, ADD or SUB, or a destination for JMP or JZ. HALT ignores it. The memory bytes themselves carry no "instruction" or "data" label. Fetching a byte using PC treats it as an instruction; reading that same location as an operand would treat it as data.

In the table, [a] is a placeholder for one hexadecimal address digit (0 through F), not literal characters stored in the byte. For example, 0x1[a] means an upper nibble of 1 followed by whichever address nibble the instruction uses.

Thus LOAD 8 is 0x18 and STORE 10 is 0x2A. LOAD 8 means "read the byte at address 8," not "put the literal number 8 in ACC." This small machine has no instruction for loading an immediate constant; constants are placed in memory. Bytes with other opcodes aren't NIB-8 instructions. If one is fetched, our teaching rule is that the machine halts.

The datapath

Read the diagram in two passes. To fetch an instruction, the address mux sends PC to memory; the returned byte enters IR, and the small adder prepares PC + 1. To execute LOAD or ADD, the same memory instead receives the address in IR. Its data goes to the ALU, whose result can enter ACC. One memory serves both jobs because the mux selects an address source at the right time.

STORE takes another route, sending ACC's value to memory. JMP and a taken JZ overwrite PC with an address from IR. The control unit chooses these routes and enables writes; it does not move data by itself. The simulator will light up the route used on each tick.

Fetch, decode, execute

NIB-8 spends three clock ticks on every instruction. This is our teaching timing model, not a claim about real memory speeds:

1. Fetch. The address mux sends PC to memory, and the byte that comes back is captured in IR. At the same edge, PC ← (PC + 1) mod 16: the 4-bit PC wraps from 15 to 0. Both updates use the old PC, just like in Lesson 3.
2. Decode. Control looks at IR's opcode and determines the required selects and enables. The phase register advances to execute at the edge, but PC, IR, ACC and memory do not change.
3. Execute. The instruction's effect happens: ACC, memory or PC changes, or the machine halts.

Trace the first instruction of the example above. At tick 1, fetch reads M[0] = 0x18 into IR and advances PC from 0 to 1. At tick 2, decode recognizes opcode 1 (LOAD) and address 8. At tick 3, execute uses that address to read M[8] = 23 and captures 23 in ACC. Only then does the phase return to fetch, with PC still 1. The next three ticks fetch, decode and execute ADD 9; the three after those do the same for STORE 10. Separating these moments makes it possible to say exactly which value each circuit sees.

Inside the control box

The controller is a small state machine: a phase register plus combinational logic. The register records whether the machine is fetching, decoding or executing. The logic reads the current phase, the opcode in IR and whether ACC is zero. It produces control signals for the datapath and the next phase.

For example, during execute, LOAD enables a write to ACC and selects memory data as the ALU's output. STORE enables a write to memory and leaves ACC alone. The diagram and table below spell out the choices.

The whole controller fits in one table. A dash means the signal doesn't matter; every write enable not listed is 0.

Run it: the NIB-8 simulator

Start with Add two numbers. Before pressing Tick, predict the first three edges: which byte enters IR, when PC advances, and when ACC finally becomes 23. Then follow ADD and STORE the same way. Memory cells are editable: type a hex byte (one or two digits, 0–9 and A–F) into any cell to change the program or its data, and the machine resets. Reset restarts from the memory as you've edited it; clicking a program button restores that program's original bytes.

Branches turn a sequence into a loop

Without branches, execution follows consecutive addresses. In NIB-8, the four-bit PC wraps from 15 to 0, so a program with no HALT would eventually run through memory again. Branches let a program choose a different next address, including making a choice based on the data. The Countdown program is a loop that ends by testing ACC:

Follow the first trip around the Countdown loop. LOAD puts 3 in ACC. SUB leaves 2; STORE writes that 2 to M[8]. JZ sees that ACC is not zero, so PC continues to JMP, which sends it back to SUB at address 1. ACC already holds the current count, so the loop need not LOAD it again. When SUB eventually leaves 0, JZ sends PC to HALT instead.

Countdown has only one changing value to keep in ACC. Try the Multiply program next: it has both a growing product in M[12] and a decreasing counter in M[14]. Its instruction bytes occupy addresses 0–8. The loop at 0–7 adds M[13] = 6 to the product, then subtracts M[15] = 1 from the counter. Because ACC holds only one working value at a time, each pass must LOAD and STORE both values.

Starting from product 0 and counter 3, the first pass leaves (product, counter) = (6, 2), the second (12, 1), and the third (18, 0). JZ then skips the JMP and fetches HALT at address 8. The first two passes execute eight instructions each; the final pass executes seven, followed by HALT: 8 + 8 + 7 + 1 = 24 instructions. If the counter began at 0, this particular loop would still run once before testing it.

What is an "execution context"?

Suppose we pause NIB-8 and later resume it. Its architectural state includes the program-visible register and memory values: PC, ACC, halted and the memory contents. At a clean instruction boundary (between an execute and the next fetch), the saved CPU context consists of PC, ACC and halted. Memory remains separate from this register snapshot and must also be available. IR and phase record the hardware's progress through an instruction:

Pause mid-instruction, after fetch but before execute, and saving PC, ACC and halted is no longer enough: you'd also need IR and the phase. Switching at an instruction boundary avoids saving those intermediate values. Correct resumption still needs the same memory contents. On this machine they can stay in place. A second independent NIB-8 would need access to the same memory or a copy of it. A real operating system saves a processor's necessary registers and preserves the program's memory and mapping while switching between tasks; Unit 2 develops that picture.

A first performance calculation

For CPU execution time, three factors multiply together. We will use this accounting throughout the course:

time = instructions executed × cycles per instruction (CPI) × seconds per cycle

Two terms need care once we leave NIB-8. Instruction count means instructions actually executed, including every repetition of a loop, not merely the number of instructions stored in the program: Multiply has nine instructions in memory (eight in the loop plus HALT) but executes 24. CPI, cycles per instruction, is an average over that run: total CPU cycles ÷ instructions executed. NIB-8's CPI is always 3, but on real machines it changes with the program and its data. At a fixed clock period the equation gives CPU execution time; elapsed time can also include waiting for I/O or for the operating system to schedule the program.

Without the simulator: explain why the machine needs both PC and ACC, why ADD and STORE are separate instructions, and how JMP changes control flow without moving any instructions.

Use LOAD 8 as a final test. Explain aloud how the machine finds the instruction, reads M[8], and changes ACC at the execute edge. The two chains below are prompts: if an arrow seems mysterious, retrace that part in the datapath figure.

Data path: a typical arithmetic result, from operands to a stored value.

Control path: what decides which values move.

Keep the distinction from Lesson 1 in view throughout: an address picks a location, the contents there are a bit pattern, and the operation using it decides how it is interpreted. At an instruction boundary, NIB-8 can resume from the saved PC, ACC and halted values, provided its memory contents are preserved. These saved CPU values form its context. Resuming mid-instruction also requires IR and the control phase.

That last limitation is where Unit 2 begins. Look at the Multiply loop. It occupies eight instructions (addresses 0–7), and four of them, LOAD 12, STORE 12, LOAD 14 and STORE 14, transfer the product and the counter between memory and ACC, because there's only one place to keep a working value. With separate registers for the product and counter, arithmetic instructions can read and update those registers directly, avoiding the LOAD and STORE instructions used to move these working values through memory.

One more, unseen: a transfer exercise

Memory holds M[0..4] = [0x18, 0x39, 0x64, 0x2A, 0xF0], with M[8] = 250, M[9] = 6 and M[10] = 99. Everything else is 0, and the machine starts with PC = 0, ACC = 0. Decode the program by hand, then predict the final PC, ACC and M[10], the number of instructions executed, and the number of ticks.