Teorie informace

Garant předmětu:

Aurél Gábor Gábris

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

The course focuses on the mathematical description of a random message source, its coding and transmission of the source through a noisy channel. The coding problem is addressed probabilistically, the relation of the mean length of the optimal code with the entropy and entropy rate of the random source is emphasized. In the case of the noisy channel we focus on the set of typical sequences and its appropriate coding by self-correcting codes. The course includes a reminder of necessary concepts such as conditional distributions, goodness-of-fit and independence tests, and an introduction to random chains.

Požadavky:

Osnova přednášek:

1. Repetition of probability, random variables and their distribution.

2. Random vectors, multivariate distribution, conditional distribution.

3. Characteristics of random vectors.

4. Distances between distributions, relation to goodness-of-fit tests, tests of independence.

5. Hypothesis testing, tests of independence.

6. Message source, entropy, conditional entropy, relative entropy, mutual information.

7. Differential entropy, maximum entropy principle.

8. Data compression, instantaneous and uniquely decodable codes, Huffman coding, relation to source entropy.

9. Introduction to the Markov chain theory.

10. Entropy and Markov source coding.

11. Information channels, channel capacity.

12. Transmission of a source through the information channel, typical sequences.

13. Simulation of a random message source.

Osnova cvičení:

1. Opakování pravděpodobnosti, náhodné veličiny a jejich rozdělení.

2. Náhodné vektory, vícerozměrné rozdělení.

3. Charakteristiky náhodných vektorů, podmíněné rozdělení.

4. Vzdálenosti mezi rozděleními, testy dobré shody.

5. Testy nezávislosti.

6. Entropie, podmíněná entropie, relativní entropie, vzájemná informace.

7. Princip maximální entropie.

8. Huffmanovo kódování, souvislost s entropií zdroje.

9. Markovské řetězce, markovská podmínka.

10. Entropie a kódování markovského zdroje.

11. Informační kanály, kapacita kanálu.

12. Množina a kódování typických zpráv, Hammingovy kódy.

13. Simulace náhodného zdroje zpráv.

Cíle studia:

The course focuses on the mathematical description of a random message source, its coding and transmission of the source through a noisy channel. The coding problem is addressed probabilistically, the relation of the mean length of the optimal code with the entropy and entropy rate of the random source is emphasized. In the case of the noisy channel we focus on the set of typical sequences and its appropriate coding by self-correcting codes. The course includes a reminder of necessary concepts such as conditional distributions, goodness-of-fit and independence tests, and an introduction to random chains.

Studijní materiály:

1. Cover, T. M., Thomas, J. A.: Elements of Information Theory, 2nd Edition

Wiley-Interscience 2006

ISBN 9780471241959

2. Johnson, J. L.: Probability and Statistics for Computer Science

Wiley-Interscience 2008

ISBN 9780471326724

3. Wilde, M. M.: Quantum Information Theory

Cambridge University Pres 2013

ISBN 9781316809976

Poznámka:

Výuka probíhá v anglickém jazyce.

Další informace:

https://courses.fit.cvut.cz/QNIE-TIN

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: