COMPUTER SCIENCE/DISCRETE MATH I | |

Topic: | History of the Theory of Error-Correcting Codes |

Speaker: | Elwyn Berlekamp |

Affiliation: | University of California at Berkeley |

Date: | Monday, April 30 |

Time/Room: | 11:15am - 12:15pm/S-101 |

This subject began in the late 1940s with the opus of Shannon [1948] and the short papers of Hamming [1950] and Golay [1949], followed a decade later by the powerful constructions of Bose-Chaudhuri-Hocquenghem and Reed-Solomon. A variety of techniques, some general, and some very specific, led to a large collection of results on how well code points can be distributed subject to various boundary constraints. The decoding problem motivated the invention of several algorithms, some of which are now used to address a wider variety of problems, such as factoring polynomials. In this talk, I will summarize and review some of the salient results of the latter half of the 20th century. I will also mention some easily-stated problems which remain unsolved.