Unit 6: Error-Correcting Codes

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 6-1 · transcript (2023-11-16, 13:43): §6.1 Error correcting codes introduction
  
• Video 6-2 · transcript (2023-11-17, 28:05): §6.2 Lower bounds for error correcting codes
  
• Video 6-3 · transcript (2023-11-17, 29:48): §6.3 Hamming codes introduction
  

---

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 are very nicely explained by 3Blue1Brown:

• Hamming codes and error correction

---

Unit 5  ⋅  Syllabus  ⋅  Unit 7