Notes on Error-Correcting Codes

An alphabet is a finite set. We call the elements of an alphabet letters or symbols.

A word over an alphabet $\Sigma$ of length $n \in \N$ is an element of $\Sigma^n$ (the $n$-fold Cartesian product of $\Sigma$ with itself). The set of all words of any length over $\Sigma$ is called the Kleene star or Kleene closure of $\Sigma$, and is denoted by $\Sigma^*$.

A code over an alphabet $\Sigma$ of block length $n \in \N$ is a subset of $\Sigma^n$. The elements of a code are called its codewords.

Let $\Sigma$ be an alphabet, and let $n, k \in \N$ with $k \le n$. A systematic encoding map is a function $f: \Sigma^k \to \Sigma^n$ that has the following property: for any $x \in \Sigma^k$, the first $k$ symbols of $f(x)$ coincide with $x$.

The indicator function of a logical proposition $P$ is the quantity

Let $\Sigma$ be an alphabet, and let $n \in \N$. The Hamming distance between two words $x, y \in \Sigma^n$ is the quantity

Similarly, the relative Hamming distance between $x$ and $y$ is the quantity

Let $\Sigma$ be an alphabet, and let $n \in \N$.

• The message length or dimension of a code $C \subseteq \Sigma^n$ is the quantity $\log_{\abs{\Sigma}} \abs{C}$.
• The rate of a code $C \subseteq \Sigma^n$ is the quantity $(\log_{\abs{\Sigma}} \abs{C}) / n$.
• The minimum distance (or simply distance) of a code $C \subseteq \Sigma^n$ is the minimum Hamming distance between its distinct codewords, i.e., $\min\,\{ \Delta(c, c') : c, c' \in C \text{ and } c \ne c' \}$.

A code $C \subseteq \Sigma^n$ with message length $k$ and minimum distance $d$ is called an $(n, k, d)_{\abs{\Sigma}}$-code.

Let $\Sigma$ be an alphabet, and let $n \in \N$. The Hamming ball in $\Sigma^n$ of radius $r \in \N$ about a word $w \in \Sigma^n$ is the set

The volume of a Hamming ball is simply its cardinality, and is denoted by

Note that this quantity is independent of the choice of word $w \in \Sigma^n$.

TODO

Theorem: Let $\Sigma$ be an alphabet, and let $n \in \N$. If a code $C \subseteq \Sigma^n$ has minimum distance $d$, then:

• $C$ can correct $\le d - 1$ erasures.
• $C$ can detect $\le d - 1$ errors.
• $C$ can correct $\le \lfloor \frac{d-1}{2} \rfloor$ errors.

Proof: TODO

Theorem: Let $\Sigma$ be an alphabet, and let $n \in \N$. If a code $C \subseteq \Sigma^n$ has minimum distance $d$, then its rate $R$ is bounded above by

Proof: Let $\mathcal{B} \coloneqq \{ B_{\Sigma^n}(c, \lfloor\!\frac{d-1}{2}\!\rfloor) : c \in C \}$ denote the collection of Hamming balls of radius $\lfloor\!\frac{d-1}{2}\!\rfloor$ about each codeword in $C$. Observe that the members of $\mathcal{B}$ are pairwise disjoint. Indeed, if there were two distinct codewords $c, c' \in C$ whose Hamming balls intersect, say at $\tilde{c} \in B_{\Sigma^n}(c, \lfloor\!\frac{d-1}{2}\!\rfloor) \cap B_{\Sigma^n}(c', \lfloor\!\frac{d-1}{2}\!\rfloor)$, then by definition, we would have $\Delta(c, \tilde{c}) \le \lfloor\!\frac{d-1}{2}\!\rfloor$ and $\Delta(\tilde{c}, c') \le \lfloor\!\frac{d-1}{2}\!\rfloor$. The triangle inequality would then imply

contradicting the hypothesis that $C$ has minimum distance $d$. Now, the members of $\mathcal{B}$ are all subsets of $\Sigma^n$, so it follows that the total cardinality of all of the balls in $\mathcal{B}$ is bounded above by $\abs{\Sigma}^n$.

Taking the base-$\abs{\Sigma}$ logarithm of both sides, we obtain:

Dividing both sides by $n$ yields the desired result. □

Let $\Sigma$ be an alphabet, and let $n \in \N$. A code $C \subseteq \Sigma^n$ is perfect if the collection of Hamming balls $\{ B_{\Sigma^n}(c, \lfloor\!\frac{d-1}{2}\!\rfloor) : c \in C \}$ covers $\Sigma^n$, where $d$ denotes the minimum distance of $C$.

Let $F$ be a finite field. A linear code of dimension $k \in \N$ and block length $n \in \N$ over $F$ is a $k$-dimensional linear subspace of $F^n$.

Let $F$ be a finite field, $n, k \in \N$, and let $C \subseteq F^n$ be a linear code of dimension $k$.

• A generator matrix for $C$ is a matrix $G \in F^{n \times k}$ whose column space is $C$.
• A parity-check matrix for $C$ is a matrix $H \in F^{(n - k) \times k}$ whose kernel is $C$.
• The dual of $C$ is the linear code $C^\perp \coloneqq \{ \vd \in F^n : \langle \vc, \vd \rangle = 0_F \text{ for all } \vc \in C \}$.

Here, $\langle \cdot, \cdot \rangle$ denotes the standard inner product on $F^n$, i.e., $\langle \vv, \vw \rangle \coloneqq \sum_{i=1}^n v_i w_i$.

Theorem: Let $q \in \N$ be a prime power, and let $n, d \in \N$ with $d \le n$. There exists a linear code $C \subseteq (\F_q)^n$ of minimum distance $d$ and rate

Proof: Let $C$ be a uniformly random linear subspace of $(\F_q)^n$ of dimension $k \coloneqq n - \lfloor \log_q(\Vol_q(d-1, n)) \rfloor - 1$. Note that there are only finitely many such subspaces, so this uniform distribution makes sense. We will show that $C$ has minimum distance $\ge d$ with probability $> 0$.

Let $G \in (\F_q)^{n \times k}$ be a uniformly random generator matrix for $C$. Observe that, for any fixed $\vx \in (\F_q)^n \setminus \{\vo\}$, the vector $G\vx$ is uniformly distributed in $(\F_q)^n \setminus \{\vo\}$. Indeed, all of the random choices we have made so far are invariant under a linear isomorphism of $(\F_q)^n$, and there exist isomorphisms of $(\F_q)^n$ that send any nonzero vector to any other nonzero vector, so this random process cannot favor any nonzero vector.

TODO