Varshamov-Gilbert gränsen

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 november 2021; verifiering kräver 1 redigering .

Varshamov-Gilbert-gränsen är en olikhet som definierar gränsvärden för kodparametrar (inte nödvändigtvis linjära ), erhållna oberoende av Edgar Gilbert och Rom Varshamov . Ibland används namnet Gilbert- Shannon -Varshamov ojämlikhet , och i utländsk vetenskaplig litteratur - Gilbert-Varshamov ojämlikhet .

Formulering

Låta

A_q(n,\;d)

betecknar den maximala möjliga kardinaliteten för den -: e längdkoden och Hamming -avståndet ( den -e koden är koden med symboler från fältet som består av element). $q$ $C$ $n$ $d$ $q$ $\mathbb {F} _{q}$ $q$

Sedan

A_q(n,\;d)\geqslant\frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1) ^j}.

När är en potens av ett primtal kan man förenkla olikheten till , där är det största heltal för vilket . $q$ $A_q(n,\;d)\geqslant q^k$ $k$ $\displaystyle A_q(n,\;d)\geqslant\displaystyle \frac{q^n}{\displaystyle \sum\limits_{j=0}^{d-2}\displaystyle \binom{n-1}{j }(q-1)^j}$

Bevis

Låt vara den maximala effektkoden för längd och Hamming-avstånd : $C$ $n$ $d$

|C|=A_q(n,\;d).

Sedan för alla finns det minst ett kodord , så Hamming-avståndet mellan och uppfyller $x\in\mathbb{F}_q^n$ $c_x \i C$ $d(x,\;c_x)$ $x$ $c_x$

d(x,\;c_x)\leqslant d-1,

eftersom vi annars skulle kunna utöka koden med ordet , lämna Hamming-avståndet oförändrat, vilket motsäger det maximala maktantagandet . $x$ $d$ $|C|$

Därför kan fältet packas genom föreningen av uppsättningarna av alla sfärer med radie centrerade vid : ${\mathbb {F}}_{q}^{n}$ $d-1$ $c\in C$

\mathbb{F}_q^n =\bigcup_{c\in C}B(c,\;d-1).

Volymen av varje boll

\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j,

eftersom vi kan låta (eller välja ) som mest -th av komponenterna i kodordet att ta på sig ett av de andra möjliga värdena. Därför är följande ojämlikhet sann $(d-1)$ $n$ $(q-1)$

|\mathbb{F}_q^n|=\left|\bigcup_{c\in C}B(c,\;d-1)\right|\leqslant\bigcup_{c\in C}|B(c, \;d-1)|=|C|\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j.

Det är

A_q(n,\;d)\geqslant\frac{q^n}{\sum\limits_{j=0}^{d-1}\displaystyle\binom{n}{j}(q-1)^j }

(ersätter ). $|\mathbb{F}_q^n|=q^n$

Litteratur

Gilbert EN A comparison of signaling alphabets // Bell System Technical Journal , 31:504-522 [1], 1952.
Varshamov R. R. Uppskattning av antalet signaler i koder med felkorrigering // Reports of the Academy of Sciences of the USSR , 117(5):739-741 [1], 1957.

Varshamov-Gilbert gränsen

Formulering

Bevis

Litteratur

Se även