Théorème du codage de source

L'article doit être débarrassé d'une partie de son jargon (septembre 2020).

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.

Cet article ne cite pas suffisamment ses sources (septembre 2020).

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

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Cet article est une ébauche concernant l’informatique et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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

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.

Théorème du codage de source pour les codes par symboles

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

Preuves

Preuve du théorème de codage de source

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.

Preuve d'atteignabilité

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)}$.

Preuve inverse

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.

Preuve pour les codes par symboles

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.

Voir aussi

• Compression de données
• Codage de canal
• Théorème du codage de canal

Bibliographie

• C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379-423, July 1948.
• O. Fawzi, Cours de théorie de l'information, ENS de Lyon, Automne 2018.
• D. MacKay, Information Theory, Inference and Learning Algorithms, Cambridge University Press, 2005, (ISBN 0-521-64298-1).

• Portail de l’informatique
• Portail des télécommunications