Introduction to data compression

Data compression is one of the most important problems encountered when storing and sending information. Both pure text and encoded sounds and images are transmitted. Security and transmission speed require information to be sent in compressed form. This is the topic devoted to the textbook.
The author explains the concepts of data compression. Describes the methods of coding Shannon, Shannon-Fano, Huffman, arithmetic and dictionary coding, sampling and quantization. He devotes a lot of space to the compression of still images and video images. The issues discussed are illustrated by aptly selected examples. At the end of each chapter there are exercises with solutions, which increases the didactic value of the book.
The book is intended for students of computer science, electronics and telecommunications, who know the basics of algorithm theory and data structures.

Table of Contents

Preface

Chapter 1

Information and coding

1.1.Information and entropy
1.1.1. Properties of entropy
1.2. Noise and non-memory coding
1.2.1. Kraft's inequality
1.2.2. The basic theorem on discrete coding
1.3. Addition: Restrictions of the entropy H function
1.4. Appendix: Tables of the -lgp and -plgp functions

Chapter 2

Shannon-Fano coding

2.1. Shannon coding
2.2. Shannon-Fano coding

Chapter 3

Huffman coding

3.1. Huffman coding with low memory requirements
3.2. Dynamic Huffman coding

Chapter 4

Arithmetic coding

4.1. Implementation of arithmetic coding
4.1.1. Integer implementation

Chapter 5

Dictionary coding

5.1. LZ77 method
5.1.1. The LZSS method
5.2. LZ78 method
5.2.1. LZW method

Chapter 6

Sampling and quantization

6.1. sampling
6.2. quantization
6.2.1. Scalar quantization
6.2.1.1. Even quantization
6.2.1.1.1. Dynamic quantization
6.2.1.2. Quantized quantization
6.2.2. Vector quantization
6.2.2.1. The centroid algorithm
6.2.2.2. Woody book codes
6.3. Appendix: Probability distribution functions

Chapter 7

Predictive coding

7.1. Delta modulation
7.1.1. Dynamic delta modulation
7.1.2. Delay coding and delta modulation
7.2. DPCM method
7.2.1. Dynamic DPCM method
7.2.1.1. Dynamic prediction

Chapter 8

Transforms and coding

8.1. Definition of transform
8.2. Interpretation of transformation
8.2.1. Transform and rotation of coordinate axes
8.2.2. Transform and base matrices
8.3. Karhunen-Loeve transform
8.4. Hadamard's transformation
8.5. Discrete Fourier transform
8.6. Discrete cosine transform
8.7. Discrete wavelet transform
8.8. Appendix: Matrices

Chapter 9

Subband coding

9.1. filters
9.2. Sub-sampling (decimation) and oversampling
9.3. Bit allocation

Chapter 10

Compression of static images: JPEG

10.1. The base system
10.1.1. The format of the source image
10.1.2. Coding based on DCT
10.1.3. quantization
10.1.4. Coding of quantized coefficients
10.1.4.1. Coding of DC coefficients
10.1.4.2. Coding of AC coefficients
10.1.5. Images with many components
10.1.6. Extended sequential system
10.2. Progressive operation mode based on DCT
10.2.1. Spectral selection
10.2.2. Another approximations
10.3. Hierarchical mode
10.4. Sequential, lossless operation mode
10.5. JPEG 2000

Chapter 11

Image compression: MPEG

11.1. MPEG-1
11.1.1. Levels in the MPEG-1 system
11.1.2. Motion compensation and traffic estimation
11.3. MPEG-4 and MPEG-7

Chapter 12

Fourier series and Fourier transform

12.1. Fourier series
12.2. Fourier transform
12.3. Discrete Fourier transform
12.3.1. Discrete cosine transform
12.4. The sampling theorem
12.5. Appendix: Complex numbers and the identity of Euler

Exercise solutions

Index