Teorie informace a kódování

Garant předmětu:

Přednášející:

Cvičící:

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).

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A0B01TIK

Požadavky:

Pravděpodobnost, statistika a teorie informace (A0B01PSI),

Diskrétní matematika (A4B01DMA)

Více informací viz. http://math.feld.cvut.cz/gollova/tik.html

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:

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

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