Sparse and balanced reed-solomon and tamo-barg codes

Wael Halbawi, Zihan Liu, Iwan M. Duursma, Hoang Dau, Babak Hassibi

Research output: Contribution to journalArticle

Abstract

We study the problem of constructing balanced generator matrices for Reed-Solomon and Tamo-Barg codes. More specifically, we are interested in realizing generator matrices, for the full-length cyclic versions of these codes, where all rows have the same weight and the difference in weight between any columns is at most one. The results presented in this paper translate to computationally balanced encoding schemes, which can be appealing in distributed storage applications. Indeed, the balancedness of these generator matrices guarantees that the computation effort exerted by any storage node is essentially the same. In general, the framework presented can accommodate various values for the required row weight. We emphasize the possibility of constructing sparsest and balanced generator matrices for Reed-Solomon codes, i.e., each row is a minimum distance codeword. The number of storage nodes contacted once a message symbol is updated decreases with the row weight, so sparse constructions are appealing in that context. Results of similar flavor are presented for cyclic Tamo-Barg codes. In particular, we show that for a code with minimum distance d and locality r , a construction in which every row is of weight d + r - 1 is possible. The constructions presented are deterministic and operate over the codes' original underlying finite field. As a result, efficient decoding from both errors and erasures is possible thanks to the plethora of efficient decoders available for the codes considered.

Original languageEnglish (US)
Article number8478350
Pages (from-to)118-130
Number of pages13
JournalIEEE Transactions on Information Theory
Volume65
Issue number1
DOIs
StatePublished - Jan 2019

Keywords

  • Reed-Solomon codes
  • encoding
  • maintenance engineering
  • polynomials
  • vectors

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Sparse and balanced reed-solomon and tamo-barg codes'. Together they form a unique fingerprint.

  • Cite this