Balanced Reed-Solomon codes for all parameters

Wael Halbawi, Zihan Liu, Babak Hassibi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

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.
Original languageEnglish (US)
Title of host publication2016 IEEE Information Theory Workshop (ITW)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages409-413
Number of pages5
ISBN (Print)9781509010905
DOIs
StatePublished - Oct 27 2016
Externally publishedYes

Fingerprint

Dive into the research topics of 'Balanced Reed-Solomon codes for all parameters'. Together they form a unique fingerprint.

Cite this