Sparse and Balanced MDS Codes over Small Fields
Preprint
Abstract
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$.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Gabidulin Codes With Support Constrained Generator MatricesIEEE Transactions on Information Theory, 2019
- Optimum Linear Codes With Support-Constrained Generator Matrices Over Small FieldsIEEE Transactions on Information Theory, 2019
- Reed–Solomon Codes Over Small Fields With Constrained Generator MatricesIEEE Transactions on Information Theory, 2019
- Sparse and Balanced Reed–Solomon and Tamo–Barg CodesIEEE Transactions on Information Theory, 2018