Sparse and Balanced MDS Codes Over Small Fields
Tingting Chen, Xiande Zhang · IEEE Transactions on Information Theory · 2022
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}$.