Petr Kovář - Teorie kódování

Teorie kódování; TK 2023/2024

Předmět: 470-4203/01: Teorie kódování (TK)
Garant: Doc. Petr Kovář, Ph.D.
Rozsah: 6 kreditů (2/2/2/0/0)
Akademický rok: 2023/2024

Osnova předmětu je v systému Edison.

Průběh přednášek

Každý týden budou probíhat přednášky i cvičení. Přednášku povede Petr Kovář a cvičení povede Tereza Kovářová. Účast na cvičeních je povinná a účast na přednáškách je předpokládaná, neboť přednášky a cvičení navazují.

Zápočet a zkouška

Pro získání zápočtu je nutno získat alespoň 10 bodů z 20 za projekt.

Pro úspěšné absolvování zkoušky pak potřebujete získat alespoň 41 bodů z 80.

Projekty (20 bodů)

Vypracujte projekt popisující řešení následujících problémů:

Cyklický kód Cyklickým posunem vektoru a₁ a₂ ... a_n rozumíme kterýkoliv vektor a_t a_t+1 ... a_na₁ a₂ ... a_t-1 pro t=2,3,... n. Mějme binární kód C, který vznikne všemi možnými cyklickými posuny vektorů 11010000, 11100100, 10101010, 00000000 a 11111111. Ukažte, že kód C je (8,20,3)-kód.
Pokud bychom nebrali v úvahu cykličnost kódu, kolik porovnání vektorů je třeba provést, abychom určili minimální vzdálenost kódu?
Pokud uvážíme cykličnost kódu, kolik porovnání vektorů je třeba provést, abychom určili minimální vzdálenost kódu?
Kombinatorické designy Mějme kombinatorický design B = { { 1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {1, 4, 7}, {2, 5, 8}, {3, 6, 9}, {1, 5, 9}, {2, 6, 7}, {3, 4, 8}, {1, 6, 8}, {2, 4, 9}, {3, 5, 7} }. Určete parametry tohoto kombinatorického designu.
Sestavte kód z incidenční matice blokového designu B tak, že vezmete řádky incidenční matice. Dále vezmeme matici B', která vznikne z matice B permutací symbolů 0 a 1. Do kódu přidáme řádky matice B' a vektor nul a vektor jedniček.
Určete parametry (n, M, d) sestaveného kódu.
Největší minimální vzdálenost Mějme binární lineární [n,k]-kód C. Ukažte, že minimální vzdálenost kódu C nemůže být větší než n-k+1. Je to pravda i pro ternární kód?
Pravděpodobnost chyby Mějme ternární symetrický komunikační kanál s pravděpodobností chyby p=0.01. Mějme nějaký ternární lineární [4,2,3]-kód. Ověřte, zda se jedná o perfektní kód.
Zapište generující matici, sestavte a zapište všechna kódová slova a určete pravděpodobnost, že při dekódování pomocí Slepianova standardního rozmístění bude přijaté slovo dekódováno chybně.
Sestavte syndromovou vyhledávací tabulku a pomocí syndromů dekódujte slova 0002, 1111 a 1222.

Můžete se podívat na projekty z let 2022/2023.

Očekává se, že projekty budou vypracovány na úrovni, která odpovídá studentům magisterského nebo doktorského studia. Nezapomeňte na správné citace použitých zdrojů. Případná různá obtížnost témat bude kompenzována mírou, jak přísně budou projekty hodnoceny.

Termín odevzdání projektů je pondělí 13.5.2024 (pro studenty posledního ročníku je termín dříve, už v zápočtovém týdnu).

Průběh semestru

Předpokládáme, že výuka bude probíhat prezenčně. V rozvrhu je výuka formálně rozdělena na přednášky a cvičení.

Rozdělení přednášek a cvičení

Orientační rozdělení témat přednášek.

Úvod. Samoopravné kódy, (n, M, d)-kódy, Hammingova vzdálenost.
Hlavní problém teorie kódování. Ekvivalence kódů, nutná a postačující podmínka existence (n, M, d)-kódů, Hammingova hranice, perfektní kódy.
Blokové designy v teorii kódování.
Konečná tělesa a vektorové prostory.
Lineární kódy. Výhody a nevýhody lineárních kódů, ekvivalence lineárních kódů, kódování a dekódování lineárními kódy, pravděpodobnost korekce a detekce chyby.
Duální kódy. Duální kód, kontrolní matice, syndromové dekódování.
Hammingovy kódy. Binární a rozšířené Hammingovy kódy.
Perfektní kódy, Golayovy kódy.
Kódy a latinské čtverce.
Cyklické kódy. Polynomy, cyklické kódy.
Kódy pro dvojnásobné opravy

Orientační rozdělení témat cvičení.

Příklady samoopravných kódů, Hammingova vzdálenost.
Příklady ekvivalence kódů, Hammingova hranice, příklady perfektní kódy.
Příklady blokových designů.
Příklady využití konečných těles a vektorových prostorů.
Příklady lineárních kódů, kódování a dekódování lineárními kódy.
Příklady duálního kódu, kontrolní matice, syndromového dekódování.
Příklady Hammingových kódů a rozšířených Hammingových kódů.
Příklady perfektních kódů, vlastnosti.
Příklady kódů sestavených z latinských čtverců.
Příklady cyklických kódů.

Literatura

P. Kovář, Teorie kódování, rozpracovaný učební text, (2024).

pdf pro tisk: text základní (skriptum_teorie_kodovani_tisk.pdf) a rozšířený (skriptum_teorie_kodovani_rozsirene_tisk.pdf)
pdf pro čtení na obrazovce - s aktivními linky: text základní (skriptum_teorie_kodovani.pdf) a rozšířený (skriptum_teorie_kodovani_rozsirene.pdf)

R. Hill: A First Course in Coding Theory, Oxford University Press, (2009), ISBN 978-0-19-853803-5.
T. Kovářová: Teorie kódování, pracovní texty na stránce předmětu, (2023).

Je možné používat i jiné úvodní knihy a skripta, ovšem pozor: některé detaily se mohou lišit! (zejména definice pojmů) a u zkoušky platí to, co bylo probráno na přednášce.

Konzultační hodiny

Zastihnete mne nejlépe osobně během konzultačních hodin, případně (po dohodě emailem) on-line přes MS Teams.

Best way to reach me is during my office hours. It is also possible to arrange (ahead via e-mail) an on-line appointment in MS Teams.

Den	Čas	Místnost
Čtvrtek/Thursday	9:00-10:00	EA536*
**Dne 11.4.2024 konzultace nebudou.
Konzultace on-line po předchozí domluvě.

Po předchozí domluvě jsou konzultace možné i v jinou dobu. / Or by appointment.

Petr<tečka>Kovar<zavináč>vsb<tečka>cz
kancelář EA536, tel. 597 325 972

Upraveno: 24.04.2024