Stručný seznam samoopravných kódů probíraných na přednášce Samoopravné kódy (NMIB004). Bez nároku na úplnost, připomínky vítány.

Malý atlas samoopravných kódů

Pro lepší orientaci v kódech probraných na přednášce uvádím jejich stručný seznam a základní vztahy mezi nimi. Seznam je bez nároku na úplnost, připomínky a návrhy na vylepšení vítám.

BCH kódy

Jde o třídu cyklických kódů nad tělesem Fq pojmenovaných podle jmen tvůrců těchto kódů: Bose, Ray-Chaudhuri a Hocquenghem. Jejich výhodou je flexibilita, kterou máme při konstrukci kódu se zadanými parametry.

Značení: BCHq,m,δ, kde q je velikost abecedy (jde o lineární kód nad tělesem Fq), m určuje délku kódu, která je dána vztahem n=qm-1, a δ je tzv. zadaná vzdálenost kódu.

Jedná se o cyklické kódy s parametry [n, k, d]q, kde n=qm-1, k ≥ qm - m(δ-1) - 1 a d ≥ δ. Zvláště odhad na dimenzi kódu k nemusí být příliš přesný.

Speciálními případy BCH kódů jsou Reed-Solomonovy kódy a Hammingův kód H3.

Cyklické kódy

Lineární kódy, které jsou invariantní vzhledem k cyklickému posunu souřadnic. Dají se vyjádřit jako ideály okruhu Fq[x]/(xn-1), kde Fq je abeceda a n je délka kódu.

Příklady: BCH kódy, QR kódy, Reed-Solomonovy kódy.

Golayovy kódy

Tento název je v přednášce použit především pro perfektní kód G23 objevený M. Golayem v roce 1949. Jedná se o lineární binární kód s parametry [23, 12, 7]. Rozšířením o paritní bit vznikne tzv. rozšířený Golayův kód G24, který je samoduální.

Pozn.: Existuje i ternární perfektní Golayův kód G11 s parametry [11, 6, 5] a rozšířený ternární Golayův kód s parametry [12, 6, 6].

Hadamardovy kódy

Jedná se o binární obecně nelineární kódy s relativní vzdáleností 1/2. Mají parametry (n, log(2n), n/2), které jsou v určitém smyslu optimální. Až na triviání případ n=2 musí být délka kódu n dělitelná 4. Pro některé délky se dají konstruovat např. pomocí Sylvesterovy nebo Paleyovy konstrukce.

Pozn.: Pomocí Sylvesterovy kontrukce dostaneme Hadamardovy kódy délky 2m, které jsou lineární a splývají s Reed-Mullerovými kódy R(1, m).

Hammingovy kódy

Jedná se o třídu lineárních binárních kódů s minimální vzdáleností 3. Pro každé r ≥ 2 máme kód Hr s parametry [2r-1, 2r-r-1, 3]. Hammingovy kódy jsou perfektní.

Příklad: Pro r=3 máme známý Hammingův [7, 4, 3]-kód H3.

Lineární kódy

Kódy, jejichž abecedou je nějaké koněčné těleso Fq a které tvoří vektorový podprostor prostoru (Fq)n.

Příklady: Prakticky všechny probírané kódy kromě Hadamardových kódů.

MDS kódy

MDS kódy (z anglického maximum distance separable) jsou kódy optimální z hlediska Singletonova odhadu. To jest, jde o (n, k, d)q-kódy, kde d=n-k+1. Zajímavé příklady většinou nejsou binární kódy, což naznačují i některé teoretické vlastnosti MDS kódů.

Příklady: Reed-Solomonovy kódy, dále pak některé jednoduché kódy (totální kódy, opakovací kódy, paritní kódy).

Perfektní kódy

Kódy, které jsou optimální v tom smyslu, že pro ně platí rovnost v Hammingově odhadu. To jest, prostor všech slov dané délky se rozkládá kombinatorické koule s pevným poloměrem a středy v kódových slovech. U perfektních kódů obecně nepředpokládáme, že jsou lineární.

Příklady: Hammingovy kódy, Golayův kód G23, dále pak některé jednoduché kódy (totální kódy, jednoprvkové kódy, binární opakovací kódy liché délky).

QR kódy

Jedná se o cyklické kódy prvočíselné délky s hustotou blízkou jedné polovině. Název QR pochází od kvadratických zbytků, anglicky se nazývají též quadratic residue codes. Příklady pro malé abecedy a délky mají relativně velké minimální vzdálenosti (jsou mezi nimi např. perfektní kódy H3 a G23), pro jejich asymptotické chování však zůstává hodně nevyřešených otázek.

Binární QR kódy mají parametry [p, (p+1)/2, d], kde p je prvočíslo splňující p ≡ ±1 (mod 8) a pro d platí tzv. odmocninový odhad d ≥ √p. Pokud p ≡ -1 (mod 8), máme dokonce d2-d+1 ≥ p.

Příklady: Hammingův kód H3, Golayův kód G23.

Reed-Mullerovy kódy

Reed-Mullerovy kódy jsou lineární kódy zadané pomocí evaluace polynomů více proměnných. Na přednášce uvažujeme hlavně binární Reed-Mullerovy kódy, které se dekódují pomocí algoritmu využívajícího tzv. většinovou logiku.

Značení: q-ární Reed-Mullerovy kódy značníme Rq(r, m), kde r určuje celkový stupeň evaluovaných polynomů a m počet proměnných. Pro q=2 píšeme pouze R(r, m).

Parametry: Binární kód R(r, m) má parametry [2m, k, 2m-r], kde dimenze kódu k je rovna součtu kombinačních čísel
(m nad 0) + ... + (m nad r)

Pozn.: Reed-Mullerovy kódy R(1, m) jsou zároveň Hadamardovy kódy.

Reed-Solomonovy kódy

Jde o nejdůležitější příklad MDS kódů s významným praktickým využitím (např. CD, DVD a Blu-ray disky). Jsou zvláště vhodné pro aplikace, kde se chyby přenosu nevyskytují zcela náhodně, nýbrž v dávkách (tj. typicky se špatně přenese více po sobě jdoucích bitů).

Značení: RSq,k, kde q je velikost abecedy (jde o lineární kód nad tělesem Fq) a k je dimenze kódu.

Jde o q-ární MDS kódy, které jsou až na ekvivalenci cyklické. Kód RSq,k má parametry [q-1, k, q-k]q a je ekvivaletní BCH kódu BCHq,1,q-k.