Posted by: atri | September 19, 2007

Project 2: Fast decoding of Reed-Solomon codes

Reed-Solomon codes are an important class of algebraic codes. They have many practical applications including their use in CDs and DVDs. These codes also have been the focus of intense theoretical study. For example, these codes have been instrumental in the spurt of research activity in list decoding in the last decade or so (some of which we will cover in the course).

Given its practical and theoretical importance, fast decoding algorithms of Reed-Solomon codes are of paramount importance. Your task in this project is to review literature on very fast implementations of Reed-Solomon decoders.

The first polynomial time algorithm for unique decoding of Reed-Solomon codes was presented by Peterson in 1960, which was before polynomial running time had been accepted as a viable metric for efficiency! Near-linear time unique decoding algorithms are known. For example, see the paper titled The fast decoding of Reed-Solomon codes using Fermat theoretic transforms and continued fractions (IEEE IT 78) by Reed, Scholtz, Truong and Welch.

As far as list decoding algorithms are concerned the first polynomial time algorithm for list decoding Reed-Solomon codes beyond half the distance (for all rates) was designed by Guruswami and Sudan. Near-linear time implementations of their algorithms are also known. For example, see Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes (FOCS 02) by Alekhnovich.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: