How to Trust a Noisy World

In my earlier article about von Neumann’s lecture on automata, I kept coming back to a question about organization. How can a system behave reliably when the things it is made from occasionally fail? Communication gives us a particularly clean version of that problem. A transmitter sends something, the physical world interferes, and a receiver has to work out what was originally sent. The receiver cannot inspect the sender’s memory. It has whatever survived the journey, plus whatever rules the two sides agreed on beforehand.

When John Horgan visited Claude Shannon in 1989, he wanted to hear how information theory had happened. Shannon wanted to show him his gadgets. At seventy three, he was still delighted to demonstrate chess machines, a pogo stick powered by gasoline, and a unicycle with two seats. His home was called Entropy House. The man whose mathematics helped make modern communication possible had filled it with things he enjoyed making.

I like that scene because it makes the papers feel less remote. Shannon moved comfortably between an abstract problem and an object assembled from parts. A peculiar machine poses a concrete question: how would you make that behavior happen? Sometimes the answer produces a gadget. Sometimes working out the mechanism reveals a problem shared by thousands of other machines.

Shannon grew up in Gaylord, Michigan, where he built models and a telegraph connection to a friend’s house using barbed wire around a pasture. By 1936 he had degrees in both mathematics and electrical engineering from the University of Michigan. He then went to MIT, where his research assistantship included operating Vannevar Bush’s differential analyzer. This was an analog calculating machine: setting it up meant translating differential equations into a physical arrangement that could produce their solutions.

For Shannon, the relationship between mathematics and machinery was something he worked with every day. An equation had to become a physical arrangement before the analyzer could solve it. His later work would let engineers reason about that relationship without tracing every shaft, wire, and contact.

The analyzer also had a complicated relay control circuit. Shannon had encountered Boolean algebra at Michigan, and recognized that the mathematics of logic with two values could describe switching networks. His master’s work on the subject appeared as a paper in 1938. In Boolean terms, two conducting contacts in series implement an AND condition: both must close to complete the path. Two alternative branches implement OR: either can complete it. A drawing of wires can therefore be translated into an expression whose properties you can work out before building the circuit.

Consider the condition that an output should activate when A is true and either B or C is true. You can draw separate paths for A together with B, and A together with C. Or you can put A before the branch into B and C. The identity AB + AC = A(B + C) tells you that the logical condition is the same. In a simple contact network, the second arrangement can save a contact. The algebra becomes a practical way to reason about hardware, including which differences in the drawing do not change its behavior.

Switching algebra gave engineers a way to calculate what a circuit would do. Communication required another step: how many different messages could a physical system distinguish, and how would that change when its observations were uncertain? Logic alone could not answer that. Shannon would need probability, and a definition of information that applied equally well to a telephone conversation, a telegraph message, or something neither machine had been built to carry.

By February 1939, Shannon was writing to Bush about relationships among transmission time, bandwidth, noise, and distortion. In a later oral history, he identified Ralph Hartley’s work on transmitting information as an important starting point, and recalled pursuing these questions during his Princeton fellowship in 1940–41. The theory was taking shape years before its publication, alongside other work and across changes of institution.

Shannon joined Bell Labs in 1941. His wartime work included problems of gunfire control and secrecy systems. These put uncertainty into practical settings: observations were imperfect, a prediction had to be useful before an event occurred, and a message might be intercepted by someone who should not understand it. They also make an appealing origin story, but Shannon’s recollection resisted a simple sequence in which cryptography produced information theory. He said that information came first in his work, with cryptography subsequently contributing ideas back to it.

The connection becomes clear in his later published paper, Communication Theory of Secrecy Systems. A receiver with the key and an interceptor without it observe the same ciphertext but face different uncertainty about the original message. The paper treats messages, keys, and observations probabilistically. Language redundancy matters because patterns can help an interceptor narrow down possible originals. Think of two puzzles built around the same hidden message: in one, you want the available evidence to identify it; in the other, you want that evidence to remain insufficient for someone lacking the key.

Encrypting a file does not ordinarily protect it from damaged bits, and adding parity does not make it secret. But both problems invite the same precise question: what does an observation reveal? In communication, we arrange for the receiver to learn enough. In secrecy, we arrange for an interceptor to learn too little.

During the war, Shannon also had lunches with Alan Turing. In his 1982 interview, he remembered conversations about brains and computing machines, but rejected the suggestion that an exchange of cryptographic ideas with Turing had supplied his information measure. It is tempting to locate a great idea in a meeting between two great minds. Here, Shannon’s own recollection points instead to the slower work already underway.

By 1948, those questions had become a theory that reached across individual transmission technologies. To see what Shannon had found, we can start with something much smaller than a telephone network: a sender, a receiver, and a channel that gets one bit in ten wrong.

Send a photograph through that channel without protection and the result might be damaged. Send an executable and the consequences could be considerably less entertaining. Now imagine that replacing the channel is not an option. Your transmitter is already on a spacecraft, your power budget is fixed, or the storage device you are reading has started to deteriorate. You can change how information is represented. The underlying medium remains imperfect. What can you do?

Claude Shannon’s 1948 paper, A Mathematical Theory of Communication, established that reliable communication does not require a noiseless channel. For a suitable channel model, information can be transmitted at a fixed rate below its capacity with a decoding error probability that becomes arbitrarily small as code length grows. The surprising part is the fixed rate. You do not have to approach complete silence in order to approach reliability. Shannon also established a boundary: attempting to communicate above capacity cannot achieve the same vanishing error probability.

Repetition gives us a first way to approach that question. Its benefit is easy to calculate, and so is its cost. It also exposes an assumption that will matter throughout the story.

Suppose each transmitted bit is independently flipped with probability 0.1. The probability is the same for zeros and ones. We send 000 for zero and 111 for one, then choose whichever bit appears most often at the receiver. Receiving 101 means we choose one. A single damaged copy is harmless; two damaged copies make the vote wrong. If the bit flip probability is p, there are three ways for exactly two copies to fail, plus one way for all three to fail. The probability of an incorrect decoded bit is therefore

P_error = 3p²(1 − p) + p³ = 3p² − 2p³

At p = 0.1, this is 0.028. We have reduced a ten percent error rate to 2.8 percent without improving the physical channel at all. The channel still damages each transmitted bit with the same probability. What changed is the receiver’s ability to recover from that damage. We paid for the improvement by using three channel bits for every bit of actual payload.

There is an immediate catch. If one disturbance flips all three copies together, majority voting faithfully returns the wrong answer. Imagine a toy channel that either delivers an entire triplet correctly or inverts the entire triplet, with probabilities 0.9 and 0.1. Each individual bit still has a ten percent error probability, but repetition now gives no improvement. The marginal error rate is identical in both examples. The relationship between the errors is different, and that changes the result completely.

Before celebrating three copies of anything, ask what can damage all three. Three storage volumes on one failing machine and three machines with independent failures are different designs. Running the same buggy program three times does not turn it into three independent measurements. Counting copies is easy; understanding how they can fail together is the engineering work.

Shannon made this problem tractable by separating the message’s meaning from the engineering of its transmission. The channel does not need to know whether the bits represent a photograph, a bank balance, or a terrible joke. It needs to preserve the distinction between the messages the sender could have selected. That abstraction lets one theory apply across very different physical media and applications.

Information, in this setting, is related to uncertainty. If a source always produces the same symbol and both parties know this, transmitting it again tells the receiver nothing new. A fair coin toss has two equally likely outcomes and contributes one bit of uncertainty. A heavily biased coin has less uncertainty on average, even though we could still record each outcome using a physical zero or one. Entropy measures this average uncertainty under a specified probability model. It does not measure how interesting, true, or emotionally important a message is.

There is something beautiful in choosing a quantity that survives a change of medium. A sentence can be written on paper, represented by electrical states, transmitted as light, and stored as patterns in a device. Those physical arrangements have very little in common. Yet the receiver can still recover the same sentence. For the communication problem, what must survive is the distinction between that sentence and the alternatives the sender might have chosen. That gives us a way to discuss the journey without developing a separate theory for every material the message passes through.

A small counting example shows why the mathematics feels so well matched to the problem. Suppose one independent choice has eight equally likely possibilities and another has four. Together they have thirty two possibilities: the counts multiply. But specifying the first takes three binary decisions and specifying the second takes two, for a total of five. The logarithm converts the multiplication of possibilities into addition of information. What looks like a mathematical convenience gives engineers an accounting system that behaves sensibly when messages are assembled from independent parts.

Shannon did not need to anticipate a new image format, an unfamiliar language, or the state of a future machine. Once something has a representation, its transmission can be described in terms of possible messages and observations. That is part of the beauty of defining the problem so carefully: the theory remains useful while the devices and applications change almost beyond recognition.

For a deliberately small example, suppose a sensor sends one of four equally likely states. Two bits are enough to name the state: 00, 01, 10, or 11. But this uses every available two bit string. If 00 is damaged into 01, the receiver sees another perfectly legitimate state. Nothing in the received string announces that an error happened. We saved space by leaving no unused representations, and now there is nowhere for damage to reveal itself.

Error correcting codes deliberately leave some representations unused. The valid messages occupy selected positions in a larger space of possible strings. A damaged string can then carry evidence about where it came from. In our repetition code, only 000 and 111 are valid. The received string 001 is one change away from the former and two changes away from the latter. This distance is simply the number of differing positions, usually called Hamming distance. To guarantee correction of up to t bit flips, a code needs minimum distance at least 2t + 1.

A parity bit is the smallest useful step in that direction. Add a bit so that the total number of ones is even. A single flip changes the parity, making the damage detectable, but does not identify its location. Richard Hamming’s 1950 paper went further by combining overlapping parity checks so that their pattern of failures identifies a single incorrect bit. His motivation included computing machines where detecting a fault could stop an unattended calculation. Detection was useful, but correction would let the work continue.

Here is a complete example using four payload bits, 1011. We place them in positions 3, 5, 6, and 7 of a seven bit word. Positions 1, 2, and 4 hold parity bits. The first check covers positions 1, 3, 5, and 7; the second covers 2, 3, 6, and 7; the third covers 4, 5, 6, and 7. Each group must contain an even number of ones. This is a conventional arrangement of the Hamming (7,4) code.

For the transmitted word, the three groups contain two, four, and two ones respectively, so all checks pass. After position 6 flips, the first group still passes. The second and third groups now contain an odd number of ones. Assign the checks weights 1, 2, and 4, then add the weights of the failed checks: 2 + 4 = 6. The receiver flips position 6 back and extracts 1011 from the data positions. It has recovered the original payload without requesting another copy.

The arrangement works because each position participates in a distinct combination of checks. Position 6 participates in the checks weighted 2 and 4, while position 5 participates in those weighted 1 and 4. The failed checks form a short address for the damaged position. This pattern is called the syndrome. The parity bits travel through the same channel and can be damaged too; a single error in one of those positions also produces its identifying syndrome.

Now break the example. Flip positions 2 and 4 together. The failed checks again suggest position 6, so a decoder assuming at most one error will change a third bit and produce the wrong valid word. Our seven bit code promises to correct any single bit error; we have exceeded that promise. An extended Hamming code adds an overall parity bit to support single error correction together with double error detection. That distinction determines whether a decoder can flag damage it cannot repair.

The Hamming example is satisfying because everything fits on a page. But it does not solve our original ten percent channel particularly well. Under independent flips, the probability that a seven bit block contains at least two errors is 1 − 0.9⁷ − 7(0.1)(0.9⁶), approximately 15 percent. Also, four payload bits in seven channel uses is a rate of about 0.571. These numbers are useful reminders that a beautiful construction and a suitable construction are not necessarily the same thing.

For the binary symmetric channel we have been using, capacity is C = 1 − H₂(p) bits per channel use, where H₂(p) = −p log₂ p − (1 − p) log₂(1 − p). At a flip probability of 0.1, capacity is approximately 0.531. A rate of 0.5 lies below it, while the Hamming code’s rate of about 0.571 lies above it. Increasing the length of a suitably chosen family of codes can drive error probability toward zero at the former rate. Repeating the same short Hamming code does not acquire that property.

Imagine our channel carries a million binary symbols each second. A rate of 0.5 gives us half a million payload bits per second before other overheads. Shannon’s result allows reliability to improve while retaining that rate. If we instead repeat each payload bit a thousand times, we are left with only a thousand payload bits per second. Carefully arranged redundancy can accomplish something that simply increasing the number of copies cannot: approach reliable communication without surrendering nearly all the channel’s useful throughput.

A helpful counting intuition is that a long binary string has an enormous number of possible neighbors. Typical noise on our channel changes roughly a tenth of its positions, so a decoder must distinguish the resulting clouds of plausible observations. Well chosen codewords occupy only part of the available space, leaving room for those clouds to be distinguished with high probability. This is a probabilistic argument, not a promise to repair every possible pattern of damage. Shannon’s existence argument also did not supply a generally practical encoder and decoder achieving the limit.

The gap between a code’s existence and its implementation was enormous. A decoder that compared a received block with every possible message could be mathematically legitimate and too expensive to use. Engineers needed enough structure to make encoding and decoding practical without losing the separation between messages that protects them from noise. Much of the history after Shannon is the work of meeting those demands together.

The theorem gives an engineering team both a possibility and a boundary. When a design performs poorly, capacity helps distinguish room for improvement from a demand that cannot be met under the stated conditions. More power, more bandwidth, or a different channel may move the boundary. A better code and decoder can bring a system closer to it.

This gives engineers something more useful than a comparison with last year’s product. An established design may still leave substantial room unused. A capacity calculation tells us how ambitious to be, even though it leaves the choice of circuits, codes, and decoding algorithms unresolved.

It also lets us separate a physical error from a failure to communicate. A bit can flip while the message is recovered correctly, as we saw with the Hamming code. At larger scales, the same distinction lets engineers tolerate ordinary physical mistakes while making errors in the delivered information exceptionally rare. The channel has not become perfect. The representation and recovery process have made its imperfections manageable.

Reed–Solomon codes offer another way to see structured redundancy. In one formulation, k message symbols specify a polynomial of degree less than k over a finite field. The encoder evaluates it at n distinct points and sends those values. Any k correct evaluations determine the polynomial, so extra evaluations provide room for losses. The finite field matters: these are exact algebraic operations in a finite set, rather than approximate curve fitting with floating-point numbers.

A tiny illustration makes the reconstruction tangible. Work modulo 7 and let the message be the two coefficients of f(x) = 2 + 3x. Evaluating at x = 0, 1, 2, 3 gives 2,5,1,4. Suppose the first two values disappear and we retain the values 1 at x = 2 and 4 at x = 3. Their difference gives slope 3 modulo 7; substituting back gives intercept 2. Two surviving values recover both message symbols. We transmitted four symbols, but any two correctly identified survivors would have been enough.

Notice the phrase “correctly identified.” Missing data and incorrect data are different problems. If a receiver knows which symbols are absent or unusable, those positions are erasures. For a conventional Reed–Solomon code with n − k redundant symbols, unique decoding can handle e unknown symbol errors and s erasures when 2e + s ≤ n − k. Locating an unknown error consumes part of the correction budget. This is why a device reporting that it could not read a value can be more useful than one confidently returning the wrong value.

For example, a Reed–Solomon arrangement with ten data symbols and four additional symbols can recover four erasures, or two unknown symbol errors, within that model. In storage, an analogous layout can protect data across devices. But placing all fourteen pieces on equipment that shares the same power failure would defeat the intended protection. The algebra describes recoverability from a specified pattern of loss. Deciding where those pieces live determines which patterns the real world is likely to produce.

Space communications make the trade especially concrete. NASA’s account of Voyager describes the use of Reed–Solomon coding to improve communication performance. A distant spacecraft has limited transmitter power, and changing the receiver’s ability to interpret a weak signal can increase the amount of useful science returned. Redundant bits consume transmission resources, but can still improve useful throughput compared with a less effective scheme at the required reliability. The relevant quantity is successfully recovered information, rather than the number of raw symbols sent.

Convolutional codes generate outputs from the current input and the encoder’s internal state. A decoder follows possible sequences of states, comparing how well each explains what arrived. NASA describes convolutional coding with Viterbi decoding as an established technique in spacecraft communication, including combinations with Reed–Solomon coding. Evidence is spread across time: a doubtful observation can become interpretable when considered alongside the observations around it.

Robert Gallager approached the implementation problem through sparse parity constraints. In his low-density parity-check codes, each check involves relatively few bits. His 1962 paper addressed the gap between the existence of good long codes and the cost of decoding them. The checks let a decoder combine evidence from the channel with relationships among the bits. Our small Hamming example contains the beginnings of that idea, but making it work at scale requires careful structure and algorithms.

In 1993, Claude Berrou, Alain Glavieux, and Punya Thitimajshima introduced turbo codes, combining constituent convolutional codes with a rearrangement of the input sequence. Their decoders exchange probabilistic information over successive iterations. Instead of committing immediately to a zero or one, a receiver keeps track of how confident it is and revises that confidence as other evidence becomes available. The paper reported performance close to the relevant Shannon limit under its tested conditions, forty five years after Shannon had established the theoretical possibility.

At first, this can make digital communication look wasteful. We compress a message to remove redundancy, then add redundancy before sending it. But the redundancy we remove and the redundancy we add serve different purposes. Compression exploits predictability in the source; channel coding creates relationships designed for recovery after transmission. A thousand repeated characters might be represented compactly as a character and a count. Protecting that compact representation with a suitable code can be far more efficient than transmitting the thousand characters and hoping their repetition also protects every other part of the message.

The distinction becomes even clearer if a damaged field is a length, address, or encryption key. A reader can often infer a missing word in a sentence, but arbitrary binary data may offer no such context. And a plausible replacement is not necessarily the original. For software engineers, this is a useful boundary around the word “recovery.” Reconstructing the exact bytes and generating something that looks reasonable are different deliverables. A communication system needs an explicit account of which one it promises.

Successful error control tends to hide its own achievement. When someone sends you a photograph, you do not see which observations were uncertain, which blocks needed correction, or which packets were sent again. You see a photograph. Expecting a document to arrive intact has become ordinary, even though no engineer expects every physical event along its journey to go perfectly.

Think about a voice message from somebody you love. At the application level, what matters is their voice, their timing, perhaps the particular way they say your name. Below that, the recording has a digital representation. A codec controls how much data is needed for an acceptable reconstruction; communication protocols and error control help move the resulting bytes. A damaged transmission and a deliberate reduction in audio fidelity are different events, handled by different parts of the system. Shannon’s work helped give engineers the language to separate such questions and reason about their limits. It did not supply every codec or protocol, but it clarified the problems those inventions had to solve.

The emotional importance of that message never appears in the channel’s equations. I find that part unexpectedly moving. A system capable of preserving arbitrary messages can carry something profoundly personal without having to understand it. The same machinery can deliver a joke, a photograph of a newborn, or the last recording of someone’s voice. Its usefulness depends on preserving what was supplied, including things its designers could never have anticipated or assigned a value to.

Storage offers a related way to think about the achievement. Writing a file and reading it years later is a form of communication across time. The sender and receiver may be the same person, but the physical representation has had to persist between those moments. The practical problem still includes distinguishing the intended data from possible corruption. Recovery information consumes space, just as it consumes transmission resources on a link. In return, the logical object can be more durable than an unprotected arrangement of the underlying physical states would suggest.

These achievements also depended on transistors, manufacturing, algorithms, standards, software, and generations of engineering work. Shannon gave much of that effort a shared mathematical language and limits worth pursuing. Each practical code was an invention in its own right. Knowing what was possible helped make the long search for those inventions worthwhile.

Shannon himself became concerned about what happened when the vocabulary travelled faster than the mathematics. In 1956 he published a short editorial, The Bandwagon, warning that information theory’s popularity was encouraging applications that had not earned their conclusions. He did not rule out usefulness in biology, psychology, or other fields. He argued that moving there required actual hypotheses and experimental tests. Calling a person a decoder does not establish that the person behaves like the decoder in your model.

The warning belongs beside the achievement. Shannon generalized far beyond any particular telephone or telegraph, yet insisted that further generalizations needed justification. A useful abstraction preserves the relationships an argument depends on. An analogy may quietly discard them. For an engineer, the difference becomes apparent when an attractive diagram has to produce a prediction someone can test.

We should also return to the phrase “reliable systems from unreliable components.” In the usual coding model, the noise is in the channel, while the encoder and decoder execute their algorithms correctly. Von Neumann’s Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components examines the harder composition problem in which the logical elements themselves can malfunction. His treatment includes redundant representations and mechanisms for restoring reliable logical behavior under assumptions about component errors.

Our majority vote shows why that extra problem exists. We calculated how often two of three copies are wrong, but quietly trusted the thing counting them. If the voter can fail, it must enter the model too. A correct received word is little comfort if a faulty decoder corrupts it, and a flawless decoding algorithm cannot compensate for a shared software bug that changes the message before encoding. This does not diminish Shannon’s result. It tells us exactly which part of a larger system the result helps us design.

For any actual product, “arbitrarily small” eventually becomes a numerical requirement. We choose a block length, a latency budget, a target error probability, and a decoder that fits available resources. We also choose what happens when recovery fails: request another transmission, discard the block, report an unreadable value, or continue with an explicitly degraded result. Those decisions belong to the application. A spacecraft image, a live voice conversation, and a database log do not necessarily benefit from the same compromise.

Meanwhile, Shannon kept building things. His 1950 mouse and maze apparatus, Theseus, used relay circuitry hidden beneath the maze to control a magnetic mouse. The arrangement makes the apparent location of intelligence slightly deceptive: the mouse is the visible actor, while the machinery producing its behavior is elsewhere. That is a nice companion to the question von Neumann was asking about organized systems. To understand what a thing does, we may need to look beyond the thing we instinctively identify as the agent.

Horgan’s account records another scene from an information theory gathering in Brighton in 1985. Shannon addressed the audience, then took out three balls and juggled. People who had built careers around his ideas queued for autographs. He had helped define their field, but remained the person who wanted to see what he could make things do. The relays, the maze, and the mathematics had all given that curiosity somewhere to go.

Return to the receiver at the beginning. It still cannot inspect the sender’s memory, and the channel still damages what passes through it. Yet it can recover a message it never observed intact, because the sender gave that message enough structure to survive the trip. A photograph arriving from far away does not mean every bit had a safe journey. It means the receiver had enough evidence to put things right.

That is where the beauty of Shannon’s work becomes concrete for me. A theory of possible messages helps preserve particular ones: a scientific measurement, a piece of software, a voice that matters to someone. The mathematics does not need to know their significance to protect them. We usually see only the message that arrived, and that ordinary experience is the achievement. An imperfect world can carry something faithfully.