Gilbert – Varshamov směřoval k lineárním kódům - Gilbert–Varshamov bound for linear codes

The Gilbert – Varshamov směřoval k lineárním kódům souvisí s obecným Gilbert – Varshamov vázán, což udává dolní mez maximálního počtu prvků v kód pro opravu chyb dané délky bloku a minima Hammingova hmotnost přes pole ${ displaystyle mathbb {F} _ {q}}$ . To lze přeložit do prohlášení o maximální rychlosti kódu s danou délkou a minimální vzdáleností. Gilbert – Varshamov směřoval k lineární kódy tvrdí existenci q- lineární lineární kódy pro jakoukoli relativní minimální vzdálenost menší, než je daná hranice, které mají současně vysokou rychlost. Důkaz existence používá pravděpodobnostní metoda, a proto není konstruktivní. Vazba Gilbert – Varshamov je nejznámější z hlediska relativní vzdálenosti pro kódy nad abecedami o velikosti menší než 49.^{[Citace je zapotřebí ]} U větších abeced Kódy Goppa někdy dosáhnout asymptoticky lepší poměr rychlost vs. vzdálenost, než je dána vázanou Gilbert-Varshamov.^[1]

Gilbert – Varshamov vázal větu

Teorém: Nechat

{ displaystyle q geqslant 2}

. Pro každého

{ displaystyle 0 leqslant delta <1 - { tfrac {1} {q}}}

a

{ displaystyle 0 < varepsilon leqslant 1-H_ {q} ( delta),}

existuje kód s sazbou

{ displaystyle R geqslant 1-H_ {q} ( delta) - varepsilon}

a relativní vzdálenost

{ displaystyle delta.}

Tady ${ displaystyle H_ {q}}$ je q-ary entropická funkce definovaná takto:

{ displaystyle H_ {q} (x) = x log _ {q} (q-1) -x log _ {q} x- (1-x) log _ {q} (1-x). }

Výše uvedený výsledek byl prokázán Edgar Gilbert pro obecný kód pomocí chamtivá metoda tak jako tady. Pro lineární kód, Rom Varshamov prokázáno pomocí pravděpodobnostní metoda pro náhodný lineární kód. Tento důkaz bude uveden v následující části.

Důkaz na vysoké úrovni:

Chcete-li ukázat existenci lineárního kódu, který splňuje tato omezení, pravděpodobnostní metoda se používá ke konstrukci náhodného lineárního kódu. Konkrétně je lineární kód vybrán náhodně výběrem náhodný matice generátoru ${ displaystyle G}$ ve kterém je prvek vybrán rovnoměrně nad polem ${ displaystyle mathbb {F} _ {q} ^ {n}}$ . Také Hammingova vzdálenost lineárního kódu se rovná minimální hmotnosti kódové slovo. Takže dokázat, že lineární kód generovaný ${ displaystyle G}$ má Hammingovu vzdálenost ${ displaystyle d}$ , ukážeme to pro všechny ${ displaystyle m in mathbb {F} _ {q} ^ {k} smallsetminus left {0 right }, operatorname {wt} (mG) geq d}$ . Abychom to dokázali, dokazujeme opak; tj. pravděpodobnost, že lineární kód generovaný ${ displaystyle G}$ má Hammingovu vzdálenost menší než ${ displaystyle d}$ je exponenciálně malý v ${ displaystyle n}$ . Pak pravděpodobnostní metodou existuje lineární kód splňující teorém.

Formální důkaz:

Použitím pravděpodobnostní metody k prokázání, že existuje lineární kód, který má Hammingovu vzdálenost větší než ${ displaystyle d}$ , ukážeme, že pravděpodobnost že náhodný lineární kód mající vzdálenost menší než ${ displaystyle d}$ je exponenciálně malý v ${ displaystyle n}$ .

Víme, že lineární kód je definován pomocí matice generátoru. Takže používáme "matici náhodného generátoru" ${ displaystyle G}$ jako prostředek k popisu náhodnosti lineárního kódu. Matice náhodného generátoru ${ displaystyle G}$ velikosti ${ displaystyle kn}$ obsahuje ${ displaystyle kn}$ prvky, které se volí nezávisle a rovnoměrně nad polem ${ displaystyle mathbb {F} _ {q}}$ .

Připomeňme, že v lineární kód, vzdálenost se rovná minimální hmotnosti nenulového kódového slova. Nechat ${ displaystyle operatorname {wt} (y)}$ být váha kódového slova ${ displaystyle y}$ . Tak

{ displaystyle { begin {aligned} P & = Pr _ {{ text {random}} G} ({ text {lineární kód generovaný}} G { text {má vzdálenost}}

Poslední rovnost vyplývá z definice: if a codeword ${ displaystyle y}$ patří do lineárního kódu generovaného ${ displaystyle G}$ , pak ${ displaystyle y = mG}$ pro nějaký vektor ${ displaystyle m in mathbb {F} _ {q} ^ {k}}$ .

Podle Booleova nerovnost, my máme:

{ displaystyle P leqslant sum _ {0 neq m in mathbb {F} _ {q} ^ {k}} Pr _ {{ text {random}} G} ( operatorname {wt} ( mG)

Nyní k dané zprávě ${ displaystyle 0 neq m in mathbb {F} _ {q} ^ {k},}$ chceme počítat

{ displaystyle W = Pr _ {{ text {random}} G} ( operatorname {wt} (mG)

Nechat ${ displaystyle Delta (m_ {1}, m_ {2})}$ být Hammingova vzdálenost dvou zpráv ${ displaystyle m_ {1}}$ a ${ displaystyle m_ {2}}$ . Pak pro jakoukoli zprávu ${ displaystyle m}$ , my máme: ${ displaystyle operatorname {wt} (m) = Delta (0, m)}$ . Proto:

{ displaystyle W = sum _ { {y in mathbb {F} _ {q} ^ {n} | Delta (0, y) leqslant d-1 }} Pr _ {{ text {random}} G} (mG = y)}

Kvůli náhodnosti ${ displaystyle G}$ , ${ displaystyle mG}$ je rovnoměrně náhodný vektor z ${ displaystyle mathbb {F} _ {q} ^ {n}}$ . Tak

{ displaystyle Pr _ {{ text {random}} G} (mG = y) = q ^ {- n}}

Nechat ${ displaystyle operatorname {Vol} _ {q} (r, n)}$ je objem Hammingovy koule s poloměrem ${ displaystyle r}$ . Pak:^[2]

{ displaystyle P leqslant q ^ {k} W = q ^ {k} left ({ frac { operatorname {Vol} _ {q} (d-1, n)} {q ^ {n}}} right) leqslant q ^ {k} left ({ frac {q ^ {nH_ {q} ( delta)}} {q ^ {n}}} right) = q ^ {k} q ^ { -n (1-H_ {q} ( delta))}}

Výběrem ${ displaystyle k = (1-H_ {q} ( delta) - varepsilon) n}$ , stane se výše uvedená nerovnost

{ displaystyle P leqslant q ^ {- varepsilon n}}

Konečně ${ displaystyle q ^ {- varepsilon n} ll 1}$ , což je exponenciálně malé v n, to je to, co chceme dříve. Pravděpodobnostní metodou pak existuje lineární kód ${ displaystyle C}$ s relativní vzdáleností ${ displaystyle delta}$ a hodnotit ${ displaystyle R}$ alespoň ${ displaystyle (1-H_ {q} ( delta) - varepsilon)}$ , který doplňuje důkaz.

Komentáře

Varshamovova výše uvedená konstrukce není explicitní; to znamená, že neurčuje deterministickou metodu pro konstrukci lineárního kódu, který splňuje Gilbert – Varshamovovu vazbu. Naivní způsob, který můžeme udělat, je projít všechny matice generátoru ${ displaystyle G}$ velikosti ${ displaystyle kn}$ přes pole ${ displaystyle mathbb {F} _ {q}}$ a zkontrolujte, zda má tento lineární kód uspokojivou Hammingovu vzdálenost. To vede k exponenciálnímu časovému algoritmu k jeho implementaci.
Máme také Stavba v Las Vegas který vezme náhodný lineární kód a ověří, zda má tento kód dobrou Hammingovu vzdálenost. Přesto má tato konstrukce exponenciální dobu chodu.
U dostatečně velkého nepřiměřeného q a pro určité rozsahy proměnné δ je vazba Gilberta-Varshamova vylepšena Tsfasman-Vladut-Zink vázán.^[3]

Viz také

Reference

^ Tsfasman, M. A.; Vladut, S.G .; Zink, T. (1982). "Modulární křivky, křivky Shimura a kódy Goppa jsou lepší než vázané Varshamov-Gilbertem." Mathematische Nachrichten. 104.
^ Pozdější nerovnost pochází z horní mez koule Hammingova míčku Archivováno 08.11.2013 na Wayback Machine
^ Stichtenoth, H. (2006). "Přechodné a samodvojné kódy dosahující vazby Tsfasman-Vla / spl breve / dut $ 80-Zink". Transakce IEEE na teorii informací. 52 (5): 2218–2224. doi:10.1109 / TIT.2006.872986. ISSN 0018-9448.

[1] Tsfasman, M. A.; Vladut, S.G .; Zink, T. (1982). "Modulární křivky, křivky Shimura a kódy Goppa jsou lepší než vázané Varshamov-Gilbertem." Mathematische Nachrichten. 104.

[2] Pozdější nerovnost pochází z horní mez koule Hammingova míčku Archivováno 08.11.2013 na Wayback Machine

[3] Stichtenoth, H. (2006). "Přechodné a samodvojné kódy dosahující vazby Tsfasman-Vla / spl breve / dut $ 80-Zink". Transakce IEEE na teorii informací. 52 (5): 2218–2224. doi:10.1109 / TIT.2006.872986. ISSN 0018-9448.

[1]

[2]

[3]