Reed-Solomon Code

A Reed-Solomon code is a linear code obtained by evaluating polynomials of degree less than over a finite field at distinct field elements. For , it has length , dimension , and minimum Hamming distance , so it is a maximum distance separable code. When the evaluation points are all of , the code is called full-length. The words farthest from a full-length Reed-Solomon code are its deep holes, whose classification is studied by Chen and Huang (2026).

Higher-order maximum-distance-separable conditions impose additional constraints on intersections of column spans of a generator matrix. A code is MDS(3) when, for every three subsets of the columns, the intersection of their linear spans has the same dimension as the corresponding intersection for a generic matrix of the same size, whose entries are algebraically independent over the base field (Chatterjee et al. 2026).

Chatterjee et al. (2026) gave a deterministic construction of MDS(3) Reed-Solomon codes for every . Writing for a suitable quasipolynomial bound, the construction takes time and uses a finite field of size at most .