Systematic Reed-Muller code

Solution 1:

The standard description of a $(r,m)$ Reed-Muller code is that there are $k = \sum_{i=0}^r \binom{m}{i}$ information bits that are denoted as \begin{align} &d_0\\ &d_1, d_2, \ldots, d_m\\ &d_{1,2}, d_{1,3}, \ldots, d_{1,m}, d_{2,3}, d_{2,4}, \ldots, d_{m-1,m}\\ &\ddots\\ &d_{1,2,\ldots, r-1, r}, d_{1,2,\ldots, r-1, r+1}, \ldots \end{align} where the $i$-th row above lists $\binom{m}{i}$ bits on it, and the transmitted codeword is the sequence of values $(c_0, c_1, \ldots, c_{2^m-1})$ of the degree $r$ $m$-variate polynomial \begin{align} &d_0\\ \oplus \ &d_1x_1 \oplus d_2x_2 \oplus \ldots \oplus x_md_m\\ \oplus \ &d_{1,2} x_1x_2 \oplus d_{1,3}x_1x_3 \oplus \ldots \oplus d_{1,m}x_1x_m \oplus d_{2,3}x_2x_3 \oplus d_{2,4}x_2x_4 \oplus \ldots \oplus d_{m-1,m}x_{m-1}x_m\\ \oplus \ &\ddots\\ \oplus \ &d_{1,2,\ldots, r-1, r}x_1x_2\cdots x_{r-1}x_r \oplus d_{1,2,\ldots, r-1, r+1}x_1x_2\cdots x_{r-1}x_{r+1} \oplus \ldots \end{align} as $(x_m, x_{m-1}, \ldots, x_2, x_1)$ varies from $(0,0, \ldots, 0)$ to $(1,1,\ldots, 1)$. So, upon receiving the $2^m$ bits, one can apply the standard Reed-Muller decoding algorithm to recover the $d$'s and then reconstruct the codeword $(c_0, c_1, \ldots, c_{2^m-1})$. If we want to think of $(c_0, c_1, \ldots, c_{k-1})$ as the real information bits $(D_0, D_1, \ldots, D_{k-1})$, then so be it: the decoder's job is done.

The harder question is at the transmitter: we want to find $d_0, d_1, \ldots, $ corresponding to the real information bits so that the standard Reed-Muller encoding produces for us the codeword $$(c_0, c_1, \ldots, c_{2^m-1}) = (D_0, D_1, \ldots, D_{k-1}, c_k, \ldots, c_{2^m-1})$$ in which the leading $k$ bits are the information bits. Not to worry. As @JyrkiLahtonen's comments point out, linear algebra rides to the rescue. Do row transformations on the given generator matrix $G$ of the standard Reed-Muller code to transform it into $\hat{G} = [I\mid P]$. $G$ and $\hat{G}$ have the same row space. So, at the transmitter, we have that $$(D_0, D_1, \ldots, D_{k-1})\hat{G} = (D_0, D_1, \ldots, D_{k-1}, c_k, \ldots, c_{2^m-1})$$ exactly the same codeword as we would have gotten if we had first laboriously transformed $(D_0, D_1, \ldots, D_{k-1})$ into the $d$'s and then applied the standard Reed-Muller encoding procedure!

In summary,

• Use $(D_0, D_1, \ldots, D_{k-1})\hat{G}$ to encode at the transmitter. DO NOT attempt to convert the $D$'s to the $d$'s to be followed by standard Reed-Muller encoding.

• Decode the received word using standard Reed-Muller decoding. This will give you the $d$'s. USE standard Reed-Muller encoding to reconstruct the transmitted codeword, and take its first $k$ bits as the information bits.