Théorème du codage de source

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éatoires i.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.

Enoncés du théorème modifier

Théorème du codage de source modifier

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 modifier

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  .

Preuves modifier

Preuve du théorème de codage de source modifier

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.

Preuve d'atteignabilité modifier

Pour   et  , on définit un ensemble de réalisations typiques de   ainsi :  .

On a alors, avec   et   l'entropie :

 

Puisque  , la loi faible des grands nombres nous assure  .

Pour   assez grand,   et comme   on peut coder cet ensemble avec moins de   bits.

Ainsi   pour tout   et   correspondant assez grand, donc  .

Preuve inverse modifier

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.

Preuve pour les codes par symboles modifier

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

 

d'après l'Inégalité de Gibbs.

 

d'après l'Inégalité de Kraft. On a donc bien la borne inférieure.

Comme  , on a  

On peut tenter de fixer   pour avoir  .

Ensuite,   donc   et l'inégalité de Kraft nous donne l'existence d'un code préfixe pour   avec ces longueurs de mots là.

Finalement,

 

Ce qui nous donne la borne supérieure et achève la preuve.

Voir aussi modifier

Bibliographie modifier