Théorie de l’information
Théorie de l’information
Communication, Information Theory, Data Compression · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
La communication peut être analogique ou numérique :
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.
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 :
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).
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.
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.
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.
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.
Un code de longueur fixe attribue à chaque symbole un code binaire de même longueur. Exemples :
Avantages :
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 %.
Pour améliorer l’efficacité, on peut coder des blocs de J symboles au lieu d’un seul :
Cette technique permet d’augmenter l’efficacité η, qui tend vers 100 % lorsque J augmente.
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.
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é.
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.
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.
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.
L’algorithme de Huffman construit un code préfixe optimal en minimisant la longueur moyenne :
Les symboles sont les feuilles de l’arbre final, et les codes sont déterminés par les chemins (0 à gauche, 1 à droite).
Source : S = {(A, 1/3), (B, 1/2), (C, 1/12), (D, 1/12)}
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.
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.
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 :
Le codage obtenu est moins efficace que celui de Huffman mais partage certaines propriétés.
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.
Huffman est utilisé dans les formats TIFF, JPEG, MNP, etc.
Limitations :
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.
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 :
Codage de la chaîne "abbbabbbab...". Le dictionnaire évolue en ajoutant les séquences répétées et les remplace par des indices.
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 %.
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 :
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).