Borne de Gilbert-Varshamov

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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}(q-1)q^{n-k}

mais cette formule n'a pas été prouvée pour les codes binaires (cas q = 2), bien qu'elle a 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{KerH} = 2n − 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.