Samoopravné kódy


Průběh přednášky

  1. týden:
       (3.3.) 0.Motivace a cíle přednášky. Co znamená a jak lze matematicky modelovat úkol efektivního a bezztrátového přenosu informace prostřednictvým kanálu ze zdroje k příjemci? 1.Vzdálenost a nosnost blokového kódu. Blokový kód délky n, vzdálenost a váha kódu, detekce a oprava chyby [D, 1.2-1.3].
       (4.3.) Nosnost kódu, velikost koule v prostoru Fn. Hammingova nerovnost a perfektní kódy [D, 4.1], Singletonův odhad [K, 1.7.1-2], pojem MDS-kódu, příklady (paritní a triviální kódy). Permutační ekvivalence kódů.
  2. týden:
       (10.3.) 2.Lineární kódy. Generující a kontrolní matice lineárního kódu. standardní tvar generující matice [D, 1.1], výpočet vzdálenosti lineárního kódu pomocí kontrolní matice [D, 1.4, 2.6]. Bodový součin a duální kódy [D, 2.1-2.5].
  3. týden:
       (17.3.) 3.MDS-kódy. Charakterizace lineárních MDS-kódů, vztah dimenze, vzdálenosti a velikosti tělesa lineárních MDS kódů [D, 2.8, 4.5-6]. Příklady netriviálních lineárních MDS-kódů.
       (18.3.) 4.Samoduální a propíchnuté kódy. Propíchnutí MDS kódu [D, 3.10, 4.7]. Samoortogonální, samoduální a dvojnásobně sudé kódy [D, 2.9-2.14].
  4. týden:
       (24.3.) 5.Cyklické kódy. Popis lineárních cyklických kódů jako ideálů okruhu F[x]/(xn-1). Generující a kontrolní matice lineárního cyklického kódu.
  5. týden:
       (31.3.) 6. GRS kódy a jejich reziduální kódy Zobecněné Reed-Solomonovy kódy. Generující matice Reed-Solomonových kódů [D, část 5]. Konstrukce kontrolní matice GRS-kódu. Cyklické kódy dané nulovými body polynomů a Reed-Solomonovy kódy [K, 6.2]. Reziduální kódy, konstrukce kódů o zaručené vzdálenosti (designed distance) [D, 5.2, D.1-3].
       (1.4.) 7.Úvod do teorie informace. Diskrétní pravděpodobností prostor [Ko, část 1.]. Diskrétní náhodná veličina a r-ární entropie náhodné veličiny. Združená entropie a nezávislost náhodných veličin [Ko, 3.1-3.4].
  6. týden:
       (7.4.) 8.Diskrétní informační kanál Podmíněná entropie a vzájemná informace [Ko, 3.5-3.8]. diskrétní informační kanál bez paměti, vzájemná informace vstupu a výstupu a kapacita kanálu. Kapacita binárního symetrického kanálu a entropická funkce.
  7. týden:
       (14.4.) 9.Kódování zdroje. Prosté a prefixové kódování informačního zdroje, prefixové kódování je nutně prosté. Průměrná délka kódování. Kritérium existence prefixového kódů s danými délkami kódových slov (Kraftova věta). a Shanonovo-Fanovo kódování. Průměrná délka kódování a entropie informačního zdroje.
       (15.4.) První Shannonova věta. Existence optimálního kódování. Konstrukce Huffmanova r-árního kódování.
  8. týden:
       (20.4.) 10.Dekódovací schéma. Blokové kódování a jeho nosnost (informační poměr), přenos kódovaného zdroje informačním kanálem, metoda nejbližšího slova je ML dekódovací schéma. Maximální a uniformní pravděpodobnost chyby dekódovacího schématu. [H], [Š], [D, část Teorie informace]
  9. týden:
       (27.4.) 11.Shannonovy věty o kapacitě kanálu. Důsledky slabého zákona velkých čísel. Odhad velikosti binární koule pomocí entropické funkce. Shannonova hlavní věta teorie informace [H], [Š], [D, část Teorie informace]
       (28.4.) Doknčení důkazu Shannonovy věty, Inverzní Shannonova věta. [H], [Š], [D, část Teorie informace].
  10. týden:
       (6.5.) 12. Symetrické designy. Nutné podmínky pro parametry 2-(n,k,l)-designů, Fanova rovina, matice incidence [D, 3.1-3]. Charakterizace symetrických 2+designů [D, 3.4-6]. Permutace na S5 a neorientované grafy na pěti vrcholech, konstrukce 2-[11,5,2]-desgnů [D, 3.7].
  11. týden:
       (13.5.) 13. Golayovy perfektní kódy. Existence a jednoznačnost 2-[11,5,2] a 2-[11,6,3]-designů [D, 3.8-9]. Existence a jednoznačnost lineárního dvojnásobně sudého samoduálního [24,12,8]2 kódu a existence 3-perfektního Golayova [23,12,7]2 kódu.
  12. týden:
       (19.5.) Jednoznačnost 3-perfektního Golayova kódu délky 23. 14. Reed-Mullerovy kódy. Konstrukce [K, části 7.1 a 7.2], dimenze a vzdálenost Reed-Mullerových kódů [K části 7.3].
  13. týden:
       (26.5.) Dualita Reed-Mullerových kódů. Kódování a dekódovcí algoritmus RM kódů. [K části 7.4]
       (27.5.) Příklady Reed-Mullerových kódů a jejich dekódování.
    Shrnutí probraných témat.

Doporučená četba.
[D] - skripta A. Drápala,
[H] - text Š.Holuba
[K] - skripta T. Kaisera
[Ko] - text A.Kozlíka
[Š] - text J.Šťovíčka