Balanced Reed-Solomon codes for all parameters
- 27 October 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 409-413
Abstract
We construct balanced and sparsest generator matrices for cyclic Reed-Solomon codes with any length n and dimension k. By sparsest, we mean that each row has the least possible number of nonzeros, while balanced means that the number of nonzeros in any two columns differs by at most one. Codes allowing such encoding schemes are useful in distributed settings where computational load-balancing is critical. The problem was first studied by Dau et al. who showed, using probabilistic arguments, that there always exists an MDS code over a sufficiently large field such that its generator matrix is both sparsest and balanced. Motivated by the need for an explicit construction with efficient decoding, the authors of the current paper showed that the generator matrix of a cyclic Reed-Solomon code of length n and dimension k can always be transformed to one that is both sparsest and balanced, when n and k are such that k/n (n-k+1) is an integer. In this paper, we lift this condition and construct balanced and sparsest generator matrices for cyclic Reed-Solomon codes for any set of parameters.Keywords
This publication has 11 references indexed in Scilit:
- Balanced Reed-Solomon codes2016
- Coding with constraints: Minimum distance bounds and systematic constructions2015
- On Simple Multiple Access NetworksIEEE Journal on Selected Areas in Communications, 2014
- Distributed gabidulin codes for multiple-source network error correction2014
- On the existence of MDS codes over small fields with constrained generator matrices2014
- Balanced Sparsest generator matrices for MDS codes2013
- The Theory of Information and Coding2002
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- Shift-register synthesis and BCH decodingIEEE Transactions on Information Theory, 1969
- Polynomial Codes Over Certain Finite FieldsJournal of the Society for Industrial and Applied Mathematics, 1960