Error Correcting Codes and Finite Fields
Math 5251 Fall 2006
MWF 1:25-2:15pm, Ford Hall 151
Instructor: Jonathan Rogness
Office: Vincent Hall 358
Phone: 612-625-3896
Email: rogness@math.umn.edu
Web Page: http://www.math.umn.edu/~rogness/
Course Page: http://www.math.umn.edu/~rogness/math5251/

The fastest, most reliable way to get ahold of me is via email. I have two different offices on campus, so I may not always be in Vincent 358, but I check my email (very) frequently. Please include the number 5251 in the Subject line so your email will get filtered as a high priority message.

Course Description: This course is an introduction to the mathematics behind coding, specifically codes used for data compression, error detection and correction. The plan for the semester includes:
  • Basics of information theory and coding theory
  • Simple compression coding, including Huffman Coding and the Kraft-McMillan inequality.
  • Basic ideas behind error detection and correction, including the Noisy Coding Theorem.
  • Error detecting/correcting codes, with a focus on linear codes. We will also examine bounds on how efficient these codes can be.
  • Cyclic linear codes (Hamming, BCH, Reed-Solomon)
Covering these topics requires reviewing and learning a wide variety of mathematics, including counting, probability, modular arithmetic, various abstract properties and algorithms involving the integers, primitive polynomials, and more! Many of these topics will be tied together when we talk about the structure of finite fields. We won't cover any of these concepts in full detail, but we want enough math to understand why these coding techniques work; they won't just be algorithms which happen to work.

Please note that this is not a course about encrypting information to make it secret (see Math 5248: Cryptology and Number Theory), compression using wavelets (see Math 5467: Introduction to the Mathematics of Image and Data Analysis), or the serious details about implementing these codes (see any number of EE courses, such as 5501, 5581 and 5585). For more about finite fields, groups, and the abstract properties of the integers, consider a course like Math 5286H: Fundamentals of Abstract Algebra.

I should also note that most of the previous instructors of this course haven't covered Goppa codes, based on algebraic codes, even though these objects are sometimes included in the title of the course. If this topic is important to you, let me know (early!), and I may be able to rearrange things so that we can fit in a brief overview.
Prerequisites: Two semesters of sophomore level math. We'll use lots of matrices and vectors, so a solid background in linear algebra is important. Some familiarity with modular arithmetic would be helpful, but isn't necessary.
Textbook: The Mathematics of Coding Theory: Information, Compression, Error Correction and Finite Fields by Paul Garrett, Prentice Hall, 2004.
Homework and Exams: Homework will be due (roughly) every two weeks. Assignments will be announced in class and placed online. Homework will not be accepted after an announced due date unless you've made previous arrangements with me. Collaboration is highly encouraged -- please work with other students! However, your solutions need to be written in your own words, and your homework should include a note saying whom you worked with. Occasionally I'll give a special problem in class which is not required, but might be worth some extra credit.

We'll have in-class two midterms, tentatively scheduled for Wednesday 10/18 and Wednesday 11/15. Our final exam is scheduled for 4:00-6:00pm on Wednesday, 12/20, unless at least 90% of the students in the class vote to have a take-home final instead. Make-up exams will only be permitted in extraordinary situations. (Think "emergency surgery," not "oversleeping.")
Grading Scheme: 50% Homework
30% Midterms (15% each)
20% Final Exam

Overall course grades will be at least this generous; I reserve the right to lower gradelines if a test or homework assignment turns out to be harder than intended.
90%-100%A-, A
80%-89%B-, B, B+
70%-79%C-, C, C+
60%-69%D, D+
Other Policies: We will follow all University and IT policies regarding academic honesty and other matters. The most common situation involves asking for a grade of incomplete. Incompletes are given only in extremely unusual circumstances, and only if you arrange it with me in advance. Incompletes are given only if you have completed most of the course material at a satisfactory level -- at least two midterms at a C level -- but some terrible, unexpected event prevents you from finishing the course. In particular, we cannot give you an incomplete if you simply fall behind in your work.