List Decoding of Locally Repairable Codes

被引：0
作者：
Holzbaur, Lukas [1 ]
Wachter-Zeh, Antonia [1 ]
机构：
[1] Tech Univ Munich, Inst Commun Engn, Munich, Germany
来源：
2018 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) | 2018年
关键词：
locally repairable codes; list decoding; Tamo-Barg codes; REED-SOLOMON;
D O I：
暂无
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We show 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. We give a general list decoding algorithm for LRCs that achieves this radius along with an explicit realization for a class of LRCs based on Reed-Solomon codes (Tamo-Barg LRCs). Further, a probabilistic algorithm for unique decoding of low complexity is given and its success probability analyzed.
引用
收藏
页码：1331 / 1335
页数：5
相关论文
共 13 条
  • [1] On the Locality of Codeword Symbols
    Gopalan, Parikshit
    Huang, Cheng
    Simitci, Huseyin
    Yekhanin, Sergey
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (11) : 6925 - 6934
  • [2] Improved decoding of Reed-Solomon and algebraic-geometry codes
    Guruswami, V
    Sudan, M
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (06) : 1757 - 1767
  • [3] Guruswami V., 2012, EL C COMP COMPL
  • [4] Algorithmic Results in List Decoding
    Guruswami, Venkatesan
    [J]. FOUNDATIONS AND TRENDS IN THEORETICAL COMPUTER SCIENCE, 2006, 2 (02): : 107 - 195
  • [5] A NEW UPPER BOUND FOR ERROR-CORRECTING CODES
    JOHNSON, SM
    [J]. IRE TRANSACTIONS ON INFORMATION THEORY, 1962, 8 (03): : 203 - 207
  • [6] Kamath GM, 2013, IEEE INT SYMP INFO, P1606, DOI 10.1109/ISIT.2013.6620498
  • [7] Kar-Ming Cheung, 1988, MILCOM 88. 21st Century Military Communications - What's Possible? Conference Record. 1988 IEEE Military Communications Conference (IEEE Cat. No.88CH2537-9), P163, DOI 10.1109/MILCOM.1988.13385
  • [8] McEliece R. J., 2003, IPN PROGR REPORT, V42
  • [9] ON THE DECODER ERROR-PROBABILITY FOR REED-SOLOMON CODES
    MCELIECE, RJ
    SWANSON, L
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1986, 32 (05) : 701 - 703
  • [10] Every list-decodable code for high noise has abundant near-optimal rate puncturings
    Rudra, Atri
    Wootters, Mary
    [J]. STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, : 764 - 773
12