Toggle lights

How can a CD still be read even if some scratches adorn its back? How can a rover that is to conduct investigations on the Moon transmit its data to the base station on Earth, even though there will certainly be 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 is now always stored/transmitted in blocks of length $n$ . However, such a block $b$ actually contains only the information of a smaller number $k\leq n$ of $F$ -bits. That is, during encoding, one word of length $k$ above the alphabet $F$ is always converted into one word of length $n$ above the same alphabet. Thereby $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$ . Your 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 similar). Let us say these are $m$ symbols. Thus, a new disturbed block $b'$ is created. Can the original information still be reconstructed? To do 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 disturbed block $b'$ to the codeword in $C$ that is closest to this block measured in Hamming distance. But is this code word even unique? Generally not!

In order to recognize “too heavily disturbed” blocks $b'$ as such, and to identify reconstructable blocks can always be reconstructed unambiguously, a ball $B_r(c)\coloneqq\{d\in C\,|\, d_{\mathrm H}(c,d)\leq r\}$ of radius $r$ is therefore drawn at Hamming distance around each admissible codeword $c\in C$ , 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 to choose the radius $r$ here? We want $B_r(c)$ and $B_r(d)$ not to intersect for $c\neq d$ from $C$ . But this is exactly right 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$ ), $r\coloneqq\left\lfloor\frac{d(C)-1}{2}\right\rfloor$ is the best possible radius. The parameter $d\coloneqq d(C)$ thus 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$ (here $l\geq 2$ is a parameter to be chosen, which exactly measures the redundancy of the code), developed by the mathematician Richard Wesley Hamming. The word linear here means that our alphabet $F$ is a field, 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$ (in the following we always use covariant notation) and checks all $l=n-k$ digits to see if they are zero, and $bH$ is therefore 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. So the $(n=2^l-1,k=n-l)$ -Hamming code has exactly $l$ bits of redundancy, because you have to do 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) we can assume that $d=0$ is the zero vector (which, since $C$ is a linear code, is always contained in $C$ ). There are certainly three vectors $u,v,w\in\mathrm{GF}(2)^l\setminus\{0\}$ which 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 less than three ones as entries, then it cannot satisfy the control condition, because every 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 correct a single error at a time. This may seem a bit unsatisfactory at first. The big advantage that Hamming codes have, however, is that they can be implemented very elegantly. For that, feel free to watch this video by YouTuber 3Blue1Brown.

But now to the exhibit “Hamming code”: Here is shown the Hamming code for which $l=3$ and consequently $n=2^l-1=7$ and $k=n-l=4$ ; thus the so-called $(7,4)$ –Hamming code. Therefore, there are $n=7$ lamps and $k=4$ buttons. You can try out for yourself which constellations of burning lamps can be set and which cannot. What is striking is that — if at least one lamp is burning — then already 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. Can you also find three control conditions that can be used to check whether a constellation of burning lights is permissible? This seems to be significantly more difficult at first. If you would write your found three conditions into a matrix, you get the searched control matrix $H$ of the dimension $7\times 3$ .

$\mathbf{GF(2)^5}$

This exhibit also represents a linear code. Du siehst neun Lämpchen. If you could switch each of these lamps on and off, there would be $2^9$ possibilities. Coding the state that a lamp is burning as $1$ , and the state that it is not burning as $0$ , each of these possibilities corresponds to exactly one element from the $9$ -dimensional vector space $V=\mathrm{GF}(2)^9$ over the body $\mathrm{GF}(2)$ with the two elements $0$ and $1$ . But 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. Thus 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 $2^5$ possibilities, as just explained) This code is generated as a vector space from the base constellations-that is, from those constellations in which exactly the lamps of a row or column are lit (one of which is superfluous). This, in turn, provides a good explanation of the concept of the generator matrix. Indeed, 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 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0\end{pmatrix}$

We do not need the last column here as a base constellation, since it can be composed of the others.

But what does a suitable control matrix $H$ look like for the $5$ -dimensional code at hand here? Thus, we are looking for $4=n-k=9-5$ linear control conditions that 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 the four lamps closest to this corner (they form a $2\times 2$ square). It can be observed that in all constellations that you can set, an even number of these four lamps always burns. But can this be proven? 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 you now combine basic constellations together, this property must be preserved, since pressing a button always switches either zero or two of the four lamps. So, in this way we get four control conditions (one for each corner) that must be satisfied for a constellation of burning lamps to actually 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 condition 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 & 0 & 1\\ 1 & 1 & 0 & 0\\1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 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