How does sand become a switch? · From Transistor to Browser

Chapter 1
How does sand become a switch?

The browser
The network
Software and languages
The CPU
Memory
Arithmetic
Logic gates
The switch

Figure 1.1: Where we are in the climb from transistor to browser: the very bottom rung. This chapter starts at doped silicon, turns it into a switch, and builds the first logic gate, NAND, from it.

That one repeated part, the switch, is where the climb begins. Not a light switch you flip by hand, but a switch flipped by another wire. A small voltage on a control line decides whether a second, signal line conducts. That is the whole device, and the rest of this book is what happens when you wire enough of them together. But a switch flipped by a wire is not obvious, so we begin one level lower still, at the sand it is made from.

1.1 From sand to a transistor

The physical part is a transistor, and a transistor begins as silicon, the main ingredient of sand. A silicon atom has four outer electrons, and in a crystal each is locked into a bond with a neighbour, so pure silicon barely conducts: there are no loose charges to carry a current. The trick is to spoil it on purpose, called doping. Mix in a trace of an element with five outer electrons, such as phosphorus, and the fifth electron of each has no bond to join, so it drifts free: the silicon now carries current with spare electrons, and is called n-type for their negative charge. Mix in an element with three, such as boron, and each leaves a bond unfilled, a hole that behaves like a mobile positive charge, and the silicon is p-type. Doping turns a stubborn insulator into a material whose conductivity you can engineer.

1.2 The field-effect switch

A transistor is a sandwich of these. An n-channel transistor sets two n-type wells, the source and the drain, in a p-type body, with a metal gate above the gap between them, held just off the silicon by a whisker-thin layer of glass. Nothing connects the wells until a voltage is put on the gate. When one is, the gate’s electric field reaches through the glass and pulls electrons up to the surface, where they form a thin conducting bridge, a channel, from source to drain. Take the voltage away and the channel vanishes. So the gate is a switch, and Figure 1.2 shows it both open and closed.

mosfet — Figure 1.2: An n-channel field-effect transistor. Left: a LOW gate leaves no channel, so the source and drain wells are cut off. Right: a HIGH gate pulls electrons into a channel that bridges them. The gate switches the path with a voltage, not a finger.

Example 1-1. A transistor conducts on command

def conducts(kind: str, gate: int) -> bool:
    """Whether a field-effect transistor conducts. An n-channel device forms its
    channel and conducts when the gate is HIGH; a p-channel device is the mirror,
    conducting when the gate is LOW."""
    return gate == HIGH if kind == "n" else gate == LOW1

an n-channel device conducts when its gate is HIGH; a p-channel device is the mirror, conducting when its gate is LOW

Read as a switch, its gate is the control line and the drain-to-source path is the signal it gates, the device Figure 1.3 names.

transistor-switch — Figure 1.3: The same transistor, read as a switch. The control line (the gate, in green) decides whether the signal line (blue) conducts from drain to source. This is the single moving part of all digital computing.

Real gates use two flavours of this switch together. Put a p-channel above the output to pull it HIGH and an n-channel below to pull it LOW, both fed the same input, and for either input exactly one of them conducts: the output is driven cleanly to a rail, never shorted and never left floating. That complementary pair, CMOS, is how every gate in a modern chip is built, and its simplest form just inverts its input.

Example 1-2. A complementary pair inverts a bit

def inverter(a: int) -> int:
    """A CMOS inverter: a p-channel pull-up to HIGH and an n-channel pull-down to
    LOW sharing the input as their gate. Exactly one conducts, so the output is the
    clean opposite of the input, never shorted and never left floating."""
    pull_up = conducts("p", a)      # the path to the HIGH rail1
    pull_down = conducts("n", a)    # the path to the LOW rail2
    assert pull_up != pull_down     # complementary: one path open, never both3
    return HIGH if pull_up else LOW

the p-channel is the path to the HIGH rail
the n-channel is the path to the LOW rail
exactly one is ever open, so the output is a clean bit, the input’s opposite

The chapter’s program dopes silicon both ways, gates a transistor, and inverts a bit with the pair; the output below is the program’s own, captured as it ran, not typed in.

output · ftb.transistor

Doping silicon (4 outer electrons):
  silicon    4 outer electrons  nothing spare   -> insulator
  phosphorus 5 outer electrons  a free electron -> n-type
  boron      3 outer electrons  a hole          -> p-type

A field-effect transistor conducts when the gate opens a channel:
  n-channel  gate 0  blocks
  n-channel  gate 1  conducts
  p-channel  gate 0  conducts
  p-channel  gate 1  blocks

A complementary (CMOS) pair inverts its input:
  in 0  ->  out 1
  in 1  ->  out 0

1.3 Why two values, and only two

A real wire carries a continuous voltage, and that voltage sags over distance, warms with the room, and picks up noise from its neighbours. If we tried to read shades of meaning off it, every long wire would lie a little. So we refuse to. We agree to recognise only two bands, a low one and a high one, and to call them exactly 0 and 1, LOW and HIGH. Anything that drifts into the low band is snapped back to a clean 0; anything in the high band, to a clean 1. A lone switch only passes its input along, but the gates built from switches do the restoring, the inverter earlier in this chapter and the NAND a few pages ahead: their output is pinned to a rail, not to whatever fuzzy level arrived. Noise that would corrupt an analog signal dies at every gate. That single act of rounding, repeated everywhere, is why computing went digital.

1.4 The first gate: NAND

Stack two n-channel switches end to end between the output and the LOW rail, and add a pull-up of two p-channel switches side by side between the output and the HIGH rail: either one drives the output HIGH when its own input is LOW. Now the output is dragged LOW only when current can flow all the way down, which needs both series switches closed at once. For every other input at least one p-switch is driving the output HIGH. That behaviour, low only when both inputs are high, is the gate called NAND. Figure 1.4 shows it twice: the tidy symbol an engineer draws, and the transistors that actually do the work, set side by side so the abstraction and its implementation sit in one view.

nand-two-ways — Figure 1.4: NAND, two ways. Left: the gate symbol, the abstraction we will reuse from here on. Right: the CMOS implementation, two switches in series (green) forming the pulldown, with a pull-up above holding the output HIGH until that series path conducts.

The whole truth of NAND fits in one picture. Figure 1.5 is the centrepiece of this chapter: the same pulldown drawn four times, once per input combination. A switch whose control is HIGH is shown closed and lit green; a switch whose control is LOW is open and grey. The series path conducts only in the last panel, where both switches close, so only there is the output dragged to 0. Read the output bits left to right and you have read the truth table, without a single number having been asserted by hand.

Figure 1.5: The NAND pulldown at all four inputs (a Tufte small-multiple). Lit green switches conduct; grey switches are open. Current reaches the LOW rail, pulling the output to 0, only when both switches close (rightmost panel). The four output bits, 1,1,1,0, are the NAND truth table read off the geometry.

1.5 The program

The model in code is just as small as the picture. A switch passes its signal only when its control is HIGH; a NAND is one switch standing in for the series pulldown, with the result inverted by hand to mean “low only when it conducts.”

Example 1-3. NAND, built from a switch

def nand(a: int, b: int) -> int:
    """NAND built from two switches in series to ground.

    `switch(a, b)` conducts only when a is HIGH and b is HIGH, so the pulldown
    drags the output low for exactly that one input combination; the pull-up
    holds it HIGH for the other three.
    """
    pulldown_conducts = switch(a, b) == HIGH1
    return LOW if pulldown_conducts else HIGH2

the series pulldown conducts only when a and b are both HIGH (that is exactly what switch(a, b) reports)
so the output is LOW for that one case and HIGH for the other three, which is NAND

Run it, and the program prints its own truth table. This is the same 1,1,1,0 the small-multiple drew, now produced by the code rather than claimed by the prose:

output · ftb.switch

a b | NAND
----+-----
0 0 |  1
0 1 |  1
1 0 |  1
1 1 |  0

1.6 Why NAND is enough

NAND is not just a gate; it is the only one we strictly need. Tie its two inputs together and the “both high” case becomes “input high,” so the output is the opposite of the input: that is NOT. Feed a NAND through such a NOT and you undo the inversion, leaving plain AND. Figure 1.6 draws both constructions, and the chapter’s program already carries them as two one-line functions.

not-and-from-nand — Figure 1.6: NAND wearing two hats. Left: tie a NAND’s inputs together and “both high” collapses to “input high,” so the output is the input inverted: NOT. Right: follow a NAND with that NOT and the two inversions cancel, leaving AND. The program carries both as not_ and and_.

Example 1-4. NOT and AND, from nothing but NAND

def not_(a: int) -> int:
    """NOT from one NAND: tie both inputs together."""
    return nand(a, a)

def and_(a: int, b: int) -> int:
    """AND from two NANDs: NAND then invert."""
    return not_(nand(a, b))

Why is that enough? Because a circuit’s whole job can be written down as a truth table, and any truth table at all can be built from the gates we now hold, mechanically. Take each row whose output is a 1 and build a detector for it: AND together the inputs, first inverting any the row wants LOW, so the detector answers 1 for exactly that row and no other. Then merge the detectors, so the circuit’s output is 1 whenever any of them fires. The merging step is an OR, the one gate this recipe still lacks, and it too falls out of NAND: one of the exercises below asks you to find it, and the next chapter derives it from a law worth knowing. Nothing about the recipe cares which table you started from. Whatever behaviour you can tabulate, you can build, and the parts list never grows past NAND.

So a single repeated part, the switch, gives us NAND, and NAND alone gives us everything else. That is the door into the next chapter: building the rest of the gates, and then arithmetic, out of nothing but this.

Exercises

Boron has three outer electrons. Doped into silicon, does it make n-type or p-type, and what carries the current?
Build OR from NAND alone, then check its truth table against the OR gate you meet in the next chapter.
An AND gate is a NAND followed by a NOT, and both were built from switches in this chapter. Count the switches in the whole AND gate.

Previous Next

Chapter 1How does sand become a switch?