Math 5251: Error-correcting codes, finite fields, algebraic curves
Spring 2018: Professor Andrew Odlyzko
Classes: MW 4:00 - 5:15, in Lind 217 (not Vincent 217, as initially stated)
Office Vincent Hall 511
Office hours: Mon 5:30 - 7:00, Tue 2:00 - 5:30, and by appointment. However, always check this web page
before coming over, as on some days the hours may be restricted.
Textbook: "The Mathematics of Coding: Information,
Compression, Error Correction, and Finite Fields" by Paul Garrett.
An electronic copy can be downloaded freely and legally from the author's
If you would like a hard copy, please print this one out, or else buy a used
copy. (This book has not been revised recently, so recent used copies will
be fine. The book is out of print, so there are no brand new copies to purchase.)
Please note that some corrections are available at
You might find useful two books that are available
freely (and legally) online,
A Computational Introduction to Number Theory and Algebra, and
Notes on Coding Theory.
Computer algebra systems (very helpful, but not essential and not required): Maple, Mathematica,
available in Math computer labs, and also (for CSE undergrads) for free downloads at
CSE Labs. One can also do well with the freely
available Web-based Wolfram Alpha, or other systems.
A calculator is advisable, even if you use a computer
algebra system, to reduce the tedium of computations.
Tests: No final, but a term paper (described below) and three 75-minute in-class mid-terms on Wed Feb 14, Wed Mar 28, and Wed May 2 (last class day).
Weekly homework assignments (usually, excluding mid-term days), due (usually) on Wednesdays, first one (a small one) due Jan 24.
Will be posted by the preceding Friday, and will (usually) cover material through the preceding Wednesday.
Always due at the beginning of a class, late homeworks will not be accepted.
If you can't make it to class, you can leave your homework in
my mailbox in Vincent 107, or email it to me (in either typeset or scanned form, in either
case PDF is preferred).
- phone 612-625-5413
- email: firstname.lastname@example.org (preferred and most reliable method)
Special challenge problems: There will be occasional challenge problems for extra credit.
No collaborations are permitted on those.
- You may work with others on homework
problems, but you have to write up your solutions yourself, in your own words, to show you
understand the arguments.
Solutions to homework problems will be available through this site, usually posted the
evening of the day they are due. However, they will not be
live links, but URLs that you will have to paste into your browser to download (to keep
crawlers from downloading and archiving them). These are for your use only, do not put
them up on any web sites, Facebook pages, etc.
Tests will be open book: you may bring books, notes, and calculators, but no smart
phones, iPads, or other communication devices can be used, and you have to do all the work
Term paper: due Mon May 7, by 11:00 am either via email (PDF format strongly preferred) or in my mail box in Vincent 107.
Each of these problems will be worth some number of points towards the
homework score (with fractional credit for partial solutions).
Suppose that the maximal score on all the regular homeworks is x, and you get y points
on those regular homeworks and z on the extra credit ones. Then your final homework score will be
the minimum of x and y+z.
Grades: homework will count for 30%, term project for 15%, the three tests for 15%, 20%, and 20%, respectively.
Expected effort: This is a 4-credit course, so you are expected to devote 12 hours
per week, on average (including lectures).
Solution files for homeworks and midterms are provided for your personal use only. Do not
distribute them via email or posting anyplace.
Scholastic Conduct: Cheating or other misconduct will not be tolerated. The standard University
policies will be followed.
How can music CDs that have been scratched still produce perfect music? How does your smart phone get
the texts and videos? How do spacecraft out past Saturn communicate with Earth? And how do high quality movies fit on DCDs? All these depend on some pretty mathematics that is not too complicated and can be learned with minimal prerequisites, given the willingness to pick up some abstract algebraic, combinatorial, and probabilistic concepts.
- Flexible format, could be done individually or in groups of up to 3.
To encourage collaborative efforts, the maximal score on an individual term paper
will be 80 (as compared to 100 in general).
Expected length 5 to 10 pages, less for an individual effort, more for a group.
to be coordinated with me, typically literature searches on methods used for error-correction
or compression in various settings, with requirement to explain how the material of this course
is (or, often, is not) relevant there. Presentation should be clear, but relatively little weight will
be placed on spelling, grammar, and the like, as this is not a writing-intensive course.
References should be given, with preference to the peer-reviewed literature. Online
references are fine to some extent, with Wikipedia on the borderline, but in all such
cases give the complete URL and date material was downloaded.
Historical material is welcome, but should not dominate, as the point
is to learn some new technical matter, even if not to a great depth.
- A good approach might be to think of the paper as something meant for your
fellow students in the class, teaching them something that was not covered in
the course, but related to it, and doing it in a way that will be understandable based on course
- I will be happy to provide rough feedback on early drafts that are submitted (preferably
in PDF) by 11 am on Fri May 4.
This course develops basic ideas of information theory,
compression, and error-correction. It does not present a comprehensive
coverage of these topics. Instead, the stress is on basic concepts that
have cohesive mathematical foundations.
Homework assignments and other notes:
Material covered on Jan 17: Sections 3.1 and 3.2 of Chapter 3.
Due Wed Jan 17:
Textbook exercise 3.02 (20 pts).
A1. A source emits one of 20 different letters at each time period. You want to encode
the results as a uniquely decodable code of length 2. What is the smallest alphabet
size q that will let you do that? (20 pts)
A2. Find a prefix code over an alphabet of size 4 with word lengths 1, 1, 1, 3, 3, 4, 4, 4, 4, 4. (20 pts)
A3. Extra credit problem (20 pts, remember that no collaborations are allowed on these):
Consider the example presented in class on Wednesday Jan 17:
A source emits A with probability 1/2,
B with probability 1/2 - 1/10^6, and C with probability 1/10^6. Find a way
to do lossless encoding of this source into binary strings that uses only a little bit more
than 1 bit on average per source symbol. (Unlike the setting in class and in the book,
the recipient may
use knowledge of the past outcomes, and may have to wait a while to get
the correct decoding.)
Return to home page