166 lines
5.4 KiB
Markdown
166 lines
5.4 KiB
Markdown
# 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\}
|
|
$$
|
|
|
|
<details>
|
|
<summary>Example of RM code</summary>
|
|
|
|
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$.
|
|
</details>
|
|
|
|
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}$.
|
|
|
|
<details>
|
|
<summary>Proof</summary>
|
|
|
|
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}$
|
|
|
|
</details>
|
|
|
|
## 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}\}$.
|
|
|
|
<details>
|
|
<summary>Example</summary>
|
|
|
|
$\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)$.
|
|
|
|
</details>
|
|
|
|
### 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$.
|
|
|
|
<details>
|
|
<summary>Proof for the theorem</summary>
|
|
|
|
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)$.
|
|
|
|
</details> |