Textbook:

• Chapters 5 and 6 of MacKay, D.J.C. (2003). Information theory, inference, and learning algorithms. Cambridge University Press.
  • why/use: After doing lossy compression (chapter 4), we learn about classes of practical algorithms for lossless compression: prefix code (Huffman coding), stream code (Arithmetic coding, Lempel-Ziv coding).

Optional video and lecture note for chapter 5:

• Lecture 8 of Singh, A. (2012). Information Processing and Learning. Lecture notes.
  • why/use: if you want clarification about the transition from fixed length to variable length codes, this lecture note has a table and a justification. It also goes into the difference in the source encoding theorem for symbol codes, building off of the Kraft inequality.
• Reducible (2021). Huffman Codes: An Information Theory Perspective. Reducible on Youtube.
  • why/use: There are other parts of the readings to focus on during class, so the goal is to consolidate knowing why Huffman Code works and how to use it before class. This video reviews why Huffman Code can achieve asymptotic code length given a fixed probability distribution.

Optional lecture note and video for chapter 6:

• mathematicalmonk (2011). (IC 5.1) Arithmetic coding - introduction. mathematicalmonk on Youtube.
  • why/use: if you get stuck on the exercise for applying arithmetic coding, you can refer to this video and the followup (Arithmetic coding - example #1).
• Lecture 9 of Singh, A. (2012). Information Processing and Learning. Lecture notes.
  • why/use: this lecture note goes through example cases of using arithmetic coding. It also briefly connects to universal codes (exemplified by Lempel-Ziv coding).