Bound for MDS Codes

The MDS-code-conjecture states that the only linear orthogonal arrays with index unity and linear MDS-codes (i.e., codes meeting the Singleton bound with equality) are (extended) Reed-Solomon codes, codes from the hyperoval and codes with dimension or codimension equal to 0 or 1, namely repetition codes, parity-check codes, codes without redundancy, and trivial codes.

In other words, the conjecture states that for every linear OA(bm, s,Fb, m) and every linear [s, sm, m + 1]-code over Fb we have

s\begin{displaymath}\begin{cases}\infty & \textrm{if $m\in\{0,1\}$}\\ m+1 & \t… …en and $m\in\{3,b−1\}$}\\ b+1 & \textrm{otherwise.}\end{cases}\end{displaymath}

For m ∈ {0, 1} the bound is trivial. For m ∈ {2, 3} it follows e.g. from the Hamming bound and for mb it can be derived from the Plotkin bound. So the only interesting cases are 4 ≤ mb−1 and therefore b ≥ 5.

Linear [s, sm, m + 1]-codes are equivalent to s-arcs in the projective space PG(m−1, b). Therefore, proving the MDS-code-conjecture is also a problem of finite geometry.

The MDS-code-conjecture is known to be true for all b ≤ 27, with the result for 11 ≤ b ≤ 19 due to [1] and the result for 23 ≤ b ≤ 27 due to [2]. For b = 32 it is known to hold at least for m ≤ 7 (and therefore for m ≥ 27 by considering the dual MDS code), see [3, Table 3.1].

More information on s-arcs can be found in [3, Section 3] and [4].


[1]Jin-Ming Chao and H. Kaneta.
Classical arcs in PG(r, q) for 11 ≤ q ≤ 19.
Discrete Mathematics, 174(1–3):87–94, September 1997.
[2]Jin-Ming Chao and H. Kaneta.
Classical arcs in PG(r, q) for 23 ≤ q ≤ 29.
Discrete Mathematics, 226(1–3):377–385, January 2001.
[3]James W. P. Hirschfeld and Leo Storme.
The packing problem in statistics, coding theory and finite projective spaces: Update 2001.
In Finite Geometries, volume 3 of Developments in Mathematics, pages 201–246. Kluwer Academic Publishers, 2001.
[4]James W. P. Hirschfeld.
Complete arcs.
Discrete Mathematics, 174(1–3):177–184, September 1997.


Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Bound for MDS Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2008-04-04.

Show usage of this method