Error Correction

The noisy channel

Up to this point we have assumed that our messages travel through an ideal, antiseptic universe: every character sent off by the transmitter arrived clean and untouched. The real physical world is far harsher and more restless. Whether the signal runs through a copper wire crossed by heat, along a ray of light in an optical fibre, through the air as a radio wave, or waits patiently for years on the surface of a hard disc, it is forever stalked by imperfections. This lesson looks that degradation straight in the eye: not as a regrettable accident, but as a fundamental law of nature that can be measured, mastered and, in the end, overcome.

We call a channel any physical medium that carries bits from one point in space to another, or from one moment in time to another: a network cable, a Wi-Fi channel, a tiny cell of RAM, even a scrap of silicon inside a chip. No channel in the universe works perfectly. Now and then a fluctuation of voltage or a stray interference makes a 0 read as 1, or a 1 as 0.

The simplest and most intuitive model for such an imperfect channel is called the binary symmetric channel: we imagine that every bit sent has, quite independently of its neighbours, a small probability p of being flipped along the way. That probability is called the error rate. It is usually small — one per cent (1%), say — but the messages of digital life hold millions or billions of bits, so the small mistakes inevitably add up. At a rate of one per cent, a modest text of a thousand bits will reach its destination with some ten bits damaged, quite enough to turn the words into a jumble hard to recognise.

In the interactive example above, every character is coded on 5 bits out of an alphabet of 32 signs (the ordinary letters, a few punctuation marks and the space). Flipping any bit turns the original character into another valid letter of the alphabet, so that the effect of the noise can be read with the naked eye in the text received.

Detecting an error

What is the simplest and cheapest trick by which we can find out whether a message was damaged on the way? The answer is to add a single watchman bit at the end of the message, called the parity bit. Its value is chosen so that the total number of 1s in the whole group is always an even number. That extra bit adds nothing new about the content; it works as a mathematical guarantee, like a wax seal pressed on a letter.

If a single bit is struck by noise and changes its value along the route, the total number of 1s becomes odd. The receiver counts the 1s, notices the irregularity and raises the alarm at once: something is broken. Yet this simple mechanism has two great limits: first, it tells us that there is an error but cannot tell us where it lies (every position remains equally suspect); second, if the noise unluckily strikes two bits at once, the number of 1s is even again and the double error slips by completely unnoticed. The parity bit is therefore a modest watchman: it detects only an odd number of mistakes, and it can repair nothing by itself.

The distance between words

To move from mere detection to the automatic repair of mistakes, we need an intuitive geometric picture. Out of all the theoretical combinations of bits that can be written, we shall agree to declare only a small part of them valid. Such an authorised string is called a code word. All the other combinations are considered illegal and should never turn up in a normal transmission. If the receiver gets an illegal combination, he knows an error has occurred; and if the valid words were set far enough apart from one another, he can guess without fail where the message set out from.

How “far apart” are two strings of bits? The number of positions in which two sequences differ is called the Hamming distance. A single error on the wire moves the received word to distance 1 from the original; two errors push it to distance 2, and so on.

Think of the valid words as islands in an ocean of bits. If any two islands lie at least 3 steps apart, then a boat blown off course by a single mistake (1 step) will still be much closer to the island it left than to any other. The receiver need do nothing but pick the nearest valid island, and he will land on exactly the original message. That minimum distance d between the words of a code dictates its whole protective power: we can always detect d−1 errors and fully repair half that number.

The most naive and direct way of obtaining a distance of 3 steps is threefold repetition: instead of a single bit we send every bit three times (0 becomes 000 and 1 becomes 111). If a bit flips on the way and we receive 101, we take a simple democratic vote: we have two 1s and a single 0, so we decide the message was 1. Correction by vote handles any isolated error admirably.

The price paid for repetition is enormous, though: we add two guard bits for every useful bit, which triples the length of the whole message and clogs the network. The brilliant question the engineers asked themselves was this: could we not build a safety net just as strong, but with far fewer bits to spare?

The Hamming code

The answer came in 1950 from the mathematician Richard Hamming at Bell Labs. He showed that in a packet of 7 bits we can carry 4 bits of useful data, impeccably protected by only 3 checking bits. Instead of mechanically repeating the message bits, Hamming wove the checks together brilliantly: each of the three control bits watches over a different group of positions, so that the combination of the three control results (0 or 1), read as a binary number, points directly at the position number of the damaged bit.

How does this magic work? The first check watches the positions whose binary spelling ends in 1 (positions 1, 3, 5, 7); the second watches the positions with a 1 in the second binary place (positions 2, 3, 6, 7); and the third looks at the positions with a 1 in the third place (positions 4, 5, 6, 7). If some position — say position 5 — is damaged by noise, it will set off the alarm in exactly the first and the third check (because 5 is written 101 in binary). Reading the three alarms as a number, we get 101, that is 5. We have pointed a finger at the culprit and can flip it back on the spot. You will recognise here the game of questions from our first lesson: three binary yes-or-no questions tell perfectly between the eight possible situations (the state “no errors” plus the seven positions that might be faulty).

The saving is spectacular: we no longer add eight guard bits to four useful ones (as the repetition code demanded), but only three checking bits for four bits of message. If two errors occur on the wire at once, however, the checks fool one another and point to a third, innocent position, and the automatic correction will damage one more bit. The classical Hamming code is designed to correct a single error with a guarantee, but its principle opens the door to modern codes able to repair hundreds of errors at once.

Redundancy taken out and redundancy put in

Set side by side, the last two lessons seem to contradict each other: in the second we worked hard to clean the redundancy out of a message to make it as short and lithe as possible, and now, in the third, we willingly add extra bits to lengthen the message again. Is this one step forward and one step back? Not in the least. The secret lies in the quality and the structure of the redundancy used.

The natural redundancy of a language is chaotic and inefficient: it exists only because certain letters happen to turn up often, without following any plan of protection. It can sometimes help us guess a smudged letter, but it cannot tell us with mathematical precision where the mistake occurred, nor does it guarantee that we can repair it. The redundancy added by a correcting code, by contrast, is a masterpiece of engineering: every bit added has a precise mission, answers a specific question and cooperates with the others to locate the error.

That is why the order of operations in a computer is sacred: first we compress the data to remove all the useless waste and chaotic ballast, and only then do we protect it by adding a fine armour of controlled redundancy. A file cleverly compressed and then protected by a correcting code is at once slimmer and incomparably more weatherproof than the raw original. The two lessons do not clash; they are the two arms of the same noble discipline: the art of deciding what in a message is worth paying for.

The capacity of the channel

One last, grand question remains: how far can we push this efficiency? Every bit devoted to checking is a bit that carries no message of its own. Hence an essential ratio, called the rate of the code: the ratio between the number of useful bits and the total number of bits sent on the wire. The threefold repetition code has a modest rate of 1/3 (only 33% is useful message), while the Hamming code reaches 4/7 (over 57%). Can we transmit messages that are almost 100% useful and still be fully sheltered from noise?

The answer Claude Shannon gave in 1948 astonished the whole scientific community. He proved that every communication channel possesses a precise barrier called its capacity. If our rate of transmission is below that capacity, there are always mathematical codes that can guarantee a transmission practically free of errors, however long the message. If, on the other hand, we try to transmit above the capacity of the channel, no human mind can escape errors. Physical noise does not demand an infinite sacrifice of us; it levies a fixed, measurable toll, equal to the entropy of the error.

Look at the interactive graph: capacity falls steadily until it reaches zero at an error rate of 50%. Why exactly at 50%? Because when every bit has an equal chance of being right or inverted, the channel becomes a simple coin tossed in the air: the output has no connection left with the input, and the information has evaporated completely. If the rate goes above 50%, capacity curiously begins to rise again: a wire that inverts almost everything is in fact an excellent channel — we need only invert our convention at the other end.

Shannon’s theorem proved that these ideal codes certainly exist, but without leaving a mechanical recipe for building them. Scientists laboured for more than half a century to design them, and the modern codes that today equip 5G telephones, the transmissions of space probes at the edge of the solar system and the hard discs in data centres reach 99% of that supreme theoretical limit.