4 The construction

Definition 22 Definition 6: the expander code \(\mathcal{C}(B,\mathcal{S})\)

Let \(B\) be a \((c,d)\)-regular graph between a set of \(n\) nodes \(\{ v_1,\dots ,v_n\} \), called variables, and a set of \(cn/d\) nodes \(\{ C_1,\dots ,C_{cn/d}\} \), called constraints, with \(d{\gt}c\). Let \(b(i,j)\) be a function so that for each constraint \(C_i\) the variables neighbouring \(C_i\) are \(v_{b(i,1)},\dots ,v_{b(i,d)}\). Let \(\mathcal{S}\) be an error-correcting code of block length \(d\). The expander code \(\mathcal{C}(B,\mathcal{S})\) is the code of block length \(n\) whose codewords are the words \((x_1,\dots ,x_n)\) such that, for \(1 \le i \le cn/d\), the restriction \((x_{b(i,1)},\dots ,x_{b(i,d)})\) is a codeword of \(\mathcal{S}\). Because the restrictions are linear, \(\mathcal{C}(B,\mathcal{S})\) is a linear code.

Theorem 23 Theorem 7: rate and distance of \(\mathcal{C}(B,\mathcal{S})\)

Let \(B\) be a \((c,d,\alpha ,c/(d\epsilon ))\)-expander and let \(\mathcal{S}\) be an error-correcting code of block length \(d\), rate \(r {\gt} (c-1)/c\), and minimum relative distance \(\epsilon \). Then \(\mathcal{C}(B,\mathcal{S})\) has rate at least \(cr-(c-1)\) and minimum relative distance at least \(\alpha \).

Proof ▶

Rate. Each of the \(cn/d\) constraints imposes at most \((1-r)d\) linear restrictions on the variables, so the variables suffer at most

\[ n\, \frac{c}{d}\, (1-r)d = cn(1-r) \]

linear restrictions in total. Hence they have at least \(n\bigl(cr-(c-1)\bigr)\) degrees of freedom, giving rate at least \(cr-(c-1)\).

Distance. We show \(\mathcal{C}(B,\mathcal{S})\) has no nonzero codeword of weight \(\alpha n\) or less. Let \(w\) be a nonzero word of weight at most \(\alpha n\) and let \(V\) be the set of variables that are \(1\) in \(w\), so \(|V| \le \alpha n\). There are \(c|V|\) edges leaving \(V\). By the expansion property (since \(|V| \le \alpha n\)), these edges enter more than \(\frac{c}{d\epsilon }|V|\) constraints. Hence the average number of edges per neighbouring constraint is less than

\[ \frac{c|V|}{(c/(d\epsilon ))|V|} = d\epsilon , \]

so some constraint \(C\) neighbouring \(V\) has fewer than \(d\epsilon \) neighbours in \(V\). The restriction of \(w\) to \(C\) is therefore a nonzero word of weight less than \(\epsilon d\), the minimum distance of \(\mathcal{S}\); so it is not a codeword of \(\mathcal{S}\). Thus \(w\) is not a codeword of \(\mathcal{C}(B,\mathcal{S})\). Hence the minimum relative distance is at least \(\alpha \).