Unit 8: Clever Codes

This is an archived version of this module from Winter 2024-25.

This unit covers techniques to represent information via bits.

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

Learning outcomes

1. Understand the principles of arithmetic coding and where it is applicable.
2. Understand the context of error-prone communication.
3. Understand concepts of error-detecting codes and error-correcting codes.
4. Know and understand the terminology of block codes.
5. Know and understand Hamming codes, in particular (7,4) Hamming code.
6. Reason about the suitability of a code for an application.

Material

• slides

• lecture notes

• Video 8-1 (2024-12-03): §8.1 Arithmetic coding

• Video 8-2 (2024-12-03): §8.2 Practical arithmetic coding

• Video 8-3 (2024-12-03): §8.3 Error correcting codes introduction

• Video 8-4 (2024-12-09): §8.4 Lower bounds for error correcting codes

• Video 8-5 (2024-12-09): §8.5 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):

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

Hamming codes are very nicely explained by 3Blue1Brown:

• Hamming codes and error correction

The code for practical arithmetic coding is taken from

• Moffat, Neal, Witten: Arithmetic Coding Revisited (1998), ACM Transactions on Information Systems

---

Unit 7  ⋅  Syllabus  ⋅  Unit 9