A Caltech Library Service

Balanced Reed–Solomon Codes for All Parameters

Halbawi, Wael and Liu, Zihan and Hassibi, Babak (2016) Balanced Reed–Solomon Codes for All Parameters. In: 2016 IEEE Information Theory Workshop (ITW). IEEE , Piscataway, NJ, pp. 409-413. ISBN 978-1-5090-1091-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Halbawi, Wael0000-0001-5951-7002
Additional Information:© 2016 IEEE. This work was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund, and by King Abdullah University of Science and Technology.
Funding AgencyGrant Number
JPL Director's Discretionary FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Caltech President’s FundUNSPECIFIED
Subject Keywords:Reed–Solomon Codes, Error-Correcting Codes, Erasure Codes, Distributed Storage, Load Balancing, Welch-Berlekamp Algorithm
Record Number:CaltechAUTHORS:20161102-081439051
Persistent URL:
Official Citation:W. Halbawi, Z. Liu and B. Hassibi, "Balanced Reed-Solomon codes for all parameters," 2016 IEEE Information Theory Workshop (ITW), Cambridge, United Kingdom, 2016, pp. 409-413. doi: 10.1109/ITW.2016.7606866
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71677
Deposited By: Ruth Sustaita
Deposited On:02 Nov 2016 15:51
Last Modified:11 Nov 2021 04:49

Repository Staff Only: item control page