A rate-distortion perspective on multiple decoding attempts for Reed-Solomon codes Conference Paper uri icon


  • Recently, a number of authors have proposed decoding schemes for Reed-Solomon (RS) codes based on multiple trials of a simple RS decoding algorithm. In this paper, we present a rate-distortion (R-D) approach to analyze these multiple-decoding algorithms for RS codes. This approach is first used to understand the asymptotic performance-versus-complexity trade-off of multiple error-and-erasure decoding of RS codes. By defining an appropriate distortion measure between an error pattern and an erasure pattern, the condition for a single error-and-erasure decoding to succeed reduces to a form where the distortion is compared to a fixed threshold. Finding the best set of erasure patterns for multiple decoding trials then turns out to be a covering problem which can be solved asymptotically by rate-distortion theory. Next, this approach is extended to analyze multiple algebraic soft-decision (ASD) decoding of RS codes. Both analytical and numerical computations of the R-D functions for the corresponding distortion measures are discussed. Simulation results show that proposed algorithms using this approach perform better than other algorithms with the same complexity. 2009 IEEE.

name of conference

  • 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

published proceedings

  • 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton)

author list (cited authors)

  • Nguyen, P. S., Pfister, H. D., & Narayanan, K. R.

citation count

  • 1

complete list of authors

  • Nguyen, Phong S||Pfister, Henry D||Narayanan, Krishna R

publication date

  • September 2009