Finding the error without reading the message

A code that corrects one error can always be decoded by comparing the received word against every codeword and keeping the nearest. That works, and it is the wrong way to do it.

The right way costs three exclusive-ors and involves no search at all, and the reason it works is a single observation about linearity.

The check, as a matrix #

The three parity equations of the previous rung can be written as a matrix over the two-element field, with one row per check and one column per position. A one in row $r$, column $c$ means that position $c$ takes part in check $r$.

Multiplying that matrix by a word — which over this field means, for each row, adding up the bits in the positions the row marks — produces three bits. Call the result the syndrome of the word.

Addition here is arithmetic modulo two, which is what makes “the bits in these positions sum to zero” a linear equation rather than a condition needing cases.

A codeword is exactly a word whose three parity equations balance, so:

The syndrome of a codeword is $000$, and only codewords have syndrome $000$.

That is the definition of the code restated, and it is already useful: checking membership costs three additions rather than a comparison against sixteen candidates.

The observation that does the work #

Suppose a codeword $c$ is sent and arrives as $r = c + e$, where $e$ is the pattern of flipped bits. The syndrome is computed by a linear operation, so

$$\text{syn}(r) = \text{syn}(c + e) = \text{syn}(c) + \text{syn}(e) = 0 + \text{syn}(e) = \text{syn}(e).$$

The syndrome depends on the error and not on the message. Two different codewords corrupted in the same position produce the same three bits.

That is the whole trick, and it is worth sitting with, because it is unusual. The receiver computes a quantity from the received word that contains no information about what was sent — only about what went wrong. The message has been thrown away, deliberately, and what is left is exactly the part needed.

Nothing in the calculation ever recovers the four data bits. It does not need to.

Why the arithmetic is a field and not merely bits #

The step above used linearity twice and it is worth being explicit about where that comes from, because the same move is what makes the last rung of this ladder possible over a much bigger alphabet.

Bits with exclusive-or as addition and the and gate as multiplication form the two-element field: addition and multiplication are defined, both are associative and commutative, multiplication distributes over addition, and the only non-zero element has a reciprocal, namely itself. Everything linear algebra does over the real numbers it does here — matrices, null spaces, dimension, rank — with no changes at all.

A code defined by parity equations is therefore the null space of a matrix, and a null space is a subspace. That is where the linearity comes from, where the coset structure comes from, and where the count of codewords comes from: a subspace cut out by three independent equations in a seven-dimensional space has dimension four, and $2^4 = 16$.

The whole of this essay is the observation that a linear map applied to $c+e$ splits. That is an unremarkable fact about linear maps. What makes it striking is that the domain is messages, the map is a checksum, and the splitting means a checksum can be about an error without being about anything else. The generalisation to a field with more than two elements costs nothing, and buys the last rung of this ladder.

Three bits, seven positions, and one to spare #

Now the design condition from the previous essay pays off.

The columns of the check matrix are the seven non-zero three-bit patterns, each appearing once. If the error is a single flip at position $i$, then $e$ has a one in position $i$ and zeros elsewhere, so the syndrome is the $i$-th column.

Since the columns are all different, the syndrome names the position. There is a table with seven rows, it is a bijection between the seven non-zero syndromes and the seven positions, and looking up a three-bit pattern is not a search in any meaningful sense.

The counting is exactly tight. Three bits have eight values. There are seven positions that could break, plus the case of nothing breaking: eight outcomes. Not one value of the syndrome is wasted, which is another way of seeing that the code is perfect — a spare syndrome value would be a class of words the decoder had no story for.

Checked over the whole space #

The claim “every word is repaired correctly” is checkable in full, and the figures check it.

For each of the one hundred and twenty-eight seven-bit words, the generator computes the syndrome, looks up the position it names, flips that bit, and asserts that the result is a codeword. All one hundred and twenty-eight pass.

That is not a sample and it is not an argument; it is the statement itself, evaluated. The alternative — quoting the theorem that the columns being distinct implies correct decoding — would be quoting a proof of the thing the figure is supposed to be showing.

The partition is the general statement, and the general statement is worth having because it survives when perfection does not. For any linear code, the received words split into classes by syndrome; each class is a shifted copy of the code; and decoding means subtracting the class’s lightest member, its coset leader. What is special about the Hamming code is that every coset leader has weight at most one, so the table is short and the correction is a single flip.

For a code that is not perfect the table is longer and some cosets have several equally light leaders, which is what an undecodable word looks like from the inside.

The cost, counted #

It is worth putting the two decoding procedures side by side, since the whole point of the syndrome is that it replaces one with the other.

By nearest codeword. Compare the received word against each of the sixteen codewords, counting differences: sixteen comparisons of seven bits each, and the count grows with the number of codewords — which grows exponentially with the message length. At a length of 255 with 247 data bits, the number of codewords is larger than the number of atoms in anything.

By syndrome. Three exclusive-ors and one table lookup with seven entries. The work grows with the number of check bits, which is the logarithm of the number of codewords.

The gap between those two is not an optimisation; it is the difference between a procedure that can be run and one that cannot. And the reason it exists is entirely structural: the code is a subspace, so it can be described by the equations it satisfies instead of by the list of its members, and the equations are exponentially shorter than the list.

That is a pattern well beyond coding. A set defined by a short condition can be searched by checking the condition; a set defined by enumeration can only be searched by enumerating. The same distinction is what makes a matrix a workable description of an object far larger than itself.

Hamming’s own numbering #

There is a version of this code in which the syndrome does not need a lookup table at all, and it is how Hamming presented it in 1950.

Number the positions $1$ to $7$. Put the parity bits at positions $1$, $2$ and $4$ — the powers of two — and the data bits in the rest. Let check $k$ cover every position whose number has a one in bit $k$ of its binary numeral.

Then the column belonging to position $i$ is the binary numeral of $i$, and the syndrome comes out as the position number written in binary. Syndrome $101$ means position five. There is no table; the answer is the arithmetic.

That arrangement is the same code as the one drawn here up to a permutation of the positions, and the permutation changes nothing about distance, weights or perfection. It is chosen here in the systematic form — data first, parity after — because that form makes the four message bits visible in the figures, and Hamming’s numbering scatters them.

Both arrangements make the same point in the end, which is that the check matrix’s columns are a numbering of the positions. Hamming’s makes it impossible to miss.

The weighing puzzle underneath #

The structure has a familiar shape once it is stated as a question rather than as a matrix.

Three yes-or-no questions distinguish at most eight possibilities. There are eight possibilities here — seven broken positions and none. So the questions must be chosen so that every possibility gives a different pattern of answers, and each question must be asked of about half the positions.

That is the same counting that governs the pigeonhole principle run in reverse: with fewer than three questions there are more outcomes than answers and two of them must collide, so no scheme with two parity bits can locate an error among seven positions. Three is not merely sufficient; it is necessary.

The same counting appears wherever a fixed number of yes-or-no answers has to separate a fixed number of cases, and it is the reason a check digit over ten symbols can detect an error and not locate one: a single digit has ten values, and locating an error among ten positions each of which could be any of nine wrong values needs far more room than that.

The classical version is the counterfeit-coin puzzle — find the light coin among twelve in three weighings — and the solution has exactly this structure: each coin is assigned a pattern of which weighings it participates in, and the patterns must be distinct. The Hamming code is that puzzle with two outcomes per question instead of three, and its length is $2^3-1$ for the same reason the coin puzzle’s is $(3^3-3)/2$.

How rare an exact fit is #

The counting above came out exactly even — eight syndromes, seven positions and the clean case — and a reader is entitled to wonder how lucky that was. The answer is known completely, and it is one of the more satisfying classifications in the subject.

A code is perfect when the balls of radius $t$ around its codewords fill the whole space with nothing left over: every word is within $t$ of exactly one codeword, and no syndrome value goes unused. The Hamming codes are perfect at $t = 1$, at every length one less than a power of two, for the reason drawn above.

Beyond them the list is almost empty. The whole space is perfect trivially, and so is a code with one word. A repetition code of odd length — send every bit that many times, decode by majority — is perfect, because a word is within half the length of exactly one of the two codewords. And then there are exactly two more.

The binary Golay code packs twelve data bits into twenty-three and corrects three errors. Count its ball: one word at distance nought, twenty-three at distance one, two hundred and fifty-three at distance two, one thousand seven hundred and seventy-one at distance three. That is $1 + 23 + 253 + 1771 = 2048$, which is two to the eleventh, and four thousand and ninety-six codewords times two thousand and forty-eight is exactly two to the twenty-third. Not a bit spare.

The ternary Golay code does the same over a three-symbol alphabet: six data symbols in eleven, correcting two errors. Its ball holds one, plus twenty-two at distance one, plus two hundred and twenty at distance two, and $1 + 22 + 220 = 243$, which is three to the fifth — against seven hundred and twenty-nine codewords in a space of three to the eleventh. Again exact.

And that is the complete list. Tietäväinen and van Lint settled it in 1973: over any finite field, a perfect code has the parameters of a Hamming code, of one of the two Golay codes, of a repetition code of odd length, or of one of the trivial cases. Nothing else fits. Arithmetic identities of the kind above simply do not have other solutions, and a great deal of work went into showing that the near misses are all misses.

Two cautions belong with that. The classification is of parameters, not of codes: there are codes with the Hamming numbers that are not linear at all, and they are perfect too. And perfection is a property worth admiring rather than requiring — almost every code in use is imperfect, spending its spare syndrome values on detecting the errors it cannot repair, which is exactly the trade the extended code below makes.

What it cannot do #

The tightness of the count is also the limitation, and it is the same one the previous essay recorded.

If two bits flip, the syndrome is the sum of two columns, which is some other non-zero column — because the columns are all seven non-zero patterns and the sum of two distinct ones is a third. So a double error produces a perfectly ordinary syndrome naming a perfectly ordinary position, and the decoder flips a third bit, producing a word at distance three from what was sent. It fails silently, confidently, and by making things worse.

There is no defence within this code. Every syndrome value is spoken for, so there is no pattern the decoder could interpret as something is wrong here that cannot be fixed. Buying that requires a spare syndrome, which requires a bit — the extended $[8,4]$ code, whose overall parity check is zero for codewords, one for single errors and zero again for double errors, splitting the cases apart.

That small figure is the honest picture of the failure. The word $110$ is one step from $111$ and two steps from $000$; a decoder seeing it repairs to $111$, and it is right to, given what it knows. Being wrong about a double error is not a defect of the decoding rule. It is what choosing the nearest codeword means when the actual codeword is not the nearest.

Where the code came from #

The origin is worth a paragraph because it is unusually well documented and unusually mundane.

Hamming was at Bell Labs with weekend access to a relay machine that ran unattended. It checked parity on every word, and on a parity error it stopped and moved to the next job in the queue. Coming back on Monday to find that two days of computation had been abandoned on the first bad bit, he asked the obvious question: if the machine can tell that something is wrong, why can it not tell what is wrong?

The answer he produced is the matrix on this page. His account of the reasoning is that one parity bit gives one bit of information about the error, so locating an error among $n$ positions needs about $\log_2 n$ of them, and the question is how to arrange the checks so that each one contributes a full bit. The arrangement that does — each check covering half the positions, and covering them independently — is forced by the counting, which is why the code is essentially unique at each length.

Bell Labs’ patent department held the paper for two years while deciding whether the idea was patentable, which is why Golay’s half-page note of 1949 appeared first. Golay’s paper generalises Hamming’s construction to any prime alphabet and adds the code that carries his name, in a page.

What a burst does to it #

One practical limitation belongs here, because it is the reason the next rung exists.

The failure model on this page is isolated errors: at most one bit wrong in seven. Real channels frequently do something else — a scratch on a disc, a dropout on a radio link, a run of cells failing together — and corrupt a burst of consecutive symbols.

A burst of two consecutive bits is exactly the double error the code mishandles. Nothing about the geometry cares that the two flips are neighbours; the arithmetic sees a syndrome and repairs the wrong bit either way.

The standard defence is interleaving: encode many words, then transmit them column by column so that consecutive transmitted bits belong to different codewords. A burst of length $b$ then contributes at most one error to each of $b$ codewords, and each is repaired independently. That is a genuinely cheap fix and it costs only latency, since a whole block has to be collected before anything can be decoded.

The other defence is to change the alphabet so that a burst of bits becomes a single wrong symbol, which is what the next rung does. A symbol drawn from a field of 256 elements is a byte, and a burst of eight bad bits inside one byte is one error rather than eight — which is why the codes protecting discs and deep-space links work over bytes and not over bits.

Where this ladder goes #

Everything so far has been about bits and flips. The last rung of this ladder changes both.

The alphabet becomes a whole finite field rather than two symbols, a codeword becomes the list of values of a polynomial, and the errors become erasures — symbols known to be missing rather than silently wrong. That change of model turns the correction argument into something much simpler and much stronger: a polynomial of degree under $k$ is determined by any $k$ of its values, so any $n-k$ symbols may be lost, and it does not matter which ones.