Coding and information theory

Objectives and outcomes

Lectures and practical classes provide students with a basic knowledge of information theory and coding
in communication systems. Upon completion of the course, students understand the concept of the amount of
information and discrete sources with and without memory. Students know the theory of statistical
coding, Shannon’s first theorem and procedures for obtaining code with a minimum average codeword
length. Students are familiar with discrete memory and memoryless channels. They understand another
Shannon’s theorem and protective coding algorithms – block codes, cyclic codes and convolution codes.

Lectures

Communication system model. The concept of information. Definition of the amount of information.
Discrete memoryless sources. Properties of entropy. Discrete sources with memory. The entropy of the
Markov source. Continuous sources of information. Statistical coding. Kraft inequality. Prefix code.
Compact code. Shannon’s first theorem. Compact code construction methods. Shannon-Fano coding.
Huffman coding. Statistical channel model. Discrete memoryless channels. Discrete channel capacity.
Discrete channels with memory. Continuous channels. Continuous channel capacity. Protective
encryption. Shannon’s second theorem. Probability of error. Hamming distance. Block codes.
Convolutional coding. Viterbi’s algorithm. Basics of trellis coded modulation.

Practical classes

The entropy of discrete memoryless sources. State diagram, stationary state and symbol
probabilities, trellis diagram and entropy of Markov sources. Code properties – singularity, unambiguous
decodability, prefix code, compact code. Huffman coding, code efficiency and compression ratio. Lempel-
Ziv 78 algorithm. Discrete memoryless channel, equivocation, irrelevance, mutual information and
channel capacity. Maximum likelihood (ML) and maximum a posteriori (MAP) decision rule. Linear block
codes, Hamming code, cyclic codes, systematic codes and block diagrams of corresponding encoders
and decoders. Convolutional codes, code rate, code range, trellis diagram, state diagram, transfer
function, free code distance, Viterbi’s algorithm. Systematic convolutional encoder.