A list decoding algorithm for practical reed-solomon codes

A novel algorithm is proposed for decoding of Reed-Solomon codes beyond half the minimum distance. This algorithm is based on analytical continuation of the Berlekamp-Massey algorithm through additional iterations. It is shown that the proposed algorithm allows to correct more errors compared to Guruswami-Sudan (GS) algorithm. Also computational complexity of the new algorithm is less than GS algorithm one if number of extra correcting errors (τ) is small. Further complexity reduction is achieved by use of soft decisions. The coding gain of the proposed algorithm is shown for some practical codes.