Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleKey equations for list decoding of Reed–Solomon codes and how to solve them
Author(s) Peter Beelen, Kristian Brander
TypeArticle in Journal
AbstractA Reed–Solomon code of length n can be list decoded using the well-known Guruswami–Sudan algorithm. By a result of Alekhnovich (2005) the interpolation part in this algorithm can be done in complexity O ( s^4 l^4 n log^2 n loglog n ) , where l denotes the designed list size and s the multiplicity parameter. The parameters l and s are sometimes considered to be constants in the complexity analysis, but for high rate Reed–Solomon codes, their values can be very large. In this paper we will combine ideas from Alekhnovich (2005) and the concept of key equations to get an algorithm that has complexity O ( s l^4 n log^2 n log log n ) . This compares favorably to the complexities of other known interpolation algorithms.
KeywordsGuruswami–Sudan algorithm, Interpolation, List decoding, Reed–Solomon codes
URL http://www.sciencedirect.com/science/article/pii/S0747717110000477
JournalJournal of Symbolic Computation
Pages773 - 786
NoteAlgebraic Coding Theory and Applications
Translation No
Refereed No