Théorème du codage de source

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le Théorème du codage de source (ou premier théorème de Shannon, ou moins usité en français, théorème de codage sans bruit) est un théorème énoncé par Claude Shannon en 1948, qui énonce la limite théorique pour la compression d'une source.

Le raisonnement de Shannon se base sur des vecteurs de n symboles et sur une source q-aire stationnaire (suite de variables indépendantes et identiquement distribuées). Le théorème montre que lorsque n\to+\infty, la longueur moyenne du code tend vers l'entropie.

Pour les codes par symboles, le théorème se simplifie en: \frac{H(X)}{log(q)} \le E[l(X)] < \frac{H(X)}{log(q)}+1.

avec l(X) la longueur du code pour le mot X, et E l'espérance.

Bibliographie[modifier | modifier le code]