Mend An interactive monograph on error-correcting codes

Mend

How a message arrives intact across a channel that corrupts it, by carrying enough structure that the damage can be located and undone.

An interactive monograph in eight sections, with five live figures. Reading time roughly forty minutes. The figures are operable by mouse, touch and keyboard, and the document conforms to WCAG 2.2 AA. Built as a single static page in vanilla HTML, CSS and JavaScript, with no framework and no build step.

Abstract

An error-correcting code adds structured redundancy to a message so that a receiver can detect, and often repair, the corruption a noisy channel introduces. This document develops the subject from its foundations. It begins with the channel and the bluntest possible response to it, the repetition code. It reviews the historical development of the field, from Shannon's non-constructive proof that reliable communication is possible to the constructions that followed. It then treats the principal code families in turn: parity and its two-dimensional arrangement, the Hamming codes and the syndrome that locates a single error, the Reed-Solomon codes that work on symbols and so absorb bursts of damage, and the QR code that prints Reed-Solomon onto a physical surface.

Every figure is interactive. The repetition, parity and Hamming figures implement the actual decoders, and corruption applied by the reader is detected and repaired exactly as the algorithm specifies. The Reed-Solomon and QR figures model the error budget those codes must respect, the genuine capacity rule, while leaving the decoding algebra outside the scope of an explorable; each figure says so.

1Noise and the channel

Every channel that carries data is imperfect. A scratch crosses an optical disc, a wireless signal fades, a cosmic ray flips a bit in a memory chip. In each case a value that left the sender as a zero may reach the receiver as a one. The receiver has no independent record of the truth; all it ever holds is what arrived. If a bit was flipped in transit, the receiver believes the wrong value, and nothing in the bit itself reveals the error.

The only defence is to send more than the message. The sender adds extra bits that carry no new information of their own but are computed from the message according to a fixed rule, so that the bits the receiver gets are constrained: only certain combinations are valid. A combination that the noise has corrupted will, with luck and good design, fail the constraint and so announce itself. That surplus of structure is redundancy, and the whole subject is the study of how to spend it well.

Two questions are asked of every code, and the distinction between them runs through the document. How many errors can the code detect, that is, notice as having occurred? And how many can it correct, that is, repair without a retransmission? Detection is inexpensive. Correction is dear, because to repair an error the receiver must determine not only that something is wrong but precisely what and where. The sections that follow buy increasing amounts of both, for decreasing amounts of redundancy.

2Redundancy: the repetition code

The simplest code that corrects errors is the repetition code. To send a message, the sender transmits it several times; the figure below sends it three. The receiver compares the copies bit by bit and, where they disagree, takes the majority view: if two copies of a bit agree and the third differs, the third is presumed corrupted and overruled. A single error in any one copy is silently outvoted.

Corrupt one bit in a column of the figure and the majority absorbs it. Corrupt two bits in the same column and the vote tips the wrong way; the code fails, and it fails without warning. This is the bargain in its crudest form. The triple repetition code corrects any single error per column, and it pays heavily for the privilege: to send seven bits it transmitted twenty-one, so two thirds of the channel carried nothing new. The ratio of useful bits to transmitted bits, the rate of the code, is one third. Almost no real system uses repetition, because every code in the sections that follow achieves more correction for far less redundancy. What the repetition code provides is the plainest possible statement of what redundancy buys.

3A history of coding theory: a literature review

The codes treated in this document were developed across roughly half a century, and each was a response to a definite limitation of what preceded it. This section traces that development. As in any literature review the emphasis is causal: the concern is which earlier shortcoming each contribution was built to remove.

The field opens with Claude Shannon's 1948 theory of communication [1]. Shannon proved that every noisy channel has a capacity, a rate below which communication with an arbitrarily small error probability is possible, and above which it is not. The result was decisive and, in a particular sense, unsatisfying: the proof was non-constructive. It established that good codes exist without exhibiting one, and it left open the practical question of how to build a code that approached the promised capacity.

The first practical answer came from Richard Hamming, whose 1950 paper [2] was prompted by an ordinary frustration. The relay computer he used rejected a program the moment it detected an error, so a fault entered over a weekend wasted the weekend. Hamming devised codes that did not merely detect a single error but located it exactly, so the machine could repair the fault and continue. Marcel Golay had, the year before, published a short note [3] describing a remarkably efficient code of the same kind. These early codes were defined over individual bits, and they corrected a fixed, small number of bit errors in a block. That was their limitation. Real channels, and storage media in particular, do not corrupt bits independently and one at a time. They produce bursts: a scratch or a dropout ruins a long run of consecutive bits at once, and a code that corrects one or two scattered bit errors is overwhelmed.

The decisive response to burst errors was the family of codes published by Irving Reed and Gustave Solomon in 1960 [4]. Reed-Solomon codes operate not on individual bits but on symbols, typically bytes. A burst of damage that ruins twenty consecutive bits falls within only two or three symbols, and a Reed-Solomon code counts that as two or three errors, not twenty. The codes were ideally suited to storage, but they carried a difficulty of their own: as first published they had no efficient decoding procedure. That gap was closed by Elwyn Berlekamp in 1968 [5] and by James Massey in 1969 [6], whose algorithm made Reed-Solomon decoding fast enough for practical use, and it is their work that put the codes into compact discs, deep-space telemetry and, as section seven describes, the QR code.

One question raised in 1948 still stood: Shannon's capacity remained, in practice, unreached. Robert Gallager's 1962 thesis [7] had described low-density parity-check codes that could approach it, but decoding them was infeasible on the hardware of the time, and the construction was largely forgotten for thirty years. The capacity was finally approached in practice by the turbo codes of Claude Berrou and colleagues in 1993 [8], whose iterative decoder came within a fraction of a decibel of the Shannon limit and astonished the field. The turbo result prompted the rediscovery of Gallager's low-density parity-check codes, which are now standard in modern wireless and storage systems. The arc from Shannon's existence proof to a practical code that nearly meets it took forty-five years.

The last contribution this document draws on is not a new code but a new application of an existing one. The QR code, introduced by the Japanese company Denso Wave in 1994 [9], wrapped Reed-Solomon error correction around a printed two-dimensional pattern, so that a symbol could be read reliably despite the smudges, scratches and torn corners that a printed surface inevitably collects. It is the most visible piece of coding theory in ordinary life, and it is the subject the document closes on.

Return to contents

4Parity and two-dimensional parity

A parity bit is the smallest useful unit of redundancy. Given a block of data bits, count how many of them are ones, and append a single bit chosen so that the total count of ones, data and parity together, is even. The receiver counts the ones in everything it received. An even count is consistent; an odd count means a bit has flipped. Because a single flip always changes the parity of the count, a single error is always detected.

A single parity bit, however, corrects nothing, and it is defeated by two errors, since a second flip restores the count's parity and the damage passes unseen. To locate an error rather than merely notice it takes a little more redundancy, though not much. Arrange the data as a grid and add a parity bit for every row and a parity bit for every column. A single corrupted data bit now breaks the parity of exactly one row and exactly one column, and those two failing lines intersect at one cell, which is the error.

Corrupt one data bit in the figure and decode: a row fails, a column fails, and the cell where they cross is identified and repaired. This is genuine single-error correction, assembled from nothing but parity bits. Corrupt two bits and the scheme strains, as the figure shows: two failing rows and two failing columns leave four candidate intersections, and the code can no longer say which two hold the errors. It still detects the damage; it can no longer place it. Two-dimensional parity is the first appearance of the idea that drives the rest of the document, that the pattern of which checks fail is itself an address.

5Hamming codes and the syndrome

Hamming's codes make the address explicit. The Hamming (7,4) code, the figure's subject, carries four data bits in a seven-bit codeword, the remaining three bits being parity. The placement of those bits is the whole construction. Number the seven positions one to seven. The parity bits occupy the positions that are powers of two, namely one, two and four; the data bits fill the rest.

Each parity bit checks every position whose number, written in binary, includes that parity bit's place. Parity bit one checks every position with an odd number; parity bit two checks positions two, three, six and seven; parity bit four checks positions four through seven. The arrangement works because every number from one to seven has a unique binary representation, so every position is covered by a unique combination of the three checks.

To decode, the receiver recomputes the three checks and writes their pass-or-fail verdicts as a three-bit binary number, the syndrome. If the syndrome is zero, every check passed and the codeword is clean. If it is not zero, it is, read directly as a number, the position of the flipped bit, because only the bit at that position is covered by exactly the set of checks that failed. The receiver flips that bit back, and the single error is gone. Corrupt one bit in the figure and the syndrome names its position outright, with no search.

The figure also shows the code's limit. Corrupt two bits and decode anyway: the syndrome still produces a position, and the decoder confidently flips the wrong bit. The Hamming (7,4) code guarantees correction for a single error only. Adding one further parity bit over the whole codeword yields the scheme known as SECDED, which corrects one error and detects two, and which has guarded computer memory for decades.

6Reed-Solomon and symbol errors

The codes of the previous sections count individual bits. Reed-Solomon codes count symbols, where a symbol is a small group of bits, usually a byte. The data symbols are treated as the values that determine a polynomial, and the codeword consists of additional symbols sampled from that same polynomial. With enough samples the receiver can reconstruct the polynomial even when some samples are wrong, and from the polynomial it recovers the original data.

The accounting is clean. A code with n symbols in all, of which k carry data, devotes n − k symbols to redundancy and can correct up to (n − k) / 2 corrupted symbols, wherever they fall.

The decisive property is that a symbol counts as a single error whether one bit inside it flipped or all of them did. A burst of damage twenty bits long that lands across three neighbouring bytes therefore costs three symbols of the budget, not twenty. The figure makes this concrete: corrupt three adjacent symbols with the burst control, or three scattered symbols individually, and the verdict is the same, because Reed-Solomon does not care where the damage lies, only how many symbols it touched. The figure tracks that symbol budget; the decoding algebra that recovers the actual values, the Berlekamp-Massey algorithm named in the literature review, lies beyond what an explorable can show, but the budget it must respect is exactly the rule the figure enforces.

7QR codes

A QR code is Reed-Solomon error correction made physical. Each black or white square, called a module, is one bit. The three large nested squares in the corners are finder patterns, which let a scanner locate and orient the code from any angle. The remaining modules carry the data and, woven through it, Reed-Solomon parity computed over the whole symbol.

Because the parity is Reed-Solomon, the reasoning of the previous section applies without change. Damage measured in modules is damage measured in symbols, and a scratch that destroys a connected blob of modules costs only the few symbols it overlaps. A QR code lets its creator choose an error-correction level, trading data capacity for resilience: the levels recover roughly seven, fifteen, twenty-five and thirty percent of the symbol. The highest level is the reason a QR code with a company logo stamped over its centre still scans. In the figure, damage some modules, choose a level, and test the result; the corner finder patterns are marked structural and protected from editing, because a scanner that cannot locate them never reaches the stage of decoding at all.

8Conclusion

Error correction begins from the fact that a channel corrupts what it carries and the receiver cannot tell, from a corrupted value alone, that anything is wrong. The remedy is structured redundancy. The repetition code supplied it in the crudest form, at a rate of one third. A parity bit detected a single error for the cost of one bit, and arranged in two dimensions it located one. The Hamming codes made the location explicit, spelling out the address of a flipped bit in the binary syndrome of three overlapping checks. Reed-Solomon codes moved from bits to symbols and so absorbed the bursts that defeat bit-level codes. The QR code printed all of it onto paper.

The literature review placed this progression in its history. Shannon proved that reliable communication was possible without showing how; Hamming gave the first construction; Reed and Solomon answered the burst errors that bit-level codes could not; Berlekamp and Massey made their codes practical to decode; and the turbo and low-density parity-check codes finally reached, after forty-five years, the capacity Shannon had promised. A reader who has followed the argument here holds the question that organises that whole history: how to add the least redundancy that still lets a receiver find the damage and undo it.

Return to contents

RReferences

  1. Shannon, C. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3-4).
  2. Hamming, R. (1950). Error detecting and error correcting codes. Bell System Technical Journal, 29(2).
  3. Golay, M. (1949). Notes on digital coding. Proceedings of the IRE, 37.
  4. Reed, I. and Solomon, G. (1960). Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2).
  5. Berlekamp, E. (1968). Algebraic Coding Theory. McGraw-Hill.
  6. Massey, J. (1969). Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, 15(1).
  7. Gallager, R. (1962). Low-density parity-check codes. IRE Transactions on Information Theory, 8(1).
  8. Berrou, C., Glavieux, A. and Thitimajshima, P. (1993). Near Shannon limit error-correcting coding and decoding: turbo codes. Proceedings of the IEEE International Conference on Communications.
  9. Denso Wave Incorporated (1994). QR Code; later standardised as ISO/IEC 18004.