Error Decoding of Locally Repairable and Partial MDS Codes

Lukas Holzbaur, Sven Puchinger, Antonia Wachter-Zeh

Research output: Contribution to journalJournal articleResearchpeer-review

3 Downloads (Pure)

Abstract

In this work it is shown that locally repairable codes (LRCs) can be list-decoded efficiently beyond the Johnson radius for a large range of parameters by utilizing the local error-correction capabilities. The new decoding radius is derived and the asymptotic behavior is analyzed. A general list-decoding algorithm for LRCs that achieves this radius is proposed along with an explicit realization for LRCs that are subcodes of Reed--Solomon codes (such as, e.g., Tamo--Barg LRCs). Further, a probabilistic algorithm of low complexity for unique decoding of LRCs is given and its success probability analyzed. The second part of this work considers error decoding of LRCs and partial MDS (PMDS) codes through interleaved decoding. For a specific class of LRCs the success probability of interleaved decoding is investigated. For PMDS codes, it is shown that there is a wide range of parameters for which interleaved decoding can increase their decoding radius beyond the minimum distance with the probability of successful decoding approaching 1, when the code length goes to infinity.
Original languageEnglish
JournalIEEE Transactions on Information Theory
Number of pages27
ISSN0018-9448
DOIs
Publication statusAccepted/In press - 2021

Keywords

  • Locally Repairable Codes
  • List Decoding
  • Partial MDS codes
  • Interleaved Decoding
  • Metzner-Kapturowski

Fingerprint Dive into the research topics of 'Error Decoding of Locally Repairable and Partial MDS Codes'. Together they form a unique fingerprint.

Cite this