8 Linear Codes and the Uniformity Lemma

8.1 Overview

This chapter develops the theory of linear codes and a key probabilistic tool: for a uniformly random \(n\times k\) generator matrix \(G\) and any nonzero message \(x\in \alpha ^k\), the output \(Gx\) is uniformly distributed over \(\alpha ^n\).

8.2 Distance equals minimum weight in linear codes

Theorem 8.1 Minimum distance equals minimum nonzero weight

✓

Let \(\alpha \) be a finite field and let \(C\) be a linear code of length \(n\) over \(\alpha \), meaning there is a generator matrix \(G\) whose columns generate \(C\) (every \(G\)-image of a message word lies in \(C\), and every codeword of \(C\) is such an image). Suppose \(d\) is the minimum distance of \(C\), that is, some two distinct codewords of \(C\) lie at Hamming distance exactly \(d\) and no two distinct codewords lie closer. Then every nonzero codeword of \(C\) has Hamming weight at least \(d\), and some codeword of \(C\) has Hamming weight exactly \(d\), where the weight of a codeword is its Hamming distance from the all-zero codeword.

8.3 Uniform distributions and random matrices

Definition 8.2 Uniform distribution on vectors

✓

The uniform probability mass function on \(\alpha ^n\), encoded as a function \(\alpha ^n\to \mathbb {R}\) assigning \(1/|\alpha |^n\) to each vector.

Lemma 8.3 Finiteness of the solution set of a linear matrix equation

✓

Let \(\alpha \) be a finite field, and let \(n\) and \(k\) be natural numbers. Fix a codeword \(v : \mathrm{Fin}\, n \to \alpha \) of length \(n\) and a codeword \(x : \mathrm{Fin}\, k \to \alpha \) of length \(k\). Then the set of matrices \(G \in \alpha ^{n \times k}\) satisfying \(Gx = v\) is finite.

Definition 8.4 Distribution induced by random matrices

✓

\(\mu _x(v)\) is the fraction of \(n\times k\) matrices \(G\) satisfying \(Gx=v\).

Definition 8.5 Row extraction

✓

Utility returning the \(i\)-th row of a matrix as a \(1\times k\) matrix.

8.4 Uniformity lemma

Theorem 8.6 Random matrix images of a nonzero vector are uniform

✓

Let \(\alpha \) be a finite field, and fix \(n \ge 0\) and \(k \ge 1\). Let \(x \in \alpha ^k\) be a nonzero vector. Then the distribution on \(\alpha ^n\) obtained by sampling an \(n \times k\) matrix \(G\) with entries in \(\alpha \) uniformly at random and returning the product \(Gx\) coincides with the uniform distribution on \(\alpha ^n\); that is, for every \(v \in \alpha ^n\),

\[ \frac{\bigl|\{ \, G \in \alpha ^{n \times k} : Gx = v\, \} \bigr|}{\left\lvert \alpha \right\rvert ^{nk}} = \frac{1}{\left\lvert \alpha \right\rvert ^{n}}. \]