Math 567: Introduction to Coding Theory (WinterTerm 2014)
Time: Tuesday and Thursday, 1:00 - 2:30 p.m.
Place: 2866 East Hall (on central campus)
Instructor: Jeffrey Lagarias
Office: 3086 East Hall, tel.: 763-1186,
[Tentatively: Tues-Thurs, after class in office, 2:40-3:30pm;
Thursday 5:10-7:00 in basement room B743 East Hall]
(Or by appointment: call or email me)
Good knowledge of linear algebra. Some experience with
discrete probability and abstract algebra is helpful, but
is not required.
Coding theory was invented to facilitate
reliable transmission of information over noisy communication
networks. The basic algebraic and geometric ideas underlying
it are important in a range of pure and
applied questions. In pure mathematics it relates to fundamental
questions concerning densities of sphere packing, lattices,
and the geometry of high dimensional space; in theoretical computer science
codes are used in "holographic proofs," and in engineering applications
coding is used in CD's, wireless networks, satelline transmission
space probes and cellular phones/ smart phones.
To cover some basic information theory and the
foundations of the theory of error-correcting codes.
students its object is to introduce them to an important area of
applications of linear algebra and algebraic structures.
For EECS students its object is to provide
a mathematical setting for their study of communications technology.
Introduction to entropy,
Shannon's theorem and channel capacity. Noiseless coding theorem
and data compression.
Review of tools from
linear algebra and introduction to abstract algebra. Finite
fields and polynomials over finite fields. Basic examples
of codes including Golay, Hamming, BCH,
Reed-Muller and Reed-Solomon codes. New codes from old codes.
Linear codes and cyclic codes. Introduction to decoding including
syndrome decoding and weight enumerators.
Fundamental asymptotic bounds on coding efficiency.
If time permits I hope to cover one addional topic,
depending on the class interests: LDPC codes, concatenated codes
convolutional codes and Viterbi algorithm, data compression and
Lempel-Ziv algorithm, introduction to algebraic geometry
codes, quantum error-correcting codes.
Text: Steven Roman,
Coding and Information Theory,
Graduate Texts in Mathematics 134, Springer-Verlag 1992.
Another useful text: J. H. van Lint,
Introduction to Coding Theory, Third Edition,
Graduate Texts in Mathematics 86, Springer-Verlag 1999.
Here is a
Grading: The course grade
will be based on problem sets (at most eight),
a midterm exam (expected to be in-class) and a
final exam (modified take-home/in-class). The final grade
is expected to be
computed from the
Homework: 55 %
Midterm Exam: 20 %
Modified take-home Final: 25%
Homework problem sets will be given approximately biweekly.