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ů.

  7. týden (10.11.) 7. GRS kódy a jejich ostatky Zobecněné Reedovy-Solomonovy kódy. Cyklické kódy dané nulovými body polynomů a Reedovy-Solomonovy kódy, reziduální kódy GRS-kódů [JŽ, 7.1-4]. 8. Reedovy-Mullerovy kódy. Konstrukce Reedových-Mullerových kódů. Boolevy funkce, Booleovy polynomy a binární RM-kódy.
    Cvičení: Konstrukce GRS a RS kódů. Konstrukce kontrolní matice reziduálního kódu. Popis reziduální kódu RS kódu jako cyklického kódu.

  8. týden: (24.11.) Dimenze, vzdálenost a dualita Reedových-Mullerových kódů [JŽ, 8.1-4] 9. Golayovy perfektní kódy. Matice incidence systému podmnožin. Definice symetrických designů Příklady symetrických designů: Fanova rovina a projektivní roviny [JŽ, úvod sekce 9 po příklad 9.1].
    Cvičení: Generující a kontrolní matice Reed-Mullerových kódů.

  9. týden: (1.12.) Konstrukce 2-[11,5,2]-designů pomocí neorientovaných grafů na pěti vrcholech. Existence a jednoznačnost 2-[11,6,3]-designů [JŽ, 9.1-3]. Váhový polynom 3-perfektního kódu délky 23 obsahujícího nulové slovo. 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í, jednoznačnost 3-perfektního Golayova kódu délky 23 [JŽ, 9.4-9].

  10. týden: (8.12.) 10. 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 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. 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Ž, 10.1-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: (15.12.) 11. Konvoluční kódovač: obvod nebo překladač? Abstraktní konvoluční kódovač. 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, abstraktní konvoluční kódovač jako lineární časově invariantní systém s odezvou. [JŽ, 11.1-5]. 12. Polynomiální generující matice. Unimodulární matice a Smithova normální forma (SNF) polynomiální matice, Vnitřní stupeň generující matice a základní matice. [JŽ, 12.1].
    Cvičení: Realizace fyzického konvoluční kódovače obvodem. Přechod mezi abstraktním a fyzickým konvolučním kódovačem.

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.