NoteNextra-origin/content/CSE5313/CSE5313_L11.md

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)).

So

\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).