Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

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
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

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
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
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.

© The Institution of Engineering and Technology
Published

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.

Inspec keywords: AWGN channels; channel coding; decoding; Rayleigh channels; Reed-Solomon codes; interpolation

Other keywords: Reed-Solomon codes; interpolation; Guruswami-Sudan algorithm; Rayleigh fading channel; AWGN channel; list decoding algorithm

Subjects: Codes; Radio links and equipment; Interpolation and function approximation (numerical analysis)

References

    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
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com_20060057
Loading

Related content

content/journals/10.1049/iet-com_20060057
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address