Let $q$ be a power of $2$. Assume that elements of the finite field $\operatorname{GF}(q)$ are denoted by $\beta_i$ for $0\leq i \leq q-1$. We divide elements of $\operatorname{GF}(q)$ in two parts as follows; $x_i=\beta_i$, $0\leq i \leq k-1$ and $y_j=\beta_{k+j}$, for $0\leq j \leq q-k-1$.

From elements $x_i$ and $y_j$ we construct an $k \times (q-k)$ Cauchy matrix $A=\frac{1}{x_i+y_j}$ for $0\leq i \leq k-1$ and $0\leq j \leq q-k-1$. We can verify that all square sub-matrices of $A$ are non-singular Cauchy matrices over $\operatorname{GF}(q)$, since $x_i$'s and $y_j$'s are distinct elements and hence $x_i+y_j\neq 0$ for all $i$ and $j$ (proofwiki)

The matrix $A$ in coding theory is called a super-regular matrix and also in the cryptography is known as an $\operatorname{MDS}$ matrix. Consider the generator matrix $G=(I_k\mid A)$ where $I_k$ is the identity matrix of order $k$. It can be checked that $G$ generates an $\operatorname{MDS}$ code, denoted with $C$, with parameters $(n,k,d)$ page 321, Theorem 8 where $n=q$ and $d=n-k+1$. I dont know if the $\operatorname{MDS}$ code $C$ have a special name.

My question: How to extend the length of code $C$ to obtain a code $\widehat{C}$ such that the extended code $\widehat{C}$ be an $\operatorname{MDS}$ code.

My try: I think, this question is equivalent to ask how to add some columns to $A$ such that $A$ remain a super-regular matrix. The matrix $A$ consist of all elements of $\operatorname{GF}(q)$ and i dont know which column can be added to $A$ such that all square sub-matrices of the new matrix be non-singular.

I asked this question in math.stackexchange but I still haven't received an answer.

Thanks for any suggestions.


1 Answer 1


Your notation is nonstandard. Code length is $n,$ dimension is $k,$ minimum distance is $d=n-k+1$ when a code is MDS. The paper by Alderson available here proves the following:

Theorem 2. A $q-$ary $(q+k−2,k)-$ MDS code can be extended to a (unique) maximum length MDS code if and only if $q$ is even.

The authors state "It is important to point out that we can not possibly improve Theorem 2 to include (q + k − 3)-MDS codes."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.