Singletonova mez

Singletonova mez pojmenovaná po Richardu Collomovi Singletonovi je v teorii kódování relativně hrubá horní mez velikosti libovolného blokového kódu C s délkou bloku n, velikostí M a minimální vzdáleností d. Je také známa jako Joshiho mez. Její existenci dokázal a ještě dříve .

Tvrzení

Minimální vzdálenost množiny C kódových slov délky n je definována jako d = \min_{\{x,y \in C : x \neq y\}} d(x,y), kde d(x,y), je Hammingova vzdálenost mezi x a y. Výraz A_{q}(n,d) reprezentuje maximální počet možných kódových slov v q-árním blokovém kódu délky n a minimální vzdálenosti d.

Singletonova mez pak říká, že A_q(n,d) \leq q^{n-d+1}.

Důkaz

Nejdříve je třeba si uvědomit, že počet q-árních slov délky n je q^n, protože každé písmeno v takovém slově může nabývat jedné z q různých hodnot nezávisle na zbývajících písmenech.

Nechť nyní C je libovolný q-ární blokový kód minimální vzdálenosti d. Zřejmě všechna kódová slova c \in C jsou různá. +more Pokud zúžíme kód vymazáním prvních d-1 písmen každého kódového slova, pak všechna výsledná kódová slova musí stále být po dvou různá, protože všechna původní kódová slova v C mají Hammingovu vzdálenost alespoň d. Velikost upraveného kódu je tedy stejná jako velikost původního kódu.

Nově získaná kódová slova budou mít všechna délku n-(d-1) = n-d+1, a tedy jich může existovat nejvýše q^{n-d+1}. Protože kód C byl libovolný, tato mez musí platit i pro největší možný kód s těmito parametry, tedy: |C| \le A_q(n,d) \leq q^{n-d+1}.

Lineární kódy

Pokud C je lineární kód s délkou bloku n, velikostí k a minimální vzdáleností d nad konečným tělesem s q prvky, pak maximální počet kódových slov je q^k a ze Singletonovy meze plyne: q^k \leq q^{n-d+1}, , takže k \leq n - d + 1, což se obvykle píše d \leq n - k + 1.

V případě lineárního kódu lze použít jiný důkaz Singletonovy meze pozorováním, že hodnost kontrolní matice je n - k. Jiný jednoduchý důkaz vyplývá z pozorování, že řádky jakékoli vytvořující matice ve standardním tvaru mají váhu nejvýše n - k + 1.

Historie

Obvyklou citací pro tento výsledek je , ale důkaz podal již . Podle lze výsledek nalézt v článku .

MDS kódy

Lineární blokové kódy, pro které je v Singletonově mezi dosažena rovnost, se nazývají MDS kódy (kódy separabilní s maximální vzdáleností). K takovým kódům patří kódy, které mají pouze dvě kódová slova (slovo tvořené samými nulami a slovo tvořené samými jedničkami, která mají minimální vzdálenost n), kódy, které používá všech (\mathbb{F}_{q})^{n} (minimální vzdálenost 1), kódy s jediným paritním symbolem (s minimální vzdáleností 2) a jejich duální kódy. +more Tyto kódy se často nazývají triviální MDS kódy.

Pro binární abecedu existují pouze triviální MDS kódy.

K netriviálním MDS kódům patří Reedovy-Solomonovy kódy a jejich rozšířená verze.

MDS kódy jsou důležitou třídou blokových kódů, protože pro pevné n a k mají největší funkcionalitu opravy a detekce chyb. Existuje několik způsobů jak charakterizovat MDS kódy, které popisuje následující věta.

Věta

Nechť C je lineární

n,k,d

kód nad \mathbb{F}_q. Pak následující tvrzení jsou ekvivalentní: * C je MDS kód. +more * Každých k sloupců generující matice C je lineárně nezávislých. * Každých n-k sloupců kontrolní matice C je lineárně nezávislých. * C^{\perp} je MDS kód. * Jestliže G = (I|A) je generátorová matice C ve standardním tvaru, pak každá čtvercová podmatice A je regulární. * Je-li dáno d souřadnicových pozic, existuje kódové slovo (s minimální váhou), jehož nosičem jsou právě tyto pozice.

Z posledního z těchto tvrzení vyplývá díky MacWilliamsově identitě explicitní vzorec pro úplné rozdělení vah MDS kódu, který popisuje následující věta.

Věta

Nechť C je lineární

n,k,d

MDS kód over \mathbb{F}_q. Jestliže A_w označuje počet kódových slov v C váhy w, pak A_w = \binom{n}{w} \sum_{j=0}^{w-d} (-1)^j \binom{w}{j} (q^{w-d+1-j} -1) = \binom{n}{w}(q-1)\sum_{j=0}^{w-d} (-1)^j \binom{w-1}{j}q^{w-d-j}.

Hrany v projektivní geometrii

Lineární nezávislosti sloupců vytvořující matice MDS kódu připouští konstrukci MDS kódů z objektů v konečné projektivní geometrii. Nechť PG(N,q) je konečný projektivní prostor (geometrické) dimenze N nad konečným tělesem \mathbb{F}_q. +more Nechť K = \{P_1,P_2,\dots,P_m \} je množina bodů v tomto projektivním prostoru reprezentovaných homogenními souřadnicemi. Vytvoříme matici G velikosti (N+1) \times m, jejíž sloupce jsou homogenními souřadnicemi těchto bodů. Pak.

Věta

K je (prostorová) m-hrana právě tehdy, když G je generátorová matice \langle m,N+1,m-N\rangle MDS kódu nad \mathbb{F}_q.

Odkazy

Poznámky

Reference

Literatura

Související články

Gilbertova-Varshamovova mez * Plotkinova mez * Hammingova mez * Johnsonova mez * Griesmerova mez

Kategorie:Teorie kódování Kategorie:Nerovnosti