Automaty a konvoluční kódy


Průběh přednášky

   (2.10.) Motivace a nástin obsahu přednášky. 1.Od lineárních kódů ke konvolučním a zpět. Lineární blokové kódy. Generující řada posloupnosti a těleso formálních Laurentových řad.

   (5.10.) Racionální funkce, polynomy a formální mocniné řady. Konvoluční kód jako podprostor nad tělesem formálních Laurentových řad.

   (9.10.) Vnější stupeň generující matice, Forneyho indexy a stupeň kódu. 2. Konvoluční kódovač. Abstraktní a fyzický konvoluční kódovač: lineární časově invariantní systémy jako konvoluce s odezvou. Abstraktní kódovač realizující konvoluci s racionální funkcí.

   (16.10.) Přechod mezi abstraktním a fyzickým kódovačem. Fyzický kódovač realizující konvoluci s racionální funkcí.

   (19.10.) Výpočet fyzického kódovače z abstraktního a naopak. 3. Smithova normální forma. Unimodulární matice.

   (23.10.) Existence a jednoznačnost Smithovy normální formy polynomiální matice.

   (30.10.) 4. Polynomiální generující matice. Vnitřní stupeň generující matice. Ekvivalentní podmínky popisující základní matice.

   (6.11.) 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.

   (9.11.) 5. Časově invariantní systémy. "Nelineární" definice časově invariantního systému a jeho reprezentace jako abstraktního konvolučního kódovače. (kapitola nebude zkoušena)

   (13.11.) 6. Prostor abstraktních stavů. Prostor abstraktních stavů kódovače a kódu. Dimenze prostoru abstraktních stavů kódu zdola omezuje dimenzi prostoru abstraktních stavů kódovače a ta je menší nebo rovna dimenzi stavového prostoru kterékoli realizace kódovače jako abstraktního konvolučního kódovače.

   (16.11.) Minimalita kódování: pouze nula je abstraktním stavem i kódovým slovem právě pro kódovače s minimální dimenzí prostoru abstraktních stavů. Věta o stavovém prostoru (dimenze stavového prostoru kódu je rovna stupni kódu).

   (20.11.) Kostrukce minimálního abstraktního a fyzického konvolučního kódovače daného konvolučního kódu. 7. Regulární jazyky a konečné automaty. Racionálně uzavřené množiny.

   (27.11.) Regulární výrazy, regulární jazyky jsou právě racionální množiny. Konečné automaty, jazyk přijímaný automatem, ekvivalentní konečné automaty.

   (30.11.) Epsilon přechody a úplné deterministické konečné automaty. Kleeneova věta: regulární jazyky jsou právě jazyky přijímané konečnými automaty.

   (4.12.) 8. Syntaktický monoid a minimální automat. Syntaktická kongruence a syntaktický monoid. Myhill-Nerodova ekvivalence, konstrukce minimálního automatu.

   (7.12.) Minimální automat je úplný deterministiocký automat s miniální množinou stavů. Monoid transformací automatu je izomorfní syntaktickému monoidu regulárního jazyka, regulární jazyky jsou právě jazyky s konečným syntaktickým monoidem.

   (11.12.) 9. Konečné překladače. Graf konečného překladače, abstraktní konvoluční kódovač jako konečný překladač. Konečné překladače zachovávají regularitu vzoru i obrazu.

   (18.12.) 10. Viterbiho dekódovací algoritmus. Mřížoví konečného překladače (a abstraktního konvolučního kódovače), vrstvy mřížoví. Hledání minimální cesty v mřížoví konečného překladače.

   (21.12.) Viterbiho algoritmus. MAP a ML dekódování pro kanál bez paměti.

   (8.1.) Viterbiho metrika. Viterbiho algoritmus dává ML dekódování. Chybová událost. Počítání cest v grafu. Odhad pravděpodobnosti dávkové chyby.



[ŠH] většinu témat nalézt v Poznámkách k přednáškám Š. Holuba
[DF] Introduction to convolutional codes. Kapitola ze skript MIT ke kurzu Principles of Digital Communication II.
[JL] skripta Jyrki Lahtonena,