The alphabet \(\{ 0,1\} \) with addition and multiplication modulo \(2\), i.e. the field \(\mathrm{GF}(2)= \mathbb {Z}/2\mathbb {Z}\). All codes in this blueprint are built over \(\mathrm{GF}(2)\) (the constructions generalize to larger fields).

For words \(u,v \in \mathrm{GF}(2)^{\, n}\), the Hamming distance \(\Delta (u,v)\) is the number of coordinates in which \(u\) and \(v\) differ.

The Hamming weight \(\operatorname {wt}(w)\) of \(w \in \mathrm{GF}(2)^{\, n}\) is the number of nonzero coordinates of \(w\); equivalently \(\operatorname {wt}(w) = \Delta (w,0)\).

The binary entropy function is \(H(x) = -x\log _2 x - (1-x)\log _2(1-x)\) for \(x \in (0,1)\), with \(H(0)=H(1)=0\). It governs the Gilbert–Varshamov bound and the random-expansion estimates of Appendix II.

A linear code of block length \(n\) and rate \(r\) is a subspace \(\mathcal{C}\subseteq \mathrm{GF}(2)^{\, n}\) of dimension \(rn\). Words have \(n\) symbols, of which \(rn\) are message symbols (freely chosen) and the remaining \((1-r)n\) are determined by the linear constraints defining \(\mathcal{C}\).

A code \(\mathcal{C}\) has minimum relative distance \(\alpha \) if every pair of distinct words of \(\mathcal{C}\) differ in at least \(\alpha n\) symbols. For a linear code this equals \(\min \{ \operatorname {wt}(w)/n : w \in \mathcal{C},\ w \neq 0\} \).

An algorithm corrects an \(\epsilon \) fraction of error from a code \(\mathcal{C}\) if, on input a word \(w\) that differs from some \(v \in \mathcal{C}\) in at most \(\epsilon n\) symbols, it outputs \(v\) (no restriction is placed on its behaviour on other inputs).

A family of linear codes is asymptotically good if there are constants \(r{\gt}0\) and \(\alpha {\gt}0\) such that the codes have block length tending to infinity, rate at least \(r\), and minimum relative distance at least \(\alpha \).