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.
Dept Info
•
Outreach
•
College of Science
•
Newsletter
Department of Mathematics
University of Utah
155 South 1400 East, JWB 233
Salt Lake City, Utah
84112-0090
Tel: 801 581 6851, Fax: 801 581 4148
Webmaster