A Caltech Library Service

Balanced Reed-Solomon codes

Halbawi, Wael and Liu, Zihan and Hassibi, Babak (2016) Balanced Reed-Solomon codes. In: 2016 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 935-939. ISBN 978-1-5090-1807-9.

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

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle
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
Caltech President’s FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Subject Keywords:Reed–Solomon Codes, Error-Correcting Codes, Erasure Codes, Distributed Storage, Load Balancing, Welch-Berlekamp Algorithm
Record Number:CaltechAUTHORS:20160823-155622638
Persistent URL:
Official Citation:W. Halbawi, Z. Liu and B. Hassibi, "Balanced Reed-Solomon codes," 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016, pp. 935-939. doi: 10.1109/ISIT.2016.7541436 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69865
Deposited By: Tony Diaz
Deposited On:23 Aug 2016 23:03
Last Modified:11 Nov 2021 04:20

Repository Staff Only: item control page