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 [J].

Gopalan, Parikshit ;

Huang, Cheng ;

Simitci, Huseyin ;

Yekhanin, Sergey .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (11) :6925-6934

[2] Improved decoding of Reed-Solomon and algebraic-geometry codes [J].

Guruswami, V ;

Sudan, M .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (06) :1757-1767

[3]

Guruswami V., 2012, EL C COMP COMPL

[4] Algorithmic Results in List Decoding [J].

Guruswami, Venkatesan .

FOUNDATIONS AND TRENDS IN THEORETICAL COMPUTER SCIENCE, 2006, 2 (02) :107-195

[5] A NEW UPPER BOUND FOR ERROR-CORRECTING CODES [J].

JOHNSON, SM .

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 [J].

MCELIECE, RJ ;

SWANSON, L .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1986, 32 (05) :701-703

[10] Every list-decodable code for high noise has abundant near-optimal rate puncturings [J].

Rudra, Atri ;

Wootters, Mary .

STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, :764-773

← 1 2 →