main page — CS 566 Efficient Algorithms
Unit 8: Clever Codes
This is an archived version of this module from Winter 2025-26.
Click here for the current iteration.
This unit covers techniques to represent information via bits.
- arithmetic coding
- code-distance lower bounds
- parity bits
- Hamming codes
Learning outcomes
- Understand the principles of arithmetic coding and where it is applicable.
- 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 (7,4) Hamming code.
- Reason about the suitability of a code for an application.
Material
- slides
- Video 8-1 (2025-12-02, 22:06):
§8.1 Arithmetic coding
- Video 8-2 (2025-12-02, 16:13):
§8.2 Practical arithmetic beyond trits
- Video 8-3 (2025-12-02, 10:55):
§8.3 Practical arithmetic coding
- Video 8-4 (2025-12-02, 8:47):
§8.4 Error correcting codes introduction
- Video 8-5 (2025-12-08, 23:16):
§8.5 Lower bounds for error correcting codes
- Video 8-6 (2025-12-08, 29:13):
§8.6 Hamming codes
Further reading and sources
The exposition of arithmetic coding and Hamming codes is my own, with heavy inspiration from the following great book on codes (and much more):
Hamming codes are very nicely explained by 3Blue1Brown:
The code for practical arithmetic coding is taken from