Teorie informace a kódování

Přednášející:

Tomáš Kroupa (gar.), Alena Gollová

Cvičící:

Tomáš Kroupa (gar.), Alena Gollová

Předmět zajišťuje:

katedra matematiky

Anotace:

Předmět seznamuje studenty s matematickými základy zpracování digitální informace. Jsou vyloženy metody efektivního kódování (Lempel-Ziv) a možnosti přenosu informace informačním kanálem (Shannonova věta). Dále jsou uvedeny základy schémat pro sdílení utajené informace (secret sharing schemes). V druhé části je věnována pozornost kódům pro detekci a opravu chyb. V neposlední řadě slouží kurs jako panoráma rozličných matematických partií používaných v teorii informace (teorie pravděpodobnosti, náhodné procesy, ergodická teorie, algebra).

Požadavky:

Pravděpodobnost, statistika a teorie informace (A0B01PSI)

Diskrétní matematika (A4B01DMA)

Osnova přednášek:

1) Entropie, informační divergence, vzájemná informace. Podmíněná entropie a podmíněná informace.

2) Rychlost entropie pro stacionární a ergodické zdroje informace.

3) Univerzální zdrojové kódování. Lempelovy-Zivovy kód.

4) Informační kanál, základní typy kanálů.

5) Kapacita kanálu. Blahutův-Arimotův algoritmus.

6) Shannonova věta o kapacitě kanálu.

7) Úvod do schémat pro sdílení tajemství.

8) Algebraické struktury používané při detekci a opravě chyb. Okruh Z_n, lineární prostory nad tělesem Z_p.

9) Lineární kódy - generující a kontrolní matice. Hammingovy kódy.

10) Polynomy nad Z_p a faktorové okruhy polynomů.

11) Cyklické kódy - generující a kontrolní polynom.

12) Galoisova tělesa, primitivní prvek, charakteristika tělesa.

13) Kořeny cyklických kódů, BCH kódy.

14) Rezerva.

Osnova cvičení:

1) Entropie, informační divergence, vzájemná informace. Podmíněná entropie a podmíněná informace.

2) Rychlost entropie pro stacionární a ergodické zdroje informace.

3) Univerzální zdrojové kódování. Lempelovy-Zivovy kód.

4) Informační kanál, základní typy kanálů.

5) Kapacita kanálu. Blahutův-Arimotův algoritmus.

6) Shannonova věta o kapacitě kanálu.

7) Úvod do schémat pro sdílení tajemství.

8) Algebraické struktury používané při detekci a opravě chyb. Okruh Z_n, lineární prostory nad tělesem Z_p.

9) Lineární kódy - generující a kontrolní matice. Hammingovy kódy.

10) Polynomy nad Z_p a faktorové okruhy polynomů.

11) Cyklické kódy - generující a kontrolní polynom.

12) Galoisova tělesa, primitivní prvek, charakteristika tělesa.

13) Kořeny cyklických kódů, BCH kódy.

14) Rezerva.

Cíle studia:

Porozumění matematickému modelu kódování a přenosu digitální informace.

Studijní materiály:

[1] Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, 2006.

[2] Yeung, R.W.: Information Theory and Network Coding. Springer, 2008.

[3] Adámek, J.: Kódování. SNTL, Praha, 1989.

[4] Vajda, I.: Teorie informace. Vydavatelství ČVUT, 2004.

Poznámka:

Předmět bude vyučován pouze v prezenční formě bez anglické verze.

Další informace:

http://staff.utia.cas.cz/kroupa/?id=3#TIK

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St	místnost T2:C4-364 Kroupa T. Gollová A. 16:15–19:30 (přednášková par. 1) Dejvice Cvicebna
Čt
Pá

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