Théorie de l’information
Théorie de l’information
Codes de Convolution, Programmation, Mathématiques · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
D'après le document source, nous étudions un code de convolution défini par les caractéristiques suivantes :
Pour clôturer le treillis et vider les registres, nous devons ajouter M = K - 1 = 2 bits de queue (des zéros) à la fin du message. La séquence d'entrée devient donc m = [1 0 0 1 1 0 0].
L'équation de convolution donnée dans le cours est : C(j) = Σ(i=0 à K-1) g(i) · m(j - i). Toutes les additions sont effectuées modulo 2 (OU exclusif).
Calculons les sorties C1(j) et C2(j) pour chaque instant j (de j=0 à j=6) :
Pour C1, avec g1 = [0 0 1] : C1(j) = 0·m(j) + 0·m(j-1) + 1·m(j-2) = m(j-2)
Pour C2, avec g2 = [1 1 1] : C2(j) = 1·m(j) + 1·m(j-1) + 1·m(j-2) = m(j) + m(j-1) + m(j-2)
Rappel : toute valeur m avec un indice négatif est égale à 0.
j = 0 : (entrée m(0) = 1) C1(0) = m(-2) = 0 C2(0) = m(0) + m(-1) + m(-2) = 1 + 0 + 0 = 1 Mot généré = 01
j = 1 : (entrée m(1) = 0) C1(1) = m(-1) = 0 C2(1) = m(1) + m(0) + m(-1) = 0 + 1 + 0 = 1 Mot généré = 01
j = 2 : (entrée m(2) = 0) C1(2) = m(0) = 1 C2(2) = m(2) + m(1) + m(0) = 0 + 0 + 1 = 1 Mot généré = 11
j = 3 : (entrée m(3) = 1) C1(3) = m(1) = 0 C2(3) = m(3) + m(2) + m(1) = 1 + 0 + 0 = 1 Mot généré = 01
j = 4 : (entrée m(4) = 1) C1(4) = m(2) = 0 C2(4) = m(4) + m(3) + m(2) = 1 + 1 + 0 = 2 ≡ 0 (modulo 2) Mot généré = 00
j = 5 : (entrée m(5) = 0, premier bit de queue) C1(5) = m(3) = 1 C2(5) = m(5) + m(4) + m(3) = 0 + 1 + 1 = 2 ≡ 0 (modulo 2) Mot généré = 10
j = 6 : (entrée m(6) = 0, deuxième bit de queue) C1(6) = m(4) = 1 C2(6) = m(6) + m(5) + m(4) = 0 + 0 + 1 = 1 Mot généré = 11
En entrelaçant les sorties, nous obtenons le mot de code final : C = [01 01 11 01 00 10 11], ce qui correspond exactement au résultat énoncé dans le document.
Chaque séquence binaire peut être représentée par un polynôme où le coefficient correspond à la valeur du bit.
Calculons C1(x) = m(x) · g1(x) : C1(x) = (1 + x³ + x⁴) · x² = x² + x⁵ + x⁶ En binaire (de la puissance 0 à 6) : C1 = [0 0 1 0 0 1 1]
Calculons C2(x) = m(x) · g2(x) : C2(x) = (1 + x³ + x⁴) · (1 + x + x²) C2(x) = 1(1 + x + x²) + x³(1 + x + x²) + x⁴(1 + x + x²) C2(x) = 1 + x + x² + x³ + x⁴ + x⁵ + x⁴ + x⁵ + x⁶
En appliquant l'arithmétique modulo 2, (x⁴ + x⁴) = 0 et (x⁵ + x⁵) = 0, le polynôme se simplifie : C2(x) = 1 + x + x² + x³ + x⁶ En binaire (de la puissance 0 à 6) : C2 = [1 1 1 1 0 0 1]
En entrelaçant C1 et C2 (C1 en premier bit, C2 en second bit pour chaque position), on retrouve bien : C = [01 01 11 01 00 10 11].
Le décodage par maximum de vraisemblance cherche à minimiser la probabilité d'erreur. Puisque la fonction logarithme est monotone, maximiser la probabilité d'avoir reçu R sachant C (prob(R/C)) revient à maximiser : log[prob(R/C)] = d·log(p/(1-p)) + N·log(1-p)
Dans un canal binaire symétrique où la probabilité d'erreur p < 1/2, le terme log(p/(1-p)) est négatif. Ainsi, pour maximiser l'équation, il faut minimiser "d", qui représente la distance de Hamming (le nombre de bits différents) entre le mot reçu R et le mot de code évalué C. L'algorithme de Viterbi utilise le treillis du code pour trouver efficacement le chemin (le mot de code) qui présente la plus petite distance de Hamming avec le message reçu.
Le mot de code reçu dans l'énoncé est Y = [01 01 01 01 00 10 11].
Si nous le comparons avec le mot de code correctement généré à l'Exercice 1 : Emis : [01 01 11 01 00 10 11] Reçu Y : [01 01 01 01 00 10 11]
On observe une erreur de transmission dans le troisième bloc (01 reçu au lieu de 11).
Le décodage de Viterbi procède par étapes dans le treillis :
Le trajet survivant à la fin du treillis correspond à la séquence d'états engendrée par les bits [1 0 0 1 1]. L'algorithme de Viterbi parvient ainsi à corriger l'erreur de transmission et à reconstituer le message d'origine.
Face à une épreuve portant sur les codes de convolution, la rigueur dans le suivi des états est essentielle :