Rings, fields and codes

The last chapter ended with a question: what other systems of “numbers”, besides remainders modulo a prime, can do all four operations? The answer will come in handy in a problem that at first sight has nothing to do with algebra. Voyager 1 has flown more than twenty-five billion kilometres away. Its transmitter, of about twenty watts, sends a signal that takes almost a day to reach Earth and arrives so faint that it barely stands out from the noise. Some bits flip along the way: a zero was sent, a one was received. You can’t ask again: the answer would arrive two days later, and the probe has long since moved on to the next frame.

A CD player faces the same trouble when the beam hits a scratch, and so does a phone camera reading a QR code splashed with coffee. The receiver has to find the error itself and correct it itself. This chapter is an engineer’s logbook: we’ll build several prototype codes, from a naive one to the one that works in every QR code, and at every step we’ll run into one question: which arithmetic should the calculations be done in? The answer will be rings and fields.

A noisy channel

Let’s start with a simple model. A message is a sequence of bits, and the channel spoils each bit independently of the others with the same probability $p$: a zero turns into a one, or a one into a zero. With $p = 0.01$ a text of a thousand bits has on average ten spoiled. Not many, but if they’re the digits of a bank transfer or the coordinates of a frame, one is enough.

Prototype one, the most naive: repeat each bit three times. Instead of $1$ we send $111$, instead of $0$, $000$. The receiver takes a majority vote: $101$ is read as $1$, $001$ as $0$. It can go wrong only if at least two bits out of three flip.

Exactly two bits out of three flipped. Which of the three survived can be chosen in three ways, and each option has probability $p \cdot p \cdot (1 - p)$: bits are spoiled independently. All three flipped. Example: with $p = 0.01$ we get $P = 3 \cdot 0.0001 - 2 \cdot 0.000001 = 0.000298$, $33$ times fewer errors. With $p = 0.1$ it comes to $0.028$. And with $p$ above a half, voting only does harm: the channel errs more often than not.

The price is three times as much transmission. Engineers measure it like this.

Prototype two is the opposite extreme. To every eight bits add one, so that the number of ones becomes even: to $1011\,0010$ we add $0$, to $1011\,0011$ we add $1$. The rate is $\frac89$, almost lossless. If one bit flips along the way, the parity breaks, and the receiver sees that the byte is spoiled. But it doesn’t know which of the nine bits is to blame, and it won’t notice two errors in one byte at all: the parity comes back.

For a modem that can ask again, that’s enough; for Voyager it isn’t. Compare the prototypes on a picture that has to be transmitted.

Triple repetition is reliable but wasteful. Can errors be corrected more cheaply?

Hamming’s three circles

In the late 1940s Richard Hamming worked at Bell Labs and at weekends set problems for a relay computer. The machine checked itself with codes like parity and, on noticing an error, dropped the problem and moved on to the next. On Monday Hamming would find emptiness instead of an answer. By his own account, at some point he got angry: if the machine can detect an error, why can’t it find where it is and correct it? In 1950 he published codes that can do exactly that.

The best known of them is conveniently drawn with three overlapping circles. The circles divide the plane into seven regions, and we put a bit in each. The four message bits occupy the regions where circles overlap. The three check bits occupy the regions belonging to only one circle, and are chosen so that each circle contains an even number of ones.

Number the regions from $1$ to $7$ so that the binary expansion of the number says which circles the region lies in: the lowest digit is circle $A$, the middle one circle $B$, the highest circle $C$. Region $5 = 101_2$ lies in circles $A$ and $C$ but not $B$; region $7 = 111_2$ is in the centre, in all three. The check bits are in places $1$, $2$ and $4$, the message bits in places $3$, $5$, $6$ and $7$.

The idea: each bit lies in its own unique set of circles, and an error in it breaks the parity in exactly that set.

Three circles divide the plane into seven regions inside the circles, one for each non-empty set of circles: $A$, $B$, $C$, $AB$, $AC$, $BC$, $ABC$. There are exactly seven different sets, and each region got its own. The sender chooses the check bits $1$, $2$, $4$. This can always be done, and in only one way: each of them lies in only one circle and evens out the parity of its circle without touching the others. Suppose one bit flipped along the way. In each circle that contains its region, the number of ones changed by one and became odd. Nothing changed in the other circles. So exactly the circles containing the spoiled bit are “broken”. Different regions lie in different sets of circles, so the region can be recovered uniquely from the set of broken circles. If there was no error, there are no broken circles, and the empty set corresponds to no region, so this case can’t be confused with any other either. The receiver checks three circles, finds the region and flips its bit back. The number of the spoiled bit is simply the binary number made of the broken circles: $C$ gives $4$, $B$ gives $2$, $A$ gives $1$. Move the error to another region: other circles light up.

Circles are good for the eye, but for a computer the same thing is written as a matrix. Bits add like remainders modulo $2$: $1 + 1 = 0$, which is the “exclusive or” (XOR) operation. Checking a circle’s parity is the sum of its bits modulo $2$. Three checks are three rows of a matrix whose columns are the position numbers in binary.

The syndrome: three numbers, $0$ or $1$, saying whether circle $C$, $B$, $A$ is broken. Read as a binary number, it equals the number of the spoiled bit, and $000$ means there are no errors. The parity-check matrix $H$. Its $j$th column is the binary expansion of the number $j$: row $C$ marks positions $4$–$7$, row $B$ positions $2, 3, 6, 7$, row $A$ the odd positions. The received word: a column of seven bits. Example: the message $1011$ is encoded as the word $0110011$ (check: each circle has an even number of ones). Suppose the sixth bit got spoiled, and $\mathbf r = 0110001$ arrived. Row $C$: bits $4$–$7$, that is, $0 + 0 + 0 + 1 = 1$. Row $B$: bits $2, 3, 6, 7$: $1 + 1 + 0 + 1 = 1$. Row $A$: bits $1, 3, 5, 7$: $0 + 1 + 0 + 1 = 0$. The syndrome is $110_2 = 6$.

Why does the column give the number? For a codeword $\mathbf c$ all the checks are even, $H\mathbf c = \mathbf 0$. If bit $j$ is spoiled, then $\mathbf r = \mathbf c + \mathbf e_j$, where $\mathbf e_j$ has a one only in place $j$, and $H\mathbf r = H\mathbf c + H\mathbf e_j = H\mathbf e_j$, which is the $j$th column. The syndrome doesn’t depend on the message, only on the error.

The word $1110101$ arrived (bits one to seven). It’s known that there’s at most one error. In which position is the error? If there’s none, answer $0$.

Row $C$ (bits $4$–$7$): $0 + 1 + 0 + 1 = 0$. Row $B$ (bits $2, 3, 6, 7$): $1 + 1 + 0 + 1 = 1$. Row $A$ (bits $1, 3, 5, 7$): $1 + 1 + 1 + 1 = 0$. The syndrome is $010_2 = 2$: the second bit, a check bit, is spoiled. The corrected word is $1010101$, and the message (bits $3, 5, 6, 7$) is $1101$.

How many errors a code can take

Why does the Hamming code correct one error, and triple repetition one out of three? And how do you build a code that corrects more? The answer comes from a geometry in which the distance between words is measured by the number of mismatches.

The idea: draw a “ball” round each codeword, all the words that can be reached by $t$ errors, and see that the balls don’t overlap. We’ll show it on triple repetition; in general the argument is the same.

Words of length $3$ are the vertices of a cube, and an edge joins words that differ in one bit. The Hamming distance is the smallest number of edges between vertices: each step along an edge fixes one mismatch. For any words $u$, $v$, $w$ the triangle inequality holds: $d(u, w) \le d(u, v) + d(v, w)$. In each position where $u$ and $w$ differ, $v$ differs from at least one of them. The triple-repetition codewords $000$ and $111$ stand in opposite corners of the cube, $d = 3$. Draw a ball of radius $t = 1$ round each: the word itself and its three neighbours. The balls don’t overlap: if a word $w$ were within $t$ of both codewords, then by the triangle inequality they’d be at most $2t < d$ apart. Here $1 + 1 = 2 < 3$. The balls round $000$ and $111$ split the cube in half. If there are at most $t$ errors, the received word lies in the ball of the word sent and in no other, so the nearest codeword is the one sent. And fewer than $d$ errors can’t turn one codeword into another, so they’re always visible: the received word isn’t a codeword.

The minimum distance of the Hamming code is $3$. The sum of two codewords modulo $2$ is again a codeword (parities add), and the number of ones in it is the distance between the originals. A word with a single one isn’t a codeword: any region lies in at least one circle and breaks its parity. A word with two ones in different regions isn’t a codeword either: the regions have different sets of circles, and there’s a circle containing exactly one of them. But $1110000$ is a codeword: circles $A$ and $B$ have two ones each, $C$ none. By the theorem the Hamming code corrects one error and detects two.

The Hamming code wastes not a single syndrome: the decoder understands each of the $128$ possible words unambiguously. Such codes are called perfect.

Hamming’s prototype is good against single errors. But a scratch on a disc destroys hundreds of bits in a row, and a single block of seven will contain many errors at once. The way out is to count not in bits but in bytes: if all eight bits of a byte are spoiled, it’s one error in a “letter” out of $256$ possible. For this we need an arithmetic over an alphabet of $256$ symbols in which, as in $\mathbb Z_2$, you can add, subtract, multiply and divide: all the linear algebra of codes rests on division. Remainders modulo $256$ won’t do: $2 \cdot 128 = 256 \equiv 0$, and you can’t divide by $2$. What arithmetics like that exist at all?

Where you can compute

Integers, remainders modulo $n$, polynomials, square matrices: all of them have addition and multiplication, and almost all the familiar rules hold. What they have in common is described by one definition.

Examples of rings are $\mathbb Z$, $\mathbb Z_n$, and polynomials with real coefficients. $2 \times 2$ matrices form a ring too, but a non-commutative one: as we saw in the chapter on matrices, $AB$ and $BA$ usually differ. Division isn’t part of the definition. In $\mathbb Z$ you can’t divide $1$ by $2$, and in $\mathbb Z_6$ something happens that never happens with numbers: $2 \cdot 3 = 0$, although neither $2$ nor $3$ is zero.

Where there are zero divisors, familiar reasoning breaks down. From $ab = 0$ it no longer follows that one of the factors is zero, and so equations can’t be solved by factorising.

How many solutions does the equation $x^2 = 1$ have in $\mathbb Z_8$?

Two: $x = 1$ and $x = 7$ Four One Eight

$1^2 = 1$, $3^2 = 9 \equiv 1$, $5^2 = 25 \equiv 1$, $7^2 = 49 \equiv 1$. An equation of degree two with four roots! Factorising $(x - 1)(x + 1) = 0$ doesn’t help: at $x = 3$ the factors are $2$ and $4$, both non-zero, and their product is $8 \equiv 0$. $\mathbb Z_8$ has zero divisors, and the rule “a product is zero only if a factor is zero” doesn’t work.

Systems in which you can divide by everything but zero have a name of their own.

Fields include $\mathbb Q$, $\mathbb R$, $\mathbb C$ and, as we found out in the last chapter, $\mathbb Z_p$ for a prime $p$. The ring $\mathbb Z$ isn’t a field: $2$ has no integer inverse. In a field all of school algebra works: proportions, the quadratic formula (if square roots exist and $2 \ne 0$), Gaussian elimination for systems, interpolation. It all rests on division and on the following property.

Compute $\frac35$ in the field $\mathbb Z_7$, as a number from $0$ to $6$.

Dividing by $5$ means multiplying by $5^{-1}$. Since $5 \cdot 3 = 15 \equiv 1 \pmod 7$, $5^{-1} = 3$, and $\frac35 = 3 \cdot 3 = 9 \equiv 2$. Check: $5 \cdot 2 = 10 \equiv 3$.

A field of four elements

For bytes we need a field of $256$ elements, and $\mathbb Z_{256}$ isn’t a field. Let’s first try to build a field of four elements, where $\mathbb Z_4$ won’t do either: $2 \cdot 2 = 0$. The hint comes from numbers we already know how to build: $\mathbb C$ was obtained from $\mathbb R$ by adding a root of the equation $x^2 + 1 = 0$, which has no real roots (chapter 15). In the same way the square root of two can be added to $\mathbb Q$.

Now the same thing in $\mathbb Z_2$. The polynomial $x^2 + x + 1$ has no roots there: at $x = 0$ it equals $1$, and at $x = 1$ also $1 + 1 + 1 = 3 \equiv 1$. Add an imaginary root $\alpha$ for which $\alpha^2 + \alpha + 1 = 0$, that is, $\alpha^2 = \alpha + 1$: in $\mathbb Z_2$ minus and plus are the same. The elements of the new field have the form $a + b\alpha$ with $a, b \in \{0, 1\}$; there are four of them: $0$, $1$, $\alpha$, $\alpha + 1$. They add coordinatewise, and multiply like polynomials, after which $\alpha^2$ is replaced by $\alpha + 1$.

For example, $\alpha(\alpha + 1) = \alpha^2 + \alpha = (\alpha + 1) + \alpha = 1$, because $\alpha + \alpha = 2\alpha = 0$. So $\alpha$ and $\alpha + 1$ are inverses of each other, and $1$ is its own inverse: every non-zero element is invertible. There are no zeros outside the zero row and column. This is a field of four elements, and it’s built quite differently from $\mathbb Z_4$: in it $1 + 1 = 0$.

Will any polynomial do for this trick? No: if the polynomial factors, an imaginary root of one of the factors will produce zero divisors. We need polynomials that don’t factor.

From the polynomial $x^3 + x + 1$, irreducible over $\mathbb Z_2$ (it has no roots, and a polynomial of degree three that factors has a factor of degree one), we get $GF(8)$. From $x^4 + x + 1$, $GF(16)$. Switch the table above to them: for any choice each non-zero row is a permutation of the non-zero elements.

Is there a field of $6$ elements?

Yes, it’s $\mathbb Z_6$ No Yes, but it’s built differently from $\mathbb Z_6$

The number of elements of a finite field is a prime power, and $6 = 2 \cdot 3$ isn’t a prime power. There are fields of $2, 3, 4, 5, 7, 8, 9$ elements, but none of $6$ or $10$.

The converse is true too: for every prime $p$ and natural number $n$ a field of $p^n$ elements exists. For small $n$ an irreducible polynomial is easy to find by trial, as we found $x^2 + x + 1$, and in general another route helps.

The proof: the roots of the polynomial $x^{p^n} - x$

The idea: build a field in which the polynomial $x^q - x$, where $q = p^n$, splits into factors of degree one, and see that its roots themselves form a field, and that there are exactly $q$ of them.

A root can always be added. Let $F$ be a field and $g$ a polynomial over it of degree at least $1$. Take an irreducible factor $h$ of $g$. As in the theorem on a field from polynomials modulo an irreducible one (its proof works over any field $F$), the remainders on division by $h$ form a field containing $F$. In it the remainder of the polynomial $x$ is a root of $h$, and so of $g$. Split off a factor of degree one from $g$ and repeat with the quotient. After finitely many steps we get a field $L \supset \mathbb Z_p$ in which $x^q - x$ splits into $q$ factors of degree one.

The roots form a field. In a field of characteristic $p$, $(a + b)^p = a^p + b^p$: by the binomial theorem the other terms contain the coefficients $\binom pk$ for $0 < k < p$, and these are divisible by $p$, since the numerator $p!$ has the factor $p$ and the denominator $k!(p - k)!$ doesn’t. Repeating $n$ times, we get $(a + b)^q = a^q + b^q$. So if $a^q = a$ and $b^q = b$, then also $(a + b)^q = a + b$, $(ab)^q = ab$, $(-a)^q = -a$ (for $p = 2$ this is the same as $a$, since $-1 = 1$), and $(a^{-1})^q = a^{-1}$. The roots of $x^q - x$ are closed under all four operations: they form a field.

There are exactly $q$ of them. Let $r$ be a root. Then $x^q - x = (x - r)^q + r^q - x = (x - r)^q - (x - r) = (x - r)\bigl((x - r)^{q-1} - 1\bigr)$. The second factor at $x = r$ equals $-1 \ne 0$, so $r$ is a simple root, not a multiple one. A polynomial of degree $q$ has split into $q$ factors of degree one, and all the roots are distinct: there are $q$ of them. That’s the field of $p^n$ elements.

The non-zero elements of a finite field form a group under multiplication, and it’s always cyclic: there’s an element $g$ whose powers run through all the non-zero elements. The proof repeats word for word the proof of the existence of a primitive root from the last chapter. Only three things were used there: that the order of an element divides the number of non-zero elements, that a polynomial of degree $d$ over a field has at most $d$ roots (we’ll prove this in the next section for any field), and a count with Euler’s function. In $GF(4)$ the generator is $\alpha$: $\alpha^1 = \alpha$, $\alpha^2 = \alpha + 1$, $\alpha^3 = 1$. That’s why in chips multiplication in a finite field is often done by adding exponents from a table of logarithms, just as people multiplied using Napier’s tables.

A code made of polynomials

Now we have a field in which a “letter” is a byte. How do we build a code from it? In 1960 Irving Reed and Gustave Solomon of MIT’s Lincoln Laboratory published a five-page paper, Polynomial Codes over Certain Finite Fields, with an idea we’ve already seen in the chapter on polynomials: a polynomial of degree less than $k$ is recovered uniquely from its values at any $k$ points.

Declare a message of $k$ symbols of the field to be the coefficients of a polynomial $f$ of degree less than $k$. Send not the coefficients but the values of $f$ at $n > k$ distinct points of the field. The extra $n - k$ values are a reserve: even if some of them get spoiled, the polynomial passing through most of the received points can be found.

A polynomial over a finite field, into which the message is packed. The message: $k$ elements of the field, the coefficients of the polynomial. Distinct points of the field at which $f$ is evaluated. There are $n$ of them, so $n$ is at most the number of elements of the field; in the field $GF(256)$ usually $n = 255$. Example in the field $\mathbb Z_{11}$: the message $(3, 1, 4)$ is the polynomial $f(x) = 3 + x + 4x^2$. Its values at the points $0, 1, \dots, 6$: $3, 8, 10, 9, 5, 9, 10$ (for example, $f(2) = 3 + 2 + 16 = 21 \equiv 10$). This is a codeword of length $n = 7$ for a message of length $k = 3$; it withstands two errors.

Why two? It all rests on a theorem we proved for real polynomials in chapter 14. Over a field it holds just the same, while without a field it breaks: in $\mathbb Z_8$, as we saw, $x^2 - 1$ has four roots.

In our example $n = 7$, $k = 3$, and $2t \le 4$: two errors. You can’t squeeze out more: for any code turning $k$ symbols into $n$, the distance is at most $n - k + 1$ (this is called the Singleton bound), so Reed–Solomon codes spend their check symbols optimally.

The decoder in this picture works by brute force: it goes through triples of points, draws the polynomial through each by Lagrange’s formula, and looks for one that passes through at least five points. For $n = 7$ there are only $35$ triples, but for $n = 255$ brute force is hopeless. A fast decoding algorithm was found by Elwyn Berlekamp in 1968, and it’s what made Reed–Solomon codes practical. Note that Lagrange’s formula divides by the differences of the points $x_i - x_j$: here too you can’t do without a field.

It’s hard to list everywhere this code works. On compact discs (1982) two Reed–Solomon codes over $GF(256)$ are interleaved so that a scratch that destroys several thousand bits in a row turns into scattered errors in different codewords, and they’re all corrected. In a QR code you can choose the error-correction level: $L$, $M$, $Q$ or $H$ recover roughly $7$, $15$, $25$ or $30$ per cent of the codewords, which is why a stained or torn code can still be read. A Reed–Solomon code paired with a convolutional code protects the transmissions of the Voyagers, launched in 1977. It also works in DVDs, Blu-ray, digital television and RAID 6 disk arrays.

The CCSDS space communication standard uses a Reed–Solomon code over $GF(256)$ that turns $223$ message bytes into $255$ bytes. How many spoiled bytes in each block does it correct for certain?

$n = 255$, $k = 223$, and there are $n - k = 32$ check bytes. The condition $2t \le 32$ gives $t = 16$. If all eight bits of each of the sixteen spoiled bytes flipped, that’s $128$ bit errors in one block, and all of them are corrected.

Practise encoding and decoding the Hamming code: computing the check bits, finding the syndrome and correcting the error.

Where next

We built fields by adding roots: the square root of two to $\mathbb Q$, the imaginary unit to $\mathbb R$, a root of the polynomial $x^2 + x + 1$ to $\mathbb Z_2$. The quadratic formula also adds a root, a square one. Cardano’s formula for the cubic adds square and cube roots, Ferrari’s formula for the quartic a few more. But for an equation of degree five there’s no formula in radicals. Why is there no formula for the quintic? The answer was found by the same Galois whose name the finite fields bear: he studied the symmetries of the roots and the field extensions these roots generate. That’s the subject of the next chapter.