Linear Codes

Linear Codes

A code \(C \subseteq \{0,1\}^{n}\) is called linear if it is a linear subspace of \(\{0,1\}^{n}\): if \(u,v \in C\), then \(u \oplus v \in C\) (in particular, this implies that the zero word belongs to any linear code: \(u \oplus u =\mathbf{0}\in C\)). A linear code can be specified by a parity-check matrix \(H \in \{0,1\}^{(n-k) \times n}\) and then \[C=\{x \in \{ 0, 1 \}^{n}\colon Hx=\mathbf{0}\}.\] Some properties of linear codes:

1. The distance of a linear code is the weight of its minimal nonzero word: \[d=\min\{||u|| \colon u \in C,\ u \neq \mathbf{0}\}.\] Indeed, for any \(u, v \in C\) we have \(\operatorname{dist}(u,v)=\operatorname{dist}(u \oplus v, \mathbf{0})=||u \oplus v||\).
2. Any \(\le d-1\) columns of the matrix \(H\) are linearly independent, while there exist \(d\) linearly dependent columns. Indeed, if \(\le d-1\) columns were linearly dependent, then there would be a codeword of weight \(\le d-1\). Conversely, since there is a codeword of weight \(d\), there are \(d\) linearly dependent columns.