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.

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.

Description

Ramanujan Hall

Date

Thu, March 23, 2017

Start Time

2:10pm-3:10pm IST

Duration

1 hour

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Mon, March 20, 2017 7:37pm IST