Théorie de l’information

Ce matériel couvre les concepts fondamentaux du codage canal et des codes de bloc linéaires dans la théorie de l’information. Il s’adresse aux étudiants en télécommunications, informatique ou électronique souhaitant comprendre comment transmettre des données numériques de manière fiable malgré la présence de bruit et d’erreurs sur le canal de communication.

Problématique de la transmission numérique

La transmission numérique consiste à envoyer une séquence de bits d’une source vers un récepteur via un canal de transmission. Ce canal peut être un support physique (câble coaxial, fibre optique) ou un milieu sans fil (ondes électromagnétiques). Deux objectifs contradictoires se posent :

• Transmettre le maximum d’informations le plus rapidement possible, ce qui implique peu de bits redondants et une modulation efficace.
• Transmettre sans erreur, ce qui nécessite d’ajouter des bits redondants pour détecter et corriger les erreurs.

Le système de communication comprend plusieurs étapes :

• Source : produit un message binaire.
• Encodeur de source : compresse les données pour minimiser le nombre de bits.
• Encodeur de canal : ajoute des bits redondants pour lutter contre les erreurs.
• Modulateur : transforme les bits en signaux physiques adaptés au canal.
• Canal : support de transmission pouvant introduire des erreurs.
• Démodulateur : convertit les signaux reçus en bits.
• Décodeur de canal : détecte et corrige les erreurs éventuelles.
• Décodeur de source : reconstitue l’information originale.

Modèle : Canal Binaire Symétrique (CBS)

Le canal binaire symétrique est un modèle simple où chaque bit transmis peut être inversé (0 devient 1 ou 1 devient 0) avec une probabilité d’erreur p. Cette probabilité p caractérise le bruit du canal.

L’information mutuelle I(X, Y) entre la source X et la sortie Y du canal mesure la quantité d’information correcte transmise. Elle est définie par :

I(X, Y) = H(X) − H(X / Y)

où H(X) est l’entropie de la source et H(X / Y) l’entropie conditionnelle liée au bruit du canal.

Pour un canal binaire symétrique, l’information mutuelle s’exprime par :

I(X, Y) = 1 + (1 − p) · log2(1 − p) + p · log2(p)

Quelques cas particuliers :

• Si p = 0 (pas d’erreur), I(X, Y) = 1, transmission parfaite.
• Si p = 0,5 (erreur aléatoire totale), I(X, Y) = 0, aucune information transmise.
• Si p = 1 (inversion systématique), I(X, Y) = 1, car la source est parfaitement prévisible par inversion.

Capacité du canal et rôle du codage

La capacité C du canal est la quantité maximale d’information transmise sans erreur, obtenue en maximisant l’information mutuelle sur la distribution des symboles d’entrée :

C = max{p(xi)} { I(X, Y) } = max{H(X) − H(X / Y)}

Si la cadence du canal est d’un symbole toutes les Tc secondes, le débit maximal est C / Tc bits par seconde.

Le codage canal ajoute de la redondance pour réduire l’incertitude H(X / Y) liée aux erreurs. Par exemple :

• Ajouter un bit de parité et demander une retransmission en cas d’erreur détectée.
• Transmettre chaque bit plusieurs fois et utiliser la majorité pour corriger.

Le théorème de Shannon affirme :

1. Si l’entropie de la source H(X) est inférieure ou égale à la capacité C du canal, il existe un codage permettant de transmettre l’information avec une probabilité d’erreur arbitrairement faible.
2. Si H(X) > C, la perte d’information est inévitable, et un mauvais codage peut aggraver cette perte.

La transmission fiable s’obtient en codant un bloc de k bits en un mot de code de n bits (n > k), ce qui réduit le taux de codage R = k / n.

Métriques : Distance et poids de Hamming

Pour deux mots binaires x et y de longueur n :

• Distance de Hamming d(x, y) : nombre de positions où x et y diffèrent.
• Poids de Hamming w(x) : nombre de bits égaux à 1 dans x.

Exemple : x = 10110, y = 00101

• d(x, y) = 3
• w(x) = 3
• w(y) = 2

La distance minimale d’un code dmin est la plus petite distance de Hamming entre deux mots de code distincts. Elle détermine la capacité du code à détecter et corriger les erreurs.

Pouvoir de détection et pouvoir de correction

Le nombre maximal d’erreurs détectables eD et corrigibles eC dépend de la distance minimale dmin :

• eD = dmin − 1 (nombre maximal d’erreurs détectables)
• eC = floor[(dmin − 1) / 2] (nombre maximal d’erreurs corrigibles)

Exemples :

• Un code avec dmin = 1 ne peut détecter ni corriger d’erreurs.
• Un code avec dmin = 2 peut détecter une erreur mais pas la corriger.
• Un code avec dmin = 3 peut détecter deux erreurs et corriger une erreur.

Codes de bloc linéaires

Un code de bloc linéaire (n, k) encode un message de k bits en un mot de code de n bits. Le mot de code C est obtenu par :

C = m × G

où m est le vecteur message (k bits) et G la matrice génératrice (k × n).

Un code est dit systématique si G = [P | I_k], où I_k est la matrice identité k × k et P la matrice de parité (k × (n − k)). Dans ce cas, le mot de code contient les bits de parité suivis des bits de message.

Exemple de code (7,4)

Soit la matrice génératrice G :

1 0 1 1 0 0 0
1 1 1 0 1 0 0
1 1 0 0 0 1 0
0 1 1 0 0 0 1

Ce code encode un message de 4 bits en un mot de code de 7 bits. Les 3 premiers bits sont les bits redondants (b0, b1, b2) calculés à partir des bits de message m0, m1, m2, m3 selon les formules extraites de G.

Détection des erreurs par syndrome

La matrice de contrôle H est construite comme :

H = [I_(n−k) | P^T]

où I_(n−k) est la matrice identité (n−k) × (n−k) et P^T la transposée de la matrice de parité.

Pour un mot reçu Y, le syndrome S est calculé par :

S = Y × H^T

Si S = 0, aucun erreur détectée. Sinon, S dépend uniquement de l’erreur E commise :

S = E × H^T

Le syndrome permet d’identifier l’erreur la plus probable et de la corriger.

Exemple de correction par syndrome

Considérons un code (5,2) avec :

G = [1 0 1 1 0
     0 1 1 0 1]

H = [1 0 0 1 0
     0 1 0 0 1
     0 0 1 1 1]

Si le message m = [1 0], le mot de code est :

C = m × G = [1 0 1 1 0]

Supposons une erreur sur le bit 3 à la réception :

Y = [1 0 1 0 0]

Le syndrome est :

S = Y × H^T = [1 0 1]

La table d’erreur/syndrome associe ce syndrome à l’erreur E* = [0 0 0 1 0]. La correction s’effectue par :

C* = Y + E* = [1 0 1 1 0]

Le message corrigé est extrait des k derniers bits de C* : m* = [1 0].

Code de Hamming

Les codes de Hamming sont des codes binaires caractérisés par :

(n, k, dmin) = (2^m − 1, 2^m − 1 − m, 3)

Exemples : code (7,4,3), code (15,11,3).

La matrice de contrôle H est de taille (m × (2^m − 1)) et contient toutes les combinaisons possibles de m bits, sauf la combinaison nulle.

Ces codes permettent de détecter jusqu’à deux erreurs et de corriger une erreur unique.

Code de Hadamard

Les codes de Hadamard sont construits à partir de matrices par itération :

M_2n = [M_n  M_n
         M_n  complémentaire de M_n]

Par exemple :

M_2 = [0 0
       0 1]

M_4 = 
[0 0 0 0
 0 1 0 1
 0 0 1 1
 0 1 1 0]

Les lignes ou colonnes de ces matrices contiennent les mots de code. La distance minimale d’un code de Hadamard est :

dmin = n / 2

Cette structure permet une bonne détection des erreurs.

Glossaire des termes clés

• Canal binaire symétrique (CBS) : canal où chaque bit peut être inversé avec une probabilité p.
• Information mutuelle I(X, Y) : mesure de la quantité d’information correcte transmise entre X et Y.
• Capacité du canal C : débit maximal d’information transmise sans erreur.
• Distance de Hamming : nombre de bits différents entre deux mots binaires.
• Poids de Hamming : nombre de bits à 1 dans un mot binaire.
• Code de bloc linéaire (n, k) : code qui encode un message de k bits en un mot de n bits avec une structure linéaire.
• Matrice génératrice G : matrice utilisée pour encoder les messages en mots de code.
• Matrice de contrôle H : matrice utilisée pour détecter les erreurs via le syndrome.
• Syndrome : vecteur calculé à la réception qui permet d’identifier les erreurs.
• Distance minimale dmin : plus petite distance de Hamming entre deux mots de code, détermine le pouvoir de détection et correction.
• Code de Hamming : code linéaire avec dmin = 3, capable de corriger une erreur simple.
• Code de Hadamard : code construit par itération de matrices, avec une distance minimale élevée.

Points clés à retenir

• La transmission numérique doit concilier rapidité et fiabilité, ce qui impose un compromis dans le codage.
• Le canal binaire symétrique est un modèle fondamental pour étudier les erreurs de transmission.
• L’information mutuelle et la capacité du canal définissent les limites théoriques de transmission sans erreur.
• Le codage canal ajoute de la redondance pour détecter et corriger les erreurs, améliorant la fiabilité.
• La distance de Hamming est une métrique essentielle pour évaluer la performance des codes.
• Les codes linéaires permettent un codage et décodage efficaces, notamment grâce à la matrice génératrice et la matrice de contrôle.
• Le syndrome est un outil clé pour la détection et correction des erreurs.
• Les codes de Hamming sont des codes classiques capables de corriger une erreur simple.
• Les codes de Hadamard offrent une structure itérative avec une bonne distance minimale.