Borne de Gilbert-Varshamov

La limite de Gilbert-Varshamov est une minoration de la distance minimale des codes. On suppose généralement, quoique cela n'a jamais été prouvé, que les codes linéaires binaires générés par une matrice aléatoire satisfont cette limite.



Catégories :

Théorie des codes - Probabilités

Page(s) en rapport avec ce sujet :

  • ... des codes qui atteignent de manière asymptotique la limite de Gilbert - Varshamov... Mots -clés anglais / English Keywords. Code ; Reed Solomon code ; Limit ; Linear... Code ; Code Reed Solomon ; Limite ; Code linéaire ; Code linéaire... (source : cat.inist)

La limite de Gilbert-Varshamov est une minoration de la distance minimale des codes. On suppose généralement, quoique cela n'a jamais été prouvé, que les codes linéaires binaires générés par une matrice aléatoire satisfont cette limite. Elle a une valeur voisine de 0, 11n quand n = 2k, ce qui sert à 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), quoiqu'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 limite de Gilbert-Varshamov (ce nombre croît alors extrêmement rapidement avec w), et nul si w est inférieur à celle-ci.

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Borne_de_Gilbert-Varshamov.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu