On the Structure of Higher Order MDS Codes

A code of length $n$ is said to be (combinatorially) $(\rho ,L)$-list decodable if the Hamming ball of radius $\rho n$ around any vector in the ambient space does not contain more than $L$ codewords. We study a recently introduced class of higher order MDS codes, which are closely related (via duality) to codes that achieve a generalized Singleton bound for list decodability. For some $\mathrm{\ell }\ge 1$, higher order MDS codes of length $n$, dimension $k$, and order $\mathrm{\ell }$ are denoted as $(n,k)$-MDS($\mathrm{\ell }$) codes. We present a number of results on the structure of these codes, identifying the `extend-ability’ of their parameters in various scenarios. Specifically, for some parameter regimes, we identify conditions under which $(n_1,k_1)$-MDS(${\mathrm{\ell }}_1$) codes can be obtained from $(n_2,k_2)$-MDS(${\mathrm{\ell }}_2$) codes, via various techniques. We believe that these results will aid in efficient constructions of higher order MDS codes. We also obtain a new field size upper bound for the existence of such codes, which arguably improves over the best known existing bound, in some parameter regimes.