Math 641/ECE 641, Introduction to Error-Correcting Codes - Spring 2012

Nigel Boston

Contact Information

Telephone: 265-3817, 263-4753.

E-mail: boston@math.wisc.edu

Homepage

Office Hours: Weds 10:45-12:15 (in 3619 EH) and Thurs 10:30-12:00 (in 303 VV); or by appointment.

Text

Other Useful References

My favorite text is Blahut's ``Algebraic Codes for Data Transmission". Another reference book is ``Fundamentals of Error Correcting Codes" by Huffman and Pless. The classical reference was ``The Theory of Error-Correcting Codes" by MacWilliams and Sloane. A comprehensive reference is ``Handbook of Coding Theory" by Pless and Huffman. More recent developments are beautifully covered in ``Modern Coding Theory" by Richardson and Urbanke.

Computational Help

• MAGMA Coding Theory
• GUAVA

Interesting Links

• The Hat Puzzle
• Prize Problem in Coding Theory
• Code Tables
• Coding Theory Conferences

Course Overview

Coding theory is the efficient use of redundancy to ensure the correction of errors in data transmission. It is a marvelous application of clever uses of algebra and combinatorics to problems of practical importance (satellite imagery, scratched CD's). We will follow Barg's excellent course notes - covering topics such as linear codes, Reed-Solomon codes, list decoding, cyclic codes, ensembles of random codes, iterative decoding, belief propagation, and LDPC codes, culminating in describing capacity - achieving codes for the binary erasure channel, which answers a basic question posed by Shannon 60 years ago.

Sections

• Main Lecture: MWF, 9:55-10:45, 3444 Engineering Hall.

Grading Policy

Homeworks will count for 20% of the final grade, the midterms for 20% each, and the final exam for 40%. If you score 90% or higher, you will get an A; if you score 80% or higher, you will at least get a B; if you score 70% or higher, you will at least get a C; if you score 60% or higher, you will at least get a D.

Homework Assignments

Homework will be set most Fridays and due the following Friday. You are encouraged to discuss the exercises with your classmates but the work you hand in should be your own. You will be expected to read the sections of the notes to be covered in advance of class.

Exams

• Midterms - In class, Friday March 9 and Friday April 20.
• Final 12:25-2:25, Weds, May 16.
• Practice Midterm
• Practice Midterm 2