Notes on Error-Correcting Codes

David K. Zhang
Last Modified 2022-03-17

Definition: Alphabet, Letter, Symbol

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

Definition: Word, Length, Kleene Star, Kleene Closure, Σ\Sigma^*

A word over an alphabet Σ\Sigma of length nNn \in \N is an element of Σn\Sigma^n (the nn-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^*.

In other words, ΣnNΣn\Sigma^* \coloneqq \bigcup_{n \in \N} \Sigma^n, and length defines a function ΣN\Sigma^* \to \N that maps each element of Σn\Sigma^n to nn.

Definition: Code, Block Length, Codeword

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

Definition: Systematic Encoding Map

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

Definition: Indicator Function, 1[P]1[P]

The indicator function of a logical proposition PP is the quantity

1[P]{1if P.0if ¬P. 1[P] \coloneqq \begin{cases} 1 & \text{if } P. \\ 0 & \text{if } \neg P. \end{cases}

Definition: Hamming Distance, Δ(x,y)\Delta(x, y), Relative Hamming Distance, δ(x,y)\delta(x, y)

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

Δ(x,y)i=1n1[xiyi]. \Delta(x, y) \coloneqq \sum_{i=1}^n \mathbb{1}[x_i \ne y_i].

Similarly, the relative Hamming distance between xx and yy is the quantity

δ(x,y)Δ(x,y)n=1ni=1n1[xiyi]. \delta(x, y) \coloneqq \frac{\Delta(x, y)}{n} = \frac{1}{n} \sum_{i=1}^n \mathbb{1}[x_i \ne y_i].

The Hamming distance Δ\Delta and relative Hamming distance δ\delta are metrics on Σn\Sigma^n. In particular, they satisfy the triangle inequality.

Definition: Message Length, Dimension, Rate, Minimum Distance, Distance, (n,k,d)Σ(n, k, d)_{\abs{\Sigma}}-Code

Let Σ\Sigma be an alphabet, and let nNn \in \N.

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

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

Definition: Hamming Ball, BΣn(w,r)B_{\Sigma^n}(w, r), Volume, VolΣ(r,n)\Vol_{\abs{\Sigma}}(r, n)

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

BΣn(w,r){xΣn:Δ(w,x)r}. B_{\Sigma^n}(w, r) \coloneqq \{ x \in \Sigma^n : \Delta(w, x) \le r \}.

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

VolΣ(r,n)BΣn(w,r).\Vol_{\abs{\Sigma}}(r, n) \coloneqq \abs{B_{\Sigma^n}(w, r)}.

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

Volq(r,n)=1+(n1)(q1)+(n2)(q1)2++(nr)(q1)r \Vol_q(r, n) = 1 + \binom{n}{1} (q - 1) + \binom{n}{2} (q - 1)^2 + \cdots + \binom{n}{r} (q - 1)^r

Definition: Erasure, Error


Minimum Distance is a Proxy for Robustness

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

  • CC can correct d1\le d - 1 erasures.
  • CC can detect d1\le d - 1 errors.
  • CC can correct d12\le \lfloor \frac{d-1}{2} \rfloor errors.

Proof: TODO

Hamming Bound

Theorem: Let Σ\Sigma be an alphabet, and let nNn \in \N. If a code CΣnC \subseteq \Sigma^n has minimum distance dd, then its rate RR is bounded above by

RlogΣCn1logΣ ⁣(VolΣ ⁣(d12 ⁣,n))n R \coloneqq \frac{\log_{\abs{\Sigma}} \abs{C}}{n} \le 1 - \frac{\log_{\abs{\Sigma}} \! \left( \Vol_{\abs{\Sigma}} \! \left( \left\lfloor \frac{d-1}{2} \right\rfloor\!, n \right) \right)}{n}

Proof: Let B{BΣn(c, ⁣d12 ⁣):cC}\mathcal{B} \coloneqq \{ B_{\Sigma^n}(c, \lfloor\!\frac{d-1}{2}\!\rfloor) : c \in C \} denote the collection of Hamming balls of radius  ⁣d12 ⁣\lfloor\!\frac{d-1}{2}\!\rfloor about each codeword in CC. Observe that the members of B\mathcal{B} are pairwise disjoint. Indeed, if there were two distinct codewords c,cCc, c' \in C whose Hamming balls intersect, say at c~BΣn(c, ⁣d12 ⁣)BΣn(c, ⁣d12 ⁣)\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 Δ(c,c~) ⁣d12 ⁣\Delta(c, \tilde{c}) \le \lfloor\!\frac{d-1}{2}\!\rfloor and Δ(c~,c) ⁣d12 ⁣\Delta(\tilde{c}, c') \le \lfloor\!\frac{d-1}{2}\!\rfloor. The triangle inequality would then imply

Δ(c,c)Δ(c,c~)+Δ(c~,c)d12+d12d1, \Delta(c, c') \le \Delta(c, \tilde{c}) + \Delta(\tilde{c}, c') \le \left\lfloor \frac{d-1}{2} \right\rfloor + \left\lfloor \frac{d-1}{2} \right\rfloor \le d - 1,

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

CVolΣ ⁣(d12 ⁣,n)Σn \abs{C} \Vol_{\abs{\Sigma}} \! \left( \left\lfloor \frac{d-1}{2} \right\rfloor\!, n \right) \le \abs{\Sigma}^n

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

logΣC+logΣ ⁣(VolΣ ⁣(d12 ⁣,n))n \log_{\abs{\Sigma}} \abs{C} + \log_{\abs{\Sigma}} \! \left( \Vol_{\abs{\Sigma}} \! \left( \left\lfloor \frac{d-1}{2} \right\rfloor\!, n \right) \right) \le n

Dividing both sides by nn yields the desired result.

Definition: Perfect Code

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

In other words, a code is perfect if it saturates the Hamming bound.

Definition: Linear Code

Let FF be a finite field. A linear code of dimension kNk \in \N and block length nNn \in \N over FF is a kk-dimensional linear subspace of FnF^n.

Note that the linear-algebraic notion of dimension coincides with our previous definition of the dimension of a code. If CC is a kk-dimensional linear subspace of FnF^n, then C=Fk\abs{C} = \abs{F}^k, which implies k=logFCk = \log_{\abs{F}} \abs{C}.

Definition: Generator Matrix, Parity-Check Matrix, Dual, CC^\perp

Let FF be a finite field, n,kNn, k \in \N, and let CFnC \subseteq F^n be a linear code of dimension kk.

  • A generator matrix for CC is a matrix GFn×kG \in F^{n \times k} whose column space is CC.
  • A parity-check matrix for CC is a matrix HF(nk)×kH \in F^{(n - k) \times k} whose kernel is CC.
  • The dual of CC is the linear code C{dFn:c,d=0F for all cC}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 FnF^n, i.e., v,wi=1nviwi\langle \vv, \vw \rangle \coloneqq \sum_{i=1}^n v_i w_i.

Because every vector space has a basis, every linear code CFnC \subseteq F^n admits a generator matrix (whose columns are the basis vectors for CC). In fact, up to permutations of symbol positions within codewords, every linear code admits a generator matrix whose first kk rows coincide with the k×kk \times k identity matrix. Such a generator matrix defines a systematic encoding map.

Gilbert–Varshamov Bound

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

R1logq(Volq(d1,n))+1n. R \ge 1 - \frac{\lfloor \log_q(\Vol_q(d - 1, n)) \rfloor + 1}{n}.

Proof: Let CC be a uniformly random linear subspace of (Fq)n(\F_q)^n of dimension knlogq(Volq(d1,n))1k \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 CC has minimum distance d\ge d with probability >0> 0.

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


Remark: The Gilbert-Varshamov bound actually holds for any qNq \in \N, not just prime powers. A proof of this stronger result requires a different construction, and the resulting codes are not linear codes.