Lesson 2

We call a code a set of binary strings of the same length: \(C \subseteq \{0,1\}^{n}\). Elements of the set \(C\) are called codewords. These words will encode the messages we need to send. The model is as follows: the message is sent through an unreliable channel, in which symmetric substitution errors may occur (a bit \(b\) is flipped, that is, replaced with \(1 \oplus b\)).

The distance of a code is defined as the minimum distance between its codewords: \[d=\min_{u, v \in C}\{\operatorname{dist}(u,v) \colon u \neq v\}.\] Here, \(\operatorname{dist}\) is the Hamming distance, i.e., the number of positions in which the two strings differ: \[\operatorname{dist}(u,v)=|\{i \in [n] \colon u_{i} \neq v_{i}\}|.\] It is easy to see that this distance satisfies the triangle inequality: for any \(u,v,w \in \{0,1\}^{n}\) we have \[\operatorname{dist}(u,w) \le \operatorname{dist}(u,v)+\operatorname{dist}(v,w).\]

A \((n,k,d)\)-code is a code \(C \subseteq \{0,1\}^{n}\) with distance \(d\) and cardinality at least \(2^{k}\). One says that an \((n,k,d)\)-code detects \(d-1\) errors and corrects \(\lfloor \frac{d-1}{2}\rfloor\) errors. This terminology is explained as follows. If instead of the codeword \(x \in C\) we receive a word \(x'\) with at most \(d-1\) errors (that is, \(\operatorname{dist}(x,x') \le d-1\)), then we can surely detect that these errors occurred, since \(x'\) cannot coincide with another codeword: all of them are at least \(d\) away from \(x\). If moreover \(\operatorname{dist}(x,x') \le \lfloor \frac{d-1}{2}\rfloor\), then from \(x'\) we can even recover the original codeword \(x\) (i.e., correct all errors), since all other codewords are surely farther from \(x'\) than \(x\). Indeed, if there were another codeword \(y \in C\) at distance at most \(\lfloor \frac{d-1}{2}\rfloor\) from \(x'\), then, by the triangle inequality, we would have \[\operatorname{dist}(x,y) \le \operatorname{dist}(x,x')+\operatorname{dist}(x',y)\le \left\lfloor \frac{d-1}{2}\right\rfloor+\left\lfloor \frac{d-1}{2}\right\rfloor \le d-1.\]

Let's illustrate this with a simple example. Consider the following code: \[C=\{x \in \{0,1\}^{n} \colon x_{1} \oplus x_{2} \oplus \dotsb \oplus x_{n} = 0\}\] (the codewords are length \(n\) strings with even sum of bits). It is easy to check that the distance of this code equals two. This code detects one error: if through a noisy channel, where at most one substitution error can occur, we receive a message \(x'\) with parity sum 0, then we know there was no error; if instead we get a message with parity sum 1, then we know there was one error (but do not know in which bit it occurred!). In this case, \(|C|=2^{n-1}\), that is, \(k=n-1\). This means that to detect one error, it is enough to extend the original message by just one bit (you can simply append the parity bit of the original message). But to correct (rather than just detect) one error, the message needs to be extended by at least \(\log_{2} n\) bits. Intuitively, this happens because detecting one error gives us one bit of information: error or no error. But correcting one error gives us \(\log_{2} (n+1)\) bits of information: whether an error occurred and, if so, in which of the \(n\) positions.

When designing a code, we want it to have as many codewords as possible (i.e., large \(k\)) at as large a distance from each other as possible (i.e., large \(d\)). Of course, the larger one of these parameters is, the smaller the other becomes. Below, we prove bounds on the relationship of these parameters. Before formulating them, let’s also give some geometric intuition. We want to select in \(\{0,1\}^{n}\) as many points as possible with pairwise distance at least \(d\). Or equivalently: we want to choose in \(\{0,1\}^{n}\) as many pairwise disjoint balls of radius \(\lfloor \frac{d-1}{2}\rfloor\) as possible.

We call a ball of radius \(r\) centered at \(u \in \{0,1\}^{n}\) the set of all strings at distance at most \(r\) from \(u\): \[\operatorname{Ball}(u, r)=\{v \in \{0,1\}^{n} \colon \operatorname{dist}(u, v) \le r\}.\] Its volume (cardinality) is denoted by \(\operatorname{Vol}(r)\) (clearly, it does not depend on the center). The volume of a ball of radius \(r=\alpha n\) for \(\alpha \le \frac{1}{2}\) can be estimated by the following formula (which follows from Stirling’s formula): \[\operatorname{Vol}(r) = \sum_{i=0}^{\alpha n}\binom{n}{i}\approx 2^{H(\alpha)n}\ .\]

The approximate equality here should be read as: up to a polynomial (in \(n\)) factor. The function \(H(p) \colon [0,1] \to [0,1]\) is called the Shannon entropy function: \[H(p)=-p\log_{2}p-(1-p)\log_{2}(1-p).\]