Borne de Gilbert-Varshamov

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Borne.
Cet article ne cite pas suffisamment ses sources (décembre 2012).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

La borne de Gilbert-Varshamov est une minoration de la distance minimale des codes. On suppose habituellement, bien que cela n'a 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 0,11n lorsque 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 à 0,11n.

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

mais cette formule n'a pas été prouvée pour les codes binaires (cas q=2), bien qu'elle ait des chances de ne pas être trop éloignée de la vérité. En effet, pour x aléatoire, les événements (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 p=1/2 (ce qui est loin d'être prouvé), on a : card\{x,Hx=0\}=card\{Ker H\}=2^{n-k} 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 w si w est supérieur à la borne de Gilbert-Varshamov (ce nombre croît alors extrêmement rapidement avec w), et nul si w est inférieur à celle-ci.