  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$ provided that $n\leq 2k$, by designing
several algorithms with complexity running in polynomial time in $k$ and $n$.
