Information Theory and Coding

Lecturer: Dr J.G. Daugman (jgd1000@cl.cam.ac.uk)

No. of lectures: 12

Prerequisite courses: Continuous Mathematics, Discrete Mathematics  

Foundations and uncertainty.

How the movements and transformations of information, just like those of a fluid, are law-governed. How signals, channels, encoders and decoders are constrained in how much information they can provide. How the formal concepts of information are grounded in the principles and rules of probability; and how randomness, redundancy, compressibility, noise, bandwidth, and uncertainty are intricately connected to information.

Probability and information measures.

Ensembles, random variables, marginal and conditional probabilities. Bayes' rule. Marginal entropy, joint entropy, conditional entropy, and the Chain Rule for entropy. Mutual information between ensembles of random variables. Why entropy is the fundamental measure of information content.

Coding theorems, channels, and communication capacity.

Shannon's Source Coding Theorem. Prefix, variable-, and fixed-length symbol codes. Capacity of a noiseless discrete channel. Error correcting codes. Perfect communication through a noisy channel. Shannon's Noisy Channel Coding Theorem. Continuous information, signal-to-noise ratio, and power spectral density. Gaussian channels. SNR in frequency bands. The Shannon Limit.

Fourier analysis and information.

Representation of continuous or discrete data by complex exponentials. Fourier series and Fourier transforms in multiple dimensions. Transform pairs and useful theorems. FFT algorithms. Nyquist's sampling theorem; aliasing. The relation between spectral properties and statistical ones. Filters, correlation, modulation, demodulation, and coherence. Wiener analysis and the information in a time-series.

Quantized degrees-of-freedom in signals; complexity.

Why a continuous signal of finite bandwidth and duration has a fixed number of degrees of freedom. The Gabor-Heisenberg-Weyl uncertainty relation. Gabor's optimal expansion basis. Logons. Multi-resolution wavelet codes, and their extensions to images. Minimal description length and Kolmogorov complexity.

Recommended book:

Cover, T.M. & Thomas, J.A. (1991). Elements of Information Theory. New York: Wiley.