Samoopravné kódy


Průběh přednášky

  1. týden:
       (3.10.) 0.Motivace a cíle přednášky. Jak lze matematicky modelovat úkol bezztrátového přenosu informace? 1.Najít, opravit a neloudat se! Blokový kód délky n, vzdálenost a váha kódu.
       (4.10.) Koule v prostoru Fn, detekce a oprava chyby. Nosnost kódu, Hammingova nerovnost a perfektní kódy, Singletonův odhad. [J.Ž, 1.1-5]
  2. týden:
       (10.10.) Pojem MDS-kódu, příklady (paritní a triviální kódy) [J.Ž, 1.6]. 2.S linearitou jde všechno lépe. Generující a kontrolní matice lineárního kódu. Permutační ekvivalence kódů, standardní tvar generující matice, systematické kódování. [JŽ, 2.1].
       (11.10.) Výpočet vzdálenosti lineárního kódu pomocí kontrolní matice. Bodový součin a duální kódy [JŽ, 2.2-5].
    Cvičení: Perfektní Hammingův [7,4,3]2-kód.
  3. týden:
       (17.10.) Cvičení: Matice a výpočet vzdálenosti lineárních kódů, duální kódy, obecné q-ární Hammingovy 1-perfektní kódy.
    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ů. [JŽ, 3.1-4].
       (18.10.) Příklady netriviálních lineárních MDS-kódů. Samoortogonální a samoduální kódy. Propíchnutí MDS kódu [JŽ, 3.5-8]. Cvičení: Samoduální [8,4,4]2-kód a jeho propíchnutí.
  4. týden:
       (24.10.) 4.Rozkládáme 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].
       (25.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:
       (31.10.) 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Ž, sekce 5].
       (1.11.) Cvičení: Rozklady polynomů xn-1. Popis a struktura cyklických kódů. Konstrukce GRS a RS kódů.
  6. týden:
       (7.11.) 6. GRS kódy a jejich reziduální kódy Zobecněné Reedovy-Solomonovy kódy. Generující matice Reedových-Solomonových kódů Konstrukce kontrolní matice GRS-kódu. Cyklické kódy dané nulovými body polynomů a Reedovy-Solomonovy kódy [JŽ, 6.1-2]
       (8.11.) Reziduální kódy, konstrukce kódů o zaručené vzdálenosti (designed distance), BCH a alternantní kódy jako reziduální kódy RS a GRS-kódů [JŽ, 6.3-6].
  7. týden:
       (14.11.) Cvičení: Konstrukce MDS kódů jako GRS kódů. Reziduální kódy RS kódů.
       (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, parametry a dualita Reedových-Mullerových kódů [JŽ, 7.1-3]
  8. týden:
       (21.11.) Kódovací a dekódovcí algoritmus pro RM kódy. [JŽ, 7.4-6]. Cvičení: Příklady Reed-Mullerových kódů, jejich kódování a dekódování.
       (22.11.) 8. Golayovy perfektní kódy. Matice incidence systému podmnožin. Symetrické designy a jejich příklady: Fanova rovina a projektivní roviny. Konstrukce 2-[11,5,2]-designů pomocí neorientovaných grafů na pěti vrcholech. Existence a jednoznačnost 2-[11,6,3]-designů [JŽ, 8.1-3].
  9. týden:
       (28.11.) Váhový polynom 3-perfektního kódu délky 23. Existence 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.4-5].
       (29.11.) Jednoznačnost dvojnásobně sudého samoduálního [24,12,8]2 kódu a jeho propíchnutí. Jednoznačnost 3-perfektního Golayova kódu délky 23. [JŽ, 8.6-9].
  10. týden:
       (5.12.) 9. Kódujme konvolučním kódem! Těleso formálních Laurentových řad a jeho podobory. Těleso racionálních funkcí a realizovatelné mocninné řady. Konvoluční kód jako podprostor nad tělesem formálních Laurentových řad, jeho generující matice [JŽ, 9.1].
       (6.12.) Existence generující matice konvolučního kódu. Vnější stupeň, Forneyho indexy a stupeň kódu, fyzický konvoluční kódovač jako posloupnost součtů konvolucí, realizace konvoluce s realizovatelnou racionální funkcí obvodem. [JŽ, 9.2-4].
  11. týden:
       (12.12.) Cvičení: Generující matice, její vnější stupeň a fyzický konvoluční kódovač. Realizace fyzického konvoluční kódovače obvodem.
       10. Konvoluční kódovač: obvod nebo překladač? Abstraktní konvoluční kódovač jako lineární časově invariantní systém s odezvou [JŽ, 10.1].
       (13.12.) Abstraktní kódovač realizující konvoluci s racionální funkcí. Přechod mezi abstraktním a fyzickým konvolučním kódovačem. Výpočet fyzického kódovače z abstraktního a naopak [JŽ, 10.2-4].
  12. týden:
       (19.12.) Cvičení: Přechod mezi abstraktním a fyzickým konvolučním kódovačem.
    11. Polynomiální generující matice. Unimodulární matice a Smithova normální forma polynomiální matice [JŽ, 11.1].
       (20.12.) Vnitřní stupeň generující matice. Ekvivalentní podmínky popisující základní matice a 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 [JŽ, 11.2-6].
    Cvičení: Výpočet vnitřního a vnějšího stupně jednořádkové generující matice.
  13. týden:
       (2.1.) Cvičení: Čtvercové základní matice. Ověřování redukovanosti a kanoničnosti matice. Nalezení kanonické generující matice a výpočet stupně konvolučního kódu.
    12. Viterbiho dekódovací algoritmus. Multigraf abstraktního konvolučního kódovače [JŽ, 12.1].
       (3.1.) Mřížoví abstraktního konvolučního kódovače, vrstvy mřížoví, reprezentace kódování prostřednicvím cest mřížoví. Viterbiho algoritmus pro hledání minimální cesty v mřížoví abstraktního konvolučního kódovače [JŽ, 12.2-4].
    Cvičení: Výpočet multigrafu a vrstvy mřížoví konvolučního kódovače.

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.