main page — COMP 526 Efficient Algorithms
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
- Understand the context of error-prone communication.
- Understand concepts of error-detecting codes and error-correcting codes.
- Know and understand the terminology of block codes.
- Know and understand Hamming codes, in particular 4+3 Hamming code.
- Reason about the suitability of a code for an application.
Material
- slides
- Video 6-1 (2023-11-16):
§6.1 Error correcting codes introduction
- Video 6-2 (2023-11-17):
§6.2 Lower bounds for error correcting codes
- Video 6-3 (2023-11-17):
§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):
Hamming codes are very nicely explained by 3Blue1Brown: