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 ${\displaystyle C}$ s délkou bloku ${\displaystyle n}$, velikostí ${\displaystyle M}$ a minimální vzdáleností ${\displaystyle d}$. Je také známa jako Joshiho mez.^[1] Její existenci dokázal Joshi 1958 a ještě dříve Komamiya 1953.

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

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

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

Nechť nyní ${\displaystyle C}$ je libovolný ${\displaystyle q}$-ární blokový kód minimální vzdálenosti ${\displaystyle d}$. Zřejmě všechna kódová slova ${\displaystyle c\in C}$ jsou různá. Pokud zúžíme kód vymazáním prvních ${\displaystyle 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 ${\displaystyle C}$ mají Hammingovu vzdálenost alespoň ${\displaystyle 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 ${\displaystyle n-(d-1)=n-d+1,}$ a tedy jich může existovat nejvýše ${\displaystyle q^{n-d+1}}$. Protože kód ${\displaystyle C}$ byl libovolný, tato mez musí platit i pro největší možný kód s těmito parametry, tedy:^[2] ${\displaystyle |C|\leq A_{q}(n,d)\leq q^{n-d+1}.}$

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

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.

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 ${\displaystyle n}$), kódy, které používá všech ${\displaystyle (\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.^[5][6]

K netriviálním MDS kódům patří Reedovy–Solomonovy kódy a jejich rozšířená verze.^[7][8]

MDS kódy jsou důležitou třídou blokových kódů, protože pro pevné ${\displaystyle n}$ a ${\displaystyle 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.^[9]

Nechť ${\displaystyle C}$ je lineární [${\displaystyle n,k,d}$] kód nad ${\displaystyle \mathbb {F} _{q}}$. Pak následující tvrzení jsou ekvivalentní:

• ${\displaystyle C}$ je MDS kód.
• Každých ${\displaystyle k}$ sloupců generující matice ${\displaystyle C}$ je lineárně nezávislých.
• Každých ${\displaystyle n-k}$ sloupců kontrolní matice ${\displaystyle C}$ je lineárně nezávislých.
• ${\displaystyle C^{\perp }}$ je MDS kód.
• Jestliže ${\displaystyle G=(I|A)}$ je generátorová matice ${\displaystyle C}$ ve standardním tvaru, pak každá čtvercová podmatice ${\displaystyle A}$ je regulární.
• Je-li dáno ${\displaystyle 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.^[10]

Nechť ${\displaystyle C}$ je lineární [${\displaystyle n,k,d}$] MDS kód over ${\displaystyle \mathbb {F} _{q}}$. Jestliže ${\displaystyle A_{w}}$ označuje počet kódových slov v ${\displaystyle C}$ váhy ${\displaystyle w}$, pak ${\displaystyle 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}.}$

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ť ${\displaystyle PG(N,q)}$ je konečný projektivní prostor (geometrické) dimenze ${\displaystyle N}$ nad konečným tělesem ${\displaystyle \mathbb {F} _{q}}$. Nechť ${\displaystyle 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 ${\displaystyle G}$ velikosti ${\displaystyle (N+1)\times m,}$ jejíž sloupce jsou homogenními souřadnicemi těchto bodů. Pak<platí následující věta.^[11]

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

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. 

• 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.