A modified Guruswami-Sudan algorithm for decoding Reed-Solomon codes

被引：0
作者：
Wang, Xiaorong [1 ]
Shi, Hongbo [1 ]
机构：
[1] Nanjing Univ Finance & Econ, Dept Appl Math, Nanjing 210046, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 22期
关键词：
Reed-Solomon codes; List decoding algorithm; Design of algorithms; Computational complexity; ALGEBRAIC-GEOMETRY;
D O I：
10.1016/j.ipl.2010.08.009
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We tighten a key estimate, which dictates the computational complexity of Guruswami-Sudan algorithm, on the lower bound of the degrees of freedom, and then propose a modified decoding algorithm for Reed-Solomon codes beyond half the minimum distance. The computational complexity of the modified algorithm is lower than the Guruswami-Sudan algorithm for the medium to high rate Reed-Solomon codes, and has the same asymptotic complexity as the algorithm proposed by Wu. Besides we also claim that our modified algorithm outperforms Wu's algorithm to some extent. (C) 2010 Elsevier By. All rights reserved.
引用
收藏
页码：992 / 997
页数：6
相关论文
共 50 条
[41]   Fast En/Decoding of Reed-Solomon Codes for Failure Recovery [J].
Tang, Yok Jye ;
Zhang, Xinmiao .
IEEE TRANSACTIONS ON COMPUTERS, 2022, 71 (03) :724-735
[42]   Subspace Polynomials and Limits to List Decoding of Reed-Solomon Codes [J].
Ben-Sasson, Eli ;
Kopparty, Swastik ;
Radhakrishnan, Jaikumar .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (01) :113-120
[43]   Progressive algebraic Chase decoding algorithms for Reed-Solomon codes [J].
Zhao, Jiancheng ;
Chen, Li ;
Ma, Xiao ;
Johnston, Martin .
IET COMMUNICATIONS, 2016, 10 (12) :1416-1427
[44]   Improved decoding of Reed-Solomon and algebraic-geometry codes [J].
Guruswami, V ;
Sudan, M .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1999, 45 (06) :1757-1767
[45]   Belief propagation decoding of Reed-Solomon codes; a bit-level soft decision decoding algorithm [J].
Kamali, B ;
Aghvami, AH .
IEEE TRANSACTIONS ON BROADCASTING, 2005, 51 (01) :106-113
[46]   Improved probabilistic decoding of interleaved Reed-Solomon codes and folded Hermitian codes [J].
Ozbudak, Ferruh ;
Yayla, Oguz .
THEORETICAL COMPUTER SCIENCE, 2014, 520 :111-123
[47]   Repairing Reed-Solomon Codes [J].
Guruswami, Venkatesan ;
Wootters, Mary .
STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, :216-226
[48]   Balanced Reed-Solomon Codes [J].
Halbawi, Wael ;
Liu, Zihan ;
Hassibi, Babak .
2016 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, 2016, :935-939
[49]   Repairing Reed-Solomon Codes [J].
Guruswami, Venkatesan ;
Wootters, Mary .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2017, 63 (09) :5684-5698
[50]   Twisted Reed-Solomon Codes [J].
Beelen, Peter ;
Puchinger, Sven ;
Rosenkilde, Johan .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2022, 68 (05) :3047-3061
12345