Error Correcting Codes

Jim Carlson
August 31, 1999.

Abstract. CDs and digital cell phones give remarkable audio quality, even when the CD is scratched and the air is full of radio static. The technology that makes this possible is based on the mathematics of finite fields that grew out of the work of Gauss published in 1801. The aim of the talk is to explain the technology and the mathematics which makes this possible. mathematics?

Lecture Notes. (PDF File. You'll need Adobe Acrobat Reader for this).

Courses which deal with the mathematics needed to understand error-correcting codes are Math 2270 (Linear Algebra), Math 4300 (Introduction to Algebra), Math 5010 (Introduction to Probability), Math 5310 and 5320 (Introduction to Modern Algebra I and II). You don't need to know everything in these courses to start understanding codes --- see the lecture notes above, or begin looking at the references. The book by Lindsay Childs is especially good.

Basic References

• Childs, Lindsay N., A Concrete Introduction to Higher Algebra. Basics of abstract algebra (rings, fields, etc.). Applications to error-correcting codes (Hamming) and secret codes (RSA).
  
  
• Garding, L. and T. Tambour, Algebra for Computer Science. Just what the title says. Discusses RSA codes, Hamming codes, cyclic codes such as Reed-Solomon. Also shift registers, used to implement these codes, and many other topics.
  
  
• Morgan, Samuel P., Richard Wesley Hamming (1915-1998), in Notices of the American Mathematical Society, vol 45, number 8, pp 972--977. A tribute to the life of Richard Hamming, inventor of the first good error-correcting code. Highly recommended.
  
  
• Ross, Sheldon M., A First Course in Probability. Used in our 5010 course. Excellent, a classic.
  
  

  Advanced References

• Artin, Michael, Algebra. A graduate text on abstract algebra. Excellent and rewarding.
  
  
• Cox, David, John Little, and Donal O'Shea, Using Algebraic Geometry. A basic graduate level text on computational algebraic geometry with applications to coding theory (and a discussion of the famous Goppa codes).
  
  
• Macwilliams F.J. and N.J.A. Sloane, The Theory of Error Correcting Codes. The bible.
  
  
• van Lint, J.H., Introduction to Coding Theory. Proof of Shannon's theorem, a classic on coding theory. Assumes a background in abstract algebra.
  
  
• van Lint, Jacobus H. and Gerard van der Geer, Introduction to Coding and Algebraic Geometry. Discusses the current best codes, which are due to Goppa. These use the algebraic curves over a finite field. The first such were modular curves, like the ones appearing in the proof of the Fermat conjecture.
  
  
• Pless, Vera, Introduction to the Theory of Error Correcting Codes.
  
  
• Welsh, Dominic, Codes and Cryptography. Proof of Shannon's theorem, among other things.