Efficient Interpolation in the Guruswami-Sudan Algorithm

Details Efficient Interpolation in the Guruswami-Sudan Algorithm Efficient Interpolation in the Guruswami-Sudan Algorithm

2008-12-29

arxiv.org/abs/0812.4937v3

Computer Science

Information Theory

Submitted to IEEE Transactions on Information Theory

Scientific paper

A novel algorithm is proposed for the interpolation step of the Guruswami-Sudan list decoding algorithm. The proposed method is based on the binary exponentiation algorithm, and can be considered as an extension of the Lee-O'Sullivan algorithm. The algorithm is shown to achieve both asymptotical and practical performance gain compared to the case of iterative interpolation algorithm. Further complexity reduction is achieved by integrating the proposed method with re-encoding. The key contribution of the paper, which enables the complexity reduction, is a novel randomized ideal multiplication algorithm.

Affiliated with

Also associated with

No associations

Rating

Efficient Interpolation in the Guruswami-Sudan Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Interpolation in the Guruswami-Sudan Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Interpolation in the Guruswami-Sudan Algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-449024