WiSe 20/21: Data compression
Heiko Schwarz
Comments
Data compression is a technology, which only enables a variety of applications in our information age. Even though the underlying technology is often hidden from the end user, we use data compression every day when we hear music, watch images and videos, or use applications on our smartphone.
In this course, the fundamental and most often used approaches for data compression are introduced. We discuss theoretical foundations as well as methods used in practice.
The first part of the course deals with lossless compression, in which the original data can be reconstructed exactly. This part includes the following topics:
- Unique decodability and prefix codes
- Entropy and entropy rate as theoretical limits of lossless compression
- Optimal codes, Huffman codes
- Arithmetic coding
- Lempel-Ziv coding
- Linear prediction
- Examples from text, image and audio compression
In the second part of the course, we consider lossy compression, by which only an approximation of the original data can be reconstructed. This type of compression enables much higher compression rates and is the dominant form of compression for audio, image and video data. The second part of the course includes the following topics:
- Scalar quantization, optimal scalar quantization
- Theoretical limits of lossy compression: Rate distortion functions
- Vector quantization
- Predictive quantization
- Transform coding
- Examples from audio, image, and video compression
Suggested reading
- Sayood, K. (2018), “Introduction to Data Compression,” Morgan Kaufmann, Cambridge, MA.
- Cover, T. M. and Thomas, J. A. (2006), “Elements of Information Theory,” John Wiley & Sons, New York.
- Gersho, A. and Gray, R. M. (1992), “Vector Quantization and Signal Compression,” Kluwer Academic Publishers, Boston, Dordrecht, London.
- Jayant, N. S. and Noll, P. (1994), “Digital Coding of Waveforms,” Prentice-Hall, Englewood Cliffs, NJ, USA.
- Wiegand, T. and Schwarz, H. (2010), “Source Coding: Part I of Fundamentals of Source and Video Coding,” Foundations and Trends in Signal Processing, vol. 4, no. 1-2.
15 Class schedule
Regular appointments