List decoding algorithms and their applications to soft-decision decoding of Reed Solomon Codes

Abstract

This dissertation is a review on the recent history regarding soft decision decoding of Reed Solomon Codes. Based on a list decoding approach, Sudan [Sud97a] developed an algorithm whereby through interpolation and factorization of a bivariate polynomial, we are able to decode correctly Reed Solomon codes with errors beyond the Hamming Bound. In fact it could decode correctly Reed Solomon codes with more errors than any previous algorithm, and the solution is found in polynomial time. This algorithm was further improved by Sudan & Guruswami [GS99], who suggested that the algorithm could be applied ±or soft decision decoding. Koetter & Vardy [KV03a] later managed to adapt the algorithm to achieve this goal. Amongst others, current work is being conducted by Parvaresh & Vardy who are attempting to improve on the efficiency of the Koetter & Vardy algorithm.