Lesson 1

A set \(C \subseteq \{0,1\}^{n}\) of binary strings of length \(n\) is called a binary code of length \(n\) and distance \(d\) if the distance between any two distinct elements of the code is at least \(d\). The elements of the set \(C\) are called codewords. The distance is usually computed as the number of differing bits (and is called the Hamming distance): for \(s,t \in \{0,1\}^{n}\), we define \[\operatorname{dist}(s,t)=\left|\{i \in [n] \colon s_{i} \neq t_{i}\}\right|.\]

For example, for any \(n=2^{k}-1\) and \(d=3\), one can construct a Hamming code \(C \subseteq \{0,1\}^{n}\) of distance three, such that \(|C|=\frac{2^n}{n+1}\). It is easy to show that for distance \(d=3\), this code size is optimal: there cannot be more than \(\frac{2^n}{n+1}\) codewords. Indeed, for each codeword \(s \in \{0,1\}^{n}\), we can consider a sphere of radius one centered at this word: \[B(s)=\{t \in \{0,1\}^{n} \colon \operatorname{dist}(s, t) \le 1\}.\] Such a sphere contains exactly \(n+1\) words. Moreover, for any two distinct codewords \(s \neq t \in C\), the corresponding spheres cannot intersect: if there were a word \(u \in B(s) \cap B(t)\), then the distance between \(s\) and \(t\) would be at most two. Indeed, \[\operatorname{dist}(s,t) \le \operatorname{dist}(s,u) + \operatorname{dist}(u,t) \le 1 + 1 = 2.\]

Similarly, upper bounds on the code size for other distances \(d\) can be derived: the larger the distance \(d\), the fewer the codewords.