Coding Theory

When data travels from one place to another, parts of it get damaged along the way. A radio signal gets disrupted, a scratch damages a DVD, a memory chip flips a single bit. Coding theory is the branch of mathematics that deals with exactly this problem. Its basic idea: you deliberately write down the data a bit longer than necessary and add extra check positions. From these additional positions, the receiver can later calculate whether something is missing, and often even what was originally there. So the goal is not secrecy, but reliability.

Why every radio connection depends on it

No real transmission path is free of interference. In mobile communications, building walls reflect the signal; with satellites, the distance is simply too great. Without error correction, a device would have to request every damaged data packet again. With a poor connection, almost nothing would then get through at all.

With good codes, a certain proportion of errors can instead be repaired directly on the spot. This allows faster connections at the same transmission power. A famous example is the Voyager probes: their signals arrived extremely weak, but were protected by codes in such a way that the images could still be reconstructed. Requesting a resend over hours of signal travel time would not have been practical at all.

It’s important to distinguish this from cryptography. Cryptography protects data from being read by unauthorized parties. Coding theory protects it from becoming unreadable by chance. Both are usually used together, but they have completely different goals.

Redundancy, distance, and check positions

The simplest method is repetition: you send each bit three times. If “101” arrives, a one was probably originally meant, since two out of three positions say so. This approach works, but is wasteful, since it triples the amount of data. Coding theory looks for methods that achieve the same level of security with far fewer extra positions.

The central concept here is the distance between two valid codewords. You define which bit sequences are valid at all, and choose them so that any two of them differ in several positions. If an invalid sequence arrives, the receiver looks for the nearest valid codeword. The greater the distance, the more simultaneous errors can still be corrected unambiguously.

You can think of this like the vocabulary of a language. If all words sound very similar, a mishearing immediately leads to a different word. If, on the other hand, the words sound clearly different, you can still recognize the intended word even amid background noise. Well-known families of such codes are called Hamming code, Reed-Solomon code, and LDPC code.

From the corner of a QR code to the data center

A QR code on a poster often still works even if part of it is covered or dirty. Behind this is a Reed-Solomon code that reserves part of the area for check information. The same principle allows CDs with small scratches to be played back without errors.

In data centers, related methods safeguard large amounts of data. Instead of storing each file multiple times, it is distributed across many hard drives using so-called erasure codes, with check blocks added alongside. If a drive fails, its contents are calculated from the remaining ones. Compared to full copies, this saves a great deal of storage space.

In tech news, error-correcting codes mainly come up in connection with two topics: new generations of mobile communications and quantum computers. The computing components of the latter are extremely prone to interference, which is why thousands of physical components there must carry a single reliable computing bit. A typical misconception, by the way, is confusing coding theory with data compression: compression removes redundancy, while error correction deliberately adds it back in.