Data Compression      COMP 423      
Instructor: Professor Michael Langer

The course was offered for final time in Winter 2008.
The notes/etc are here for the benefit of anyone who is interested.

Resources

Course Outline  
Quiz 1 (and solutions ) covered lectures 2 to 9.
Quiz 1 from 2006 and solutions
Quiz 2 (covered lectures 10-16) and Solutions
Quiz 2 (2006) and Solutions
Assignment 1 and C code
Assignment 2
Assignment 3
Exercises 1  and Solutions
Exercises 2 and Solutions
Exercises 3 and Solutions
Final Exam and Solutions
Lecture Schedule

1.  preliminary remarks (no lecture notes)
2.  codes, average code length, optimal prefix codes  (PDF)
3.  Huffman coding   (PDF)
4.  entropy,  Kraft inequality,  Shannon code, upper bd on ave code length  (PDF)
5.  lower bd on ave code length, Jensen’s inequality   (PDF) 
6.  unary code, run length codes, Golomb code   (PDF)
7.  Elias codes   (PDF)
8.  move-to-front    (PDF)
9.  header files (encoding a code)   (PDF)
10.  applications: indexes & inverted files, faxes    (PDF)
11. Lempel-Ziv 1,2,3 (PDF)
12. Lempel-Ziv 3 (best and worst case analysis) (PDF)
13.  joint/marginal/conditional probabilities and entropy, stationarity  (PDF)
14.  Markov chains (PDF)
15.  context modelling via frequency counts (PDF)
16.   prediction by partial match (PPM) (PDF)
17.  arithmetic coding:  intro  (PDF)
18.  arithmetic coding:  induction method  (PDF)


19.  arithmetic coding:  example 1   (PDF)
20.  arithmetic coding:  example 2  (PDF)
21.  arithmetic coding  "on the fly" (PDF)
22.  (lossless) differential coding, transform coding  (PDF)
23.  (lossless) video coding  (PDF)   
24.  intro to lossy compression + quantization  (PDF) 
25.  lossy differential coding  (PDF)
26.  linear predictive coding  (PDF)
27.  transform coding     (PDF)
28.  discrete cosine transform (DCT)    (PDF)  
29.  2D DCT    (PDF)  
30.   JPEG   (and MPEG) (PDF) 
31. spectrograms (PDF) 
32. intro to auditory physiology (PDF)  
33. masking and thresholds (PDF)
34. MP3 (PDF)
35. Review 1: arithmetic coding
36. Review 2: linear predictive coding and transform coding
37. Review 3: image and audio coding