7 Linear Codes and the Uniformity Lemma
7.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\).
7.2 Distance equals minimum weight in linear codes
If \(C\) is linear (witnessed by some generator matrix) and has minimum distance \(d\), then:
every nonzero codeword in \(C\) has weight at least \(d\);
some codeword in \(C\) has weight exactly \(d\).
7.3 Uniform distributions and random matrices
The uniform probability mass function on \(\alpha ^n\), encoded as a function \(\alpha ^n\to \mathbb {R}\) assigning \(1/|\alpha |^n\) to each vector.
For fixed \(x\in \alpha ^k\) and \(v\in \alpha ^n\), the set \(\{ G : Gx=v\} \) is finite.
\(\mu _x(v)\) is the fraction of \(n\times k\) matrices \(G\) satisfying \(Gx=v\).
Utility returning the \(i\)-th row of a matrix as a \(1\times k\) matrix.
7.4 Uniformity lemma
If \(x\neq 0\) and \(k\ge 1\), then for a uniformly random \(n\times k\) matrix \(G\) over \(\alpha \), the product \(Gx\) is uniformly distributed over \(\alpha ^n\):