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 条
  • [1] Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes
    Nielsen, Johan S. R.
    Zeh, Alexander
    DESIGNS CODES AND CRYPTOGRAPHY, 2014, 73 (02) : 507 - 527
  • [2] Guruswami-Sudan Decoding of Elliptic Codes Through Module Basis Reduction
    Wan, Yunqi
    Chen, Li
    Zhang, Fangguo
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2021, 67 (11) : 7197 - 7209
  • [3] Decoding Reed-Solomon Codes Using Euclid's Algorithm
    Shankar, Prill
    RESONANCE-JOURNAL OF SCIENCE EDUCATION, 2007, 12 (04): : 37 - 51
  • [4] Efficient Interpolation in the Guruswami-Sudan Algorithm
    Trifonov, Peter V.
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (09) : 4341 - 4349
  • [5] MODIFIED MINIMUM-WEIGHT DECODING FOR REED-SOLOMON CODES
    MARTIN, I
    HONARY, B
    FARRELL, PG
    ELECTRONICS LETTERS, 1995, 31 (09) : 713 - 714
  • [6] A transform-domain decoding algorithm for Reed-Solomon codes
    Cai, Z. H.
    Hao, J. Z.
    Sun, S. M.
    Chin, P. S.
    Chen, Z. N.
    2006 IEEE INTERNATIONAL CONFERENCE ON ULTRA-WIDEBAND, VOLS 1 AND 2, 2006, : 197 - +
  • [7] Fast Error and Erasure Decoding Algorithm for Reed-Solomon Codes
    Tang, Nianqi
    Chen, Chao
    Han, Yunghsiang S.
    IEEE COMMUNICATIONS LETTERS, 2024, 28 (04) : 759 - 762
  • [8] Decoding Reed-Solomon codes using Euclid’s algorithm
    Priti Shankar
    Resonance, 2007, 12 (4) : 37 - 51
  • [9] A Progressive Interpolation Approach for Guruswami-Sudan Algorithm
    Zhang, Jingwei
    Zhao, Chang-An
    Chen, Li
    Ma, Xiao
    PROCEEDINGS OF 2012 IEEE 14TH INTERNATIONAL CONFERENCE ON COMMUNICATION TECHNOLOGY, 2012, : 1214 - 1218
  • [10] Soft decision decoding of Reed-Solomon codes
    Ponnampalam, V
    Vucetic, B
    IEEE TRANSACTIONS ON COMMUNICATIONS, 2002, 50 (11) : 1758 - 1768
12345