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.