Aktuálně
- K dispozici jsou typy příkladů, které se mohou objevit v zápočtovém testu.
Základní informace
Sylabus a základní informace viz popis předmětu ve Studijním informačním systému.
Rozvrh (v hrubých rysech k nalezení též v SISu):
- přednáška v úterý 12:20-13:50 hod. v místnosti K6,
- přednáška/cvičení (střídá se po týdnu) v úterý 14:00-15:30 hod. v místnosti K6.
Zkouška
Zkouška je ústní a termíny jsou podle individuální domluvy.
Zápočet
Zápočet bude udělován za úspěšné absolvování zápočtového testu, který se bude konat na posledním cvičení v úterý 15. května. Pro lepší představu jsou ke stažení typy příkladů, které se v testu mohou objevit. V případě nesplnění těchto podmínek mě, prosím, kontaktujte ohledně dalšího postupu.
Co bylo probráno
Zde je uveden orientační seznam probrané látky po jednotlivých přednáškách, včetně odkazů do literatury.
- 20. 2. 2018
- Druhy kódování, základní model komunikačního kanálu, porovnání účinnosti kódování (žádné, opakovací kód, Hammingův kód) na příkladu, Hammingova vzdálenost a Maximum likelihood decoding, parametry kódů a Singletonův odhad, lineární kódy a jejich generující matice, systematické kódy ([Ka], kap. 1 a 3.1, [Dr], kap. 1 a 2).
- 27. 2. 2018
- Každý lineární kód je ekvivalentní systematickému, Hammingova váha, paritní matice, bodový součin a duální kódy, obecný postup pro dekódování lineárních kódů pomocí syndromů, na cvičení binární Hammingovy kódy a jejich parametry ([Ka], kap. 3.1 - 3.3, [Dr], kap. 1 a 2).
- 6. 3. 2018
- Hammingův odhad, perfektní kódy, konstrukce binárních Golayových kódů, tj. samoduálního [24,12,8]-kódu G24 a perfektního [23,12,7]-kódu G23 ([Ka], kap. 4.1 a 4.2, [Dr], kap. 3 a 4).
- 13. 3. 2018
- Tietäväinenova-van Lintova věta o perfektních kódech (bez důkazu), Reed-Mullerovy kódy, jejich parametry a duální kódy k nim, na cvičení dokončení důkazu parametrů binárních Golayových kódů ([Ka], kap. 4.4 a 7.1 - 7.3, [Dr], kap. 6)
- 20. 3. 2018
- Reedův algoritmus na dekódování Reed-Mullerových kódů, MDS kódy, jejich základní vlastnosti a omezení na velikost abecedy, Reed-Solomonovy kódy a jejich parametry ([Ka], kap. 7.4 a 6.1 - 6.3, [Dr], kap. 4, 5 a 6).
- 27. 3. 2018
- Paritní matice Reed-Solomonových kódů, cyklické kódy a jejich interpretace jakožto ideálů okruhu Fq[x]/(xn-1), generující polynom cyklického kódu a jeho určení pro RSq,k ([Ka], kap. 6.2 a 9.1, [Dr], kap. 5 a C).
- 3. 4. 2018
- Paritní matice cyklických kódů, přípravné kroky pro klasifikaci cyklických kódů: rozkladové nadtěleso polynomu xn-1 ∈ Fq[x], minimální polynom prvku rozšíření konečných těles ([Ka], kap. 9.1 a 9.2, [Dr], kap. C).
- 10. 4. 2018
- Cykoltomické třídy a rozklad xn-1 ∈ Fq[x] na ireducibilní činitele, kořeny kódu a kódy zadané pomocí kořenů, cykličnost Hammingových kódů ([Ka], kap. 9.2 a 9.3, [Dr], kap. C).
- 17. 4. 2018
- Generující kořeny cyklických kódů, BCH kódy a odhady jejich parametrů, Gilbert-Varshamovův odhad na dimenzi kódu se zadanou minimální vzdáleností, asymptotické verze Gilbert-Varshamovova, Singletonova a Hammingova odhadu ([Ka], kap. 9.3., 11.1 a 12.1 - 12.4, [Dr], kap. D a 8).
- 24. 4. 2018
- Jednoznačně dekódovatelná a prefixová kódování, McMillanova nerovnost, průměrná délka kódování a entropie jako její dolní odhad, na cvičení Huffmanovo kódování ([Jo], kap. 1, 2.2 a 3.1-3.3).
- 15. 5. 2018
- Shannonovo-Fanovo kódování a horní odhad na průměrnou délku kódování, první Shannonova věta, podmíněné entropie, vzájemná informace dvou náhodných veličin a kapacita kanálu, Shannonova věta o kapacitě kanálu pro binární symetrický kanál ([Jo], kap. 3.4-3.6, 4.1-4.4, 4.6-4.8, 5.4, [Ka], kap. 11, [Dr], kap. 9, důkazu Shannonovy věty pro binární symetrický kanál je též věnován samostatný text k přednášce).
Skripta
Níže jsou odkazy na různá skripta ve formátu PDF, ve kterých se najde drtivá většina z toho, co bylo přednášeno. Upozorňuji ale, že obsah zkoušky se bude primárně řídit obsahem přednášky.
[Ka] | T. Kaiser, Samoopravné kódy, skripta k přednášce na ZČÚ v Plzni, 2011/12. [PDF ke stažení] |
[Dr] | A. Drápal, Samoopravné kódy, skripta k přednášce na MFF UK, 2008/09. Ke stažení po kapitolách: |
Kapitola 1 – Co jsou lineární kódy, Kapitola 2 – Hrátky s maticemi, Kapitola 3 – Designy a konstrukce Golayova kódu, Kapitola 4 – Perfektní a MDS kódy, Kapitola C – Cyklické kódy, Kapitola 5 – GRS a alternantní kódy, Kapitola D – BCH kódy a QR kódy, Kapitola 6 – Reed-Mullerovy kódy, Kapitola 7 – Hadamardovy matice a kódy, a něco odhadů, Kapitola 8 – Asymptotické odhady, Kapitola 9 – Teorie informace. |
|
[Ba] | L. Barto, Konečná tělesa, 2008. [PDF ke stažení] |
Poslední přednášky o teorii informací čerpají z monografie
[Jo] | G. A. Jones, J. M. Jones, Information and coding theory, Springer Undergraduate Mathematics Series, Springer-Verlag London, London, 2000. |
Důkaz Shannonovy věty, který se na přednášce nestihl, je podrobně sepsaný i v textu
[Šť] | J. Šťovíček, Shannonovy věty a jejich důkaz. [PDF ke stažení] |
[Ho] | Š. Holub, Shannonova věta pro binární symetrický kanál. [PDF ke stažení] |
Malý atlas samoopravných kódů
Pro lepší orientaci v tématu je též k dispozici
- Malý atlas kódů - stručný seznam kódů probíraných v rámci této přednášky.