15-853: Algorithms in the Real World (Guy Blelloch and Bruce Maggs)

next up
Error Correcting Codes

[ Topics | Readings | Text Books | Links ]

Topic Outline

  • Linear and Hamming codes (modems, memory systems, io/busses)
  • Cyclic and Reed-Solomon codes (CD ROM)

    • Scribe Notes

  • Error Detecting and Correcting Codes (scribe notes by Daniel Maynes-Aminzade and Andrew Faulring).
  • Reed-Solomon Codes (scribe notes by Anton Likhodedov and Trey Smith).
  • Decoding Reed-Solomon Codes (scribe notes by Amitabh Sinha).
  • Tornado Codes (scribe notes by Sonesh Surana, 2000).
  • Tornado Codes (scribe notes by Cha Zhang, 2002).

    • Readings

  • Error-correcting Codes (lecture notes of Steve Linton at U. St Andrews). This gives a reasonably nice overview of linear and Hamming codes.
  • The complexity of error correcting codes. An overview by Dan Spielman. This goes into more theory and gives an overview of some more recent results.

    • Recommended Text Books

  • V. S. Pless (Editor), W. C. Huffman (Editor) and Richard A. Brualdi (Editor). Handbook of Coding Theory, Volume 1 and Volume 2. North-Holland, 1998. (NOTE: These cost $200+ each)
  • Richard E. Blahut Algebraic Codes for Data Transmission. Cambridge Univ. Press, 2001.
  • J. H. Van Lint. Introduction to Coding Theory. Springer Verlag, 1999.
  • Lindsay N. Childs A Concrete Introduction to Higher Algebra. Springer Verlag, 2000.
  • Benjamin Arazi. A Commonsense Approach to the Theory of Error-Correcting Codes. MIT Press, 1988.
  • Macwilliams F.J. and N.J.A. Sloane. The Theory of Error Correcting Codes.
  • Stephen B. Wicker. Error Control Systems for Digital Communication and Storage. Prentice Hall, 1995.
  • Chris Heegard and Stephen B. Wicker. Turbo Coding. Kluwer Academic, 1999.

    • Further Readings and Links

  • Overviews and Surveys
  • Coding Theory: Tutorial and Survey by Madhu Sudan at MIT.
  • The complexity of error correcting codes. An overview by Dan Spielman at MIT.
  • Error-correcting Codes (lecture notes of Steve Linton at U. St Andrews)
  • An Introduction to Error Correcting Codes
  • Error Correcting Codes lecture notes by Jim Carlson at the University of Utah.
  • Courses
  • IMA Summer Program: Codes, Systems and Graphical Models
  • A Crash Course on Coding Theory, Madhu Sudan at MIT.
  • General links
  • Google Category on Coding Theory
  • ECC Technologies, Inc. ECC FAQs
  • Daniel A. Spielman's research on error-correcting codes
  • Turbo codes
  • The Turbo Codes Home page at U. Virginia.
  • The JPL Turbo Code page.
  • Reed-Solomon codes
  • A very brief Understanding Reed-Solomon Error Correction from Multimedia Systems Design Magazine.
  • A very brief survey article by Barry Cipra.
  • A Java demo of Reed Solomon codes.
  • Reed Solomon Codes explained by 4i2i a company that "designs algorithms, components and systems for the communications industry." Here is a local copy.
  • Some other companies that use Reed Solomon codes: Texas Instruments, Radio Design, SciWorx, ECC Technologies, Signion, Xilinx, Altera
  • Convolution Codes
  • A Tutorial on Convolutional Coding with Viterbi Decoding by Chip Fleming of Spectrum Applications.
  • Convolution Codes course notes
    • Back to the Algorithms in the Real World page.
    Guy Blelloch, guyb@cs.cmu.edu.