A Caltech Library Service

Iterative algebraic soft-decision list decoding of Reed-Solomon codes

El-Khamy, Mostafa and McEliece, Robert J. (2006) Iterative algebraic soft-decision list decoding of Reed-Solomon codes. IEEE Journal on Selected Areas in Communications, 24 (3). pp. 481-490. ISSN 0733-8716. doi:10.1109/JSAC.2005.862399.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2006 IEEE. Manuscript received January 16, 2005; revised April 22, 2005. This work was supported in part by the National Science Foundation (NSF) under Grant CCR-0118670 and in part by grants from Sony, Qualcomm, and the Lee Center for Advanced Networking. This paper was presented in part at the International Symposium on Information Theory and its Applications, Parma, Italy, October 2004. The authors would like to thank J. Jiang and K. Narayanan for providing an extended version of their paper [13]. M. El-Khamy is grateful to M. Kan for confirming many of the simulation results in this paper. They gratefully acknowledge the comments of the anonymous reviewers that have improved the presentation of this paper.
Funding AgencyGrant Number
Caltech Lee Center for Advanced NetworkingUNSPECIFIED
Subject Keywords:Belief propagation, interpolation multiplicity, list decoding iterative decoding, maximum-likelihood (ML) decoding, Reed–Solomon (RS) codes, soft-decision decoding
Issue or Number:3
Record Number:CaltechAUTHORS:ELKieeejsac06
Persistent URL:
Official Citation:El-Khamy, M.; McEliece, R.J.; , "Iterative algebraic soft-decision list decoding of Reed-Solomon codes," Selected Areas in Communications, IEEE Journal on , vol.24, no.3, pp. 481- 490, March 2006 doi: 10.1109/JSAC.2005.862399
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3533
Deposited By: Archive Administrator
Deposited On:13 Jun 2006
Last Modified:08 Nov 2021 19:56

Repository Staff Only: item control page