Your browser does not support JavaScript!

Performance of Reed–Solomon codes using the Guruswami–Sudan algorithm with improved interpolation efficiency

Performance of Reed–Solomon codes using the Guruswami–Sudan algorithm with improved interpolation efficiency

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

List decoding is a novel method for decoding Reed–Solomon (RS) codes that generates a list of candidate transmitted messages instead of one unique message as with conventional algebraic decoding, making it possible to correct more errors. The Guruswami–Sudan (GS) algorithm is the most efficient list decoding algorithm for RS codes. Until recently only a few papers in the literature suggested practical methods to implement the key steps (interpolation and factorisation) of the GS algorithm that make the list decoding of RS codes feasible. However, the algorithm's high decoding complexity is unsolved and a novel complexity-reduced modification to improve its efficiency is presented. A detailed explanation of the GS algorithm with the complexity-reduced modification is given with simulation results of RS codes for different list decoding parameters over the AWGN and Rayleigh fading channels. A complexity analysis is presented comparing the GS algorithm with our modified GS algorithm, showing the modification can reduce complexity significantly in low error weight situations. Simulation results using the modified GS algorithm show larger coding gains for RS codes with lower code rates, with more significant gains being achieved over the Rayleigh fading channels.


    1. 1)
      • Kotter, R., Vardy, A.: `A complexity reducing transformation in algebraic list decoding of Reed–Solomon codes', Proc. IT Workshop ITW-2003, 31 March–4 April 2003, Paris, France.
    2. 2)
      • Y. Sugiyama , M. Kasahara , S. Hirasawa , T. Namekawa . A method for solving key equations for decoding Goppa codes. Inf. Control , 87 - 99
    3. 3)
    4. 4)
      • R. Kotter , A. Vardy . Algebraic soft-decision decoding of Reed–Solomon codes. IEEE Trans. Inf. Theory , 11 , 2809 - 2825
    5. 5)
    6. 6)
      • G.D. Forney . Generalized minimum distance decoding. IEEE Trans. Inf. Theory , 2 , 125 - 131
    7. 7)
    8. 8)
      • McEliece, R.J.: `The Guruswami–Sudan decoding algorithm for Reed–Solomon codes', IPN Progress Report, 15 May 2003, p. 42–153.
    9. 9)
      • O. Pretzel . (1998) Codes and algebraic curves.
    10. 10)
      • Elias, P.: `List decoding for noisy channels', Technical Report 335, Research Laboratory of Electronics, MIT, 1957.
    11. 11)
      • Cassuto, Y., Bruck, J.: `On the average complexity of Reed–Solomon algebraic list decoder', Proc. 8th IEE/IEEE Int. Symp. on Communication Theory and Applications, July 2005, Ambleside, UK, p. 30–35.
    12. 12)
      • H. Hasse . Theorie der hoheren Differentiale in einem algebraishen Funcktionenkorper mit vollkommenem Konstantenkorper nei beliebeger Charakteristic. J. Reine. Aug. Math. , 50 - 54
    13. 13)
      • W.C. Huffman , V. Pless . (2003) Fundamentals of error-correcting codes.
    14. 14)
      • Wozencraft, J.M.: `List decoding', Research Laboratory of Electronics, MIT 48, 1958, p. 90–95, Quarterly Progress Report.
    15. 15)
      • Kotter, R.: `On algebraic decoding of algebraic–geometric and cyclic codes', 1996, PhD, Linkoping University, Department of Electrical Engineering, Linkoping Studies in Science and Technology, No. 419.
    16. 16)
      • T.K. Moon . (2005) Error correction coding – mathematical methods and algorithms.
    17. 17)
      • R. Kotter . Fast generalized minimum-distance decoding of algebraic–geometric and Reed–Solomon codes. IEEE Trans. Inf. Theory , 3 , 721 - 736
    18. 18)
      • V. Guruswami . (2004) List decoding of error-correcting codes.
    19. 19)
      • I.S. Reed , G. Solomon . Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math. , 300 - 304
    20. 20)
      • D. Cox , J. Little , D. O'Shea . (1992) Ideals, varieties, and algorithms.
    21. 21)
    22. 22)
      • D.M. Mandelbaum . Decoding beyond the designed distance for certain algebraic codes. Inf. Control , 207 - 228

Related content

This is a required field
Please enter a valid email address