« Compression de données/Codage entropique » : différence entre les versions
Contenu supprimé Contenu ajouté
m Catégorie codage entropique |
m Typo., Replaced: c'est à dire → c'est-à-dire (4), |
||
Ligne 1 :
{{ébauche|informatique}}
{{en travaux|sylenius}}
Le '''codage entropique''' (ou '''codage statistique à longueur variable''') est une méthode de [[codage de source]] dont le but est de transformer la représentation d'une source de données pour sa [[Compression de données|compression]] sans pertes et/ou sa transmission sur un [[canal de communication]]. Le codage entropique utilise des statistiques sur la source pour construire un '''code''', c'est
Dans la théorie du codage de source, l'information à transmettre est représentée par une [[variable aléatoire]] à valeur dans un ''alphabet'' de taille finie. Un résultat important est le [[théorème du codage de source]], qui établit la limite à la possibilité de compression, et établit cette limite comme étant l'[[Entropie_de_Shannon|entropie]].
== Définitions ==
On considère une source discrète, c'est
{{Théorème|Définition|Une source est dite '''sans mémoire''' si la séquence de symboles générée par la source est une suite de [[variables indépendantes et identiquement distribuées]].}}
Ligne 15 :
L'espérance de la longueur d'un code <math>C</math> (ou longueur moyenne, selon la loi de probabilité de X) est donnée par:
:<math>L(C)=\sum_{x \in \Omega}p(x) \cdot l(x)</math>.
<math>L(C)</math> peut également se voir comme le taux de codage, c'est
{{Théorème|Définition|L''''extension''' <math>C^+</math> d'un code <math>C</math> est l'application de <math>\Omega^+</math> dans <math>A^+</math>, qui associe à une séquence de symboles de source la concaténation de ses mots de code:
Ligne 72 :
Par la méthode des [[multiplicateurs de Lagrange]], on définit le lagrangien <math>J</math>:
:<math>J=\sum_{i=1}^{|\Omega|}p_i l_i + \lambda \sum_{i=1}^{|\Omega|} D^{-l_i}</math>
que l'on différentie par rapport aux <math>l_i</math>. Un rapide calcul<ref>[[#CoTh06|Cover, Thomas (2006)]], {{p.}}110-111</ref> donne les longueurs optimales <math>l_i^*=-\log_2 p_i</math>, soit une longueur moyenne <math>L(C)=-\sum p_i \log_2 p_i</math>, c'est
Les longueurs données par cette méthode ne sont cependant pas [[entier naturel|entières]], sauf dans le cas exceptionnel où les <math>p_i</math> sont des puissance négatives de 2. Ce résultat n'est donc pas utile en pratique, et il est nécessaire d'utiliser d'autres méthodes pour construire un code optimal.
| |||