Chapter 3: Digital Logic — From Logic Gates to Computers

Vol 3: Computer Core Expedition · Chapter 3

---

Metadata Card

Attribute	Value
Difficulty	(4/5)
Prerequisites	Vol 2 (Algorithms); Basic circuit concepts
Keywords	Logic Gates, Boolean Algebra, Half Adder, Full Adder, MUX, Decoder, D Flip-Flop, Clock

---

Your Progress

"Unknowingly, you've reached the deepest layer of the Core. There's no software here — only hardware. Logic gates pile up like bedrock, from simple AND/OR/NOT gates to the complex ALU. Behind every CPU instruction lies the arrangement of these basic gates."

---

Encounter 1: From Switch to Boolean

Logic Gates

Gate	C Expression	Rule
AND	a && b	All 1 → 1
OR	a || b	Any 1 → 1
NOT	!a	Invert
NAND	!(a && b)	Universal gate
XOR	a ^ b	Different → 1

NAND is universal: All other gates can be constructed from NAND gates alone.

Encounter 2: Combinational Logic

Half Adder → Full Adder → Ripple-Carry Adder

int full_adder(int a, int b, int cin, int *sum, int *cout) {
    *sum = a ^ b ^ cin;
    *cout = (a & b) | ((a ^ b) & cin);
    return *cout;
}

int add_8bit(int a, int b) {
    int carry = 0, result = 0;
    for (int i = 0; i < 8; i++) {
        int ai = (a >> i) & 1;
        int bi = (b >> i) & 1;
        int si;
        carry = full_adder(ai, bi, carry, &si, &carry);
        result |= (si << i);
    }
    return result;
}

Encounter 3: Sequential Logic

D Flip-Flop

int d_flipflop(int d, int clk, int *prev_clk, int *q) {
    if (clk == 1 && *prev_clk == 0) { // rising edge
        *q = d;
    }
    *prev_clk = clk;
    return *q;
}

Register: 8 D Flip-Flops Sharing a Clock

struct Register8 {
    int q[8];
    int prev_clk;
};

void reg_write(struct Register8 *r, int clk, int data[8]) {
    for (int i = 0; i < 8; i++) {
        r->q[i] = d_flipflop(data[i], clk, &r->prev_clk, &r->q[i]);
    }
}

Encounter 4: Clock and Synchronization

The clock ensures all components work in sync. On each rising edge, sequential elements sample their inputs; during the clock period, combinational logic propagates.

---

Verification Checklist

• [ ] Can draw truth tables for basic gates
• [ ] Can build a full adder from half adders
• [ ] Can explain why the clock is the "heartbeat" of digital circuits
• [ ] Can distinguish level-sensitive (latch) vs edge-sensitive (flip-flop)

---

Traveler's Notes

• The computer is not a "calculating electron tube" — it's a carefully woven, ever-oscillating logic network
• Voltage propagates through this network like a tide — each wave completes a bit of computation
• A simple serial XOR in hardware uses four transistors

---

→ Next Stop Preview

Chapter 4: CPU and ISA — The Core Engine