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 >= n - 1 provided that n <= 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 <= s - 2 and m <= p - 1 , or e = s - 1 and m<p/2.