Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
L'article doit être débarrassé d'une partie de son jargon ().
Sa qualité peut être largement améliorée en utilisant un vocabulaire plus directement compréhensible.
Discutez des points à améliorer en page de discussion.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
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 ».
Le théorème du codage de source (ou premier théorème de Shannon, ou encore théorème de codage sans bruit) est un théorème en théorie de l'information, énoncé par Claude Shannon en 1948, qui énonce la limite théorique pour la compression d'une source.
Le théorème montre que l'on ne peut pas compresser une chaine de variables aléatoiresi.i.d, quand la longueur de celle-ci tend vers l'infini, de telle sorte à ce que la longueur moyenne des codes des variables soit inférieure à l'entropie de la variable source. Cependant, on peut avoir une compression avec une longueur moyenne de code arbitrairement proche de l'entropie lorsque la longueur de la chaîne tend vers l'infini.
Soit une variable aléatoire , posons la suite de variables aléatoires i.i.d de loi et en notant la longueur minimale d'un code pour à erreur de probabilité au plus .
Le théorème énonce que , c'est-à-dire, lorsque tend vers l'infini, que ne peut être compressée en moins de bits sans perte d'information presque certaine. On peut en revanche trouver un code à probabilité d'erreur négligeable approchant cette borne d'arbitrairement près.
Théorème du codage de source pour les codes par symboles
On considère une suite de symboles provenant d'une source -aire stationnaire (suite de variables i.i.d), le théorème se simplifie en: avec la longueur d'un code optimal pour .
Soit donc une variable aléatoire, notons la suite de réalisations différentes de ( suivent la même loi que et sont indépendantes). Le théorème affirme que , encadrons donc cette limite par deux inégalités.
Pour , soit tel que , posons et tels que de cette façon :
Maintenant,
Le premier terme tendant vers 0, et par la loi faible des grands nombres le second aussi, on a donc donc la probabilité de pouvoir encoder avec caractères ou moins tend vers 0. Ainsi, à partir d'un assez grand, elle passera en dessous de et donc pour tout on aura .
Comme ceci est vrai pour tout : , ce qui achève d'encadrer la limite souhaitée.
Soit une variable aléatoire et un code optimal pour (c'est-à-dire d'espérance de longueur minimale).
Pour tout , avec la longueur du code de , on définit avec la taille de l'alphabet sur lequel X prend des valeurs et une constante de normalisation telle que . Alors tout d'abord