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