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 Šablona:Harvnb a ještě dříve Šablona:Harvnb.

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=\underset{\{x,y\in C:x\ne y\}}{\min }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)\le 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:Šablona:Sfn $|C|\le A_q(n,d)\le 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\le q^{n-d+1},$ , takže $k\le n-d+1,$ což se obvykle píšeŠablona:Sfn $d\le 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$.Šablona:Sfn 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 Šablona:Harvnb, ale důkaz podal již Šablona:Harvnb. Podle Šablona:Harvnb lze výsledek nalézt v článku Šablona:Harvnb.

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í, Šablona:Vjazyce2). 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 $({𝔽}_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.Šablona:SfnŠablona:Sfn

K netriviálním MDS kódům patří Reedovy–Solomonovy kódy a jejich rozšířená verze.Šablona:SfnŠablona:Sfn

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.Šablona:Sfn

Ekvivalentní tvrzení o MDS kódech

Nechť $C$ je lineární [$n,k,d$] kód nad ${𝔽}_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.Šablona:Sfn

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 ${𝔽}_q$. Jestliže $A_w$ označuje počet kódových slov v $C$ váhy $w$, pak $A_w=(\genfrac{}{}{0ex}{}{n}{w})\sum _{j=0}^{w-d}(-1{)}^j(\genfrac{}{}{0ex}{}{w}{j})(q^{w-d+1-j}-1)=(\genfrac{}{}{0ex}{}{n}{w})(q-1)\sum _{j=0}^{w-d}(-1{)}^j(\genfrac{}{}{0ex}{}{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 ${𝔽}_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 $⟨m,N+1,m-N⟩$ MDS kódu nad ${𝔽}_q$.

Odkazy

Reference

• Šablona:Citace periodika
• Šablona:Citace periodika
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace monografie
• Šablona:Citace periodika
• Šablona:Citace monografie
• Šablona:Citace monografie

Literatura

• Šablona:Citace monografie
• Šablona:Citace monografie