Course Details
Subject {L-T-P / C} : CS6303 : Information Theory and Coding { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Sambit Bakshi
Syllabus
UNIT-I
Information theory: Concept of amount of information, information units Entropy: marginal, conditional, joint and relative entropies, relation among entropies Mutual information, information rate, channel capacity, redundancy and efficiency of channels Discrete channels – Symmetric channels, Binary Symmetric Channel, Binary Erasure Channel, Noise-Free Channel, Channel with independent I/O, Cascaded channels, repetition of symbols, Binary asymmetric channel, Shannon theorem
UNIT-II
Source coding – Encoding techniques, Purpose of encoding, Instantaneous codes, Construction of instantaneous codes, Kraft’s inequality, Coding efficiency and redundancy, Source coding theorem. Construction of basic source codes – Shannon Fano coding, Shannon Fano Elias coding, Huffman coding, Minimum variance Huffman coding, Adaptive Huffman coding, Arithmetic coding, Dictionary coding – LZ77, LZ78, LZW, ZIP coding Channel coding, Channel coding theorem for DMC
UNIT-III
Codes for error detection and correction – Parity check coding, Linear block codes, Error detecting and correcting capabilities, Generator and Parity check matrices, Standard array and Syndrome decoding, Hamming codes Cyclic codes – Generator polynomial, Generator and Parity check matrices, Encoding of cyclic codes, Syndrome computation and error detection, Decoding of cyclic codes, BCH codes, RS codes, Burst error correction
UNIT-IV
Convolutional codes – Encoding and State, Tree and Trellis diagrams, Maximum likelihood decoding of convolutional codes -Viterbi algorithm, Sequential decoding -Stack algorithm. Interleaving techniques – Block and convolutional interleaving, Coding and interleaving applied to CD digital audio system - CIRC encoding and decoding, interpolation and muting. ARQ – Types of ARQ, Performance of ARQ, Probability of error and throughput
Course Objectives
- To define and apply the basic concepts of information theory (entropy, channel capacity etc.)
- To learn the principles and applications of information theory in communication systems
- To study various data compression methods and describe the most common such methods
- To understand the theoretical framework upon which error-control codes are built
Course Outcomes
At the end of the course, students shall be equipped with the knowledge to:
CO1: quantify the notion of information, entropy, channel capacity in a mathematically sound way and understand its significance in the communications systems.
CO2: differentiate between lossy and lossless compression techniques and decide an efficient data compression scheme for a given information source.
CO3: design communication systems with error control capabilities.
Essential Reading
- T. M. Cover, J. A. Thomas, Elements of Information Theory, Wiley
- S. Lin, D.J. Costello, Error Control Coding: Fundamentals and Applications, Pentice-Hall
Supplementary Reading
- R. J. McEliece, The Theory of Information and Coding, Cambridge Uinversity Press
- R. Bose, Information Theory Coding and Cryptography, Tata McGraw Hill