« Compression de données/Codage entropique » : différence entre les versions

Contenu supprimé Contenu ajouté
Annulation de la modification de Calin-info (d)
→‎Propriétés des codes de source : ajout de l'idée de la démonstration code préfixe => uniquement décodable
Ligne 31 :
{{Théorème|Définition|Un code est un [[code préfixe]] si aucun mot de code n'est le préfixe d'un autre mot de code.}} L'intérêt des codes préfixés est qu'ils sont décodables immédiatement, en les parcourant de la gauche vers la droite. La fin d'un mot de code est reconnaissable immédiatement, sans la nécessité d'un code spécial pour indiquer la terminaison ou une séparation<ref name=McKay92/>{{,}}<ref>[[#CoTh06|Cover, Thomas (2006)]], {{p.}}106</ref>. De plus, les codes préfixes sont uniquement décodables.
 
{{Démonstration|
Soient <math>x_1x_2\dots x_m, y_1y_2\dots y_n</math> tels que <math> C^+(x_1x_2\dots x_m) = C^+(y_1y_2\dots y_n)</math>.
On a alors <math> C^+(x_1x_2\dots x_m) = C(x_1)C^+(x_2\dots x_m) = C(y_1)C^+(y_2\dots y_n) </math>.
Supposons, sans perte de généralité, que <math> |C(x_1)| \leqslant |C(y_1)| </math>.
<math> C(x_1) </math> est alors préfixe de <math> C(y_1) </math>.
Or C est sans préfixe, donc <math> x_1 = y_1 </math>.
Par récurrence sur (m,n) muni de l'ordre produit, on peut donc montrer : <math>x_1x_2\dots x_m = y_1y_2\dots y_n</math>
}}
*Exemple: Soit le code défini par le tableau suivant
{| class="wikitable centre" style="text-align:center; width:80%;"