**Coding Theory**

**Math 625**

Course number 21044

Spring 2006

Meeting: TTh, 4:00- 5:15 pm.

GMCS 325

San Diego State University

Final Exam: Tues. May 16, 3:30-5:30.

**Professor**: Mike O'Sullivan

**Email**: m.osullivan@math.sdsu.edu

**Office**GMCS 579, ext. 594-6697

**Office Hours**: MTWTh 2:30-3:30, W 5:15-6:00. (subject to change)

Other times: by appointment.

## Detailed Information

## Course Description

This course concerns error-control coding, the effort to correct
errors that occur in the transmission and storage of data.
We will focus on three types of codes and the algorithms that
are used to decode them:
Reed-Solomon codes and the Berlekamp-Massey algorithm, convolutional
codes and the Viterbi algorithm, low-density parity-check codes and
sum-product algorithm.
The first two codes are ubiquitous in
modern communications systems, while low-density parity-check codes
are a promising alternative that has dominated research conferences in
the last few years.
All three codes were developed in the late 1950's and early 1960's,
but low-density parity-check codes were not appreciated until the last
decade.
These three families of codes lead to a great variety of
interesting mathematics.
The construction and algorithms for encoding and
decoding Reed-Solomon codes employ the algebraic theory of finite fields and
polynomial rings. The code vectors take values in a finite field and
an error switches one field element to another. The Berlekamp-Massey
algorithm computes a polynomial that identifies where the error occured.

There is also a beautiful algebraic theory for convolutional codes,
but in engineering practice the algebraic aspects are minimized.
Convolutional codes are usually binary and they are modeled by circuit
diagrams. Errors are probabilistic: the decoder receives a probability
that a given bit is a 0 or 1. The Viterbi algorithm then attempts to
find the most likely codeword given the input probabilities.

Low-density parity check codes are also studied primarily in the
binary case.
There is a highly efficient decoding algorithm for these codes, based
on probabilistic reasoning, that is similar to the Viterbi algorithm
and to algorithms used in artificial intelligence.
Decoding can be modeled by messages, passed along the edges of a
bipartite graph, that represent ``beliefs'' about the binary values
of a codeword.
Research into LDPC codes is very active and includes analysis of the
decoding algorithm, both experimental and theoretical, and
construction of good codes using a variety of methods, random,
algebraic, geometric, and combinatorial.

## Course Materials

No textbooks cover exactly what I want, so the course will be based on
my lectures and course notes. A list of references
and recommendations for articles and book chapters will be given as
the course develops.
Computer experimentation will be required. You may use Maple, Matlab
or Magma or another system if you'd like.
Mytutorials for Maple and Magma may
be of some help.

Here is the first installment of the notes
Polynomials and Finite Fields

## Grading

There will be several written assignments including computer work
(35 +-5 %), a test (30 +-5%) and a project (20 +- 5%).