2
$\begingroup$

Assume that elements of the finite field $GF(2^q)$ are denoted by $\beta_i$ for $0\leq i \leq 2^q-1$. We divide elements of $GF(2^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 2^q-k-1$.

From elements $x_i$ and $y_j$ we construct an $k \times (2^q-k)$ Cauchy matrix $A=\frac{1}{x_i+y_j}$ for $0\leq i \leq k-1$ and $0\leq j \leq 2^q-k-1$. We can verify that all square sub-matrices of $A$ are non-singular over $GF(2^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$ Chapter 11.

The matrix $A$ in coding theory is called a super-regular 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 $MDS$ code, denoted with $C$, with parameters $(2^q,k,2^q-k+1)$ page 321, Theorem 8. I dont know if the $MDS$ code $C$ have a special name.

My question: How to extend the length of code $C$ to $C'$ such that the extended code $C'$ be an $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 $GF(2^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.

Thanks for any suggestions.

$\endgroup$
3
  • 1
    $\begingroup$ I'm not really familiar with MDS codes other than those you get from RS-codes and/or tweaking them a bit. Anyway, I want to remark that: 1) if your $k$ is large enough the $x_i$s begin to overlap with $-y_j$s, and you are attempting to divide by zero to get the entries of $A$. 2) See Research Problem 11.4 (page 327). It is widely believed that with MDS codes $n\le q+1$ save for the trivial exceptions. Therefore extending your matrix $A$ a lot is probably doomed to fail. $\endgroup$
    – Jyrki Lahtonen
    Mar 22, 2018 at 13:13
  • $\begingroup$ @JyrkiLahtonen I know what you mean Professor Lahtonen. In fact , when $k =1$, there exist arbitrarily long MDS codes, e.g., repetition codes, and when $k\geq q$, a code is MDS only if it has minimum distance $\leq 2$. Therefore, we shall deal only with codes of dimension $k$, $2 \leq k \leq q - 1$. In this case, it is known that MDS codes cannot be arbitrarily long. Let $N_{max}(k, q)$, $2 \leq k \leq q - 1$, be the maximal length of any MDS code of dimension $k$ over $GF(q)$. Then, $q + 1 \leq N_{max}(k, q) \leq q + k - 1$. $\endgroup$
    – Amin235
    Mar 22, 2018 at 13:59
  • $\begingroup$ @JyrkiLahtonen Furthermore, for some special cases of $k$ and $q$, it can be shown that $N_{max}( k, q) = q + 1$. As you mentioned, the MDS Conjecture states that the same equality holds for all $q$ and $2 \leq k \leq q -1$, except when $q$ is even and $k \in \{3, q -l\}$, in which case $N_{max}(k,q) = q +2$. Reference $\endgroup$
    – Amin235
    Mar 22, 2018 at 14:01

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .