Samoopravné kódy


Průběh přednášky

  1. týden:
       (2.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 [J.Ž, 1.1]
       (3.10.) Koule v prostoru Fn, 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) [J.Ž, 1.2-5]
  2. týden:
       (9.10.) 2.S linearitou jde vše 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-2].
       (10.10.) Výpočet vzdálenosti lineárního kódu pomocí kontrolní matice. Bodový součin a duální kódy. [JŽ, 2.3-4].
    Cvičení: Perfektní Hammingův [7,4,3]2-kód, obecné binární i q-ární Hammingovy 1-perfektní kódy.
  3. týden:
       (16.10.) Samoortogonální, samoduální a propíchnuté kódy [JŽ, 2.5-6].
    Cvičení: Samoduální [8,4,4]2-kód a jeho propíchnutí, matice a výpočet vzdálenosti lineárních kódů. Velikost konečného tělesa.
       (17.10.) 3.Hrajeme si s MDS-kódy. Charakterizace lineárních MDS-kódů, duál a propíchnutí MDS je opět MDS. Příklady netriviálních lineárních MDS-kódů. Vztah dimenze, vzdálenosti a velikosti tělesa lineárních MDS kódů. [JŽ, 3.1-7].
  4. týden:
       (23.10.) Cvičení: Struktura konečných těles 4.Rozkládáme polynomy nad konečnými tělesy. Shrnutí popisu struktury konečných těles.
       (24.10.) Frobeniovy automorfismy 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. Grupa kořenů polynomu xn-1 [JŽ, 4.2-5].
  5. týden:
       (30.10.) Výpočet n-tého cykotomického polynomu, popis ireducibilní polynomů a faktorů [JŽ, 4.6-8].
    Cvičení: Ireducibilní a cykotomické polynomy, rozklady polynomů xn-1, hledání ireducibilních polynomů a faktorů.
       (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-5.4].
  6. týden:
       (6.11.) Cvičení: Popis a struktura cyklických kódů. 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ů.
       (7.11.) Cyklické kódy dané nulovými body polynomů a Reedovy-Solomonovy kódy [JŽ, 6.1-2]. Pojem reziduálního kódu. Reziduální kódy GRS-kódů a obecných MDS kódů [JŽ, 6.3-4].
    Cvičení: Konstrukce GRS a RS kódů.
  7. týden:
       (13.11.) Konstrukce kódů o zaručené vzdálenosti (designed distance), příklady reziduálních kódů. [JŽ, 6.4-6]. Cvičení: Konstrukce kontrolní matice reziduálního kódu. Popis reziduální kódu RS kódu jako cyklického kódu.
       (14.11.) 7. Reedovy-Mullerovy kódy. Konstrukce Reedových-Mullerových kódů. Boolevy funkce, Booleovy polynomy a binární RM-kódy. Dimenze a vzdálenost [JŽ, 7.1-2]
  8. týden:
       (20.11.) Dualita a konstrukce Reedových-Mullerových kódů [JŽ, 7.3-4] Cvičení: Příklady Reed-Mullerových kódů, jejich kódování a dekódování. 8. Golayovy perfektní kódy. Matice incidence systému podmnožin. Definice symetrických designů [JŽ, úvod sekce 8]
       (21.11.) Příklady symetrických designů: 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]. Váhový polynom 3-perfektního kódu délky 23 obsahujícího nulové slovo.
  9. týden:
       (27.11.) 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. Jednoznačnost dvojnásobně sudého samoduálního [24,12,8]2 kódu a jeho propíchnutí [JŽ, 8.4-6].
       (28.11.) Jednoznačnost 3-perfektního Golayova kódu délky 23 [JŽ, 8.7-9]. 9. Kódujme konvolučním kódem! Těleso formálních Laurentových řad a jeho podobory [JŽ, 9.1].
  10. týden:
       (4.12.) Těleso racionálních funkcí a realizovatelné mocninné řady. Konvoluční kód jako podprostor nad tělesem Laurentových řad a jeho generující matice. Existence polynomiální generující matice konvolučního kódu, jednoznačný řádkový popis generující matice. [JŽ, 9.2].
       (5.12.) 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.3-4].
    Cvičení: Generující matice, její vnější stupeň a fyzický konvoluční kódovač. Realizace fyzického konvoluční kódovače obvodem.
  11. týden:
       (11.12.) Cvičení: Realizace fyzického konvoluční kódovače obvodem. 10. Konvoluční kódovač: obvod nebo překladač? Abstraktní konvoluční kódovač. Abstraktní kódovač realizující konvoluci s racionální funkcí. [JŽ, 10.1-2].
       (12.12.) 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, abstraktní konvoluční kódovač jako lineární časově invariantní systém s odezvou. [JŽ, 10.3-5].
  12. týden:
       (18.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 (SNF) polynomiální matice, SNF unimodulární matice [JŽ, 11.1-2].
       (19.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.3-6].
    Výpočet vnitřního a vnějšího stupně jednořádkové generující matice.
  13. týden:
       (8.1.) 12. Viterbiho dekódovací algoritmus. Multigraf abstraktního konvolučního kódovače 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.1-2, formulace 12.4].
    Cvičení: Výpočet multigrafu a vrstvy mřížoví konvolučního kódovače, dekódování chybové posloupnosti slov pomocí Viterbiho algoritmu.
       (9.1.) Aplikace teorie kódů v krayptografii (Faruk Gologlu).

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 o konečných tělesech,
[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.