Mathematical Sciences Research Institute - MSRI-UP 2009: Coding Theory

Organized By: Ivelisse Rubio (University of Puerto Rico, Humacao), Duane Cooper (Morehouse College), Ricardo Cortez (Tulane University), Herbert Medina (Loyola Marymount University), and Suzanne Weekes (Worcester Polytechnic Insitute).

2007 MSRI-UP 2008 MSRI-UP

Overview of the summer program

The MSRI-UP summer program is designed for undergraduate students who have completed two years of university-level mathematics courses and would like to conduct research in the mathematical sciences.

During the summer, each of the 18 student participants will:

participate in the mathematics research program under the direction of Dr. Little
complete a research project done in collaboration with other MSRI-UP students
give a presentation and write a technical report on his/her research project
attend a series of colloquium talks given by leading researches in their fields
attend workshops aimed at developing skills and techniques needed for research careers in the mathematical sciences and
learn techniques that will maximize a student's likelihood of admissions to graduate programs as well as the likelihood of winning fellowships

After the summer, each student will:

have an opportunity to attend a national mathematics or science conference where students will present their research
be part of a network of mentors that will provide continuous advice in the long term as the student makes progress in his/her studies
be contacted regarding future research opportunities

Topic: Coding Theory

Communication of information often takes place over noisy channels that can corrupt the messages sent over them. For reliability of communication, it is often desirable to encode the transmitted information in such a way that errors can be detected and/or corrected when they occur. Finding methods that achieve error control without introducing undue redundancy, and that admit efficient encoding and decoding, is the main goal of coding theory.

Consider a communications environment in which messages are divided into words or blocks of a fixed length, k, formed using a finite alphabet with q symbols. The simplest case (the one best adapted to electronic hardware) is an alphabet with two symbols, the binary digits 0, 1. Indeed, in the codes used for the transfer of digital information within computer systems, and for storing information on compact disks, or other media and retrieving it for use at a later time, q is either 2 or a power of 2. The alphabet with exactly two symbols can be identified with the finite field , but the theory is substantially the same if the alphabet is any finite field . In order to detect and/or correct errors when they occur, some redundancy must be built into the information that is transmitted over the channel. One possible approach is to make the encoded form of a message consist of blocks or n-tuples of length n>k over the same alphabet used for the message itself. Codes obtained in this way are called block codes of length n over the alphabet.

The summer will start with a quick (2 week) short course giving an introduction to the theory of block codes over and other finite fields including: the Hamming distance, the parameters n,k,d of codes and some elementary bounds (Gilbert-Varshamov, Hamming, Singleton, etc.) on the parameters, linear codes, generator and parity check matrices for encoding and syndrome decoding, some important examples such as Hamming and Golay codes, cyclic codes and associated polynomial algebra, general finite fields, Reed-Solomon and BCH codes, algebraic decoding algorithms.

The basic decoding method for Reed-Solomon codes (leading up to the Berlekamp-Massey algorithm) is designed to correct up to t=[(d-1)/2]=[(n-k)/2] errors in a received word. By results on the error-correcting capacity of a code in terms of its minimum distance, this restriction on the number of errors is necessary if we ask for a method that returns only one closest codeword for each received word. There has been a surge of interest in different algorithms for Reed-Solomon and other codes in recent years.

Starting with work of Sudan in the late 1990’s and followed by work of Guruswami & and Sudan and Roth & Ruckstein, a significant amount of work has been devoted to methods that produce a list of all codewords within some specified distance (possibly >t above) of the received word.

Projects

The bulk of the program will be devoted to work on the projects.

These will be questions in coding theory for which the instructors and assistants have some ideas on how to solve them, but they are open problems. Our past experience has shown that students will provide unexpected insight into these problems.

Each of the research projects will focus on some aspect of one of the following general topics.

Toric Codes -- toric codes are a sort of higher-dimensional generalization of Reed-Solomon codes, defined by polytopes in $R^n$, objects with lots of interesting combinatorial structure and many other applications in different parts of mathematics. They share many of the Reed-Solomon codes' good properties, and they are interesting for several reasons, not the least of which is that there are certain combinations of parameters $n,k,d$ and fields $F_q$ for which the toric construction yields the best known codes. Although there is a substantial amount known about the minimum distance of toric codes, the question of how to find the really good ones is very much open. Several possible project topics will focus in this area.
Algebraic List Decoding Algorithms for Reed-Solomon Codes --
Another group of project topics will deal with the listdecoding methods mentioned above (Guruswami-Sudan, Roth-Ruckstein, and a recent development due to O'Sullivan and Lee.) Different types of projects are possible here -- some dealing with implementation issues and efficiency considerations, some dealing with the theory behind extensions to the algorithms allowing the computation of error values, some with dealing relations to other methods in computational algebra including Gröbner bases, multivariable polynomial interpolation, and so forth.
Professor Little served as seminar leader/research director at the 1998, 1999, and 2001 Summer Institutes in Mathematics for Undergraduates (SIMUs) at the University of Puerto Rico-Humacao, and at the 2007 PREMUR program at the University of Puerto Rico-Mayaguez. He has an active research program and extensive experience in directing undergraduate student research in areas of coding theory, computational commutative algebra, algebraic geometry, and applications. Several projects have led to joint publications with undergraduates.

Complete an on-line application for the 2009 MSRI-UP Summer Program

Follow this link to read about the new U.S. visa requirements

For more information:
Questions about this workshop should be sent either by email to

489@msri.org

or by regular mail to:

MSRI-UP 2009: Coding Theory Mathematical Sciences Research Institute 17 Gauss Way, Berkeley, CA 94720-5070. USA

The Institute is committed to the principles of Equal Opportunity and Affirmative Action.

Back to Workshop Listing

Want to be kept updated on upcoming events? Then Click Here to Subscribe to Our Newsletters!