Granița Varșamov-Gilbert

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 18 noiembrie 2021; verificarea necesită 1 editare .

Legatura Varshamov-Gilbert este o inegalitate care definește valori limită pentru parametrii de cod (nu neapărat liniari ), obținute independent de Edgar Gilbert și Rom Varshamov . Uneori se folosește numele Gilbert- Shannon - Varshamov inegalitatea , iar în literatura științifică străină - Gilbert-Varshamov inegalitatea .

Formulare

Lăsa

A_q(n,\;d)

denotă cardinalitatea maximă posibilă a --lea cod de lungime și a distanței Hamming ( --lea cod este codul cu simboluri din câmpul format din elemente). $q$ $C$ $n$ $d$ $q$ $\mathbb {F} _{q}$ $q$

Apoi

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

Când este o putere a unui număr prim , se poate simplifica inegalitatea la , unde este cel mai mare număr întreg pentru care . $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}$

Dovada

Fie codul de putere maximă pentru lungime și distanța Hamming : $C$ $n$ $d$

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

Apoi, pentru oricare , există cel puțin un cuvânt cod , astfel încât distanța Hamming între și satisface $x\in\mathbb{F}_q^n$ $c_x \în C$ $d(x,\;c_x)$ $X$ $c_x$

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

deoarece altfel am putea extinde codul cu cuvântul , lăsând neschimbată distanța Hamming , ceea ce contrazice asumarea puterii maxime . $X$ $d$ $|C|$

Prin urmare, câmpul poate fi împachetat prin unirea mulțimilor tuturor sferelor de rază centrate la : ${\mathbb {F}}_{q}^{n}$ $d-1$ $c\în C$

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

Volumul fiecărei bile

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

deoarece putem lăsa (sau alege ) cel mult --lea dintre componentele cuvântului de cod să preia una dintre celelalte valori posibile. Prin urmare, următoarea inegalitate este adevărată $(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.

Acesta este

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

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

Literatură

Gilbert EN A comparison of signaling alphabets // Bell System Technical Journal , 31:504-522 [1], 1952.
Varshamov R. R. Estimarea numărului de semnale în coduri cu corectarea erorilor // Rapoartele Academiei de Științe a URSS , 117(5):739-741 [1], 1957.

Granița Varșamov-Gilbert

Formulare

Dovada

Literatură

Vezi și