Source → Canal : Codage en deux étapes
Le chapitre 10 de Hamming s'ouvre sur le modèle de communication de Shannon, qui s'applique à chaque système qui déplace l'information : appels téléphoniques, radio, disques durs, réplication d'ADN, mémoire informatique.
L'architecture en deux étapes
Étape 1 : Codage source (compression). Convertir le message source en une représentation compacte. Objectif : éliminer la redondance inhérente à la source. Le code Morse le fait : les lettres courantes obtiennent des codes courts, les lettres rares obtiennent des codes longs.
Étape 2 : Codage de canal (protection contre les erreurs). Ajouter la redondance contrôlée adaptée aux caractéristiques de bruit du canal. Une ligne téléphonique bruyante nécessite plus de redondance qu'un câble à fibres optiques. Les deux étapes se découplent : optimiser chacune indépendamment pour sa propre tâche.
L'interface commune entre les deux étapes - un flux de bits normalisé - signifie que toute source peut s'associer avec n'importe quel canal. Cette modularité est l'aperçu architectural clé de Shannon.
Le stockage comme communication. Hamming note que l'envoi d'un message à travers l'espace (transmission) et son envoi à travers le temps (stockage) utilisent le même modèle. Un disque dur de sauvegarde est un canal bruyant dans le temps.
Le rôle du bruit
Le modèle de Shannon fait une hypothèse radicale : le bruit est inévitable. Chaque canal, chaque support de stockage, chaque circuit de commutation introduit une certaine probabilité d'erreur. La question n'est pas « comment éliminons-nous le bruit ? » mais « comment récupérons-nous le message original malgré le bruit ? »
Cela contraste avec la physique classique, où le bruit entre comme une pensée tardive (le principe d'incertitude). Shannon traite le bruit comme la condition fondamentale - toute la théorie en découle.
Pour l'instant, le chapitre 10 se concentre sur le cas sans bruit : codage source sans erreurs. Le problème du codage de canal (correction d'erreurs) attend les chapitres suivants.
Quand pouvez-vous décoder de manière unique ?
Pour qu'un code de longueur variable soit utile, le récepteur doit décoder un flux de bits sans ambiguïté. Hamming illustre avec un code à 4 symboles qui échoue à ce test, puis introduit la solution : les codes sans préfixe.
Condition sans préfixe
Un code est sans préfixe (ou instantané) si aucun mot de code n'est un préfixe d'un autre mot de code. Compte tenu d'un flux de bits reçu, vous savez qu'un symbole a terminé au moment où vous atteignez une feuille dans l'arbre de décodage - aucune anticipation requise.
Exemple de code sans préfixe pour {s1, s2, s3, s4} : s1 = 0, s2 = 10, s3 = 110, s4 = 111.
Vérifier : 0 n'est pas un préfixe de 10, 110 ou 111. 10 n'est pas un préfixe de 110 ou 111 (10 suivi de plus de bits donne 100... ou 101..., aucun ne commençant par 110 ou 111). Le code se qualifie.
La procédure de décodage : suivez l'arbre, ramifiez-vous sur chaque bit entrant, émettez le symbole quand vous atteignez une feuille, revenez à la racine.
L'inégalité de Kraft
Pour tout code binaire sans préfixe avec les longueurs de mots de code l_1, l_2, ..., l_n :
Σ 2^(−l_i) ≤ 1
L'égalité tient quand le code est complet (les feuilles occupent complètement l'arbre binaire sans lacunes). C'est une condition nécessaire : aucun code sans préfixe ne peut la violer. Inversement, pour tout ensemble de longueurs satisfaisant l'inégalité de Kraft, un code sans préfixe existe.
Appliquer l'inégalité de Kraft
Données les longueurs de code, vérifiez Kraft : Σ 2^(−l_i) ≤ 1.
Pour {s1=0, s2=10, s3=110, s4=111} : les longueurs sont 1, 2, 3, 3.
Σ = 2^(−1) + 2^(−2) + 2^(−3) + 2^(−3) = 1/2 + 1/4 + 1/8 + 1/8 = 1. ✓
L'entropie de Shannon
La longueur moyenne du code d'un code de longueur variable : L = Σ p_i · l_i, où p_i est la probabilité du symbole s_i et l_i est sa longueur de code.
Jusqu'où L peut-il aller ? La réponse de Shannon : pas en dessous de l'entropie source.
Entropie de Shannon : H = −Σ p_i · log₂(p_i) (unités : bits/symbole)
L'entropie mesure l'information moyenne par symbole. Une entropie élevée signifie que les symboles ont à peu près la même probabilité (imprévisibilité maximale). Une faible entropie signifie que certains symboles dominent (prévisibilité élevée, plus compressible).
Théorème du codage sans bruit
Pour tout code sans préfixe, H(source) ≤ L ≤ H(source) + 1.
Aucun code ne peut battre l'entropie. Le codage Huffman (chapitre suivant) atteint la borne supérieure : L < H + 1. Pour les codes de bloc sur n symboles, la borne se resserre : H ≤ L/n < H + 1/n.
L'entropie est aussi la limite théorique de compression : vous ne pouvez pas compresser une source en dessous de H bits par symbole sans perdre d'information.
Calculer l'entropie
Exemple : 4 symboles avec les probabilités p = [1/2, 1/4, 1/8, 1/8].
H = −(1/2)·log₂(1/2) − (1/4)·log₂(1/4) − (1/8)·log₂(1/8) − (1/8)·log₂(1/8)
= (1/2)·1 + (1/4)·2 + (1/8)·3 + (1/8)·3
= 0,5 + 0,5 + 0,375 + 0,375 = 1,75 bits/symbole
Et le code Huffman {0, 10, 110, 111} atteint L = 1,75 = H exactement.
Pourquoi l'entropie est une borne inférieure
La borne inférieure du théorème du codage sans bruit n'est pas juste une formule - elle reflète quelque chose de profond sur l'information : vous ne pouvez pas compresser ce qui est déjà maximalement imprévisible.
Quand tous les symboles sont également probables (distribution uniforme), l'entropie H = log₂(n) pour n symboles. Un code de bloc de longueur log₂(n) bits atteint exactement H. Aucun code ne peut faire mieux.
Quand un symbole domine (par exemple, p(A) = 0,99, p(B) = 0,01), H est petit - proche de 0. Un code de longueur variable peut assigner à A un code très court, encodant le flux très efficacement.
L'observation pratique : les gains de compression importants n'existent que quand les probabilités des symboles diffèrent substantiellement. Si la source est déjà « uniforme » (aléatoire en apparence), le codage Huffman n'apporte rien.