Sparse and Balanced MDS Codes Over Small Fields.

Maximum Distance Separable (MDS) codes with a sparse and balanced generator matrix are appealing in distributed storage systems for balancing and minimizing the computational load. Such codes have been constructed via Reed-Solomon codes over large fields. In this paper, we focus on small fields. We prove that there exists an $[n,k]_{q}$ MDS code that has a sparse and balanced generator matrix for any $q\geq n-1$ provided that $n\leq 2k$ , by designing several algorithms with complexity running in polynomial time in $k$ and $n$. For the case $n>2k$ , we give some constructions for $q=n=p^{s}$ and $k=p^{e}m$ based on sumsets, when $e\leq s-2$ and $m\leq p-1$ , or $e=s-1$ and $m < \frac {p}{2}$. [ABSTRACT FROM AUTHOR]