Show that the matrix is a generator matrix of a MDS code Let a 1 </msub> ,

Cory Patrick

Cory Patrick

Answered question

2022-06-24

Show that the matrix is a generator matrix of a MDS code
Let a 1 , , a n be pairwise distinct elements of F q and k n. I have to show that
1. The matrix [ 1 1 0 a 1 a n 0 a 1 2 a n 2 0 0 a 1 k 1 a n k 1 1 ] 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 [ 1 1 0 0 a 1 a q 1 0 a 1 2 a q 2 0 1 ] 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 ) × ( n k ) full size minors of H are invertible
3. All k × 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

Jovan Wong

Beginner2022-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 × 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 × 3, so just approach those cases by a direct computation of the determinant.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?