## Error-correcting codes, finite fields, algebraic curves

[ambient page updated 28 Nov 10 08:07] ... [ home ] ... [ garrett@math.umn.edu ]

No, I will not be teaching this course in 2004-05

Solutions: [s01] ...[s02] ...[s03] ...[s04] ...[s05] ...[s06] ...[s07] ...[s08] ...[s09] ...[s10] ...[s11]

The text is my "The Mathematics of Coding: Information, Compression, Error Correction, and Finite Fields" (published by Prentice-Hall).

This course is an introduction to basic ideas of information theory, compression, and error-correction. The necessary mathematics developed along the way includes a bit of probability, number theory, and abstract algebra. After a small introduction to probability and information, Shannon's Noiseless Coding Theorem and the Kraft-MacMillan inequality can be discussed, along with Huffman and other efficient coding schemes. The larger part of the course starts with Shannon's Noisy Coding Theorem, and aims at making good error-correcting codes. The historical development of error-correcting codes starts with Hamming codes, and looks at other linear codes such as Reed-Solomon, Bose-Chaudhuri-Hocquengham, and Goppa codes. Construction of codes (not to mention efficient encoding/decoding algorithms) requires that we develop basic facts about finite fields and linear algebra over them. We'll also look at best-possible behavior of codes: Hamming (sphere-packing) bound, Gilbert-Varshamov bound, Singleton bound, etc. If time permits, We'll give an introduction to some very good codes, geometric Goppa codes, attached to algebraic curves, to Turbo Codes, and other special topics.

• Email is the best way to reach me! garrett@ma th.umn.edu

• Office Vincent Hall 353 (north stairwell), phone (612) 624-5012. Phone messages at the math department at (612) 625-2004, but email is best.

• My office hours for this course are MW, 3:00-3:30 (before class) and 5:00-5:30pm (after class), as well as Tuesday 3:30-4:30, or by appointment. Send email anytime!

• Grading: We'll have weekly take-home quizzes (given out Monday, collected two days later on Wednesday), three 1.25-hour in-class exams: Wed Feb 25, Wed Mar 31, Wed May 05 , (NO final) Each exam is a review of the earlier quizzes.

• Of the course grade, each of the three midterms is 19%, and the take-home quizzes are 43%.

• There will also be occasional [ challenge problems ] [updated 05 Apr 04 17:04] intended to both afford some additional entertainment at a higher mathematical level, and to potentially offer some small reward by varying amounts of extra credit. I will grade these myself. The standards for coherence, succinctness, legibility, and other aspects of presentation will be very high. That is, I won't even try to read a proposed solution if it looks garbagey. Usually no partial credit will be given. I will not accept attempted solutions within the last two weeks of the term. You may not work together on these problems.
 A = 93.00-100.0 A- = 90.00-92.99 B+ = 86.67-89.99 B = 83.34-86.66 B- = 80.00-83.33 C+ = 76.67-79.99 C = 73.34-76.66 C- = 70.00-73.33 D+ = 65.00-69.99 D = 60.00-64.99 etc
• When grading in the S/N system, an 'S' is equivalent to a 'C' or better.
• We will follow IT/CLA policies on incompletes, scholastic misconduct, etc.