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