Thursday, September 16, Volen 101, 2:00-3.00 pm
Error-correcting codes are combinatorial objects designed to deal with the problem of noise in information transmission. A code describes how to judiciously add redundancy information that recovers from a small amount of (even malicious) corruption. ``Recovery'' here is interpreted as follows: If a small number, say d, of errors occur, then it is possible to detect that errors have occurred. For an even smaller number, classically d/2, one can even find which locations are in error and fix them.
Among the simplest and yet very efficient error-correcting codes are codes based on properties of low-degree polynomials, called Reed Solomon codes. In this talk we will describe a simple algorithm for recovering from error in Reed Solomon codes. One of the novel features of this algorithm is that it recovers from much more than the above-mentioned bound of d/2 that classical algorithms could tolerate.
Host: Liuba Shrira