Math 567: Introduction to Coding Theory

Time:

Tuesday and Thursday, 11:30 - 1:00 p.m.

Place:

1068 East Hall(on central campus)

Instructor:

Jeffrey Lagarias

Office: 3086 East Hall, tel.: 763-1186,
e-mail: lagarias@umich.edu

Office hours:

Monday 5-6pm in office, 3086 East Hall
Wednesday 5--6pm in office, 3086 East Hall
Thursday 5--6pm in office, 3086 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 and space probes.

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: 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.

  • Errata in Roman's text

    • Another useful text:

    J. H. van Lint, Introduction to Coding Theory, Third Edition Graduate Texts in Mathematics 86, Springer-Verlag 1999.

    Grading:

    The course grade will be based on problem sets (at most eight), a midterm exam (expected to be in-class) and a take-home final exam. The final grade will be computed from the following:

    Homework: 55 %
    Midterm: 20 %
    Take-home Final: 25%

    Homework problem sets will be given biweekly, due at beginning of a class Tuesday. Late homeworks will be penalized.

  • Graded Homework Assignment 1 Due Thursday January 20

  • Graded Homework Assignment 2 Due Thursday February 3

  • Graded Homework Assignment 3 Due Thursday February 17

  • Graded Homework Assignment 4 Due Thursday March 24

  • Clarifications for Homework Assignment 4

  • Graded Homework Assignment 5 Due Thursday April 7

  • Clarifications for Homework Assignment 5

  • Take-Home Midterm Exam Due February 24

  • Hints for Take-Home Midterm Exam

  • Take-Home Final Exam Due Thursday April 21, 5pm (at office)

  • Hints/ Corrections for Final Exam