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 .
Lăsa
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).
Apoi
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 .
Fie codul de putere maximă pentru lungime și distanța Hamming :
Apoi, pentru oricare , există cel puțin un cuvânt cod , astfel încât distanța Hamming între și satisface
deoarece altfel am putea extinde codul cu cuvântul , lăsând neschimbată distanța Hamming , ceea ce contrazice asumarea puterii maxime .
Prin urmare, câmpul poate fi împachetat prin unirea mulțimilor tuturor sferelor de rază centrate la :
Volumul fiecărei bile
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ă
Acesta este
(înlocuind ).