I am currently studying about binary Reed-Muller codes, where we have first defined by the usual Boolean function definition:
Def The binary Reed-Muller code $RM(r, m)$ of order $r$ and length $2^m$ consists of all linear combinations of vectors $\mathbf{f}$ associated with Boolean functions $f$ that are monomials of degree $\leq r$ in m variables.
Another construction to obtain the same code is by using Kronecker m-fold products. First we define the m-fold Kronecker product as $$G_2^{\otimes m}=G_2\otimes G_2\otimes \cdots \otimes G_2$$ where there are $m$ operands, and $G_2$ is the square matrix $G_2 = \begin{bmatrix}1 & 1 \\ 0 &1\end{bmatrix}$. Then it is claimed that the Reed-Muller code $RM(r, m)$ is constructed by selecting all rows of weight $\geq 2^{m-r}$ in $G_2^{\otimes m}$.
I would like to prove that these two codes are in fact equivalent, but I cannot figure out the exact steps. I have some few observations:
- $G_2^{\otimes m}$ has $\binom{m}{i}$ rows of weight $2^i$(proof by induction).
- The rows of $G_2^{\otimes m}$ with weight $\geq w$ define a code with minimum distance $w$(provided that one of the rows has weight exactly $w$). I would like to prove this observation by the following claim:
Claim: Sum of any two distinct rows in $G_2^{\otimes m}$ with weight each $d_1$ and $d_2$ has weight $\geq \min\{d_1, d_2\}$.
The claim seems to be true when checked by a simple MATLAB program, but I could not exactly prove it.
Questions:
How would I prove the Claim, or observation 2?
How could I conclude that the two codes obtained are in fact equivalent by observation 1 and 2? I can see that both methods give the same length, dimension, hamming distance, but this isn't enough. Am I looking at the wrong direction? Is there some more elegant, easy path?
The rows of the generator matrix of RM$(r,m)$ are the vectors $\mathbf f$ correspondent to the monomials of degree $\leq r$ in $m$ binary variables, and thus the generator matrix has $\sum_{i=0}^r\binom{m}{i}$ rows. I presume that you know how to prove RM$(r,m)$ has minimum weight $2^{m-r}$,and since this is a linear code, the minimum distance is also $2^{m-r}$.
The rows of $G_2^{\otimes m}$ are, in order, the vectors $\mathbf f$ corresponding to the monomials \begin{align} 1,~ x_1 &= 1,~ x_1\\ x_2,~ x_1x_2 &= (1,~x_1)x_2\\ x_3,~ x_1x_3,~ x_2x_3~, x_1x_2x_3 &= (1,~ x_1,~x_2,~ x_1x_2)x_3\\ x_4,~ x_1x_4~, x_2x_4,~\cdots \cdots. x_1x_2x_3x_4 &=(1,~ x_1,~x_2,~ x_1x_2,~x_3,~ x_1x_3,~ x_2x_3~, x_1x_2x_3)x_4 \end{align} and so on, with the last row being for the monomial $x_1x_2\cdots x_{m-1}x_m$.Not that all rows of $G_2^{\otimes m}$ have even weight except that last which has weight $1$. Bu choosing only those rows of $G_2^{\otimes m}$ that have weight $2^{m-r}$ or more as the rows of the generator matrix of RM$(r,m)$, we get exactly the same generator matrix as the one defined on the first paragraph of this answer. Can you take it from here?