Reed Muller Codes
Introduction
\(\mathrm {RM}(r, m)\) is a binary linear block code \((n, k, d)\) of length \(2^m\). \(\mathrm {RM}(m, m)\) is defined as the universe \((2^m, 2^m, 1)\) code and \(\mathrm {RM}(0, m)\) is defined as repetition code of length \(2^m\). The remaining RM codes may be constructed from these elementary codes using the following recursive definition
\[\mathrm {RM} (r,m)=\{(\mathbf {u} ,\mathbf {u} +\mathbf {v} )\mid \mathbf {u} \in \mathrm {RM} (r,m-1),\mathbf {v} \in \mathrm {RM} (r-1,m-1)\}.\]The dimension of \(\mathrm {RM}(r, m)\) is given by
\[k=\sum _{s=0}^{r}{m \choose s}\]and the minimum distance is given by
\[d=2^{m-r}.\]The generator matrix of \(r^{\text{th}}\) order RM code of length \(N=2^m\) can be obtained by choosing rows with Hamming weight at least \(2^{m-r}\) from \(P\).
\[P = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}^{\otimes m}\]The matrix \(P\) can be seen as below for \(m=4\)
First Order RM Codes
The first order RM code is the code \(RM(1, m)\), which is a \((2^m, m+1, 2^{m-1})\) code. By definition, every codeword \(c\in RM(1, m)\) is evaluation of multivariate polynomial in \(\mathbb{F}_2[X_1, X_2, \cdots, X_m]\) of at most degree 1.