Frozen Logic
In the previously chapter, we built a switch. A single switch is useful for controlling flow, but it cannot think. To think, we need to make decisions based on multiple inputs. We need Logic.
We could wire transistors together manually every time we want to make a decision, but that is akin to rebuilding a car engine every time you want to drive to the store. Instead, we "freeze" useful patterns of transistors into blocks we call Gates.
The Universal Joint: NAND
It turns out that you can build any digital logic circuit using only one type of gate: the NAND (Not-AND) gate. It is the universal atomic unit of our digital reality.
A NAND gate outputs 0 only if both inputs are 1. Otherwise, it outputs 1.
Physically, a CMOS NAND gate requires 4 transistors (2 PMOS, 2 NMOS).
This is our unit of cost. Every abstraction you build on top of this costs you transistors, which means it costs you capacitance, which means it costs you time.
The Cost of Complexity: The Half Adder
Let's try to do math. The simplest possible addition is adding two single-bit numbers, \(A\) and \(B\).
- \(0 + 0 = 00\)
- \(0 + 1 = 01\)
- \(1 + 0 = 01\)
- \(1 + 1 = 10\) (This is 2 in binary)
To implement this, we need two outputs:
1. The Sum (the 1s place). This requires an XOR (Exclusive OR)
operation.
2. The Carry (the 2s place). This requires an AND operation.
This circuit is called a Half Adder. And it reveals a painful truth: XOR is hard.
Analysis
Look at the simulator. The AND gate (Carry) is relatively simple (NAND + NOT = 6 transistors).
The XOR gate (Sum) is a monster. To build it from our universal NAND blocks, we need 4 NAND gates arranged effectively. That's 16 transistors.
When you write a ^ b in code, it feels the same as a & b. But physically, the
XOR takes longer to settle and burns more energy. The abstraction of code hides the weight of the logic.
The slowest chain of transistors that must settle before the output is valid is called the Critical Path. The clock must wait for this path. If the XOR has not settled when the clock ticks, the machine will sample the wrong value. This is why complex logic forces slower clocks or deeper pipelines.
Hypotheses
Why not just build a dedicated XOR transistor?
We try! There are "pass-transistor" logic styles that can implement XOR more efficiently than strictly CMOS NAND-based logic. But often, standardizing the manufacturing process to print billions of identical, simple transistors is cheaper than designing specialized physical structures for every possible logic gate. Regularity beats nuance at scale.
If NAND is universal, why do CPUs use AND, OR, XOR at all?
Universality means possible, not optimal. Building everything out of NAND minimizes design complexity, not execution speed. Real CPUs use richer gate libraries because fewer transistors on the critical path means higher clock speeds. Universality is for theory; performance is for engineering.
Why does XOR appear everywhere if it’s so expensive?
Because XOR has a unique property: it detects difference. Addition, subtraction, parity checks, checksums, cryptography, and hash functions all rely on XOR. We use it because it solves problems no simpler gate can, and we accept the physical cost.
Is multiplication just a lot of adders?
Yes. A binary multiplier is essentially a grid of adders and shifters. This is why multiplication has historically been slower than addition and why modern CPUs dedicate enormous silicon area to optimized multiply units.
Why not make everything combinational and remove clocks?
Fully combinational machines exist in theory, but they are unusable in practice. Without clocks, you cannot define when a value is ‘done’. The result would oscillate, glitch, and race unpredictably. The clock is not for speed—it is for agreement.
What is the relationship between logic and heat?
Every time a transistor switches, it charges or discharges capacitance. That energy is lost as heat. More gates and deeper logic mean more switching, more energy, and more heat. This is why modern CPUs are power-limited before they are transistor-limited.
Does reversible logic solve this?
In theory, reversible logic can avoid information loss and reduce heat. In practice, it requires vastly more hardware, precise timing, and error correction. Today’s computers trade thermodynamic efficiency for reliability and simplicity.
Can we run it backwards?
No. Looking at the AND gate, if the output is 0, the inputs could be (0,0), (0,1), or (1,0). You cannot recover the input state from the output state. This loss of information is physically linked to the generation of heat (Landauer's Principle). Logic that forgets must pay a thermodynamic tax.