Data compression

Objectives and outcomes

The lectures and practical classes provide students with a basic knowledge and learning techniques for lossless and lossy compression. Students know the types of data compression and the concept of information damage function. Students know non-destructive compression algorithms – adaptive Huffman coding, Golomb coding, Rice coding, Tunstall coding and arithmetic coding. They understand dictionary-based techniques. Students know the basic techniques of non-destructive compression – scalar and vector quantisation. Furthermore, they know differential coding and delta modulation.

Lectures

Compression techniques. Modelling and coding. Huffman coding. Golomb coding. Rice coding. Tunstall coding. Arithmetic coding. Dictionary-based techniques. Applications: Unix compress, GIF, modem compression v.42 bis. Predictive coding. Dynamic Markov compression. Compression with losses. Distortion criteria. Scalar quantisation. Uniform quantisation. Adaptive quantisation. Non-uniform quantisation. Entropic quantisation. Vector quantisation. Linde-Buzo-Gray algorithm. Structured vector quantisation. Differential coding. DPCM. Delta modulation. Speech coding. Image encoding. Code transformation. Tranform coefficient quantisation and coding. Application to audio signal compression. Application to image compression – JPEG. Subband coding. Application to voice signal coding – G.726. Application to audio signal coding – MPEG audio. Application to image compression. Wavelet compression. Schemes of analysis and synthesis. Video compression. Movement compression. Algorithms for video conferencing and video telephones – H.264. Asymmetric applications – MPEG (1, 2, 4 and 7).

Practical classes

State diagram, stationary state and symbol probabilities, trellis diagram. Properties of binary codes. Statistical coding. Adaptive Huffman algorithm. Golomb coding. Tunstall’s coding. Average codeword length and redundant code. Arithmetic coding and decoding. Adaptive arithmetic coding. Arithmetic coding/decoding with scaling. Dictionary-based coding techniques. Lempel-Ziv 77 (LZ77), Lempel-Ziv 78 (LZ78) and Lempel-Ziv-Welch (LZW) algorithm. Scalar quantization, signal to quantization noise ratio (SQNR). Uniform and a non-uniform scalar quantizer. Mid-rise and mid-tread quantizer. Optimal quantizer, Max-Lloyd’s algorithm. Quantization with companding. A- and μ-companding standards. Vector quantization, mean square quantization error, rate quantizer, Voronoi domains. Differential coding. First-order predictor, optimal prediction coefficient, prediction gain. The relation between PCM and DPCM, bit rate and QSNR. Delta modulation, slope overload.