Théorie de l’information
Théorie de l’information
Codage canal et codes de bloc linéaires · 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 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.
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 :
Le système de communication comprend plusieurs étapes :
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 :
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 :
Le théorème de Shannon affirme :
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.
Pour deux mots binaires x et y de longueur n :
Exemple : x = 10110, y = 00101
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.
Le nombre maximal d’erreurs détectables eD et corrigibles eC dépend de la distance minimale dmin :
Exemples :
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.
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.
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.
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].
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.
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.