Théorie de l’Information, Codage et Canaux

Cours Simplifié et Complet

Table des matières

1 Introduction à la Théorie de l’Information 3

1.1 Objectif principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Principe fondamental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Mesure de l’Information 3
2.1 Information propre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Entropie 4
3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Propriétés fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Entropie conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 Codage de Source 4
4.1 Définitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4.2 Types de codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2.1 Codes de longueur fixe . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2.2 Codes à décodage unique . . . . . . . . . . . . . . . . . . . . . . . . 5
4.3 Représentation par arbres binaires . . . . . . . . . . . . . . . . . . . . . . . 5

5 Théorèmes Fondamentaux 6
5.1 Inégalité de Kraft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2 Théorème de MacMillan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.3 Premier Théorème de Shannon . . . . . . . . . . . . . . . . . . . . . . . . 6

6 Algorithmes de Codage 6
6.1 Code de Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
6.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
6.1.2 Optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.1.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.2 Code de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6.3 Codage Arithmétique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3.1 Principe fondamental . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3.2 Algorithme de codage . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3.3 Algorithme de décodage . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3.4 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1
Cours Complet Simplifié Théorie de l’Information

6.4 Codage Universel - Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . . 9

6.4.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.4.2 Algorithme Lempel-Ziv 78 . . . . . . . . . . . . . . . . . . . . . . . 9

7 Canaux de Transmission 9
7.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.1.1 Canal discret sans mémoire . . . . . . . . . . . . . . . . . . . . . . 9
7.1.2 Matrice de transition . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.2 Capacité d’un Canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.3 Canal Binaire Symétrique (CBS) . . . . . . . . . . . . . . . . . . . . . . . 10
7.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.3.2 Calcul de la capacité . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7.4 Canaux Symétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
7.4.1 Canal symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
7.4.2 Canal fortement symétrique . . . . . . . . . . . . . . . . . . . . . . 11
7.4.3 Canal symétrique général . . . . . . . . . . . . . . . . . . . . . . . . 11
7.5 Exemples de Canaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

8 Codes Correcteurs d’Erreurs 12

8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.2 Concepts de Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.2.1 Distance de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.2.2 Distance minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.3 Capacité de Détection et Correction . . . . . . . . . . . . . . . . . . . . . . 12
8.3.1 Détection d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
8.3.2 Correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.4 Codes Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.4.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.4.2 Matrice génératrice . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.4.3 Matrice de parité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.5 Boules de Hamming et Codes Parfaits . . . . . . . . . . . . . . . . . . . . . 13
8.5.1 Boule de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
8.5.2 Codes parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.6 Exemples de Codes Parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.6.1 Code à répétition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.6.2 Code de Hamming Hm . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.7 Exemples de Codes Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 15
8.7.1 Exemple 1 - Code trivial . . . . . . . . . . . . . . . . . . . . . . . . 15
8.7.2 Exemple 2 - Code avec redondance . . . . . . . . . . . . . . . . . . 15

9 Résumé et Conclusions 15
9.1 Concepts clés du codage de source . . . . . . . . . . . . . . . . . . . . . . . 15
9.2 Concepts clés des canaux et codes correcteurs . . . . . . . . . . . . . . . . 16
9.3 Formules essentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
9.4 Principes fondamentaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
9.5 Message final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2
Cours Complet Simplifié Théorie de l’Information

1 Introduction à la Théorie de l’Information

1.1 Objectif principal
La théorie de l’information étudie comment mesurer, transmettre et coder l’informa-
tion de manière efficace. Elle s’intéresse particulièrement à :
— La quantification de l’information
— La compression des données
— La transmission fiable malgré le bruit

1.2 Principe fondamental

Idée clé : Plus un événement est improbable, plus il apporte d’information lorsqu’il
se réalise.
Exemple : Au journal télévisé, la phrase ”Bonsoir” n’apporte presque aucune infor-
mation (très probable), tandis que ”Le monde a peur” capte immédiatement l’attention
(très improbable).

2 Mesure de l’Information
2.1 Information propre
Définition : L’information propre d’un événement x ayant une probabilité p(x) est :
I(x) = − log2 p(x) (en bits)
Propriétés importantes :
— Plus l’événement est rare, plus son information est grande
— Un événement certain (p(x) = 1) n’apporte aucune information : I(x) = 0
— L’information est toujours positive ou nulle
Exemple : Considérons une source de 16 symboles équiprobables :
1
— Probabilité de chaque symbole : p(ak ) = 16
1
— Information propre : I(ak ) = − log2 ( 16 ) = 4 bits
— Ce résultat correspond au nombre de bits nécessaires pour représenter 16 symboles
différents

2.2 Information mutuelle

Définition : L’information mutuelle entre deux événements x et y mesure ce que
l’observation de l’un apporte sur l’autre :
p(x|y)
I(x; y) = log2 = I(x) − I(x|y)
p(x)
Interprétation :
— I(x; y) > 0 : observer y augmente la probabilité de x (gain d’information)
— I(x; y) < 0 : observer y diminue la probabilité de x (perte d’information)
— I(x; y) = 0 : x et y sont indépendants (aucune information)

3
Cours Complet Simplifié Théorie de l’Information

3 Entropie
3.1 Définition
Entropie : L’entropie d’une source discrète X est la moyenne de l’information propre :
X
H(X) = − p(x) log2 p(x)
x∈X

Signification : L’entropie représente le nombre moyen minimal de bits nécessaires

pour coder une lettre de la source.

3.2 Propriétés fondamentales

Théorème : Pour une source de K symboles :

H(X) ≤ log2 K

L’égalité est atteinte si et seulement si tous les symboles sont équiprobables (loi uni-
forme).
Exemple - Source binaire :
— Alphabet : {0, 1} avec probabilités p et (1 − p)
— Entropie : H(X) = −p log2 p − (1 − p) log2 (1 − p)
— Maximum : H(X) = 1 bit quand p = 0.5 (équiprobable)

3.3 Entropie conditionnelle

Définition : Dans un espace joint XY , l’entropie conditionnelle est :
X
H(X|Y ) = − p(x, y) log2 p(x|y)
x,y

Propriété importante :
H(X|Y ) ≤ H(X)
Le conditionnement réduit toujours l’incertitude (ou la laisse inchangée si X et Y sont
indépendants).

4 Codage de Source
4.1 Définitions de base
Code : Application qui associe à chaque lettre de la source un mot binaire (mot de
code).
Longueur moyenne : Pour un code ϕ :
X
|ϕ| = p(x) · |ϕ(x)|
x∈X

où |ϕ(x)| est la longueur du mot de code associé à x.

4
Cours Complet Simplifié Théorie de l’Information

Efficacité : Mesure la qualité du codage :

H(X)
E=
|ϕ|
Plus l’efficacité est proche de 1, meilleur est le code.

4.2 Types de codes

4.2.1 Codes de longueur fixe
Définition : Tous les mots de code ont la même longueur n.
Proposition : Pour coder K symboles, la longueur nécessaire vérifie :
log2 K ≤ n < 1 + log2 K
Exemple - Chiffres décimaux :
— Alphabet : {0, 1, ..., 9} avec 10 symboles
— Longueur nécessaire : n = 4 bits (car 23 = 8 < 10 ≤ 24 = 16)
— Si uniforme : H(X) = log2 10 ≈ 3.32 bits
— Efficacité : E = 3.32
4
≈ 0.83
Amélioration par blocs : En codant des paires de chiffres (100 possibilités) sur 7
bits :
— Efficacité : E = 2×3.32
7
≈ 0.95
— En codant des triplets sur 10 bits : E ≈ 0.996

4.2.2 Codes à décodage unique

Code déchiffrable : Un code dont l’application de codage est injective. On peut
retrouver de manière unique la séquence d’origine.
Code préfixe (ou instantané) : Aucun mot de code n’est le début d’un autre mot
de code.
Propriété : Tout code préfixe est déchiffrable (mais la réciproque est fausse).
Exemple - Code non préfixe mais déchiffrable :
— a1 → 1, a2 → 10, a3 → 100
— Ce code n’est pas préfixe (1 est préfixe de 10 et 100)
— Mais il est déchiffrable : on sépare avant chaque ”1”

4.3 Représentation par arbres binaires

Principe : Les codes préfixes se représentent naturellement par des arbres binaires :
— Chaque branche est étiquetée par 0 ou 1
— Les mots de code correspondent aux feuilles
— L’ordre d’un nœud est sa distance à la racine
Propriété : Un code est préfixe si et seulement si ses mots de code sont exactement
les feuilles de son arbre.
Code irréductible : Un code préfixe est irréductible si chaque nœud a exactement
0 ou 2 fils.

5
Cours Complet Simplifié Théorie de l’Information

5 Théorèmes Fondamentaux
5.1 Inégalité de Kraft
Théorème de Kraft : Il existe un code préfixe de K mots de longueurs n1 , ..., nK si
et seulement si :
XK
2−nk ≤ 1
k=1

Signification : Cette inégalité donne une condition nécessaire et suffisante sur les
longueurs des mots pour qu’un code préfixe existe.

5.2 Théorème de MacMillan

Théorème : Il existe un code déchiffrable de longueurs n1 , ..., nK si et seulement si :
K
X
2−nk ≤ 1
k=1

Corollaire important : S’il existe un code déchiffrable avec certaines longueurs, alors
il existe un code préfixe avec les mêmes longueurs.

5.3 Premier Théorème de Shannon

Théorème (version simple) : Pour toute source discrète sans mémoire d’entropie
H :
— Tout code déchiffrable vérifie : |ϕ| ≥ H
— Il existe un code préfixe tel que : |ϕ| < H + 1
Théorème (version forte) : Pour toute source et tout ε > 0, il existe un codage
déchiffrable d’efficacité supérieure à 1 − ε.
Méthode - Codage par blocs :
1. On regroupe les lettres de la source par blocs de l lettres
2. On code la source produit X l dont l’entropie est H(X l ) = l · H(X)
3. D’après la version simple : lH ≤ |ϕl | < lH + 1
|ϕl | 1
4. La longueur moyenne par lettre devient : H ≤ l
<H+ l
5. Quand l augmente, l’efficacité tend vers 1

6 Algorithmes de Codage
6.1 Code de Huffman
6.1.1 Principe
Le code de Huffman est un algorithme qui construit un code préfixe optimal en
construisant un arbre binaire de manière ascendante.
Algorithme :

6
Cours Complet Simplifié Théorie de l’Information

1. Créer une feuille pour chaque symbole avec son poids (probabilité)
2. Répéter jusqu’à avoir un seul arbre :
— Sélectionner les deux arbres de poids minimal
— Les fusionner en un nouvel arbre dont le poids est la somme des deux poids
— Attribuer 0 à une branche et 1 à l’autre
3. Lire les codes en parcourant de la racine aux feuilles

6.1.2 Optimalité
Proposition : Le code de Huffman est optimal parmi tous les codes préfixes.
Propriétés d’un code optimal :
1. Les symboles de plus grande probabilité ont les codes les plus courts
2. Si p(xi ) > p(xj ), alors |ϕ(xi )| ≤ |ϕ(xj )|
3. Les deux symboles les moins probables ont des codes de même longueur
4. Le code est irréductible

6.1.3 Limitations
Problème principal : Huffman impose d’utiliser un nombre entier de bits par sym-
bole.
Conséquence : La longueur moyenne vérifie :
H(X) ≤ |ϕ| < H(X) + 1
Si l’entropie est faible (par exemple H = 0.2 bits), ce surcoût d’un bit est très impor-
tant.
Exemple problématique :
— Probabilités : p1 = 0.9, p2 = 0.1
— Huffman : 1 bit par symbole
— Entropie : H ≈ 0.47 bits
— Efficacité : seulement 47%
Solutions :
— Codage par blocs (augmente la complexité)
— Huffman adaptatif (mise à jour dynamique)
— Codage arithmétique (solution idéale)

6.2 Code de Shannon

Construction : Pour chaque symbole xi de probabilité pi :
1. Calculer la longueur : li = ⌈− log2 pi ⌉
P
2. Calculer la fonction cumulative : S(xi ) = j<i pj
3. Le code est la représentation binaire de S(xi ) sur li bits
Propriété : Le code de Shannon est préfixe.
Longueur moyenne :
H(X) ≤ |ϕ| < H(X) + 1
Remarque : Shannon n’est pas toujours optimal (contrairement à Huffman).

7
Cours Complet Simplifié Théorie de l’Information

6.3 Codage Arithmétique

6.3.1 Principe fondamental
Idée clé : Au lieu de coder chaque symbole individuellement, on code toute la séquence
par un unique nombre réel dans l’intervalle [0, 1).
Avantage majeur : Permet d’utiliser un nombre non entier de bits par symbole,
atteignant exactement l’entropie.

6.3.2 Algorithme de codage

Préparation : Pour chaque symbole xi , calculer :
— Sa probabilité p(xi )
P
— Sa fonction cumulative : S(xi ) = j<i p(xj )
Codage :
1. Initialisation : a = 0, b = 1 (intervalle [0, 1))
2. Pour chaque symbole xi à coder :
— Calculer nouvel intervalle : [a′ , b′ )
— a′ = a + (b − a) × S(xi )
— b′ = a + (b − a) × (S(xi ) + p(xi ))
— Mettre à jour : a = a′ , b = b′
3. Le code final est un nombre dans l’intervalle [a, b)

6.3.3 Algorithme de décodage

Entrée : Nombre réel r obtenu par le codage
Décodage :
1. Tant que r ̸= 0 :
— Trouver le symbole xi dont l’intervalle contient r
— Afficher xi
— Mettre à jour : r = r−S(x
p(xi )
i)

6.3.4 Performance
Longueur moyenne : Le codage arithmétique atteint exactement :

|ϕ| = H(X)

Comparaison avec Huffman :

Exemple 1 - Trois symboles équiprobables :
— Huffman : A → 0, B → 10, C → 11
5
— Longueur moyenne Huffman : 3
≈ 1.667 bits
— Entropie : H = log2 3 ≈ 1.585 bits
— Arithmétique : exactement 1.585 bits (5% mieux)
Exemple 2 - Distribution déséquilibrée :
— Probabilités : 0.9 et 0.1

8
Cours Complet Simplifié Théorie de l’Information

— Huffman : 1 bit par symbole

— Entropie : H ≈ 0.47 bits
— Arithmétique : 0.47 bits (plus de 2 fois mieux)
Remarque importante : Le codage arithmétique est toujours meilleur ou égal à
Huffman, sauf dans le cas dyadique (probabilités puissances de 2).

6.4 Codage Universel - Lempel-Ziv

6.4.1 Principe
Codage universel : Algorithme qui ne suppose rien sur les statistiques de la source.
Méthode à base de dictionnaire : Lempel-Ziv construit dynamiquement un dic-
tionnaire de motifs rencontrés.

6.4.2 Algorithme Lempel-Ziv 78

Principe :
1. Initialiser un dictionnaire vide
2. Lire la séquence d’entrée
3. Chercher le plus long motif déjà dans le dictionnaire
4. Coder : (position dans le dictionnaire, nouveau caractère)
5. Ajouter le nouveau motif au dictionnaire
Avantages :
— Adaptatif : s’adapte automatiquement aux statistiques
— Prend en compte les dépendances entre symboles
— Pas besoin de connaı̂tre les probabilités à l’avance
Applications : Compression de fichiers (ZIP), format d’image GIF.

7 Canaux de Transmission
7.1 Définitions
7.1.1 Canal discret sans mémoire
Définition : Un canal discret est défini par :
— Un alphabet d’entrée X = {a1 , ..., aK }
— Un alphabet de sortie Y = {b1 , ..., bJ }
— Une loi de transition PY |X (matrice stochastique Π)
Notation : Canal T = (X, Y, Π)
Sans mémoire : La probabilité de recevoir y ne dépend que du symbole x émis (pas
de l’historique).

9
Cours Complet Simplifié Théorie de l’Information

7.1.2 Matrice de transition

Élément de la matrice : Πij = p(bj |ai )

Propriété : La somme des éléments d’une ligne vaut 1 :
J
X
p(bj |ai ) = 1
j=1

7.2 Capacité d’un Canal

7.2.1 Définition
Information mutuelle moyenne :

I(X; Y ) = H(X) − H(X|Y ) = H(Y ) − H(Y |X)

Capacité : La capacité d’un canal est le maximum de l’information mutuelle sur

toutes les lois d’émission possibles :

C = max I(X; Y )
pX

Interprétation :
— H(X) : information moyenne émise
— H(X|Y ) : information perdue (due au bruit)
— I(X; Y ) = H(X) − H(X|Y ) : information correctement transmise
— C : quantité maximale d’information transmissible sans erreur

7.3 Canal Binaire Symétrique (CBS)

7.3.1 Description
Paramètres :
— Entrée : X = {0, 1}
— Sortie : Y = {0, 1}
— Probabilité d’erreur : ε
— Probabilité de transmission correcte : 1 − ε
Loi de transition :

p(0|0) = p(1|1) = 1 − ε
p(1|0) = p(0|1) = ε

7.3.2 Calcul de la capacité

Soit α = p(X = 0), alors :
1. Probabilités de sortie :

p(Y = 0) = α(1 − ε) + (1 − α)ε

p(Y = 1) = αε + (1 − α)(1 − ε)

10
Cours Complet Simplifié Théorie de l’Information

2. Entropie de sortie :
H(Y ) = −p(Y = 0) log2 p(Y = 0) − p(Y = 1) log2 p(Y = 1)
3. Entropie conditionnelle : (indépendante de α)
H(Y |X) = −ε log2 ε − (1 − ε) log2 (1 − ε)
4. Information mutuelle :
I(X; Y ) = H(Y ) − H(Y |X)
5. Capacité : Pour maximiser I(X; Y ), il faut maximiser H(Y ), ce qui est atteint
quand α = 0.5 (entrée équiprobable).
Résultat final :
C = 1 − H(ε) = 1 + ε log2 ε + (1 − ε) log2 (1 − ε)
Cas particuliers :
— ε = 0 (pas d’erreur) : C = 1 bit
— ε = 0.5 (bruit maximum) : C = 0 bit
— ε = 1 (inversion systématique) : C = 1 bit (on inverse à la réception)

7.4 Canaux Symétriques

7.4.1 Canal symétrique
Définition : Un canal est symétrique si chaque ligne de la matrice de transition est
une permutation des autres lignes, et chaque colonne est une permutation des autres
colonnes.
Propriété fondamentale : Pour un canal symétrique, H(Y |X) ne dépend que de la
loi de transition (pas de la loi d’entrée).

7.4.2 Canal fortement symétrique

Définition : Un canal est fortement symétrique si :
— Toutes les lignes sont identiques (à permutation près)
— Toutes les colonnes sont identiques (à permutation près)
Propriété : Si la loi d’entrée est uniforme, alors la loi de sortie est aussi uniforme.
Capacité d’un canal fortement symétrique :
C = log2 |Y | − H(ligne de Π)
La capacité est atteinte pour une loi d’émission uniforme.

7.4.3 Canal symétrique général

Méthode : Décomposer le canal en canaux fortement symétriques T1 , ..., Tm de capa-
cités C1 , ..., Cm .
Capacité : !
Xm
C = log2 2Ci
i=1

11
Cours Complet Simplifié Théorie de l’Information

7.5 Exemples de Canaux

Canal sans bruit :
— Pas d’erreur : p(y|x) = 1 si y correspond à x
— Capacité : C = log2 |X| (pas de perte d’information)
Canal complètement bruité :
— La sortie est indépendante de l’entrée
— Capacité : C = 0 (aucune information transmise)

8 Codes Correcteurs d’Erreurs

8.1 Introduction
Objectif : Ajouter de la redondance aux données pour pouvoir détecter et corriger
les erreurs de transmission.
Principe : On envoie n bits pour coder k bits d’information (n > k).

8.2 Concepts de Base

8.2.1 Distance de Hamming
Définition : La distance de Hamming entre deux mots x et y de même longueur est
le nombre de positions où ils diffèrent :

d(x, y) = |{i : xi ̸= yi }|

Exemple :
— x = 10110, y = 11010
— d(x, y) = 2 (positions 2 et 4)
Propriétés :
— d(x, y) ≥ 0 avec égalité ssi x = y
— d(x, y) = d(y, x) (symétrie)
— d(x, z) ≤ d(x, y) + d(y, z) (inégalité triangulaire)

8.2.2 Distance minimale

Définition : Pour un code C, la distance minimale est :

d= min d(c1 , c2 )
c1 ,c2 ∈C,c1 ̸=c2

Importance : La distance minimale détermine la capacité de détection et correction.

8.3 Capacité de Détection et Correction

8.3.1 Détection d’erreurs
Théorème : Un code de distance minimale d peut détecter jusqu’à d − 1 erreurs.
Explication : Si un mot reçu diffère d’un mot de code valide, on détecte une erreur.

12
Cours Complet Simplifié Théorie de l’Information

8.3.2 Correction d’erreurs

Théorème : Un code de distance minimale d peut corriger jusqu’à :
 
d−1
t= erreurs
2

Principe : On choisit le mot de code le plus proche du mot reçu (décodage par
maximum de vraisemblance).

8.4 Codes Linéaires

8.4.1 Définition
Code linéaire : Code qui forme un sous-espace vectoriel de dimension k dans Fnq .
Paramètres : Code (n, k, d) où :
— n : longueur des mots de code
— k : dimension (nombre de bits d’information)
— d : distance minimale
k
Taux de transmission : R = n

8.4.2 Matrice génératrice

Définition : Matrice G de taille k × n telle que tout mot de code c s’écrit : c = uG
où u est le vecteur d’information de longueur k.
Forme systématique : Une matrice génératrice est systématique si elle a la forme :
G = (Ik |P ) où Ik est la matrice identité de taille k et P est une matrice k × (n − k).
Avantage : Dans un code systématique, les k premiers bits du mot de code sont
exactement les bits d’information.

8.4.3 Matrice de parité

Définition : Matrice H de taille (n − k) × n telle que : c ∈ C ⇔ HcT = 0
Lien avec la matrice génératrice : Si G = (Ik |P ), alors : H = (−P T |In−k )
Utilisation : La matrice de parité sert à détecter les erreurs.

8.5 Boules de Hamming et Codes Parfaits

8.5.1 Boule de Hamming
Définition : La boule de rayon t centrée en un mot c est : B(c, t) = {x ∈ Fnq : d(x, c) ≤
t} Pt n


Cardinal : Le nombre d’éléments dans une boule de rayon t est : |B(c, t)| = j=0 j (q−
1)j Pt n


Pour un code binaire (q = 2) : |B(c, t)| = j=0 j

13
Cours Complet Simplifié Théorie de l’Information

8.5.2 Codes parfaits

Définition : Un code est parfait si les boules de rayon t = ⌊ d−12
⌋ centrées en tous les
n
mots de code forment une partition de l’espace Fq .
Condition nécessaire
Pt
et suffisante : Un code t-correcteur de paramètres (n, k, d)
n j n
est parfait si : |C| · j=0 j (q − 1) = q
Pour un code binaire linéaire : 2k · tj=0 nj = 2n
P

Interprétation : Dans un code parfait, chaque mot reçu appartient à exactement une
boule. Il n’y a pas de ”gaspillage” d’espace.
Propriété : Dans un code parfait, un mot transmis avec plus de t erreurs sera toujours
décodé de façon erronée (il appartiendra à une autre boule).

8.6 Exemples de Codes Parfaits

8.6.1 Code à répétition
Description : Pour transmettre 1 bit, on le répète n = 2t + 1 fois (longueur impaire).
Mots de code :
— 0...0 (n zéros)
— 1...1 (n uns)
Paramètres :
— Longueur : n = 2t + 1
— Dimension : k = 1
— Distance minimale : d = n = 2t + 1
Capacité de correction : t = n−1 2
erreurs
Décodage : Vote majoritaire (choisir le bit le plus fréquent)
Perfection : Ce code est parfait car tout mot de {0, 1}n contient soit plus de t + 1
zéros, soit plus de t + 1 uns, donc est à distance au plus t d’un des deux mots de code.
Exemple avec n = 5 :
— Mots de code : 00000 et 11111
— Distance minimale : d = 5
— Correction : t = 2 erreurs
— Si on reçoit 10010 : 3 zéros, 2 uns → décode en 00000

8.6.2 Code de Hamming Hm

Paramètres :
— Longueur : n = 2m − 1
— Dimension : k = 2m − m − 1
— Distance minimale : d = 3
— Capacité de correction : t = 1 erreur
Construction : La matrice de parité H est constituée de tous les vecteurs colonnes
non nuls de Fm
2 .
Exemple - Code de Hamming H3 :
Paramètres : (n = 7, k = 4, d = 3)

14
Cours Complet Simplifié Théorie de l’Information

 
0 0 0 1 1 1 1
Matrice de parité : H = 0 1 1 0 0 1 1
1 0 1 0 1 0 1
Perfection : Le code de Hamming est parfait car :
— Cardinal d’une boule de rayon 1 : 1 + n = 1 + (2m − 1) = 2m
m
— Nombre de boules : 2k = 22 −m−1
m m
— Total : 2k · 2m = 22 −m−1+m = 22 −1 = 2n
Cela signifie que les boules recouvrent exactement tout l’espace.
Décodage : Le syndrome s = Hy T indique la position de l’erreur (si une seule erreur).

8.7 Exemples de Codes Linéaires

8.7.1 Exemple 1 - Code trivial
Paramètres : n = 4, k = 2, q = 2
Base : g1 = (1, 0, 0, 0), g2 = (0,
 1, 0, 0) 
1 0 0 0
Matrice génératrice : G =
0 1 0 0
Mots de code :
— (0, 0) → (0, 0, 0, 0)
— (1, 0) → (1, 0, 0, 0)
— (0, 1) → (0, 1, 0, 0)
— (1, 1) → (1, 1, 0, 0)
Distance minimale : d = 1
Conclusion : Ce code ne peut ni détecter ni corriger d’erreurs (pas de redondance).

8.7.2 Exemple 2 - Code avec redondance

Paramètres : n = 4, k = 2, q = 2
Base : g1 = (1, 1, 1, 0), g2 = (0,
 1, 1, 1) 
1 1 1 0
Matrice génératrice : G =
0 1 1 1
Mots de code :
— (0, 0) → (0, 0, 0, 0)
— (1, 0) → (1, 1, 1, 0)
— (0, 1) → (0, 1, 1, 1)
— (1, 1) → (1, 0, 0, 1)
Distance minimale : d = 2
Capacité : Peut détecter 1 erreur, mais ne peut pas corriger d’erreurs (t = 0).

9 Résumé et Conclusions
9.1 Concepts clés du codage de source
1. Entropie
P : Limite théorique de compression, mesure l’information moyenne H(X) =
− x p(x) log2 p(x)

15
Cours Complet Simplifié Théorie de l’Information

2. Premier Théorème de Shannon : On peut coder avec une longueur moyenne

aussi proche de H qu’on veut, mais pas moins
3. Huffman : Algorithme optimal pour les codes préfixes, mais limité aux nombres
entiers de bits
4. Codage arithmétique : Atteint exactement l’entropie, permet des longueurs non
entières
5. Lempel-Ziv : Codage universel adaptatif, ne nécessite pas de connaı̂tre les proba-
bilités

9.2 Concepts clés des canaux et codes correcteurs

1. Capacité d’un canal : Quantité maximale d’information transmissible sans erreur
C = maxpX I(X; Y )
2. Canal binaire symétrique : Modèle fondamental avec probabilité d’erreur ε C =
1 − H(ε)
3. Distance de Hamming : Mesure la différence entre mots
4. Capacité de correction : Un code de distance d corrige t = ⌊ d−1
2
⌋ erreurs
5. Codes parfaits : Utilisent optimalement l’espace (codes à répétition, Hamming)

9.3 Formules essentielles

Information et entropie :

I(x) = − log2 p(x)

X
H(X) = − p(x) log2 p(x)
x
I(X; Y ) = H(X) − H(X|Y )

Codage :
X
2−nk ≤ 1 (Kraft)
k
H(X) ≤ |ϕ| < H(X) + 1 (Shannon)

Canaux :

C = max I(X; Y )
pX

CCBS = 1 − H(ε)

Codes correcteurs :
 
d−1
tcorrection =
2
t
X n
|B(c, t)| = (q − 1)j
j=0
j

16
Cours Complet Simplifié Théorie de l’Information

9.4 Principes fondamentaux

Dualité compression-transmission :
— Le codage de source vise à réduire la redondance (compression)
— Le codage de canal vise à ajouter de la redondance (correction d’erreurs)
— Ces deux opérations sont complémentaires dans un système de communication
Limites théoriques :
— On ne peut pas compresser en-dessous de l’entropie
— On ne peut pas transmettre au-delà de la capacité du canal
— Ces limites sont atteignables asymptotiquement (Théorèmes de Shannon)
Compromis pratiques :
— Huffman : simple mais sous-optimal pour petites entropies
— Arithmétique : optimal mais plus complexe
— Codes parfaits : efficaces mais rares (uniquement certains paramètres)
— Codes linéaires généraux : flexibles, permettent d’ajuster le compromis efficacité/redondance

9.5 Message final

La théorie de l’information fournit un cadre mathématique rigoureux pour comprendre
et optimiser la transmission et le stockage de l’information. Les deux théorèmes de Shan-
non établissent les limites fondamentales :
— Pour le codage de source : l’entropie est la limite de compression
— Pour le codage de canal : la capacité est la limite de transmission fiable
Les algorithmes pratiques (Huffman, arithmétique, Lempel-Ziv pour la compression ;
Hamming, Reed-Solomon pour la correction d’erreurs) s’appuient sur ces résultats théoriques
pour s’approcher de ces limites optimales dans des applications concrètes.

17