Linear codes

How can a CD still be read out even if some scratches adorn its back? How can a rover, which is supposed to make investigations on the moon, transmit its data to the base station on earth, even if there are surely some errors in the transmission? How can I efficiently store my data on three hard disks so that if one of them fails, all the data can still be reconstructed?

Coding theory deals with these and similar questions. The basic idea is the following: Given a finite alphabet F (e.g. F={0,1} in the binary case) and a code length n. The data to be encoded are now always stored/transmitted in blocks of length n. However, such a block b actually only contains the information of a smaller number k\leq n of F-bits. That is, during encoding always one word of length k over the alphabet F is converted into one word of length n over the same alphabet. In this process, l\coloneqq n-k F bits are redundant. Mathematically speaking, this encoding is nothing more than an injective mapping \iota\colon F^k\to F^n. Its image C\coloneqq\mathrm{im}(\iota) is called a (n,k)code (n is called the length of C and k the dimension).

Now the following can happen: In the block b of length n, some symbols are changed (by noise in the channel or the like). Let us say these are m symbols. Thus a new disturbed block b' is created. Can the original information still be reconstructed? For this we define the Hamming distance of two codewords c,d\in C as d_{\mathrm H}(c,d)=|{i\in{1,\ldots,n}\,|\,c_i\neq d_i}| (where c=(c_1,\ldots,c_n) and d=(d_1,\ldots,d_n) with c_i,d_i\in F). The idea now is to modify the perturbed block b' to the codeword in C that is closest to this block measured in Hamming distance. But is this codeword unique at all? In general not!

Therefore, in order to recognize “too disturbed” blocks b' as such and to always be able to reconstruct reconstructable blocks unambiguously, a ball B_r(c)\coloneqq{d\in C\,|\, d_{\mathrm H}(c,d)\leq r} of radius r is drawn around each admissible codeword c\in C at the Hamming distance, so that no two of these balls overlap: B_r(c)\cap B_r(d)=\emptyset for c,d\in C different. Now, if b' lies in one of these balls, it is reconstructed to the codeword b=c. In this way b is always unique due to the above condition.

But how is the radius r to be chosen here? We want B_r(c) and B_r(d) not to intersect for c\neq d from C. However, this is true if and only if r\lt d_{\mathrm{H}}(c,d)/2. This condition must now be satisfied for all c and d. Thus, if we set d(C)\coloneqq\min{d_{\mathrm{H}}(c,d)\,|\,c,d\in C,\, c\neq d} (the minimum distance from C), then r\coloneqq\left\lfloor\frac{d(C)-1}{2}\right\rfloor is the best possible radius. Thus, the parameter d\coloneqq d(C) determines the correction radius. In this situation C is also called a (n,k,d) code.


Hamming codes

The Hamming codes are binary linear codes C of length n=2^l-1, dimension k=n-l and with minimum distance d=3 developed by mathematician Richard Wesley Hamming (here l\geq 2 is a parameter to be chosen which exactly measures the redundancy of the code). The word linear here means that our alphabet F here is a body, namely the body \mathrm{GF}(2) with two elements 0 and 1 (\mathrm{GF}(2) stands for Galois field after the mathematician Évariste Galois), and C\subseteq\mathrm{GF}(2)^n is a linear subspace of the vector space V=\mathrm{GF}(2)^n. Such a linear code can in principle be represented in two ways: 1.) via a so-called generator matrix G\in F^{k\times n}; or 2.) via a control matrix H\in F^{n\times(n-k)}. A generator matrix is simply a matrix describing the above coding mapping \iota in coordinates. A control matrix H of C, on the other hand, is a matrix whose kernel is exactly the code C, i.e., to check whether a block b\in F^n belongs to the code C, one simply computes the lying vector bH (we always use covariant notation in the following) and checks all l=n-k places whether they are equal to zero, and bH is thus the zero vector. Hamming codes are most easily described by their control matrix. Namely, choose H\in\mathrm{GF}(2)^{(2^l-1)\times l} such that its rows are exactly all vectors of the l-dimensional vector space \mathrm{GF}(2)^l except the zero vector (namely, that is exactly n=2^l-1 many). Thus H is a (2^l-1)\times l matrix, as desired. The (n=2^l-1,k=n-l)-Hamming code thus has exactly l bits of redundancy, because one must perform exactly l parity tests. So the actual encoded information has a length of 2^l-1-l bits (which is much larger than the redundancy for large l). Let us now consider how many errors a Hamming code can correct. To do this, we assume that c,d\in C are distinct codewords that have minimal Hamming distance from each other. By shifting (since this leaves the Hamming distance the same, we are allowed to do so), we can assume that d=0 is the zero vector (which, since C is a linear code, is, after all, always contained in C). There are certainly three vectors u,v,w\in\mathrm{GF}(2)^l\setminus{0} that are linearly dependent, i.e. u+v+w=0. If i,j,k\in{1,\ldots,2^l-1} are the associated indices such that u,v,w are the i-th, j-th, and k-th columns of the control matrix, then the vector c=(c_1,\ldots, c_{2^l-1}) with c_m=0 if m\neq i,j,k and c_i=c_j=c_k=1 surely satisfies the above control condition cH=0, because cH is then exactly u+v+w, which was zero by assumption. This shows that the minimum distance (or, as this is also called for linear codes: the minimum weight) d=d(C) can be at most three. But if the vector c has fewer than three ones as entries, then it cannot satisfy the control condition, because any two columns of the control matrix do not combine to zero (they are linearly independent). Thus d(C)=3. From this we see that a Hamming code can only ever correct a single error. This may seem a bit unsatisfactory at first. However, the big advantage that Hamming codes have is that they can be implemented very elegantly. For that, feel free to check out this video by YouTuber 3Blue1Brown.

But now to the exhibit “Hamming code”: here is shown the Hamming code for which l=3 and therefore n=2^l-1=7 and k=n-l=4; so the so-called (7,4)Hamming code. Therefore there are n=7 lamps and k=4 buttons. You can try here once yourself, which constellations of burning lamps can be set and which not. What is striking is that — if at least one lamp is burning — then always at least three lamps are burning. This exactly reflects the fact explained above that the minimum weight of any Hamming code is exactly d=3. Also, the exhibit is a good way to practice what a control matrix and a generator matrix are. For example, the generator matrix can be easily set up by writing the base constellations (i.e., when only exactly one button is pressed) as row vectors in a 4\times 7 matrix. Do you also succeed in finding three control conditions to check whether a constellation of burning lights is allowed? This seems to be much more difficult at first. If you would write your found three conditions into a matrix, you would get the searched control matrix H of the dimension 7\times 3.


\mathbf{GF(2)^5}

This exhibit also represents a linear code. You see nine lights. If you could turn each of these lights on and off, there would be 2^9 possibilities. If you code the state that a lamp is on with 1 and the state that it is not on with 0, then each of these possibilities corresponds to exactly one element of the 9-dimensional vector space V=\mathrm{GF}(2)^9 over the body \mathrm{GF}(2) with the two elements 0 and 1. Now you can’t control each lamp individually. For this, only the lamps of one row or column of the lamps arranged in a square of 3\times 3 grid points can be switched all at once. So there can be at most 2\cdot2\cdot2\cdot2\cdot2=2^6 possible constellations (for each column and row a factor 2). But it turns out that every possible constellation can be set in exactly two ways: Namely, if you press all six buttons (i.e., those of the three rows and the three columns), you get the same constellation as before. The space of possible constellations now forms a linear code of length n=9 (because there are nine lamps) and dimension 5 (because there are, as just explained, 2^5 possibilities). This code is generated as a vector space from the basic constellations, i.e. from those constellations, where exactly the lamps of a row or column are burning (one of them being superfluous). Here again the concept of the generator matrix can be explained well. The rows of this matrix are exactly the basic constellations from which all others can be combined:

    \[G=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0\end{pmatrix}\]

We don’t need the last column here as a base constellation, because it can be composed of the others.

But what does a geiegnete control matrix H look like for the 5-dimensional code here? We are looking for 4=n-k=9-5 linear constants which ensure that we are dealing with an admissible constellation. To do this, make the following observation: select one of the four corners of the square. Now consider those four lamps which are closest to this corner (they form a 2\times 2 square). It can be observed that for all constellations you can set, always an even number of these four lamps is burning. But can this be proved? Yes! even very simple. For the basic constellations (i.e., when only one row or column of lamps is burning), either zero or two of these four lamps (i.e., an even number) are always burning. If we now combine basic constellations, this property must be preserved, since pressing a button always switches either zero or two of the four lamps. So we get in this way four control conditions (one for each corner), which must be fulfilled, so that a constellation of burning lamps can really be set. This is exactly the right number (see above). But are these four conditions also independent of each other? The answer is again: Yes! To see this, we write the above four conditions back into a matrix H\in\mathrm{GF}(2)^{9\times 4}:

    \[H=\begin{pmatrix} 1 & 0 & 0 & 0\ 1 & 0 & 0 & 1\ 0 & 0 & 1\ 1 & 1 & 0 & 0\1 & 1 & 1 & 1\ 0 & 0 & 1 & 1\ 0 & 1 & 0\ 0 & 1 & 0\ 0 & 1 & 1 & 0\ 0 & 0 & 1 & 0\end{pmatrix}.\]

The four columns of this (control) matrix H are now linearly independent, because the first, third, seventh, and ninth rows form a permutation matrix (which is regular). This is due to the fact that each of the four corner lamps occurs in exactly one of the four control conditions.

One last task: Can you also find five lamps that uniquely determine the state of all other lamps (this is called interpolation)?


Literature

[1] https://de.wikipedia.org/wiki/Linearer_Code

[2] https://de.wikipedia.org/wiki/Hamming-Code

[3] https://de.wikipedia.org/wiki/Generatormatrix

[4] https://de.wikipedia.org/wiki/Endlicher_Körper

[5] https://de.wikipedia.org/wiki/Lineare_Unabhängigkeit