Borne de Gilbert-Varshamov

La borne de Gilbert-Varshamov est une minoration de la distance minimale des codes. On suppose habituellement, bien que cela n'ait jamais été prouvé, que les codes linéaires binaires générés par une matrice aléatoire satisfont cette borne. Elle a une valeur voisine de ${\displaystyle 0,11n}$ lorsque ${\displaystyle n=2k}$, ce qui permet de dire qu'il y a de fortes chances qu'il n'y ait pas de mots non nuls du code de poids inférieur à ${\displaystyle 0,11n.}$

Pour un code linéaire quelconque sur ${\displaystyle \mathbb {F} _{q},}$ on a montré que le nombre moyen de mots de poids ${\displaystyle w}$ d'un code était proche de : ${\displaystyle {n \choose w}{\dfrac {(q-1)}{q^{n-k}}}}$

mais cette formule n'a pas été prouvée pour les codes binaires (cas ${\displaystyle q=2}$), bien qu'elle ait des chances de ne pas être trop éloignée de la vérité. En effet, pour ${\displaystyle x}$ aléatoire, les événements (${\displaystyle Hx=i}$) sont équiprobables, et en supposant que les mots du code soient répartis aléatoirement, suivant une loi binomiale de probabilité élémentaire ${\displaystyle p=1/2}$ (ce qui est loin d'être prouvé), on a : ${\displaystyle card\{x,Hx=0\}=card\{KerH\}=2^{n-k}}$ ${\displaystyle P(|x|=w)={\frac {n \choose w}{2^{n}}}.}$ On remarque, expérimentalement, que, pour un code binaire aléatoire, cette formule donne un nombre non nul de mots de poids ${\displaystyle w}$ si ${\displaystyle w}$ est supérieur à la borne de Gilbert-Varshamov (ce nombre croît alors extrêmement rapidement avec ${\displaystyle w}$), et nul si ${\displaystyle w}$ est inférieur à celle-ci.

Notes et références

Voir aussi

• Edgar Gilbert
• Rom Varshamov (en)

• Portail des mathématiques
• Portail de l'informatique théorique