| A0B01TIK | Teorie informace a kódování | Rozsah výuky: | 4+2s | ||
|---|---|---|---|---|---|
| Garant: | Kroupa T. | Typ předmětu: | V | Zakončení: | Z,ZK |
| Vyučující: | Gollová A., Kroupa T. | ||||
| Zodpovědná katedra: | 13101 | Kreditů: | 8 | Semestr: | L |
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).
Osnovy 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. |
Osnovy 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. |
Literatura:
| [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. |
Požadavky:
Pravděpodobnost, statistika a teorie informace (A0B01PSI)
Diskrétní matematika (A4B01DMA)
|
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 22. 5. 2013, semestry: L/2011-2, L/2012-3, L/2010-1, Z/2011-2, Z/2010-1, Z/2013-4, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |