main page  —  COMP 526 Applied Algorithmics

Unit 8: Error-Correcting Codes

This is an archived version of this module from Spring 2022.
Click here for the current iteration.

This unit covers techniques to detect and correct errors in a communication channel:

  • code-distance lower bounds
  • parity bits
  • Hamming codes

Learning outcomes

  1. Understand the context of error-prone communication.
  2. Understand concepts of error-detecting codes and error-correcting codes.
  3. Know and understand the terminology of block codes.
  4. Know and understand Hamming codes, in particular 4+3 Hamming code.
  5. Reason about the suitability of a code for an application.


Further reading and sources

The exposition is based on Leszek Gąsieniec’s material from previous iterations of COMP526 and the following great book on codes (and much more):

Hamming codes a very nicely explained by 3Blue1Brown:

Unit 7  ⋅  Syllabus  ⋅  Unit 9