Samoopravné kódy


Průběh přednášky

  1. týden:
       (4.10.) 0.Motivace a cíle přednášky. Jak lze matematicky modelovat úkol bezztrátového přenosu informace? 1.Vzdálenost a nosnost blokového kódu. Blokový kód délky n, vzdálenost a váha kódu, koule v prostoru Fn.
       (5.10.) Detekce a oprava chyby. Nosnost kódu, Hammingova nerovnost a perfektní kódy, Singletonův odhad, pojem MDS-kódu, příklady (paritní a triviální kódy). Permutační ekvivalence kódů. [J.Ž, 1]
  2. týden:
       (11.10.) 2.Lineární kódy. Generující a kontrolní matice lineárního kódu. standardní tvar generující matice , výpočet vzdálenosti lineárního kódu pomocí kontrolní matice.
       (12.10.) Bodový součin a duální kódy [JŽ, 2]. Cvičení: Matice a výpočet vzdálenosti lineárních kódů, duální kódy. Binární Hammingovy kódy.
  3. týden:
       (18.10.) 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ů. Příklady netriviálních lineárních MDS-kódů [JŽ, 3.1-6].
       (19.10.) Samoortogonální a samoduální kódy. Propíchnutí MDS kódu [JŽ, 3.7-9.]. Cvičení: q-ární Hammingovy kódy, konstrukce samoduálních kódů.
  4. týden:
       (25.10.) 4.Polynomy nad konečnými tělesy. Opakování: popis struktury konečných těles. Frobeniův automorfismus a struktura podtěles konečných těles, iredcubilní polynomy nad konečným tělesem F jako faktory polynomu xu-x pro u=|F|n [JŽ, 4.1-5].
       (26.10.) Grupa kořenů polynomu xn-1, výpočet a ireducibilní faktory n-tého cykotomického polynomu [JŽ, 4.6-8]. Cvičení: Ireducibilní a cykotomické polynomy.
  5. týden:
       (1.11.) 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 [JŽ, 5].
       (2.11.) Cvičení: Cyklické kódy. Konstrukce GRS a RS kódů.
  6. týden:
       (8.11.) 6. GRS kódy a jejich reziduální kódy Zobecněné Reed-Solomonovy kódy. Generující matice Reed-Solomonových kódů Konstrukce kontrolní matice GRS-kódu. Cyklické kódy dané nulovými body polynomů a Reed-Solomonovy kódy [JŽ, 6.1-3]
       (9.11.) Reziduální kódy, konstrukce kódů o zaručené vzdálenosti (designed distance), BCH a alternantní kódy [JŽ, 6.3-7]. Cvičení: Konstrukce BCH kódů.
  7. týden:
       (15.11.) 7. Reedovy-Mullerovy kódy. Konstrukce Reedových-Mullerových kódů. Boolevy funkce, Booleovy polynomy a binární RM-kódy. Vzdálenost Reed-Mullerových kódů [JŽ, 7.1].
       (16.5.) Parametry a dualita Reed-Mullerových kódů. Kódování a dekódovcí algoritmus RM kódů. [JŽ, 7.2-6]. Cvičení: Příklady Reed-Mullerových kódů a jejich dekódování.
  8. týden:
       (22.11.) 8. Golayovy perfektní kódy. Matice incidence systému podmnožin. Symetrické designy, konstrukce 2-[11,5,2]-desgnů pomocí neorientovaných grafů na pěti vrcholech [JŽ, 8.1-2].
       (23.11.) Existence a jednoznačnost 2-[11,6,3]-designů. Existence a jednoznačnost lineárního dvojnásobně sudého samoduálního [24,12,8]2 kódu a jeho vztah k 3-perfektnímu Golayovu [23,12,7]2 kódu [JŽ, 8.3-6].
  9. týden:
       (29.11.) 9. Konvoluční kódy a kódovače. Těleso formálních Laurentových řad a jeho podobory. Těleso racionálních funkcí a realizovatelné mocninné řady.
       (30.11.) Konvoluční kód jako podprostor nad tělesem formálních Laurentových řad, generující matice a její vnější stupeň, Forneyho indexy a stupeň kódu. Fyzický konvoluční kódovač.
  10. týden:
       (6.12.) Abstraktní konvoluční kódovač: lineární časově invariantní systém s odezvou. Abstraktní kódovač realizující konvoluci s racionální funkcí.
       (7.12.) Přechod mezi abstraktním a fyzickým konvolučním kódovačem. Fyzický kódovač realizující konvoluci s racionální funkcí. Výpočet fyzického kódovače z abstraktního a naopak. Cvičení: Generující matice a fyzickým konvoluční kódovač.
  11. týden:
       (13.12.) 10. Polynomiální generující matice. Unimodulární matice a Smithova normální forma polynomiální matice. Vnitřní stupeň generující matice. Ekvivalentní podmínky popisující základní matice.
       (14.12.) Cvičení: Přechod mezi abstraktním a fyzickým konvolučním kódovačem. Výpočet vnitřního a vnějšího stupně generující matice. Unimodulární a základní matice.
  12. týden:
       (20.12.) Ekvivalentní podmínky popisující redukované matice. Kanonické (tj. základní a redukované) jsou právě polynomiální generující matice konvolučního kódu s minimálním vnějším stupněm.
       (21.12.) Cvičení: Redukované a kanonické matice. Nalezení kanonické generující matice a výpočet stupně konvolučního kódu.
  13. týden:
       (3.1.) 11. Viterbiho dekódovací algoritmus. Multigraf a mřížoví abstraktního konvolučního kódovače, vrstvy mřížoví. Reprezentace kódování prostřednicvím cest mřížoví. Cvičení: Výpočet multigrafu a vrstvy mřížoví konvolučního kódovače.
       (4.1.) Viterbiho algoritmus pro hledání minimální cesty v mřížoví abstraktního konvolučního kódovače. Cvičení: Dékódování chybové posloupnosti slov pomocí Viterbiho algoritmu.

Doporučená četba.
[JŽ] - Text k letošní přednášce
[D] - skripta A. Drápala,
[K] - skripta T. Kaisera
[ŠH] Poznámky Š. Holuba o konvolučních kódech
[JL] skripta o konvolučních kódech Jyrki Lahtonena,
[BT] - skripta L.Barta a J. Tůmy,
[Z] - můj text o lineárních rekurentních posloupnostech
[DF] Introduction to convolutional codes. Kapitola ze skript MIT ke kurzu Principles of Digital Communication II.