Balanced Reed-Solomon codes
Authors:
- 11 August 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 935-939
Abstract
We consider the problem of constructing linear MDS error-correcting codes with generator matrices that are sparsest and balanced. In this context, sparsest means that every row has the least possible number of non-zero entries, and balanced means that every column contains the same number of non-zero entries. Codes with this structure minimize the maximal computation time of computing any code symbol, a property that is appealing to systems where computational load-balancing is critical. The problem was studied before by Dau et al. where it was shown that there always exists an MDS code over a sufficiently large field such that its generator matrix is both sparsest and balanced. However, the construction is not explicit and more importantly, the resulting MDS codes do not lend themselves to efficient error correction. With an eye towards explicit constructions with efficient decoding, we show in this paper 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, for all parameters n and k where k/n (n - k + 1) is an integer.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Coding with constraints: Minimum distance bounds and systematic constructions2015
- On the existence of MDS codes over small fields with constrained generator matrices2014
- A Rank-Metric Approach to Error Control in Random Network CodingIEEE Transactions on Information Theory, 2008
- Lowest density MDS codes over extension alphabetsIEEE Transactions on Information Theory, 2006
- The Theory of Information and Coding2002
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- On lowest density MDS codesIEEE Transactions on Information Theory, 1999
- EVENODD: an efficient scheme for tolerating double disk failures in RAID architecturesIEEE Transactions on Computers, 1995
- 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