Description
Time: 2.15-3.15
Title: Error Correction and List Decoding for Reed Solomon Codes
Abstract:
In this talk, we will have a look at three results, starting with the following.
[Berlekamp-Welch] Given a univariate polynomial function over F_q
with data corruption at t < q/2 points, we can recover the function
completely if the degree of the function is sufficiently low.
A generalization of the above is as follows, where instead of
'recovering' the function, we find all its 'close approximates'.
[Madhu Sudan] Given data points (x_i,y_i), i \in [n], and parameters
k and t, we can list all polynomials with degree at most k, which
satisfy at least t data points.
This result can further be generalized as follows.
[Madhu Sudan] Given data points (x_i,y_i) with weights w_i, i \in
[n], and parameters k and W, we can list all polynomials with degree
at most k such that the sum of weights of data points satisfied by the
polynomial is at least W.
The last two results provide list-decoding of Reed-Solomon codes.