Gilbert–Varshamov på väg mot linjära koder

Gilbert –Varshamov-gränsen för linjära koder är relaterad till den allmänna Gilbert–Varshamov-gränsen , som ger en nedre gräns för det maximala antalet element i en felkorrigerande kod av en given blocklängd och minsta Hamming-vikt över ett fält $\mathbb {F} _{q}$ . Detta kan översättas till ett uttalande om den maximala hastigheten för en kod med given längd och minsta avstånd. Gilbert–Varshamov-gränsen för linjära koder hävdar förekomsten av q -ära linjära koder för varje relativ minimiavstånd som är mindre än den givna gränsen som samtidigt har hög hastighet. Existensbeviset använder den probabilistiska metoden och är därför inte konstruktiv. Gilbert–Varshamov-gränsen är den mest kända när det gäller relativa avstånd för koder över alfabet med storlek mindre än 49. [ ^{citat behövs ]} För större alfabet uppnår Goppa-koder ibland en asymptotiskt bättre frekvens jämfört med avståndsavvägning än vad som ges av Gilbert -Varshamov bunden.

Gilbert–Varshamov bundet sats

Sats: Låt

q\geqslant 2

. För varje

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

och

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

det finns en kod med hastighet

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

och det relativa avståndet

\delta .

Här är $H_{q}$ den q -ära entropifunktionen definierad enligt följande:

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

Ovanstående resultat bevisades av Edgar Gilbert för allmän kod med den giriga metoden som här . För linjär kod bevisade Rom Varshamov att använda den probabilistiska metoden för den slumpmässiga linjära koden . Detta bevis kommer att visas i följande del.

Bevis på hög nivå:

För att visa förekomsten av den linjära koden som uppfyller dessa begränsningar, används den probabilistiska metoden för att konstruera den slumpmässiga linjära koden. Specifikt väljs den linjära koden slumpmässigt genom att välja slumpgeneratormatrisen $G$ där elementet väljs enhetligt över fältet $mathbb {F} _{q}^{n}}$ \ . Även Hamming-avståndet för den linjära koden är lika med kodordets minimivikt . Så för att bevisa att den linjära koden som genereras av $G$ har Hamming-avstånd $d$ , kommer vi att visa att för alla ${\ displaystyle m\in \mathbb {F} _{q}^{k}\smallsetminus \left\{0\right\},\operatörsnamn {wt} (mG)\geq d}$ . För att bevisa det bevisar vi motsatsen; det vill säga sannolikheten att den linjära koden som genereras av $G$ har Hamming-avståndet mindre än $d$ är exponentiellt liten i $n$ . Sedan, genom probabilistisk metod, finns det den linjära koden som uppfyller satsen.

Formella bevis:

Genom att använda den probabilistiska metoden, för att visa att det finns en linjär kod som har ett Hamming-avstånd större än $d$ , kommer vi att visa att sannolikheten att den slumpmässiga linjära koden har avståndet mindre än $d$ är exponentiellt liten i $n$ .

Vi vet att den linjära koden definieras med hjälp av generatormatrisen . Så vi använder "slumpgeneratormatrisen" $G$ som ett medel för att beskriva den linjära kodens slumpmässighet. Så en slumpgeneratormatris $G$ av storleken $kn$ innehåller $kn$ element som väljs oberoende och enhetligt över fältet $\mathbb {F} _{ q}$ .

Kom ihåg att i en linjär kod är avståndet lika med minimivikten för kodordet som inte är noll. Låt $\operatorname {wt} (y)$ vara vikten av kodordet $y$ . Så

{\begin{aligned}P&=\Pr _{{\text{slumpmässig }}G}({\text{linjär kod genererad av }}G{\text{ har avstånd}}<d)\\[6pt]&=\Pr _{{\text{random }}G}({\text{det finns ett kodord som inte är noll } }y{\text{ i en linjär kod genererad av }}G{\text{ så att }}\operatörsnamn {wt} (y)<d)\\[6pt]&=\Pr _{{\text{slumpmässigt }}G}\left({\text{det finns }}0\neq m\in \mathbb {F} _{q}^{k}{\text{ så att }}\operatörsnamn {wt} (mG) <d\right)\end{aligned}}

Den sista likheten följer av definitionen: om ett kodord $y$ tillhör en linjär kod genererad av $G$ , då $y=mG$ för någon vektor $m\in \mathbb {F} _{q}^{k}$ .

Genom Booles ojämlikhet har vi:

P\leqslant \sum _{0\neq m\in \mathbb {F} _{q}^{k }}\Pr _{{\text{random }}G}(\operatörsnamn {wt} (mG)<d)

För ett givet meddelande $0\neq m\in \mathbb {F} _{q}^{k},$ vill vi nu beräkna

W=\Pr _{{\text{random }}G}(\operatörsnamn {wt} (mG)<d).

Låt $\Delta (m_{1},m_{2})$ vara ett Hamming-avstånd av två meddelanden $m_{1}$ och $m_ {2}$ . Sedan har vi för alla meddelanden ${\displaystyle m} :$ $\operatorname {wt} (m)=\Delta (0,m)$ . Därför:

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

På grund av slumpmässigheten hos ${\displaystyle G} är$ $mG$ en enhetligt slumpmässig vektor från $\mathbb {F} _{q}^{n$ } . Så

\Pr _{{\text{slumpmässig }}G}(mG=y)=q^{-n}

Låt $\operatorname {Vol} _{q}(r,n)$ är en volym av Hamming ball med radien $r$ . Sedan:

P\leqslant q^{k}W=q^{k}\left({\frac {\operatörsnamn {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 ))}

Genom att välja $k=(1-H_{q}(\delta )-\varepsilon )n$ blir ovanstående olikhet

P\leqslant q^{-\varepsilon n}

Slutligen ${\displaystyle q^{-\varepsilon n}\ll 1} ,$ som är exponentiellt litet i n, det är vad vi vill ha tidigare. Med den probabilistiska metoden finns det sedan en linjär kod $C$ med relativa avståndet $\delta$ och betygsätt $R$ åtminstone ${\ displaystyle (1-H_{q}(\delta )-\varepsilon )} ,$ vilket kompletterar beviset.

Kommentarer

Varshamov-konstruktionen ovan är inte explicit; det vill säga den specificerar inte den deterministiska metoden för att konstruera den linjära koden som uppfyller Gilbert–Varshamov-gränsen. Ett naivt tillvägagångssätt är att söka över alla generatormatriser $G$ av storleken $kn$ över fältet $\mathbb {F} _{q}$ för att kontrollera om den linjära koden är associerad till $G$ uppnår det förutsagda Hamming-avståndet. Denna uttömmande sökning kräver exponentiell körtid i värsta fall.
Det finns också en Las Vegas-konstruktion som tar en slumpmässig linjär kod och kontrollerar om denna kod har bra Hamming-avstånd, men denna konstruktion har också en exponentiell körtid.
För tillräckligt stora icke-prime q och för vissa intervall av variabeln δ förbättras Gilbert-Varshamov-bindningen av Tsfasman-Vladut-Zink-bunden.

Se även