Decoding of Reed Solomon Codes beyond the Error-Correction Bound

We present a randomized algorithm which takes as inputndistinct points {(xi,yi)}i= 1nfromF×F(whereFis a field) and integer parameterstanddand returns a list of all univariate polynomialsfoverFin the variablexof degree at mostdwhich agree with the given set of points in at leasttplaces (i.e.,yi=f(xi)...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Complexity 1997-03, Vol.13 (1), p.180-193
Main Author: Sudan, Madhu
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a randomized algorithm which takes as inputndistinct points {(xi,yi)}i= 1nfromF×F(whereFis a field) and integer parameterstanddand returns a list of all univariate polynomialsfoverFin the variablexof degree at mostdwhich agree with the given set of points in at leasttplaces (i.e.,yi=f(xi) for at leasttvalues ofi), providedt= Ω(nd). The running time is bounded by a polynomial inn. This immediately provides a maximum likelihood decoding algorithm for Reed Solomon Codes, which works in a setting with a larger number of errors than any previously known algorithm. To the best of our knowledge, this is the first efficient (i.e., polynomial time bounded) algorithm which provides error recovery capability beyond the error-correction bound of a code for any efficient (i.e., constant or even polynomial rate) code.
ISSN:0885-064X
1090-2708
DOI:10.1006/jcom.1997.0439