MDS codes over finite fields

The mds (maximum distance separable) conjecture claims that a nontrivial linear mds $[n,k]$ code over the finite field $GF(q)$ satisfies $n \leq (q + 1)$, except when $q$ is even and $k = 3$ or $k = q- 1$ in which case it satisfies $n \leq (q + 2)$. For given field $GF(q)$ and any given $k$, series of mds $[q+1,k]$ codes are constructed. Any $[n,3]$ mds or $[n,n-3]$ mds code over $GF(q)$ must satisfy $n\leq (q+1)$ for $q$ odd and $n\leq (q+2)$ for $q$ even. For even $q$, mds $[q+2,3]$ and mds $[q+2, q-1]$ codes are constructed over $GF(q)$. The codes constructed have efficient encoding and decoding algorithms.


Introduction
Background on coding theory and related material made be found in [11] or in [4]. Now GF (q) denotes the finite field of order q and q is necessarily a power of a prime. An [n, k] linear code over GF (q) is a linear code C of length n and dimension k over GF (q).
The minimum distance d of C is bounded by the Singleton bound d ≤ (n + 1 − k). If d = (n + 1 − k), then the code C is termed a maximum distance separable (mds) code. The mds codes are those with maximum error correcting capability for a given length and dimension. MacWilliams and Sloane refer to mds codes in their book [11] as "one of the most fascinating chapters in all of coding theory"; mds codes are equivalent to geometric objects called n-arcs and combinatorial objects called orthogonal arrays, [11], and are, quote, "at the heart of combinatorics and finite geometries".
The mds conjecture is due originally to Segre [12] from 1955. mds conjecture: If C is a nontrivial linear mds [n, k] code over GF (q), then n ≤ (q + 1), except when q is even and k = 3 or k = (q − 1) in which case n ≤ (q + 2).
There is a large literature focusing on this problem, for example see [5,1,13]. Ball showed [2] that the mds conjecture is true for prime fields. For a list of when the conjecture is known to hold for q non-prime, see [6,7] Here for any given finite field GF (q) and any given k, series of mds [q + 1, k] codes over GF (q) are constructed.
Methods in [10] can be adopted to give efficient decoding algorithms; the complexity is max{O(log n), t 2 } where n is the length and t is the error-correcting capability which is ⌊ d−1 2 ⌋ where d is the distance. For even q, it is shown that any [n, 3] mds code and any [n, n − 3] mds code over GF (q) must satisfy n ≤ (q + 2) and for odd q any [n, 3] or [n, n − 3] mds code over GF (q) must satisfy n ≤ (q + 1). For even q, series of [q + 2, 3] mds codes and [q + 2, q − 1] mds codes over GF (q) are constructed.
The mds codes constructed over prime fields are maximum length for the field. The more general case is dealt with separately.

Basics
A primitive n th root of unity in a field F is an element ω such that ω n = 1 but ω i = 1 for 1 ≤ i < n.
See for example [4] or [11] for the following result. A k × n matrix G is the generator matrix of an mds [n, k] code if and only if any k × k submatrix of G has non-zero determinant. Also a k × n matrix is a check matrix of a [n, n − k] mds code if and only if any k × k submatrix has non-zero determinant.
An [n, k] code is an mds code if and only if its dual is an [n, n − k] mds code, [11,4].
Recall the mds codes constructed in [10].
A Fourier matrix is a special type of Vandermonde matrix. Let ω be a primitive n th root of unity in a field F; primitive here means that ω n = 1 and ω i = 1 for 1 ≤ i < n. The Fourier matrix F n , relative to ω and F, is the n × n matrix Simplifications can be made to some of the powers from ω n = 1. An n th root of unity can only exist in a field provided the characteristic of the field does not divide n and in this case n −1 exists.
The inverse of F n can be obtained from the above by multiplying through by n −1 when it exists.
Recall the following from [10]: Theorem 2.1 [10] (i) Let F n be a Fourier n × n matrix over a field F. Let C be a code obtained by choosing in order r rows of F n in arithmetic sequence with arithmetic difference k satisfying gcd(n, k) = 1. Then C is an mds [n, r, n − r + 1] code.
In particular this is true when k = 1, that is, when the r rows are chosen in succession.
(ii) Let C be as in part (i). Then there exist explicit efficient encoding and decoding algorithms for C.
Thus series of mds codes are formed from rows of a Fourier matrix using this unit-derived method developed initially in [9].
It is possible to choose rows which 'wrap over' and still get an mds code as long as the arithmetic difference k between the rows is the same and satisfies gcd(k, n) = 1 -consider row n + i the same as row i.
Some of the methods of [10] are generalizations of those of [8] but the papers are independent.
In particular the following mds codes are formed from a finite field GF (q) by using the primitive (q − 1) root.
Theorem 2.2 (See [10]) Let GF (q) be a finite field and ω a primitive (q − 1) root of unity in GF (q).
Form the Fourier (q − 1) × (q − 1) matrix relative to ω: Then choosing any r rows of F q−1 in arithmetic sequence with difference k satisfying gcd(q − 1, k) = 1 gives a generator matrix for an [q − 1, r] mds code. In particular taking consecutive rows gives an mds code.
Further there exist explicit efficient encoding and decoding algorithms for the codes.
Consider cases where the first r rows are chosen; other cases are similar.
This is a generator matrix for an [q − 1, r] mds code and A is an r × (q − 1) matrix.
Any r × r submatrix of A has non-zero determinant as A generates an mds code.
Now extend the length (q − 1) to (q − 1 + 2) = (q + 1) as follows to obtain an mds code [q + 1, r] code. Extend A by adding on two further r × 1 columns

Theorem 2.3 The matrix B generates an mds
Proof: This is proved by showing that any r × r submatrix of B has non-zero determinant.
If the r × r submatrix is from A, only, then it has non-zero determinant since A generates an mds [q − 1, r] code.
Consider the case where the r × r submatrix P is formed by taking the first column of B together with (r − 1) columns of A.
Evaluate the determinant of P by expanding via the first column and get det(P ) = det(A ′′ ) where A ′′ is an (r − 1) × (r − 1) submatrix of F q−1 with rows in sequence. Then det(A ′′ ) = 0 and so det(P ) = 0.
Similarly the case where an r × r submatrix formed by taking the second column of B with (r − 1) columns of A can be shown to have non-zero determinant.
Expand by first column and get that det submatrix of A with rows in sequence from F n . Now expand by first column and get that det(Q) = ± det(A v ) where A v is from F n with rows in sequence and so det(A v ) = 0. Hence det(Q) = 0 as required.
The result depends on the fact that any (square) y × y submatrix of y rows in sequence of the Fourier matrix have non-zero determinant [8,10]; this requires the {v, w} to have the forms given -with one starting with 1 and the other ending with 1 and all other entries equal to zero.
It is clear from Theorem 2.1 that the A may be chosen by taking r rows of F q−1 in arithmetic sequence with difference k satisfying gcd(k, q − 1) = 1.
Encoding and decoding is obtained by adapting the methods in [10] to the present situation.
Moreover the methods in [10] may be adopted to give efficient encoding and decoding algorithms for the code generated by B. The complexity of this is max{O(n log n), t 2 } where t = ⌊ d−1 2 ⌋ with d(= q − r + 2) is the distance of the mds code [q + 1, r]. Consider r = 4 as an illustration; the construction for a general r is similar.
From the general construction above, the following is an [10,4]  Then add the two columns (1, 0, 0) T , (0, 0, 1) T to the front of A to get a 3 × 10 matrix B which is then a generator matrix for a [10,3] mds code over GF (9).
Choosing {2 nd , 5 th , 8 th , 11 th = 3 rd } rows, by wrapping, to construct A and then add the two columns as before to get B which is then a [10,4] mds code over GF (3 2 ).
There are many choices. There are many other ways that the A could be formed as noted previously and the B is obtained by adding on the two extra columns, one beginning with 1 and the other ending with 1 and all other entries zero. This code is the maximum length code that can be formed from GF (257). Note also that the arithmetic for the codes is modular arithmetic performed in GF (257) = Z 257 and with powers of (3 mod 257) only. Note that efficient encoding and decoding algorithms exist of complexity max{O(n log n, t 2 ) where n = 256, t = ⌊ d−1 2 ⌋ where d is the distance which equals 257 − r.

Even q and dimension 3
Consider GF (q) where q is even.

Sample
Consider GF (2 3 ) initially. Let ω be a primitive 7 th root of unity in GF (8). Let A be the first three rows of the Fourier 7 × 7 matrix formed using ω. 1, 0) T , w = (0, 0, 1) T and A is the first three rows of the Fourier 7 × 7 matrix formed using ω as the primitive 7 th root of unity.
Show that B is an mds [10,3] code over GF (8) as follows. Now any 3 × 3 submatrix of B involving columns of A, only, has non-zero determinant as A generates an mds code, Theorem 2.1, [10].
If any of {u, v, w} with two columns of A are used to form a 3 × 3 submatrix then for it to have a zero determinant it must be that A has a 2 × 2 submatrix with zero determinant. It may be verified that no 2 × 2 submatrix of A has zero determinant directly using Lemma 3.1 below; a direct proof of a more general result which includes this is given in Proposition 3.1.
If a 3 × 3 matrix formed with two of {u, v, w} together with a column of A has a zero determinant then this means that A has a zero element which it doesn't.
Thus B is a generator of an mds [10,3] code.
To form an [10,7] mds code we may take B as the check matrix of a [10,3] code.
There are many choices for a 3 × 10 matrix A from the Fourier matrix and then add on the three columns as noted to get a B which is then a [10, 3] mds code.

General case
Consider GF (2 n ). To construct [2 n + 2, 3] mds codes in GF (2 n ) consider the Fourier F (2 n −1)×(2 n −1) matrix formed using the primitive (2 n − 1) th root of unity ω in GF (2 n ). Take the first three rows, or any three rows in arithmetic sequence with difference k satisfying gcd(k, 2 n − 1) = 1, of this Fourier matrix to form a 3 × (2 n − 1) matrix A, which generates an mds code. Now form the matrix B by adding the three columns of I 3 to the front (or anywhere indeed) of A.
The proof that this B is an [2 n + 2, 3] mds code then reduces to showing that this 3 × (2 n − 1) matrix A from the Fourier matrix has no 2 × 2 submatrix with determinant equal to zero.
Using this 3 × (2 n + 2) matrix B as a check matrix gives a [2 n + 2, 2 n − 1] mds code. It remains to show that a 2 × 2 submatrix formed from second and third row cannot have determinant equal to zero.
These are all different and so by Lemma 3.1 there is no 2 × 2 submatrix from second and third rows with determinant equal to zero. Proof: If the 3 × 3 submatrix is taken from A, only, then know it has non-zero determinant as A generates an mds code. If the submatrix involves one of the first three columns of B then by expanding along this column its determinant is zero if and only if A has a 2 × 2 submatrix whose determinant is zero; by Lemma 3.2 this cannot happen. If it involves two of the first three columns of B then by expansion by these columns in order its determinant is non-zero as A has no zero entry. If it involves all three of the first columns of B then obviously the determinant is 1 and is non-zero. The matrix A in the construction may be formed by taking three rows of the Fourier matrix, as in Proposition 3.1, in arithmetic sequence with difference k satisfying gcd(k, 2 n − 1) = 1. Then adding in the columns of the matrix I 3 gives an mds [2 n + 2, 3] code over GF (2 n ).
By taking the matrix B as the check matrix of a code, an [2 n + 2, 2 n − 1] mds code is obtained.
For even q any [n, 3] mds code over GF (q) must satisfy n ≤ q + 2; this is shown in Proposition 3.2. Thus the [q + 2, 3] mds codes and [q + 2, q − 1] produced here are best possible length over the field GF (q) for those dimensions and even q.
That efficient encoding and decoding methods are available by adapting the methods of [10] is a great advantage. The complexity of encoding and decoding is max{n log n, t 2 } where n is the length and t = ⌊ d−1 2 ⌋ with distance d.

General [n, 3], [n, n − 3]
Suppose G is a generator matrix for an mds [n, r] code. Then the row-reduced echelon form of G is (I r , A). Now all the entries in A must be non-zero for otherwise an r × r submatrix exists with zero determinant.
Theorem 3.1 Let G = (I r , A) be the generator matrix of an [n, r] mds code. Then no j × j submatrix of A has det = 0 for j ≤ r.
In fact: Theorem 3.2 Let G = (I r , A) be the generator matrix of an [n, r] code. The code is an mds code if and only no j × j submatrix of A has det = 0 for j ≤ r.
The proof is not included. 3] is an mds code over GF (q). Then n ≤ (q + 1) when q is odd and n ≤ (q + 2) when q is even.
Proof: Let ω be a primitive element in GF (q) and thus ω is a primitive (q − 1) root of unity. By row operations a generator matrix for the [n, 3] mds code has the form G = ( If any zero appears in A then there exists a 3 × 3 submatrix with determinant equal to zero and then the code would not be an mds code. Hence If there is a repeat in any of the second or third rows then together with a (1, 1) from the first row this gives a 2 × 2 submatrix of A with determinant 0. Thus the second and third rows of the A part of G contain all the elements {1, ω, ω 2 , . . . , ω q−2 } once only.
Thus n ≤ q + 2 in all cases.
No element is repeated in second row and no element is repeated in third row and all powers of ω appear in second and third rows of the A part of G.
Suppose now q is odd and n = q + 2. Then the sum of the powers of ω in rows 2, 3 is congruent to q−1 2 mod q. When subtracting the powers of third row from the powers of the second row above then all the powers must appear or otherwise a 2 × 2 submatrix from second and third rows with determinant 0 is obtained. Thus the subtraction must result in all the powers appearing and hence the sum of these powers is ≡ q−1 2 mod q. But since each of the second and third row sums is ≡ q−1 2 mod q, the subtraction results in powers summing to ≡ 0 mod q. Therefore in all cases there exists a 2 × 2 submatrix of A part with determinant 0. Then G has a 3 × 3 submatrix with determinant 0.
Thus n ≤ q + 1 when q is odd.
In summary then we get the following for dimension 3. Let C be an [n, 3] or an [n, n − 3] mds code over a finite field GF (q). Then