Repairing Reed-Solomon Codes via Subspace Polynomials

Son Hoang Dau, Thi Xinh DInh, Han Mao Kiah, Tran Thi Luong, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review

Abstract

We propose new repair schemes for Reed-Solomon codes that use subspace polynomials and hence generalize previous works in the literature that employ trace polynomials. The Reed-Solomon codes are over mathbb {F}_{{q}{ell }} and have redundancy {{r}} = {{n}}-{{k}} geq {{q}}{{m}} , 1leq {{m}}leq ell , where {{n}} and {{k}} are the code length and dimension, respectively. In particular, for one erasure, we show that our schemes can achieve optimal repair bandwidths whenever {{n}}={{q}}ell and {{r}} = {{q}}{{m}} , for all 1 leq {{m}} leq ell . For two erasures, our schemes use the same bandwidth per erasure as the single erasure schemes, for ell /{{m}} is a power of {{q}} , and for ell ={{q}}{{a}} , {{m}}={{q}}{{b}}-1>1 ( {{a}} geq {{b}} geq 1 ), and for {{m}}geq ell /2 when ell is even and {{q}} is a power of two.

Original languageEnglish (US)
Pages (from-to)6395-6407
Number of pages13
JournalIEEE Transactions on Information Theory
Volume67
Issue number10
DOIs
StatePublished - Oct 2021

Keywords

  • Reed-Solomon code
  • distributed storage system
  • erasure codes
  • repair bandwidth
  • subspace polynomial

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Repairing Reed-Solomon Codes via Subspace Polynomials'. Together they form a unique fingerprint.

Cite this