User Tools

Site Tools


A Rate-Distortion Perspective on Multiple Decoding Attempts for Reed-Solomon Codes

Henry Pfister
School of Engineering, Texas A&M

*Monday*, May 24th, 2010
HED 116

Abstract: 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 design and analyze these multiple-decoding algorithms using tools from rate-distortion (RD) theory. By defining an appropriate distortion measure between (generalized) error patterns and (generalized) erasure patterns, one finds that errors-and-erasures RS decoding succeeds if and only if the distortion is less than a fixed threshold.

Finding the best set of (generalized) erasure patterns turns out to be a covering problem which is solved asymptotically by RD theory. The Blahut-Arimoto algorithm is extended to handle independent non-identical sources and used to find the optimal distribution for the erasure-pattern codebook. Simulation results show that this approach outperforms previous approaches for a fixed number of decoding trials.

Since this approach is asymptotic in the block length, it does not lead to precise theoretical statements for any particular RS code. An extension, based on the rate-distortion exponent (RDE), allows one to directly minimize the exponential decay rate of the error probability. The RDE method enables rigorous bounds on the error probability for finite-length RS codes and modest performance gains are observed via simulation. In this case, the Arimoto algorithm is modified to handle independent non-identical sources and used to find the optimal codebook distribution.

This is joint work with Phong S. Nguyen and Krishna R. Narayanan.

Biography: Henry was born in Redondo Beach, CA and enjoyed an unproductive California youth playing volleyball and surfing.

He received his Ph.D. in electrical engineering from UCSD in 2003 and he joined the faculty of the School of Engineering at Texas A&M University in 2006. Prior to that he spent two years in R&D at Qualcomm, Inc. and one year as a post-doc at EPFL.

He received the NSF Career Award in 2008 and was a coauthor of the 2007 IEEE COMSOC best paper in Signal Processing and Coding for Data Storage.

His current research interests include information theory, channel coding, and iterative decoding with applications in wireless communications and data storage.

Host: Alex Dimakis, dimakis [at]

Back to CommNetS Seminar Page

a_rate-distortion_perspective_on_multiple_decoding_attempts_for_reed-solomon_codes.txt · Last modified: 2016/09/01 19:15 (external edit)