Aims

The aims of the course are to:

• To introduce students to the principles of information theory, data compression, and error-correction, which form the foundations of modern communication and information processing systems.

Objectives

As specific objectives, by the end of the course students should be able to:

• Explain why entropy and channel capacity arise as fundamental limits for data compression and transmission, respectively
• Understand and implement basic compression algorithms such as Huffman coding and Arithmetic coding
• Encode and decode information using simple linear block codes
• Implement decoding algorithms for modern error-correcting codes such as LDPC codes

Content

Information Theory and Data Compression (11L)

1. Probability fundamentals; Definitions of entropy, joint entropy, conditional entropy: interpretations as measures of uncertainty 

2. Noiseless source coding theorem; Significance of entropy as the fundamental limit of compression 

3. Bounds on code length for lossless data compression

4. Practical compression algorithms: Huffman coding, Arithmetic coding

5. Relative Entropy, Mutual Information: Properties and some applications

6. Discrete Memoryless Channels and Channel Capacity

7. The channel coding theorem: Random coding and the direct coding theorem; Fano's inequality and the converse theorem

8. The additive white Gaussian noise (AWGN) channel and its capacity

Channel Coding (Error-correcting codes) (5L)

1. Introduction to block codes; Linear block codes

2. Representing a linear code using a factor graph; Sparse-graph codes

3. Message passing decoding of sparse-graph codes for binary erasure channels

4. The Belief Propagation (BP) algorithm; BP decoding of sparse-graph codes for general binary input channels