3
$\begingroup$

Is there a code that is Maximum Distance Separable and not isomorphic to Reed Solomon Codes? When is a MDS code isomorphic to Reed Solomon Code?

Is there an easy test? If so, could someone provide me a reference?

In short, if given a $[n,k,n-k+1]_q$ code how do you show it is RS or not?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

I guess you exclude trivial MDS codes, generalized Reed-Solomon codes, and MDS codes that can be obtained by code extension.

If you exclude them all, there are still a bunch of MDS codes. In general, MDS codes of length $n$ and dimension $k$ over $\mathbb{F}_q$ are equivalent to $n$-arcs in $\text{PG}(k-1,q)$. Generalized Reed-Solomon codes are $n$-arcs which are subsets of normal rational curves. So, other $n$-arcs are not Reed-Solomon codes. A quick google search gave me the following paper that enumerates all nonequivalent MDS codes of dimension $2$ and $3$ over $\mathbb{F}_q$ for $4 \leq q \leq 32$:

G. Kéri, Classification of $2$ and $3$ dimensional MDS codes for $4 \leq q \leq 32$.

The equivalence between MDS codes and arcs in $\text{PG}$ is well-known. I think you can find a reference that gives the proof somewhere with a little bit of searching.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Also is there a simple test that tells when a MDS code is Reed-Solomon? $\endgroup$
    – Turbo
    Commented Nov 1, 2013 at 10:45
  • $\begingroup$ @JAS The simplest way is to see if your code is linear or not. If it's not linear, it can't be a Reed-Solomon code. If it's linear, the weight distributions are all the same across (linear) MDS codes for a given length, dimension, and alphabet size. So, I doubt there is an extremely elementary way to distinguish two MDS codes, although I could be wrong. $\endgroup$
    – Yuichiro Fujiwara
    Commented Nov 1, 2013 at 10:47
  • $\begingroup$ Actually I think the following question could provide an upper bound on the complexity? "How many non-isomorphic $[n,k,n-k+1]_q$ MDS codes are there?" $\endgroup$
    – Turbo
    Commented Nov 1, 2013 at 11:02
  • 2
    $\begingroup$ An interesting example are the $[10,5,6]_9$ Glynn codes which are quite different from Reed-Solomon codes, see fma2.math.uni-magdeburg.de/~willems/papers/RS_GL3.ps $\endgroup$
    – Peter Mueller
    Commented Nov 1, 2013 at 11:25
  • 1
    $\begingroup$ Actually does Ghorpade's work tell number of MDS codes or number of non-isomorphic MDS codes? $\endgroup$
    – Turbo
    Commented Nov 1, 2013 at 11:35
3
$\begingroup$

It has been proved by Simeon Ball that for $k \leq p$, all $[n, k, n-k+1]_q$ codes are Reed-Solomon codes, where $q = p^h$. See Corollary 9.2 in the following paper:

Ball, S. On sets of vectors of a finite vector space in which every subset of basis size is a basis. J. Eur. Math. Soc. 14: pp. 733-748 (2012). http://www.ems-ph.org/journals/show_abstract.php?issn=1435-9855&vol=14&iss=3&rank=4

You should also check out the subsequent work done on the MDS conjecture:

Ball S., De Beule J.: On sets of vectors of a finite vector space in which every subset of basis size is a basis II. Des. Codes Cryptogr. 65, 5–14 (2012). http://link.springer.com/article/10.1007/s10623-012-9658-6

Improve this answer
$\endgroup$
0
$\begingroup$

If you have access to explicit constructions of the code, you could use that a $[n, k, n+1-k]$ code $C$ with $k < \frac{n}{2}$ is Reed-Solomon if and only if the dimension of its Schur (coordinate-wise) square $C^{2}$ is $2k-1$. For $k > \frac{n}{2}$ you can use the dual $C^\bot$.

See D. Mirandola and G. Zémor, "Critical Pairs for the Product Singleton Bound," in IEEE Transactions on Information Theory, vol. 61, no. 9, pp. 4928-4937, Sept. 2015. doi: 10.1109/TIT.2015.2450207.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .