Iterative Algebraic Soft-Decision List Decoding of Reed-Solomon Codes
Mostafa El‐Khamy, Robert J. Mceliece · 2005
Abstract—In this paper, we present an iterative soft-decision decoding algorithm for Reed–Solomon (RS) codes offering both complexity and performance advantages over previously known decoding algorithms. Our algorithm is a list decoding algorithm which combines two powerful soft-decision decoding techniques which were previously regarded in the literature as competitive, namely, the Koetter–Vardy algebraic soft-decision decoding algorithm and belief-propagation based on adaptive parity-check matrices, recently proposed by Jiang and Narayanan. Building on the Jiang–Narayanan algorithm, we present a belief-propagation-based algorithm with a significant reduction in computational complexity. We introduce the concept of using a belief-propagation-based decoder to enhance the soft-input information prior to decoding with an algebraic soft-decision decoder. Our algorithm can also be viewed as an interpolation multiplicity assignment scheme for algebraic soft-decision decoding of RS codes. Index Terms—Belief propagation, interpolation multiplicity, list decoding iterative decoding, maximum-likelihood (ML) decoding, Reed–Solomon (RS) codes, soft-decision decoding. I.