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.
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 .
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.