# Maximum distance seperable codes?

Started by October 7, 2003
```Hi,

Reed-Solomon codes are well-known codes which are also maximum
distance separable (MDS), i.e. the minimum amount of redundancy is
needed to correct errors ( => dmin = 2t+1, where t equals the amount
of correctable errors).

RS codewords have length n, where n equals 2^m - 1 and m defines the
Galois field GF(2^m) in which the code polynomial is defined.  Thus,
the Galois Field have 2^m distinct elements.  Will the amount of
distinct elements in the Galois Field play a role in the maximum
length of MDS codes' codewords of a specific Galois Field?

Thank you very much,
Jaco Versfeld
```
```
Jaco Versfeld wrote:
>
> Hi,
>
> Reed-Solomon codes are well-known codes which are also maximum
> distance separable (MDS), i.e. the minimum amount of redundancy is
> needed to correct errors ( => dmin = 2t+1, where t equals the amount
> of correctable errors).
>
> RS codewords have length n, where n equals 2^m - 1 and m defines the
> Galois field GF(2^m) in which the code polynomial is defined.  Thus,
> the Galois Field have 2^m distinct elements.  Will the amount of
> distinct elements in the Galois Field play a role in the maximum
> length of MDS codes' codewords of a specific Galois Field?
>
> Thank you very much,
> Jaco Versfeld

If I understood you correctly, the answer is 'likely yes'. A 'standard' example
is the following. Assume that your alphabet is a field F of q elements, and
assume that you are interested in linear MDS codes C defined by two check
equations, i.e. the check matrix H of C has two rows, and your code should
have minimum distance 3 (MDS means that the code is at the Singleton bound).
Let n be the length of your code. Then any two of the n columns of H must
be linearly independent. For otherwise, you have two columns that are scalar
multiples of each other. Consequently you get codewords of weight two
contradicting the MDS property. But any vector in F^2 is a scalar multiple
of either (0,1) or (1,x) for some x in F. Thus the maximum number of pairwise
linearly independent vectors is q+1 (there were q choices for x above). Thus
we arrive at the inequality n < q+2.

MacWilliams & Sloane lists the maximum length of a k-dimensional MDS-code (over F)
as an open research problem. In another research problem they "conjecture" (look
up their exact wording) that the maximum length is q+1 except for the cases
k=3,k=q-1, where q=2^m, when the answer should be q+2.

Cheers,

Jyrki Lahtonen, Turku, Finland
```