Forums

Maximum distance seperable codes?

Started by Jaco Versfeld 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