Théorème du codage de source

Soit une variable aléatoire ${\displaystyle X}$, posons ${\displaystyle X^{n}=X_{1}X_{2}...X_{n}}$ la suite de ${\displaystyle n}$ variables aléatoires i.i.d de loi ${\displaystyle X}$ et en notant ${\displaystyle L(Y,\delta )}$ la longueur minimale d'un code pour ${\displaystyle Y}$ à erreur de probabilité au plus ${\displaystyle \delta }$.

Le théorème énonce que ${\displaystyle lim_{n\rightarrow \infty }{\frac {L(X^{n},\delta )}{n}}=H(X)}$, c'est-à-dire, lorsque ${\displaystyle n}$ tend vers l'infini, que ${\displaystyle X^{n}}$ ne peut être compressée en moins de ${\displaystyle n\ H(X)}$ 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.

On considère une suite de ${\displaystyle n}$ symboles provenant d'une source ${\displaystyle a}$-aire stationnaire (suite de variables i.i.d), le théorème se simplifie en: ${\displaystyle {\frac {H(X)}{log_{2}(a)}}\leq \mathbb {E} [l(X)]<{\frac {H(X)}{log_{2}(a)}}+1}$ avec ${\displaystyle l(X)}$ la longueur d'un code optimal pour ${\displaystyle X}$.

Soit donc ${\displaystyle X}$ une variable aléatoire, notons ${\displaystyle X^{n}=X_{1}X_{2}...X_{n}}$ la suite de ${\displaystyle n}$ réalisations différentes de ${\displaystyle X}$ (${\displaystyle (X_{i})_{i\leq n}}$ suivent la même loi que ${\displaystyle X}$ et sont indépendantes). Le théorème affirme que ${\displaystyle lim_{n\rightarrow \infty }{\frac {L(X^{n},\delta )}{n}}=H(X)}$, encadrons donc cette limite par deux inégalités.

Pour ${\displaystyle n\in \mathbb {N} }$ et ${\displaystyle \epsilon >0}$, on définit un ensemble de réalisations typiques de ${\displaystyle X^{n}}$ ainsi : ${\displaystyle S_{\delta }=\{x^{n}\in A^{n}/\ \mathbb {P} (X^{n}=x^{n})\geq 2^{-n(H(X)+\epsilon )}\}}$.

On a alors, avec ${\displaystyle h_{X}(x)=-\log(p(X=x))}$ et ${\displaystyle H}$ l'entropie :

${\displaystyle {\begin{aligned}\mathbb {P} (X_{1}...X_{n}\in S_{\delta })&=\mathbb {P} _{X}{\{\mathbb {P} (X^{n}=x^{n})\geq 2^{-n(H(X)+\epsilon )}\}}\\&=\mathbb {P} _{X}\{-\log {\mathbb {P} (X^{n}=x^{n})}\leq n(H(X)+\epsilon )\}\\&=\mathbb {P} _{X}\{-\log(\mathbb {P} (X_{1}=x_{1})...\mathbb {P} (X_{n}=x_{n}))\leq n(H(X)+\epsilon )\}\\&=\mathbb {P} _{X}\{\sum _{i=1}^{n}h_{X}(X_{i})\leq n(H(X)+\epsilon )\}\\&=\mathbb {P} _{X}\{{\frac {1}{n}}\sum _{i=1}^{n}h_{X}(X)\leq H(X)+\epsilon \}\\\end{aligned}}}$

Puisque ${\displaystyle H(X)=E(h_{X}(X))}$, la loi faible des grands nombres nous assure ${\displaystyle \lim _{n\rightarrow \infty }\mathbb {P} \{X_{1}...X_{n}\in S_{\delta }\}=1}$.

Pour ${\displaystyle n}$ assez grand, ${\displaystyle \mathbb {P} \{X_{1}...X_{n}\in S_{\delta }\}\geq 1-\delta }$ et comme ${\displaystyle |S_{\delta }|\leq 2^{n(H(X)+\epsilon )}}$ on peut coder cet ensemble avec moins de ${\displaystyle n(H(X)+\epsilon )}$ bits.

Ainsi ${\displaystyle {\frac {L(X^{n},\delta )}{n}}\leq H(X)+\epsilon }$ pour tout ${\displaystyle \epsilon }$ et ${\displaystyle n}$ correspondant assez grand, donc ${\displaystyle lim_{n\rightarrow \infty }{\frac {L(X^{n},\delta )}{n}}\leq H(X)}$.

Pour ${\displaystyle \epsilon >0}$, soit ${\displaystyle S\subseteq A^{n}}$ tel que ${\displaystyle |S|\leq 2^{n(H(X)-\epsilon )}}$, posons ${\displaystyle S_{s}}$ et ${\displaystyle S_{b}}$ tels que ${\displaystyle S=S_{s}\cup S_{b}}$ de cette façon :

${\displaystyle {\begin{aligned}&S_{s}=S\cap \{x^{n}|\ \mathbb {P} (X=x^{n})\leq 2^{-n(H(X)-\epsilon /2)}\}\\&S_{b}=S\cap \{x^{n}|\ \mathbb {P} (X=x^{n})>2^{-n(H(X)-\epsilon /2)}\}\end{aligned}}}$

Maintenant,

${\displaystyle {\begin{aligned}\mathbb {P} (X_{1}...X_{n}\in S)&=\mathbb {P} (X_{1}...X_{n}\in S_{s})+\mathbb {P} (X_{1}...X_{n}\in S_{b})\\&\leq |S|2^{-n(H(X)-\epsilon /2)}+\mathbb {P} \{\mathbb {P} (X^{n}=X_{1}...X_{n})>2^{-n(H(X)-\epsilon /2)}\}\\&\leq 2^{-n\epsilon /2}+\mathbb {P} \{\sum _{i=1}^{n}h_{X}(X_{i})<n(H(X)-\epsilon /2)\}\\&\leq 2^{-n\epsilon /2}+\mathbb {P} \{{\frac {1}{n}}\sum _{i=1}^{n}h_{X}(X)<(H(X)-\epsilon /2)\}\end{aligned}}}$

Le premier terme tendant vers 0, et par la loi faible des grands nombres le second aussi, on a donc ${\displaystyle \lim _{n\rightarrow \infty }\mathbb {P} (X_{1}...X_{n}\in S)=0}$ donc la probabilité de pouvoir encoder ${\displaystyle X^{n}}$ avec ${\displaystyle n(H(X)-\epsilon )}$ caractères ou moins tend vers 0. Ainsi, à partir d'un ${\displaystyle n_{\delta }}$ assez grand, elle passera en dessous de ${\displaystyle \delta }$ et donc pour tout ${\displaystyle n>n_{\delta }}$ on aura ${\displaystyle {\frac {L(X^{n},\delta )}{n}}\geq H(X)-\epsilon }$.

Comme ceci est vrai pour tout ${\displaystyle \epsilon }$: ${\displaystyle lim_{n\rightarrow \infty }{\frac {L(X^{n},\delta )}{n}}\geq H(X)}$, ce qui achève d'encadrer la limite souhaitée.

Soit ${\displaystyle X}$ une variable aléatoire et ${\displaystyle l}$ un code optimal pour ${\displaystyle X}$ (c'est-à-dire d'espérance de longueur minimale).

Pour tout ${\displaystyle i\leq n}$, avec ${\displaystyle l(x_{i})}$ la longueur du code de ${\displaystyle x_{i}}$, on définit ${\displaystyle q_{i}={\frac {a^{-l(x_{i})}}{C}}}$ avec ${\displaystyle a}$ la taille de l'alphabet sur lequel X prend des valeurs et ${\displaystyle C}$ une constante de normalisation telle que ${\displaystyle \sum q_{i}=1}$. Alors tout d'abord

${\displaystyle {\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\\end{aligned}}}$

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

${\displaystyle {\begin{aligned}H(X)&\leq -\sum _{i=1}^{n}p_{i}\log _{2}a^{-l(x_{i})}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-l(x_{i})}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-l(x_{i})p_{i}\log _{2}a\\&\leq \mathbb {E} [l(X)]\log _{2}a\\\end{aligned}}}$

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

Comme ${\displaystyle C=\sum a^{-l(x_{i})}\leq 1}$, on a ${\displaystyle \log {C}\leq 0.}$

On peut tenter de fixer ${\displaystyle l(x_{i})=\lceil -\log _{a}p_{i}\rceil }$ pour avoir ${\displaystyle -\log _{a}p_{i}\leq l(x_{i})<-\log _{a}p_{i}+1}$.

Ensuite, ${\displaystyle a^{-l(x_{i})}\leq p_{i}}$ donc ${\displaystyle \sum a^{-l(x_{i})}\leq 1}$ et l'inégalité de Kraft nous donne l'existence d'un code préfixe pour ${\displaystyle X}$ avec ces longueurs de mots là.

Finalement,

${\displaystyle {\begin{aligned}E[l(X)]&=\sum p_{i}l(x_{i})\\&<\sum p_{i}(-\log _{a}(p_{i})+1)\\&=\sum -p_{i}{\frac {log_{2}(p_{i})}{log_{2}(a)}}+1\\&={\frac {H(X)}{log_{2}(a)}}+1\end{aligned}}}$

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