Samoopravné kódy


Průběh přednášky
  1. týden (29.9.) : 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 Koule v prostoru Fn, detekce a oprava chyby. Nosnost kódu, Hammingova nerovnost a perfektní kódy, Singletonův odhad. [J.Ž, 1.1-4]

  2. týden (6.10.): Pojem MDS-kódu, příklady (paritní, triviální a totální kódy) [J.Ž, 1.5]. 2.S linearitou je 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í. Výpočet vzdálenosti lineárního kódu pomocí kontrolní matice. [JŽ, 2.1-4].
    Cvičení: Perfektní Hammingův [7,4,3]2-kód.

  3. týden (13.10.) : Cvičení: Obecné binární i q-ární Hammingovy 1-perfektní kódy. Velikost binární koule.
    3.Co všechno přežijí MDS-kódy. Bodový součin a duální kódy. Samoortogonální, samoduální a propíchnuté 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ů. [JŽ, 3.1-7].
    Cvičení: Samoduální [8,4,4]2-kód a jeho propíchnutí, matice a výpočet vzdálenosti.

  4. týden (20.10.) : 4.Co už ani MDS-kódy nepřežijí. Vztah dimenze, vzdálenosti a velikosti tělesa lineárních MDS kódů. Pojem reziduálního kódu, reziduální kódy MDS kódů (kódy o zaručené vzdálenosti), příklady reziduálních kódů. [JŽ, 4.1-4].
    Cvičení: Matice a parametry lineárních kódů. Struktura konečných těles

  5. týden (27.10.): 5. Polynomy nad konečnými tělesy. Shrnutí popisu struktury konečných těles. 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. Výpočet n-tého cyklotomického polynomu, popis ireducibilní polynomů a faktorů [JŽ, 5.1-8]. Cvičení: Frobeniovy automorfism a podtělesa konečných těles. Cykotomické polynomy a rozklady polynomů xn-1.

  6. týden (3.11.): 6.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 6.1-6.5]. Cvičení: Popis a struktura cyklických kódů, vyžití hledání ireducibilních polynomů a faktorů.

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.