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 Joshi 1958 a ještě dříve Komamiya 1953.

Tvrzení o minimální vzdálenosti a Singletonově mezi

Znění

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á. 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|\leq 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 Singleton 1964, ale důkaz podal již Joshi 1958. Podle Welsh 1988, p. 72 lze výsledek nalézt v článku Komamiya 1953.

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í, anglicky maximum distance separable codes). 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. 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.

Ekvivalentní tvrzení o MDS kódech

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.
• 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 o rozdělení vah kódových slov v MDS kódu

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}$. 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<platí následující věta.

Věta o m-hraně a generátorové matici MDS kódu

$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

Reference

V tomto článku byl použit překlad textu z článku Singleton bound na anglické Wikipedii.

• JOSHI, D.D, 1958. A Note on Upper Bounds for Minimum Distance Codes. Information and Control. Roč. 1, čís. 3, s. 289–295. DOI 10.1016/S0019-9958(58)80006-6. 
• KOMAMIYA, Y., 1953. Application of logical mathematics to information theory. Proc. 3rd Japan. Nat. Cong. Appl. Math.. S. 437. 
• LING, San; XING, Chaoping, 2004. Coding Theory / A First Course. [s.l.]: Cambridge University Press. ISBN 0-521-52923-9. 
• MACWILLIAMS, F.J.; SLOANE, N.J.A. The Theory of Error-Correcting Codes. [s.l.]: North-Holland, 1977. Dostupné online. ISBN 0-444-85193-3. S. 33, 37. 
• PLESS, Vera, 1998. Introduction to the Theory of Error-Correcting Codes. 2. vyd. [s.l.]: Wiley Interscience. ISBN 0-471-19047-0. 
• ROMAN, Steven, 1992. Coding and Information Theory. [s.l.]: Springer-Verlag. (GTM). ISBN 0-387-97812-7. 
• SINGLETON, R.C., 1964. Maximum distance q-nary codes. IEEE Trans. Inf. Theory. Roč. 10, čís. 2, s. 116–118. DOI 10.1109/TIT.1964.1053661. 
• VERMANI, L. R., 1996. Elements of algebraic coding theory. [s.l.]: Chapman & Hall. Dostupné online. 
• WELSH, Dominic, 1988. Codes and Cryptography. [s.l.]: Oxford University Press. Dostupné online. ISBN 0-19-853287-3. 

Literatura

• J.H. van Lint. Introduction to Coding Theory. 2. vyd. [s.l.]: Springer-Verlag, 1992. (GTM). Dostupné online. ISBN 3-540-54894-7. S. 61. 
• NIEDERREITER, Harald; XING, Chaoping, 2001. Rational points on curves over finite fields. Theory and Applications. Cambridge: Cambridge University Press. (London Mathematical Society Lecture Note Series). Dostupné online. ISBN 0-521-66543-4. Kapitola 6. Applications to algebraic coding theory. 

Portály: Matematika