Digital Foundations of a CPU

Learning Objectives

Derive a one-bit full adder, extend it to an (N)-bit ALU, explain two's-complement subtraction and overflow, show how D flip-flops form registers, and separate combinational delay from clocked state updates.

Before we write a single assembly instruction, let's take a step back and ask: how does a CPU actually work at the transistor and gate level?

Everything in a microprocessor — arithmetic, comparisons, branching, register storage — is built from the same handful of primitive logic gates you studied in digital electronics. This page connects those fundamentals to the real hardware inside an AVR or ARM core.

[!TIP] Prerequisite refresher links
If any concept below feels unfamiliar, these digital electronics lessons cover it in depth:

• Logic Gates — AND, OR, NOT, XOR (coming soon)
• Combinational Circuits — Adders, Multiplexers (coming soon)
• Sequential Circuits — Latches and Flip-Flops (coming soon)
• Number Systems — Binary, Hex, Two's Complement (coming soon)

The Big Picture — Gates → ALU → CPU

Every box above is made of transistors wired as gates. A modern AVR ATmega328P has roughly 100 million transistors. Every single one is doing Boolean algebra.

Part 1 — Building the ALU

Step 1: The Half Adder

The simplest addition circuit: two input bits, one sum bit, one carry bit.

Truth table:

The half adder cannot add multi-bit numbers because it has no carry input. That is what the full adder fixes.

Step 2: The Full Adder

A full adder has three inputs: A, B, and Cin (carry in from the previous bit position). It is built from two half adders and an OR gate.

Step 3: The 8-bit Ripple Carry Adder

Chain eight full adders together — carry out of bit 0 feeds into carry in of bit 1, and so on. This is how ADD R16, R17 works physically inside the AVR:

The C (Carry) flag in the AVR's SREG register is literally the carry-out wire of FA bit 7. When you do BRCS (Branch if Carry Set), the CPU is testing that one wire.

Step 4: Subtraction — Two's Complement

The ALU does not have a separate subtractor circuit. Subtraction is done by inverting B and adding 1 (two's complement negation):

A − B  =  A + (NOT B) + 1

One adder circuit handles both ADD and SUB by routing the SUB control signal to XOR gates on the B input and to Cin. Elegant.

Step 5: Adding More Operations — The Full ALU

The real ALU selects between multiple operations using a multiplexer controlled by the opcode:

All operation units compute their result in parallel every clock cycle. The MUX simply selects which result to output. This is why the ALU is fast — no waiting for the right unit to "turn on."

Part 2 — Building Registers

Step 1: The SR Latch — One Bit of Memory

The simplest memory circuit: two cross-coupled NAND gates. Set (S) forces output to 1. Reset (R) forces output to 0. When both inputs are inactive, the output holds its last value.

The feedback wires are what make this a memory element — the output feeds back to reinforce itself. Remove power and the state is lost (volatile). This is why SRAM loses data on power-off.

Step 2: The D Flip-Flop — Clocked Storage

The SR latch has a problem: S and R must not both be active simultaneously. The D flip-flop solves this with a single data input and a clock:

On the rising clock edge, the D input is captured and held at Q until the next rising edge. This is how every register in every CPU works — data is sampled once per clock cycle.

Step 3: An 8-bit Register

Eight D flip-flops sharing a common clock and a write-enable signal form one 8-bit register:

The Write Enable signal is why you can have 32 registers but only write to one at a time — every register sees the ALU result bus, but only the destination register's WE is asserted.

Step 4: The AVR Register File

32 registers × 8 bits each = 256 flip-flops, plus address decode and read/write mux logic:

The opcode bits directly encode which registers to read from and write to. The decoder is just combinational logic — it converts 5-bit register address fields in the opcode to one-hot write-enable signals across 32 registers.

Part 3 — Flags: The ALU Output You Don't See

After every arithmetic or logical operation, the ALU updates the SREG (Status Register) flags. These are also D flip-flops — they store one bit each:

When you write BRNE (Branch if Not Equal) in assembly, the CPU is checking: is the Z flip-flop currently storing a 0? That's it. A conditional branch is a mux selecting between PC+2 and the target address, controlled by a single flag flip-flop.

Putting It All Together — One Clock Cycle

This is what happens inside the AVR in a single clock cycle when executing ADD R18, R16:

On a pipelined processor (like modern ARM Cortex-M), these stages overlap across multiple instructions — while one instruction is in ALU, the next is being decoded, and the one after that is being fetched. That is how a 16 MHz AVR can execute up to 16 million instructions per second.

Why This Matters for Firmware

Understanding the gate-level hardware explains real embedded programming constraints:

Summary

Worked Timing Check

For a synchronous datapath:

[
T_{clk} \ge t_{CQ} + t_{logic,max} + t_{setup} + t_{skew}
]

With (t_{CQ}=0.4\text{ ns}), logic and routing (=6.8\text{ ns}), setup (=0.6\text{ ns}), and skew/jitter allowance (=0.4\text{ ns}), (T_{clk}\ge8.2\text{ ns}) and (f_{max}\le1/8.2\text{ ns}\approx122\text{ MHz}). Hold time is a separate minimum-delay check and cannot be fixed merely by lowering frequency.

Common Mistakes

• Treating gates as instantaneous instead of checking propagation delay.
• Using carry-out as signed overflow.
• Inferring a latch through an incomplete combinational assignment.
• Releasing an asynchronous reset without clock synchronization.
• Checking setup but ignoring hold time and clock skew.

Further Reading

• MIT OpenCourseWare, Computation Structures
• Nandland, Setup and Hold Time
• RISC-V International, Unprivileged ISA

Mind Map