Unit 8: Error-Correcting Codes

This is an archived version of this module from Fall 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.

Material

• slides

• lecture notes

• Video 8-1 · transcript (2022-12-07, 13:03): §8.1 Error correcting codes introduction
  This is an archive video covering the same material; audio in recording was broken.
  
  Chapters

  0:38 Learning Outcomes
  1:50 Communication
  9:08 Intuition
  
• Video 8-2 · transcript (2022-12-07, 23:15): §8.2 Lower bounds for error correcting codes
  This is an archive video covering the same material; audio in recording was broken.
  
  Chapters

  0:02 Lower Bounds
  1:41 Block Codes
  5:15 Injective Function
  
• Video 8-3 · transcript (2022-12-07, 36:17): §8.3 Hamming codes introduction
  This is an archive video covering the same material; audio in recording was broken.
  
  Chapters

  0:30 Parity Bit
  7:04 Error-correcting codes
  10:14 How to locate errors?
  19:44 4+3 Hamming Code - Decoding
  22:29 Clicker Question
  27:22 4+3 Hamming Code - Properties
  30:17 Hamming Codes - General recipe
  33:03 Outlook
  

---

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):

• MacKay: Information Theory, Inference, and Learning Algorithms (2003), Cambridge University Press

Hamming codes a very nicely explained by 3Blue1Brown:

• Hamming codes and error correction

---

Unit 7  ⋅  Syllabus  ⋅  Unit 9