Borne de Gilbert-Varshamov

Borne de Gilbert-Varshamov
Page d'aide sur l'homonymie Pour les articles homonymes, voir Borne.

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{KerH} = 2nk 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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Borne de Gilbert-Varshamov de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • 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 a jamais été prouvé, que les codes linéaires binaires générés par une matrice aléatoire satisfont cette borne. Elle a… …   Wikipédia en Français

  • 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 a jamais été prouvé, que les codes linéaires binaires générés par une matrice aléatoire satisfont cette borne. Elle a… …   Wikipédia en Français

  • Borne — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Borne », sur le Wiktionnaire (dictionnaire universel) Sommaire 1 …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”