Singleton vázán - Singleton bound - Wikipedia

v teorie kódování, Singleton vázán, pojmenovaný po Richardu Collomovi Singletonovi, je relativně hrubá horní hranice velikosti libovolného blokovat kód ${ displaystyle C}$ s délkou bloku ${ displaystyle n}$, velikost ${ displaystyle M}$ a minimální vzdálenost ${ displaystyle d}$.

Prohlášení o vazbě

Minimální vzdálenost sady ${ displaystyle C}$ kódových slov o délce ${ displaystyle n}$ je definován jako

${ displaystyle d = min _ { {x, y v 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)}$ představuje maximální počet možných kódových slov v a ${ displaystyle q}$-ary blokový kód délky ${ displaystyle n}$ a minimální vzdálenost${ displaystyle d}$.

Potom to říká Singletonská vazba

${ displaystyle A_ {q} (n, d) leq q ^ {n-d + 1}.}$

Důkaz

Nejprve si všimněte, že počet ${ displaystyle q}$- dlouhá slova ${ displaystyle n}$ je ${ displaystyle q ^ {n}}$, protože každé písmeno v takovém slově může mít jeden z ${ displaystyle q}$ různé hodnoty, nezávisle na zbývajících písmenech.

Teď nech ${ displaystyle C}$ být libovolný ${ displaystyle q}$- blokový kód minimální vzdálenosti ${ displaystyle d}$. Je zřejmé, že všechna kódová slova ${ displaystyle c v C}$ jsou odlišné. Kdybychom propíchnout kód odstraněním prvního ${ displaystyle d-1}$ písmena každého kódového slova, pak všechna výsledná kódová slova musí být stále párově odlišná, protože všechna původní kódová slova v ${ displaystyle C}$ mít Hammingova vzdálenost alespoň ${ displaystyle d}$ od sebe navzájem. Velikost změněného kódu je tedy stejná jako původní kód.

Každá nově získaná kódová slova mají délku

${ displaystyle n- (d-1) = n-d + 1}$,

a tak tam může být maximálně ${ displaystyle q ^ {n-d + 1}}$ z nich. Od té doby ${ displaystyle C}$ byl libovolný, tato vazba musí platit pro největší možný kód s těmito parametry, tedy:^[1]

${ displaystyle | C | leq A_ {q} (n, d) leq q ^ {n-d + 1}.}$

Lineární kódy

Li ${ displaystyle C}$ je lineární kód s délkou bloku ${ displaystyle n}$, rozměr ${ displaystyle k}$ a minimální vzdálenost ${ displaystyle d}$ přes konečné pole s ${ displaystyle q}$ prvků, pak je maximální počet kódových slov ${ displaystyle q ^ {k}}$ a vazba Singleton znamená:

${ displaystyle q ^ {k} leq q ^ {n-d + 1}}$,

aby

${ displaystyle k leq n-d + 1}$,

který se obvykle píše jako^[2]

${ displaystyle d leq n-k + 1}$.

V případě lineárního kódu lze získat jiný důkaz o vázanosti Singleton pozorováním této pozice paritní kontrolní matice je ${ displaystyle n-k}$.^[3] Další jednoduchý důkaz vyplývá z pozorování, že řádky jakékoli matice generátoru ve standardní formě mají nanejvýš váhu ${ displaystyle n-k + 1}$.

Dějiny

Obvyklá citace uvedená pro tento výsledek je Singleton (1964), ale podle Velština (1988, str. 72) výsledek lze nalézt v článku Komamiya z roku 1953.^[4]

Kódy MDS

Lineární blokové kódy, které dosahují rovnosti ve vázané Singleton jsou volány Kódy MDS (maximální vzdálenost oddělitelná). Mezi příklady takových kódů patří kódy, které mají pouze dvě kódová slova (slovo s nulovou hodnotou a slovo s nulovou hodnotou, které má tedy minimální vzdálenost ${ displaystyle n}$), kódy, které používají celý ${ displaystyle ( mathbb {F} _ {q}) ^ {n}}$ (minimální vzdálenost 1), kódy s jediným symbolem parity (minimální vzdálenost 2) a jejich duální kódy. Často se jim říká triviální Kódy MDS.

V případě binárních abeced existují pouze triviální kódy MDS.^[5][6]

Mezi příklady netriviálních kódů MDS patří Kódy Reed-Solomon a jejich rozšířené verze.^[7][8]

Kódy MDS jsou důležitou třídou blokových kódů, protože pro pevné ${ displaystyle n}$ a ${ displaystyle k}$, mají největší možnosti opravy a detekce chyb. Existuje několik způsobů, jak charakterizovat kódy MDS:^[9]

Teorém: Nechte ${ displaystyle C}$ být lineární [${ displaystyle n, k, d}$] kód skončil ${ displaystyle mathbb {F} _ {q}}$. Následující jsou ekvivalentní:

• ${ displaystyle C}$ je kód MDS.
• Žádný ${ displaystyle k}$ sloupce a matice generátoru pro ${ displaystyle C}$ jsou lineárně nezávislé.
• Žádný ${ displaystyle n-k}$ sloupce a paritní kontrolní matice pro ${ displaystyle C}$ jsou lineárně nezávislé.
• ${ displaystyle C ^ { perp}}$ je kód MDS.
• Li ${ displaystyle G = (I | A)}$ je generátorová matice pro ${ displaystyle C}$ ve standardní formě, pak každá čtvercová submatice o ${ displaystyle A}$ je nesmyslný.
• Vzhledem k jakékoli ${ displaystyle d}$ pozice souřadnic, existuje kódové slovo (minimální hmotnost), jehož Podpěra, podpora jsou právě tyto pozice.

Poslední z těchto charakterizací umožňuje použití MacWilliams identity, explicitní vzorec pro úplné rozložení hmotnosti kódu MDS.^[10]

Teorém: Nechte ${ displaystyle C}$ být lineární [${ displaystyle n, k, d}$] Kód MDS skončil ${ displaystyle mathbb {F} _ {q}}$. Li ${ displaystyle A_ {w}}$ označuje počet kódových slov v ${ displaystyle C}$ hmotnosti ${ displaystyle w}$, pak

${ displaystyle A_ {w} = { binom {n} {w}} suma _ {j = 0} ^ {wd} (- 1) ^ {j} { binom {w} {j}} (q ^ {w-d + 1-j} -1) = { binom {n} {w}} (q-1) sum _ {j = 0} ^ {wd} (- 1) ^ {j} { binom {w-1} {j}} q ^ {wdj}.}$

Oblouky v projektivní geometrii

Lineární nezávislost sloupců matice generátoru kódu MDS umožňuje konstrukci kódů MDS z objektů v konečný projektivní geometrie. Nechat ${ displaystyle PG (N, q)}$ být konečný projektivní prostor (geometrické) dimenze ${ displaystyle N}$ přes konečné pole ${ displaystyle mathbb {F} _ {q}}$. Nechat ${ displaystyle K = {P_ {1}, P_ {2}, tečky, P_ {m} }}$ být množina bodů v tomto projektivním prostoru reprezentovaná homogenní souřadnice. Vytvořte ${ displaystyle (N + 1) krát m}$ matice ${ displaystyle G}$ jejichž sloupce jsou homogenní souřadnice těchto bodů. Pak,^[11]

Teorém: ${ displaystyle K}$ je (prostorový) ${ displaystyle m}$-oblouk kdyby a jen kdyby ${ displaystyle G}$ je matice generátoru ${ displaystyle [m, N + 1, m-N]}$ Kód MDS skončil ${ displaystyle mathbb {F} _ {q}}$.

Viz také

• Gilbert – Varshamov vázán
• Plotkin vázán
• Hamming vázán
• Johnson vázán
• Griesmer vázán

Poznámky

Reference

• Ling, San; Xing, Chaoping (2004), Teorie kódování / První kurz, Cambridge University Press, ISBN  0-521-52923-9
• MacWilliams, F.J.; Sloane, N.J.A. (1977), Teorie kódů pro opravu chyb, Severní Holandsko, str.33, 37, ISBN  0-444-85193-3
• Pless, Vero (1998), Úvod do teorie chybových kódů (3. vyd.), Wiley Interscience, ISBN  0-471-19047-0
• Roman, Steven (1992), Kódování a informační teorie, GTM, 134, Springer-Verlag, ISBN  0-387-97812-7
• Singleton, R.C. (1964), "Maximální počet kódů vzdálenosti", IEEE Trans. Inf. Teorie, 10 (2): 116–118, doi:10.1109 / TIT.1964.1053661
• Vermani, L. R. (1996), Základy teorie algebraického kódování, Chapman & Hall
• Welsh, Dominic (1988), Kódy a kryptografie, Oxford University Press, ISBN  0-19-853287-3

Další čtení

• J.H. van Lint (1992). Úvod do teorie kódování. GTM. 86 (2. vyd.). Springer-Verlag. p.61. ISBN  3-540-54894-7.
• Niederreiter, Harald; Xing, Chaoping (2001). "6. Aplikace na teorii algebraického kódování". Racionální body na křivkách nad konečnými poli. Teorie a aplikace. Série přednášek London Mathematical Society. 285. Cambridge: Cambridge University Press. ISBN  0-521-66543-4. Zbl  0971.11033.