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

Question 2

Let $C$ be a Reed-Solomon code generated by

G=\begin{bmatrix} 1 & 1 & \cdots & 1\\ \alpha_1 & \alpha_2 & \cdots & \alpha_n\\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2\\ \vdots & \vdots & \cdots & \vdots\\ \alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_n^{k-1} \end{bmatrix}

prove that there exists $v_1,v_2,\ldots,v_n\in \mathbb{F}_q\setminus \{0\}$ such that the parity check matrix is

H=\begin{bmatrix} 1 & 1 & \cdots & 1\\ \alpha_1 & \alpha_2 & \cdots & \alpha_n\\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2\\ \vdots & \vdots & \cdots & \vdots\\ \alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_n^{k-1} \end{bmatrix}\begin{bmatrix} v_1 & 0 & \cdots & 0\\ 0 & v_2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & v_n \end{bmatrix}

Some lemmas for linear codes

First we introduce the following lemmas for linear codes

Let $G$ and $H$ be the generator and parity-check matrices of (any) linear code

Lemma 1

H G^\top = 0

Proof

By definition of generator matrix and parity-check matrix, $forall e_i\in H$ , $e_iG^\top=0$ .

So $H G^\top = 0$ .

Lemma 2

Any matrix $M\in \mathbb{F}_q^{(n-k)\times n}$ such that $\operatorname{rank}(M) = n - k$ and $M G^\top = 0$ is a parity-check matrix for $C$ (i.e. $C = \ker M$ ).

Proof

It is sufficient to show that the two statements

$\forall c\in C, c=uG, u\in \mathbb{F}^k$

$M c^\top = M(uG)^\top = M(G^\top u^\top) = 0$ since $M G^\top = 0$ .

Thus $C \subseteq \ker M$ .

$\dim (\ker M) +\operatorname{rank}(M) = n$

We proceed by showing that $\dim (\ker M) =\dim (C)$ .

Suppose $C$ does not span $\ker M$ . Let $u_1,...,u_k$ be a basis for $C$ . Then there exists $v\in \ker M\setminus C$ .

By linear independence, if we have scalar $a_1,...,a_k$ and $b$ such that $a_1u_1+...+a_ku_k+bv=0$ , then $a_1=...=a_k=b=0$ . So $v=a_1u_1+...+a_ku_k$ for some $a_1,...,a_k$ .

By definition of linear code, we have $v\in C$ , contradicting the assumption.

Solution

We proceed by applying the lemma 2.

$\operatorname{rank}(H) = n - k$ since $H$ is a Vandermonde matrix times a diagonal matrix with no zero entries, so $H$ is invertible.
$H G^\top = 0$ .

note that $\forall$ row $i$ of $H$ , $0\leq i\leq n-k-1$ , $\forall$ column $j$ of $G^\top$ , $0\leq j\leq k-1$

\begin{aligned} H G^\top &= \begin{bmatrix} 1 & 1 & \cdots & 1\\ \alpha_1 & \alpha_2 & \cdots & \alpha_n\\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2\\ \vdots & \vdots & \cdots & \vdots\\ \alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_n^{k-1} \end{bmatrix}\begin{bmatrix} v_1 & 0 & \cdots & 0\\ 0 & v_2 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & v_n \end{bmatrix}\begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \cdots & \alpha_1^{k-1}\\ 1 & \alpha_2 & \alpha_2^2 & \cdots & \alpha_2^{k-1}\\ \vdots & \vdots & \vdots & \cdots & \vdots\\ 1 & \alpha_n & \alpha_n^2 & \cdots & \alpha_n^{k-1} \end{bmatrix}\\ &= \begin{bmatrix} 1 & 1 & \cdots & 1\\ \alpha_1 & \alpha_2 & \cdots & \alpha_n\\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2\\ \vdots & \vdots & \cdots & \vdots\\ \alpha_1^{k-1} & \alpha_2^{k-1} & \cdots & \alpha_n^{k-1} \end{bmatrix} \begin{bmatrix} v_1\\ v_2\\ \vdots\\ v_n \end{bmatrix}\\ &=\sum_{l=1}^n\alpha_l^{r}v_l=0 \end{aligned}

Question 3

Show that in an MDS code $[n,k,d]_{\mathbb{F}_q}$ , $d=n-k+1$ , every $k$ entries determine the remaining $n-k$ entries of $G$ .

That is, every $k\times k$ submatrix of $G$ is invertible.

Proof

Let $G$ be the generator matrix, and $G'$ be any $k\times k$ submatrix of $G$ .

G=\begin{bmatrix} G'\in \mathbb{F}^{k\times k}|G''\in \mathbb{F}^{k\times (n-k)} \end{bmatrix}

We proceed by contradiction, suppose $G'$ is not invertible.

Then there exists $m',m''\in \mathbb{F}_q^k$ such that $m'\neq m''$ but $m'G'=m''G'$ .

Note that $m'G=[m'G'|m'G'']$ and $m''G=[m''G'|m''G'']$ .

So there are only $n-k$ entries of $m'G$ and $m''G$ are different, so $d\leq n-k$ .

That violate with the assumption that $d=n-k+1$ .

Reed-Muller code

Definition of Reed-Muller code (binary case)

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

Length of $RM(r,m)$ is $2^m$ .

Example of Reed-Muller code

Let $r=2$ , $m=3$ .

$\alpha_1=(0,0,0)$ , $\alpha_2=(0,0,1)$ , $\alpha_3=(0,1,0)$ , $\alpha_4=(0,1,1)$ , $\alpha_5=(1,0,0)$ , $\alpha_6=(1,0,1)$ , $\alpha_7=(1,1,0)$ , $\alpha_8=(1,1,1)$ .

$p(x)\deg\leq 2=\{1,x_1,x_2,x_3,x_1x_2,x_1x_3,x_2x_3\}$ .

So $p(x)=1+x_1+x_2+x_3+x_1x_2+x_1x_3+x_2x_3$ .

The generator matrix is defined by

G=\begin{bmatrix}1\\x_1\\x_2\\x_3\\x_1x_2\\x_1x_3\\x_2x_3\end{bmatrix}\begin{bmatrix} 1& 1&1&1&1&1&1&1\\ 0& 0&0&0&1&1&1&1\\ 0& 0&1&1&0&0&1&1\\ 0& 1&0&1&0&1&0&1\\ 0& 0&0&0&0&0&1&1\\ 0& 0&0&0&0&1&0&1\\ 0& 0&0&1&0&0&0&1\\ \end{bmatrix}

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

Question 4

$RM(m-1,m)$ is the parity check code.

Proof

By previous lemma, it is sufficient to show that $\dim (RM(m-1,m))=n-1$ and $RM(m-1,m)\subseteq \text{ parity code}$ .

For the first property,

\dim (RM(m-1,m))=\sum_{i=0}^{m-1}\binom{m}{i}=\sum_{i=0}^{m}\binom{m}{i}-\binom{m}{m}=2^m-1=n-1

For the second property,

recall that $c=(c_1,c_2,\ldots,c_n)\in$ parity if $\sum_{i=1}^n c_i=0$ .

So we need to show that $\sum_{i=1}^{2^m}f(\alpha_i)=0$ for every $f$ with $\deg f\leq m-1$ .

Note that $\forall f\in RM(m-1,m)$ , we can write $f(x_1,x_2,\ldots,x_m)=\sum_{S\subseteq [m],|S|\leq m-1}f_Sx_S$

So $\sum_{i=1}^{2^m}f(\alpha_i)=\sum_{S\subseteq [m],|S|\leq m-1}f_S\sum_{i=1}^{2^m}x_S(\alpha_i)=0$ .

We denote $J(s)=\sum_{i=1}^{2^m}x_S(\alpha_i)$ .

Note that $J(S)=\begin{cases} 1 & \text{if number of 1 in$ S $is odd} 0 & \text{otherwise} \end{cases}$

And number of 1 in $S$ is $2^{m-|S|}$ which is even.

So $J(S)=0$ for all $S\subseteq [m],|S|\leq m-1$ .