Samoopravné kódy (NMMB304) - informace k přednášce v letním semestru 2017/2018.

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