Sparse and Balanced MDS Codes Over Small Fields
- 25 March 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (8) , 5112-5125
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-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}$ .Keywords
All Related Versions
Funding Information
- NSFC (12171452, 11771419)
- Anhui Initiative in Quantum Information Technologies (AHY150200)
- National Key Research and Development Program of China (2020YFA0713100)
This publication has 21 references indexed in Scilit:
- An algebraic-combinatorial proof technique for the GM-MDS conjecture2017
- Cooperative data exchange based on MDS codes2017
- Balanced Reed-Solomon codes for all parameters2016
- Balanced Reed-Solomon codes2016
- On Simple Multiple Access NetworksIEEE Journal on Selected Areas in Communications, 2014
- Weakly secure data exchange with Generalized Reed Solomon codes2014
- On the existence of MDS codes over small fields with constrained generator matrices2014
- Distributed reed-solomon codes for simple multiple access networks2014
- Balanced Sparsest generator matrices for MDS codes2013
- Advanced determinant calculus: A complementLinear Algebra and its Applications, 2005