main page — CS 566 Efficient Algorithms
Unit 8: Clever Codes
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
— to be added —
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