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,
e-mail: lagarias@umich.edu

Office hours:

[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)

Prerequisite:

Good knowledge of linear algebra. Some experience with discrete probability and abstract algebra is helpful, but is not required.

Background:

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.

Course objective:

To cover some basic information theory and the foundations of the theory of error-correcting codes. For mathematics 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.

Course description:

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

  • 2014 Syllabus

    • 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 following:

    Homework: 55 %
    Midterm Exam: 20 %
    Modified take-home Final: 25%

    Homework problem sets will be given approximately biweekly.