Abstract.
An (n, k)q-MDS code C over an alphabet A (of size q) is a collection of q k n−tuples over A such that no two words of C agree in as many as k coordinate positions. It follows that n ≤ q + k − 1. By elementary combinatorial means we show that every (6, 3)4-MDS code, linear or not, turns out to be a linear (6, 3)4-MDS code or else a code equivalent to a linear code with these parameters. It follows that every (5, 3)4-MDS code over A must also be equivalent to linear.
1. Introduction
A linear [n, k]-code of minimum distance d satisfies d ≤ n − k + 1–the Singleton bound [10]. A linear [n, k]-code meeting the Singleton bound is called a linear Maximum Distance Separable, or MDS code. Analogously, when no assumptions regarding linearity are made, an (n, k)-MDS code C over an alphabet A of size q (an (n, k)q-MDS code) is a collection of q k n−tuples over A such that no two words of C agree in as many as k coordinate positions. It follows that n ≤ q + k − 1 (with equality only if q is even). Such codes, when they exist may or may not be linear. Linear MDS codes are much studied in the mathematical and engineering sciences (see [5], [10], or [13]). Under the rubric of MDS codes there are many open questions. In particular, very little is known in the nonlinear case.
