Codage Source

Les 3 Types de Codes à Connaître

  1. Code à longueur fixe: - Tous les mots ont la même longueur - Facile mais pas optimal

  2. Code à longueur variable: - Plus fréquent → mot plus court - Ex: Code de Huffman

  3. Code préfixe: - Aucun mot n'est le début d'un autre - Garantit le décodage unique

Formules Essentielles

\[\begin{split}\text{Longueur moyenne} &= n(C) = \sum_{i=1}^N p(x_i)n(x_i)\\ \text{Inégalité de Kraft} &= \sum_{i=1}^N Q^{-n(x_i)} \leq 1\\ \text{Redondance} &= R = (1 - \frac{H(X)}{\log_2(N)}) \times 100\%\\ \text{Débit d'information} &= D \times H(X) \text{ [bits/sec]}\end{split}\]

Méthode de Huffman en 4 Étapes

  1. Préparation: - Lister les symboles et leurs probabilités - Ordonner par probabilités décroissantes

  2. Construction de l'arbre: a. Prendre les 2 plus petites probabilités b. Les additionner → nouveau nœud c. Répéter jusqu'à prob = 1

  3. Attribution des bits: - Gauche = 0 - Droite = 1

  4. Lecture des codes: - Suivre le chemin de la racine à chaque feuille - Noter les 0 et 1 rencontrés

Exemple Simple Résolu

Symboles | A   | B   | C   | D
Prob     | 0.4 | 0.3 | 0.2 | 0.1

  1. Construction de l'arbre:

           1.0
      /   \
    0.7   0.3(B)
   /   \
 0.4   0.3
(A)   /   \
     0.2   0.1
     (C)   (D)

  2. Codes résultants: - A = 0 - B = 11 - C = 100 - D = 101

  3. Longueur moyenne: n = 1×0.4 + 2×0.3 + 3×0.2 + 3×0.1 = 1.9 bits

Vérifications à Faire

  1. Pour tout code: - Somme des probabilités = 1 - Vérifier l'inégalité de Kraft - n(C) ≥ H(X)

  2. Pour Huffman: - Arbre binaire complet - Probabilités bien additionnées - Plus petite prob → mot le plus long

Procédure d'Examen

  1. Si on demande un code: a. Vérifier si longueur fixe possible b. Si non, faire Huffman c. Vérifier l'inégalité de Kraft

  2. Si on demande compression: a. Calculer H(X) b. Comparer avec log2(N) c. Calculer la redondance

  3. Si on demande efficacité: a. Calculer n(C) b. Comparer avec H(X) c. Plus proche = plus efficace

Tips et Pièges

  1. Pièges courants: - Oublier de vérifier la somme des probabilités - Se tromper dans l'ordre des probabilités - Mal additionner dans l'arbre

  2. Astuces: - Toujours dessiner l'arbre proprement - Noter les probabilités à chaque nœud - Vérifier que chaque symbole a un code unique