Varshamov-Gilbert grænse

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 18. november 2021; verifikation kræver 1 redigering .

Varshamov-Gilbert-grænsen er en ulighed, der definerer grænseværdier for kodeparametre (ikke nødvendigvis lineære ), opnået uafhængigt af Edgar Gilbert og Rom Varshamov . Nogle gange bruges navnet Gilbert- Shannon - Varshamov - ulighed , og i udenlandsk videnskabelig litteratur - Gilbert-Varshamov-ulighed .

Ordlyd

Lade

A_q(n,\;d)

angiver den maksimalt mulige kardinalitet af den -te kode for længde og Hamming-afstand ( den -te kode er koden med symboler fra feltet bestående af elementer). $q$ $C$ $n$ $d$ $q$ $\mathbb {F} _{q}$ $q$

Derefter

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

Hvornår er en potens af et primtal , kan man forenkle uligheden til , hvor er det største heltal , for hvilket . $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

Lad være den maksimale effektkode for længde og Hamming-afstand : $C$ $n$ $d$

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

Så for enhver er der mindst ét kodeord , så Hamming-afstanden mellem og opfylder $x\in\mathbb{F}_q^n$ $c_x \i C$ $d(x,\;c_x)$ $x$ $c_x$

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

fordi ellers kunne vi udvide koden med ordet , og lade Hamming-afstanden være uændret, hvilket modsiger den maksimale magtantagelse . $x$ $d$ $|C|$

Derfor kan feltet pakkes ved foreningen af sættene af alle sfærer med radius centreret ved : ${\mathbb {F}}_{q}^{n}$ $d-1$ $c\in C$

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

Volumen af hver kugle

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

fordi vi kan lade (eller vælge ) højst -th af komponenterne i kodeordet til at antage en af de andre mulige værdier. Derfor er følgende ulighed sand $(d-1)$ $n$ $(q-1)$

|\mathbb{F}_q^n|=\venstre|\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 er

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

(erstatter ). $|\mathbb{F}_q^n|=q^n$

Litteratur

Gilbert EN En sammenligning af signaleringsalfabeter // Bell System Technical Journal , 31:504-522 [1], 1952.
Varshamov R. R. Estimat af antallet af signaler i koder med fejlkorrektion // Reports of the Academy of Sciences of the USSR , 117(5):739-741 [1], 1957.

Varshamov-Gilbert grænse

Ordlyd

Bevis

Litteratur

Se også