Gilbert – Varshamov vázán - Gilbert–Varshamov bound

v teorie kódování, Gilbert – Varshamov vázán (kvůli Edgar Gilbert^[1] a nezávisle Rom Varshamov^[2]) je limit na parametry a (nemusí být nutně lineární ) kód. To je občas známé jako Gilbert-Shannon –Varshamov vázán (nebo GSV vázán), ale název „Gilbert – Varshamov bound“ je zdaleka nejpopulárnější. Varshamov to dokázal pomocí pravděpodobnostní metody pro lineární kódy. Další informace o tomto důkazu viz Gilbert – Varshamov směřoval k lineárním kódům.

Prohlášení o vazbě

Nechat

${ displaystyle A_ {q} (n, d)}$

označte maximální možnou velikost a q-ary kód ${ displaystyle C}$ s délkou n a minimální Hammingova vzdálenost d (A q-ary code je kód přes pole ${ displaystyle mathbb {F} _ {q}}$ z q elementy).

Pak:

${ displaystyle A_ {q} (n, d) geqslant { frac {q ^ {n}} { sum _ {j = 0} ^ {d-1} { binom {n} {j}} ( q-1) ^ {j}}}.}$

Důkaz

Nechat ${ displaystyle C}$ být kódem délky ${ displaystyle n}$ a minimální Hammingova vzdálenost ${ displaystyle d}$ s maximální velikostí:

${ displaystyle | C | = A_ {q} (n, d).}$

Pak pro všechny ${ displaystyle x in mathbb {F} _ {q} ^ {n}}$ , existuje alespoň jedno kódové slovo ${ displaystyle c_ {x} v C}$ taková, že Hammingova vzdálenost ${ displaystyle d (x, c_ {x})}$ mezi ${ displaystyle x}$ a ${ displaystyle c_ {x}}$ splňuje

${ displaystyle d (x, c_ {x}) leqslant d-1}$

protože jinak bychom mohli přidat X ke kódu při zachování minimální Hammingovy vzdálenosti kódu ${ displaystyle d}$ - rozpor ohledně maximality ${ displaystyle | C |}$.

Proto celá ${ displaystyle mathbb {F} _ {q} ^ {n}}$ je obsažen v unie ze všech koule poloměru ${ displaystyle d-1}$ mít jejich centrum u některých ${ displaystyle c v C}$ :

${ displaystyle mathbb {F} _ {q} ^ {n} = bigcup _ {c v C} B (c, d-1).}$

Nyní má každá koule velikost

${ displaystyle sum _ {j = 0} ^ {d-1} { binom {n} {j}} (q-1) ^ {j}}$

protože můžeme dovolit (nebo Vybrat ) až do ${ displaystyle d-1}$ z ${ displaystyle n}$ komponenty kódového slova, které se mají odchýlit (od hodnoty odpovídající komponenty koule) centrum ) jednomu z ${ displaystyle (q-1)}$ možné další hodnoty (vyvolání: kód je q-ary: načte hodnoty dovnitř ${ displaystyle mathbb {F} _ {q} ^ {n}}$). Proto odvodíme

${ displaystyle q ^ {n} = left | mathbb {F} _ {q} ^ {n} right | = left | bigcup _ {c v C} B (c, d-1) vpravo | leqslant sum _ {c in C} | B (c, d-1) | = | C | sum _ {j = 0} ^ {d-1} { binom {n} {j} } (q-1) ^ {j}}$

To je:

${ displaystyle A_ {q} (n, d) = | C | geqslant { frac {q ^ {n}} { sum _ {j = 0} ^ {d-1} { binom {n} { j}} (q-1) ^ {j}}}.}$

Vylepšení případu primární energie

Pro q hlavní síla, lze zlepšit navázané na ${ displaystyle A_ {q} (n, d) geq q ^ {k}}$ kde k je největší celé číslo, pro které

${ displaystyle q ^ {k} <{ frac {q ^ {n}} { sum _ {j = 0} ^ {d-2} { binom {n-1} {j}} (q-1 ) ^ {j}}}.}$

Viz také

• Singleton vázán
• Hamming vázán
• Johnson vázán
• Plotkin vázán
• Griesmer vázán
• Gray – Rankin vázán
• Gilbert – Varshamov směřoval k lineárním kódům
• Elias-Bassalygo vázán

Reference