Coding
Theory
John B. Little, Seminar Leader/Research Advisor
Prerequisites: A solid course in linear
algebra and a course where a student develops skill in reading and
constructing proofs.
Overview: 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.
We will 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 (also the one best adapted to electronic
hardware) is an alphabet with two symbols, the binary digits 0, 1. And
indeed in most applications, for instance in the codes used for the transfer
of digital information within computer systems, and for storing information
on compact disks, digital audio tape, 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 F2,
but the theory is substantially the same if the alphabet is any finite field
Fq. In order to detect and/or correct errors when
they occur, some redundancy must be built into the information that is
actually 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 as that used for the
message itself. Codes obtained in this way are called block codes of
length n over the alphabet Fq.
The proposed seminar for SIMU
2001 would give students a rapid introduction to the theory of block codes
over F2 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 for
Reed-Solomon and BCH codes.
Student research projects will be based on
extensions of some of the topics listed above.
Back to the top.
Computational
Algebra
Reinhard Laubenbacher, Seminar Leader/Research Advisor
Prerequisites: Will be based
on the mathematical background of students accepted to SIMU 2001.
Overview: Computational algebra is a very active and rapidly growing field, with many applications to other areas of mathematics, as well as computer science and engineering. Easily accessible without extensive specialized mathematical expertise, the theory quickly leads to deep research problems as well as realistic applications to other subjects. It is therefore ideally suited to provide undergraduate students with a genuine research experience
in a very limited amount of time. The topics of the seminar are chosen to expose participants to a variety of
subjects, unified by the theme of effective computational methods based on polynomial algebra.
The main goal of the seminar will be to enable participants to engage
in a genuine research project in computational algebra or one of its applications. During the first part of SIMU (2-3 weeks),
we will study basic concepts of computational algebra and some applications within and outside of mathematics. For the remainder
of the seminar students will work on a research project, in groups of three.
For a sample of the types of projects in which
students working in computational algebra will engage, please visit the SIMU 2000 website.
Back to the top.
