Théorie de l’information

Ce matériel couvre les bases de la théorie de l’information, en particulier le codage source. Il s’adresse aux étudiants en informatique, télécommunications ou disciplines connexes, souhaitant comprendre les principes fondamentaux du codage, de la mesure de l’information, et des algorithmes classiques de compression.

Problématique de la communication

La communication peut être analogique ou numérique :

• Analogique : transmission via une onde continue (exemple : voltage d’un micro), utilisant des modulations d’amplitude (AM) ou de fréquence (FM). Elle repose sur l’électronique analogique et vise la fidélité à la forme d’onde.
• Numérique : transmission d’un message formé par des symboles issus d’un alphabet discret, généralement codés en séquences adaptées au canal (exemple : 0 et 1). La communication numérique utilise la communication analogique pour traverser le canal, mais vise la fidélité au message. Elle est adaptée à la minimisation de l’énergie, au stockage, à la transmission de big data, au débruitage et à l’immunité contre les erreurs.

La notion d’information et d’entropie, la compression, ainsi que les notions de bruit, d’erreurs, de détection et correction d’erreurs sont au cœur de cette problématique.

Mesure de l’information et entropie

Définition de l’information

Selon Claude Shannon, l’information est la résolution de l’incertitude. La quantité d’information d’un symbole est d’autant plus grande que sa probabilité est faible. Pour deux symboles successifs, la quantité d’information est additive.

La quantité d’information I associée à un symbole de probabilité p vérifie :

• I(p) est une fonction continue de p.
• I(p) est décroissante quand p augmente.
• I(p1 et p2) = I(p1) + I(p2).
• Un symbole certain (p=1) a une information nulle : I(1) = 0.

La fonction qui satisfait ces conditions est :

I(xk) = log(1 / pk) = -log(pk)

avec log en base 2, l’unité est le bit (ou shannon). On peut aussi utiliser nat (logarithme naturel) ou dit (log base 10).

Entropie

Soit une source S émettant N symboles s1, s2, ..., sN avec probabilités p1, p2, ..., pN. L’entropie H(S) est la quantité moyenne d’information reçue :

H(S) = Σ (k=1 à N) pk × I(sk) = - Σ (k=1 à N) pk log2(pk)

Si tous les symboles sont équiprobables (pk = 1/N), alors :

H(S) = log2(N)

Ce qui est la valeur maximale que peut atteindre l’entropie.

Exemple : source binaire

Pour une source binaire avec symboles 0 et 1 de probabilités p et 1-p :

H(S) = -p log2(p) - (1-p) log2(1-p)

Le maximum est atteint lorsque p = 0.5, donnant H(S)max = 1 bit.

Signification de l’entropie pour le codage binaire

Si un symbole est très rare, par exemple p = 1/1024, alors :

H(S) ≈ 0.0112 bits

Ce qui signifie qu’en moyenne, on a très peu d’incertitude par essai. Utiliser un bit par essai est donc inefficace. On peut coder 1024 essais en moyenne avec seulement 0.0112 bits par essai, ce qui montre l’importance de la compression.

Interprétation

L’entropie représente la limite inférieure moyenne du nombre de bits nécessaires pour coder une source sans perte. Envoyer moins de bits que cette limite entraîne une incertitude au décodage, tandis qu’envoyer plus de bits est une perte de ressources. Atteindre cette limite est l’objectif principal de la compression.

Codes de longueurs fixes

Un code de longueur fixe attribue à chaque symbole un code binaire de même longueur. Exemples :

• ASCII 7 bits pour 96 caractères imprimables.
• Unicode UTF-16.
• BCD (Binary Coded Decimal) 4 bits pour 10 chiffres décimaux.

Avantages :

• Accès aléatoire possible : on peut décoder directement le n-ième symbole.
• Tables de correspondance simples pour coder/décoder.

Limites

L’efficacité d’un code est définie par η = H(S) / R où R est la longueur du code. Par exemple, pour une source avec entropie H(S) = 1.626 bits, un code fixe de 2 bits par symbole donne une efficacité de 81,3 %.

Extension de source

Pour améliorer l’efficacité, on peut coder des blocs de J symboles au lieu d’un seul :

• Une source primaire de K symboles devient une source secondaire de K^J symboles.
• La longueur de code par bloc N ≥ J × log2(K).
• La longueur moyenne par symbole primaire R = N / J ≈ log2(K) + 1/J.

Cette technique permet d’augmenter l’efficacité η, qui tend vers 100 % lorsque J augmente.

Premier théorème de Shannon

Pour un codage sans erreur, la longueur moyenne par symbole R doit satisfaire :

R ≥ H(S)

Ce théorème découle de l’extension de source et établit la limite inférieure du codage.

Codes de longueurs variables et codes préfixes

Les codes à longueurs variables attribuent des codes binaires de longueurs différentes selon la probabilité des symboles. Un code préfixe est un code où aucun code n’est préfixe d’un autre, ce qui garantit un décodage unique et instantané.

Exemple de problème de décodage

Un code où un symbole a pour code "1" et un autre "10" n’est pas un code préfixe car "1" est préfixe de "10". Le message codé peut être interprété de plusieurs façons, ce qui est problématique.

Construction d’un arbre de code

• Un déplacement à gauche correspond à un "0".
• Un déplacement à droite correspond à un "1".
• Chaque déplacement crée un nœud.
• Un nœud sans fils est une feuille, représentant un symbole.

Inégalité de Kraft

Pour un code préfixe avec K symboles et longueurs de code n1, n2, ..., nK, l’inégalité suivante doit être satisfaite :

Σ (k=1 à K) 2^(-nk) ≤ 1

Cette condition est nécessaire et suffisante pour l’existence d’un code préfixe avec ces longueurs.

Deuxième théorème de Shannon

La longueur moyenne R d’un code à longueur variable satisfait :

H(S) ≤ R < H(S) + 1

La longueur optimale est obtenue lorsque :

nk ≈ -log2(pk)

où pk est la probabilité du symbole k.

Algorithme de Huffman

L’algorithme de Huffman construit un code préfixe optimal en minimisant la longueur moyenne :

1. Classer les symboles par ordre décroissant de probabilité.
2. Associer les deux symboles de plus faible probabilité en un nœud père, dont la probabilité est la somme des deux.
3. Remplacer ces deux symboles par ce nœud dans la liste et répéter jusqu’à obtenir un seul nœud racine.

Les symboles sont les feuilles de l’arbre final, et les codes sont déterminés par les chemins (0 à gauche, 1 à droite).

Exemple

Source : S = {(A, 1/3), (B, 1/2), (C, 1/12), (D, 1/12)}

• Itération 1 : fusionner C et D (1/12 + 1/12 = 1/6), nouvelle source S = {(A, 1/3), (B, 1/2), (CD, 1/6)}
• Itération 2 : fusionner A et CD (1/3 + 1/6 = 1/2), nouvelle source S = {(B, 1/2), (ACD, 1/2)}
• Itération 3 : fusionner B et ACD (1/2 + 1/2 = 1), arbre complet.

Remarque

Un code ne respectant pas ces règles peut avoir une longueur moyenne inférieure à l’entropie, ce qui est impossible, indiquant un code non décodable.

Autre exemple

Source : S = {(A, 0.1), (B, 0.3), (C, 0.2), (D, 0.3), (E, 0.1)}. L’algorithme de Huffman peut être appliqué pour déterminer les codes optimaux.

Algorithme de Fano-Shannon

Antérieur à Huffman, cet algorithme construit un arbre de codage en divisant la liste des symboles ordonnés en deux groupes de probabilités aussi proches que possible :

1. Ordonner les symboles par probabilité décroissante.
2. Diviser en deux groupes de probabilités proches.
3. Attribuer "0" au groupe supérieur et "1" au groupe inférieur pour le bit le plus significatif.
4. Répéter la division dans chaque sous-groupe jusqu’à ce que chaque symbole soit isolé.

Le codage obtenu est moins efficace que celui de Huffman mais partage certaines propriétés.

Exemple

Source : {(E, 0.48), (A, 0.21), (S, 0.12), (T, 0.08), (U, 0.06), (U, 0.05)}. Huffman et Fano-Shannon donnent des longueurs de code similaires dans ce cas.

Points communs entre Fano-Shannon et Huffman

• Codes à longueurs variables.
• Compression de données.
• Nécessitent la connaissance des probabilités des symboles.
• Transmission de la table de codage nécessaire.
• Appartiennent au codage statistique à longueur variable.

Huffman est utilisé dans les formats TIFF, JPEG, MNP, etc.

Limitations de Fano-Shannon et Huffman et supériorité de LZW

Limitations :

• Les probabilités des symboles peuvent être inconnues ou variables dans le temps.
• Les symboles ne sont pas toujours indépendants identiquement distribués (iid), comme dans le texte anglais où le contexte est important.

Par exemple, l’entropie calculée sans contexte pour l’anglais est environ 4.177 bits/symbole, mais en tenant compte du contexte, elle peut descendre entre 0.6 et 1.3 bits/lettre.

Algorithme Lempel-Ziv-Welch (LZW)

Développé dans les années 1970-1980, LZW est un algorithme sans connaissance préalable des probabilités. Il construit un dictionnaire dynamique des séquences répétées dans le message à compresser :

• Un dictionnaire initial contient tous les symboles de base.
• Lors du traitement, l’encodeur construit un tableau associant des séquences de symboles à des codes fixes de N bits.
• L’encodeur transmet l’indice de la séquence dans le dictionnaire au lieu de la séquence elle-même.
• Le dictionnaire est reconstruit par le décodeur à partir du flux codé, il n’est jamais transmis.
• Une réinitialisation du dictionnaire est effectuée lorsque celui-ci est plein.

Exemple

Codage de la chaîne "abbbabbbab...". Le dictionnaire évolue en ajoutant les séquences répétées et les remplace par des indices.

Exemple avancé

Codage de "LES PAGES D’IMAGES D’ORAGES" avec ajout de caractères spéciaux de contrôle. Le message codé sur 10 bits (dictionnaire de 1024 mots) occupe 200 bits contre 216 bits en ASCII 8 bits, soit un taux de compression de 92,6 %.

Code par répétition

Le codage par répétition, ou RLE (Run Length Encoding), est une méthode simple qui remplace les séquences de symboles identiques consécutifs par :

1. Un nombre indiquant le nombre de répétitions.
2. La donnée répétée elle-même.

Exemple :

La séquence binaire 11111111000001111110000 devient :

81 50 61 40

On peut optimiser en ne précisant que la nature du premier bit :

81 5 6 4

Pour les données en couleur, un caractère séparateur "#" est utilisé pour éviter la confusion entre le nombre de répétitions et la valeur de la couleur :

#8 8#7 24#4 67#

RLE est utilisé dans des logiciels d’images (PCX, IFF/LBM, JPEG) et dans la télécopie (normes CCITT groupes 3 et 4).

Glossaire des termes clés

• Entropie (H(S)) : Quantité moyenne d’information d’une source, limite inférieure du codage.
• Code préfixe : Code où aucun code n’est préfixe d’un autre, garantissant un décodage unique et instantané.
• Code à longueur fixe : Code où tous les symboles ont la même longueur de code binaire.
• Code à longueur variable : Code où la longueur des codes varie selon la probabilité des symboles.
• Algorithme de Huffman : Méthode de construction d’un code préfixe optimal minimisant la longueur moyenne.
• Algorithme de Fano-Shannon : Méthode de codage basée sur la division récursive des symboles en groupes de probabilités proches.
• Algorithme LZW : Algorithme de compression sans connaissance préalable des probabilités, utilisant un dictionnaire dynamique.
• RLE (Run Length Encoding) : Codage par répétition remplaçant les séquences consécutives par un compte et la donnée.
• Longueur moyenne (R) : Moyenne pondérée des longueurs des codes, R = Σ pk × nk.
• Efficacité (η) : Rapport entre l’entropie et la longueur moyenne du code, η = H(S) / R.

Points clés à retenir

• L’entropie mesure la quantité moyenne d’information et fixe la limite inférieure du codage.
• Les codes à longueur fixe sont simples mais peu efficaces pour des symboles non équiprobables.
• Les codes préfixes à longueur variable, comme ceux construits par Huffman, permettent une compression proche de l’entropie.
• L’algorithme de Huffman est optimal pour un codage instantané avec connaissance des probabilités.
• Le codage de Fano-Shannon est une méthode plus ancienne, moins efficace que Huffman.
• Les algorithmes LZW permettent une compression efficace sans connaissance préalable des probabilités, adaptés à des données avec redondances complexes.
• Le codage par répétition (RLE) est simple et efficace pour des données avec longues séquences répétées.