CSE5313 Coding and information theory for data science (Recitation 10)

Question 5

Prove the minimum distance of Reed-Muller code $RM(r,m)$ is $2^{m-r}$ .

$n=2^m$ .

Recall that the definition of RM code is:

\operatorname{RM}(r,m)=\left\{(f(\alpha_1),\ldots,f(\alpha_2^m))|\alpha_i\in \mathbb{F}_2^m,\deg f\leq r\right\}

Example of RM code

Let $r=0$ , it is the repetition code.

$\dim \operatorname{RM}(r,m)=\sum_{i=0}^{r}\binom{m}{i}$ .

Here $r=0$ , so $\dim \operatorname{RM}(0,m)=1$ .

So the minimum distance of $RM(0,m)$ is $2^{m-0}=n$ .

Let $r=m$ ,

then $\dim \operatorname{RM}(r,m)=\sum_{i=0}^{r}\binom{m}{i}=2^m$ . (binomial theorem)

So the generator matrix is $n\times n$

So the minimum distance of $RM(m,m)$ is $2^{m-m}=1$ .

Then we can do the induction on $r$ .

Assume the minimum distance of $RM(r',m')$ is $2^{m'-r'}$ for all $0\leq r'\leq r$ , $r'\leq m'<m-1$ .

Then we need to show that the minimum distance of $RM(r,m)$ is $2^{m-r}$ .

Proof

Recall that the polynomial $p(x_1,x_2,\ldots,x_m)$ can be written as $p(x_1,x_2,\ldots,x_m)=\sum_{S\subseteq [m],|S|\leq r}f_s X_s$ , where $f_s\in \mathbb{F}_2$ , the monomial $X_s=\prod_{i\in S}x_i$ .

Every monomial $f(x_1,x_2,\ldots,x_m)$ can be written as

\begin{aligned} p(x_1,x_2,\ldots,x_m)&=\sum_{S\subseteq [m],|S|\leq r}f_s X_s\\ &=g(x_1,x_2,\ldots,x_{m-1})+x_m h(x_1,x_2,\ldots,x_{m-1})\\ \end{aligned}

So $g(x_1,x_2,\ldots,x_{m-1})$ has degree at most $r$ and does not contain $x_m$ .

And $x_m h(x_1,x_2,\ldots,x_{m-1})$ has degree at most $r-1$ and contains $x_m$ .

Note that the codeword of $RM(r,m)$ is the truth table of some monomial evaluated at all $2^m$ $\alpha_i\in \mathbb{F}_2^m$ .

And the minimum distance of $RM(r,m)$ is the minimum hamming weight for linear code, which is the number of $\alpha_i$ such that $f(\alpha_i)=1$

Then we can defined the weight of $f$ to be all $\alpha_i$ such that $f(\alpha_i)=1$ .

\operatorname{wt}(f)=\{\alpha_i|f(\alpha_i)=1\}

Note that $g(x_1,x_2,\ldots,x_{m-1})$ is a $RM(r,m-1)$ and $h(x_1,x_2,\ldots,x_{m-1})$ is a $RM(r-1,m-1)$ .

If $x_m=0$ , then $f(\alpha_i)=g(\alpha_i)$ . If $x_m=1$ , then $f(\alpha_i)=g(\alpha_i)+h(\alpha_i)$ .

So $\operatorname{wt}(f)=\operatorname{wt}(g)\cup\operatorname{wt}(g+h)$ .

Note that $\operatorname{wt}(g+h)$ is the number of $\alpha_i$ such that $g(\alpha_i)+h(\alpha_i)=1$ , which is XOR in binary field.

So $\operatorname{wt}(g+h)=(\operatorname{wt}(g)\setminus\operatorname{wt}(h))\cup (\operatorname{wt}(h)\setminus\operatorname{wt}(g))$ .

\begin{aligned} |\operatorname{wt}(f)|&=|\operatorname{wt}(g)|+|\operatorname{wt}(g+h)|\\ &=|\operatorname{wt}(g)|+|\operatorname{wt}(g)\setminus\operatorname{wt}(h)|+|\operatorname{wt}(h)\setminus\operatorname{wt}(g)|\\ &=|\operatorname{wt}(h)|+2|\operatorname{wt}(h)\setminus\operatorname{wt}(g)|\\ \end{aligned}

Note $h$ is in $\operatorname{RM}(r-1,m-1)$ , so $|\operatorname{wt}(h)|=2^{m-r}$

Theorem for Reed-Muller code

\operatorname{RM}(r,m)^\perp=\operatorname{RM}(m-r-1,m)

Let $\mathcal{C}=[n,k,d]_q$ .

The dual code of $\mathcal{C}$ is $\mathcal{C}^\perp=\{x\in \mathbb{F}^n_q|xc^\top=0\text{ for all }c\in \mathcal{C}\}$ .

Example

$\operatorname{RM}(0,m)^\perp=\operatorname{RM}(m-1,m)$ .

and $\operatorname{RM}(0,m)$ is the repetition code.

which is the dual of the parity code $\operatorname{RM}(m-1,m)$ .

Lemma for sum of binary product

For $A\subseteq [m]=\{1,2,\ldots,m\}$ , let $X^A=\prod_{i\in A}x_i$ , we can defined the inner product $\langle X^A,X^B\rangle=\sum_{x\in \{0,1\}^m}\prod_{i\in A}x_i\prod_{i\in B}x_i=\sum_{x\in \{0,1\}^m}\prod_{i\in A\cup B}x_i$ .

So $\langle X^A,X^B\rangle=\begin{cases} 1 & \text{if }A\cup B=[m]\\ 0 & \text{otherwise} \end{cases}$

because $\prod_{i\in A\cup B}x_i=1$ if every coordinate in $A\cup B$ is 1.

So the number of such $x\in \{0,1\}^m$ is $2^{m-|A\cup B|}$ .

This implies that $\langle X^A,X^B\rangle=1$ if and only if $m-|A\cup B|=0$ .

Recall that $\operatorname{RM}(r,m)$ is the evaluation of $f=\sum_{B\subseteq [m],|B|\leq r}\beta X^B$ at all $\beta_i\in \{0,1\}^m$ .

$\operatorname{RM}(m-r-1,m)$ is the evaluation of $h=\sum_{A\subseteq [m],|A|\leq m-r-1}\alpha X^A$ at all $\alpha_i \in \{0,1\}^m$ .

By linearity of inner product, we have

\begin{aligned} \langle f,h\rangle&=\langle \sum_{B\subseteq [m],|B|\leq r}\beta X^B,\sum_{A\subseteq [m],|A|\leq m-r-1}\alpha X^A\rangle\\ &=\sum_{B\subseteq [m],|B|\leq r}\sum_{A\subseteq [m],|A|\leq m-r-1}\beta\alpha\langle X^B,X^A\rangle\\ \end{aligned}

Because $|A\cup B|\leq |A|+|B|\leq m-r-1+r=m-1$ .

So $\langle X^B,X^A\rangle=0$ since $m-1<m$

So $\langle f,h\rangle=0$ .

Proof for the theorem

Recall that the dual code of $\operatorname{RM}(r,m)^\perp=\{x\in \mathbb{F}_2^m|xc^\top=0\text{ for all }c\in \operatorname{RM}(r,m)\}$ .

So $\operatorname{RM}(m-r-1,m)\subseteq \operatorname{RM}(r,m)^\perp$ .

So the last step is the dimension check.

Since $\dim \operatorname{RM}(r,m)=\sum_{i=0}^{r}\binom{m}{i}$ and the dimension of the dual code is $2^m-\dim \operatorname{RM}(r,m)=\sum_{i=0}^{m}\binom{m}{i}-\sum_{i=0}^{r}\binom{m}{i}=\sum_{i=r+1}^{m}\binom{m}{i}$ .

Since $\binom{m}{i}=\binom{m}{m-i}$ , we have $\sum_{i=r+1}^{m}\binom{m}{i}=\sum_{i=r+1}^{m}\binom{m}{m-i}=\sum_{i=0}^{m-r-1}\binom{m}{i}$ .

This is exactly the dimension of $\operatorname{RM}(m-r-1,m)$ .