Cory Patrick

Answered

2022-06-24

Show that the matrix is a generator matrix of a MDS code

Let ${a}_{1},\dots ,{a}_{n}$ be pairwise distinct elements of ${\mathbb{F}}_{q}$ and $k\le n$. I have to show that

1. The matrix $\left[\begin{array}{cccc}1& \dots & 1& 0\\ {a}_{1}& \dots & {a}_{n}& 0\\ {a}_{1}^{2}& \dots & {a}_{n}^{2}& 0\\ \vdots & & \vdots & 0\\ {a}_{1}^{k-1}& \dots & {a}_{n}^{k-1}& 1\end{array}\right]$ is a generator matrix of an $[n+1,k,n-k+2]$ MDS code.

2. if q is a power of 2, then the matrix $\left[\begin{array}{ccccc}1& \dots & 1& 0& 0\\ {a}_{1}& \dots & {a}_{q}& 1& 0\\ {a}_{1}^{2}& \dots & {a}_{q}^{2}& 0& 1\end{array}\right]$ is a generator matrix of an $[q+2,3,q]$ MDS code.

I don't even know where to start, the things we covered in the lecture are not so many, but what I thought could be useful, but don't know how to apply are:

Theorem: Let C be an [n,k] code with generator matrix G and parity check matrix H. The following are equivalent:

1. C is MDS

2. All $(n-k)\times (n-k)$ full size minors of H are invertible

3. All $k\times k$ full size minors og G are invertibleMaybe I could use this theorem, part (3), but I'm not sure how to show that all the minors og G are invertible.

Should I maybe, from definition of MDS, show that the distance is indeed $d(C)=n-k+2$, and then conclude that the code is MDS? But aren't the elements arbitrary?

Should I maybe look for a parity check matrix H and do something?

Let ${a}_{1},\dots ,{a}_{n}$ be pairwise distinct elements of ${\mathbb{F}}_{q}$ and $k\le n$. I have to show that

1. The matrix $\left[\begin{array}{cccc}1& \dots & 1& 0\\ {a}_{1}& \dots & {a}_{n}& 0\\ {a}_{1}^{2}& \dots & {a}_{n}^{2}& 0\\ \vdots & & \vdots & 0\\ {a}_{1}^{k-1}& \dots & {a}_{n}^{k-1}& 1\end{array}\right]$ is a generator matrix of an $[n+1,k,n-k+2]$ MDS code.

2. if q is a power of 2, then the matrix $\left[\begin{array}{ccccc}1& \dots & 1& 0& 0\\ {a}_{1}& \dots & {a}_{q}& 1& 0\\ {a}_{1}^{2}& \dots & {a}_{q}^{2}& 0& 1\end{array}\right]$ is a generator matrix of an $[q+2,3,q]$ MDS code.

I don't even know where to start, the things we covered in the lecture are not so many, but what I thought could be useful, but don't know how to apply are:

Theorem: Let C be an [n,k] code with generator matrix G and parity check matrix H. The following are equivalent:

1. C is MDS

2. All $(n-k)\times (n-k)$ full size minors of H are invertible

3. All $k\times k$ full size minors og G are invertibleMaybe I could use this theorem, part (3), but I'm not sure how to show that all the minors og G are invertible.

Should I maybe, from definition of MDS, show that the distance is indeed $d(C)=n-k+2$, and then conclude that the code is MDS? But aren't the elements arbitrary?

Should I maybe look for a parity check matrix H and do something?

Answer & Explanation

Jovan Wong

Expert

2022-06-25Added 23 answers

Step 1

Use characterization (3) of your theorem and remember the formula for the determinant of a Vandermonde matrix!

Step 2

Come up with different cases for the $k\times k$ minor, depending on the number of the involved "special" columns (the 1 or 2 rightmost columns of the generator matrix). Then, you can either directly apply Vandermonde or you have to do some transformation first.

For the second case of the $[q+2,3]$ MDS code, there are cases without Vandermonde. But here, the minors are of fixed size $3\times 3$, so just approach those cases by a direct computation of the determinant.

Use characterization (3) of your theorem and remember the formula for the determinant of a Vandermonde matrix!

Step 2

Come up with different cases for the $k\times k$ minor, depending on the number of the involved "special" columns (the 1 or 2 rightmost columns of the generator matrix). Then, you can either directly apply Vandermonde or you have to do some transformation first.

For the second case of the $[q+2,3]$ MDS code, there are cases without Vandermonde. But here, the minors are of fixed size $3\times 3$, so just approach those cases by a direct computation of the determinant.

Most Popular Questions