Varshamov-Gilbert határ

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 18-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Varshamov-Gilbert kötés egy egyenlőtlenség, amely határértékeket határoz meg a kódparaméterekhez (nem feltétlenül lineáris ), amelyet Edgar Gilbert és Rom Varshamov egymástól függetlenül kapott . Néha a Gilbert- Shannon - Varshamov egyenlőtlenség nevet , a külföldi tudományos irodalomban pedig a Gilbert-Varshamov egyenlőtlenséget használják .

Megfogalmazás

Hadd

A_q(n;\;d)

a hosszúság és a Hamming-távolság -edik kódjának maximális lehetséges számosságát jelöli ( a -edik kód az elemekből álló mező szimbólumait tartalmazó kód ). $q$ $C$ $n$ $d$ $q$ $\mathbb {F} _{q}$ $q$

Akkor

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

Amikor egy prímszám hatványa , az egyenlőtlenséget leegyszerűsíthetjük , ahol az a legnagyobb egész szám , amelyre . $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}$

Bizonyítás

Legyen a hossz és a Hamming-távolság maximális teljesítménykódja : $C$ $n$ $d$

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

Ekkor bármelyikhez van legalább egy kódszó , tehát a és a Hamming - távolság teljesül $x\in\mathbb{F}_q^n$ $c_x \in C$ $d(x,\;c_x)$ $x$ $c_x$

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

mert különben kibővíthetnénk a kódot a szóval , a Hamming-távolságot változatlanul hagyva , ami ellentmond a maximális teljesítmény feltételezésnek . $x$ $d$ $|C|$

Ezért a mező becsomagolható az összes sugarú gömb halmazainak egyesítésével, amelynek középpontja : ${\mathbb {F}}_{q}^{n}$ $d-1$ $c\in C$

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

Az egyes golyók hangereje

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

mert a kódszó komponenseinek legfeljebb -edik részét hagyhatjuk (vagy választhatjuk ), hogy felvegye valamelyik lehetséges értéket. Ezért igaz a következő egyenlőtlenség $(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.

Azaz

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

(helyettesítő ). $|\mathbb{F}_q^n|=q^n$

Irodalom

Gilbert EN A jelzőábécék összehasonlítása // Bell System Technical Journal , 31:504-522 [1], 1952.
Varshamov R. R. A jelek számának becslése a kódokban hibajavítással // A Szovjetunió Tudományos Akadémiájának jelentései , 117(5):739-741 [1], 1957.

Varshamov-Gilbert határ

Megfogalmazás

Bizonyítás

Irodalom

Lásd még