Théorie de l’information

Exercice 1 - Encodage temporel et polynomial

Paramètres du code et définitions

D'après le document source, nous étudions un code de convolution défini par les caractéristiques suivantes :

• Rapport de code (rendement) r = 1/2 (n = 2 sorties entrelacées).
• Longueur de contrainte K = 3 (le nombre de bascules est de K - 1 = 2).
• Polynômes générateurs sous forme binaire : g1 = [0 0 1] et g2 = [1 1 1].
• Message à encoder : m = [1 0 0 1 1] (longueur L = 5).

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].

Encodage par la méthode temporelle (convolution)

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.

Encodage par la méthode polynomiale

Chaque séquence binaire peut être représentée par un polynôme où le coefficient correspond à la valeur du bit.

• g1(x) = 0·1 + 0·x + 1·x² = x²
• g2(x) = 1·1 + 1·x + 1·x² = 1 + x + x²
• m(x) = 1·1 + 0·x + 0·x² + 1·x³ + 1·x⁴ = 1 + x³ + x⁴

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].

Exercice 2 - Décodage par l'algorithme de Viterbi (Maximum de Vraisemblance)

Fondements et probabilités

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.

Analyse de l'erreur et correction

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 :

1. Phase initiale : L'algorithme part du nœud correspondant à l'état des registres à 00. Les deux premiers blocs (01 01) permettent d'avancer dans le treillis en calculant les distances de Hamming partielles.
2. Phase centrale : À chaque nouvelle portion de code, l'algorithme calcule la distance avec les sorties théoriques des branches. Lorsqu'il y a deux façons d'atteindre un nœud, l'algorithme ne conserve que le "survivant", c'est-à-dire le trajet ayant accumulé la distance de Hamming la plus faible. L'erreur du troisième bloc (01 au lieu de 11) va temporairement augmenter la distance de Hamming du bon chemin de 1, mais les chemins concurrents accumuleront des distances plus importantes sur les blocs suivants.
3. Phase finale (bits de queue) : Sur les M=2 derniers instants, le décodeur sait que les entrées sont obligatoirement des "0" (représentés par un trait continu dans les conventions graphiques du document). Cela force le chemin à retourner vers l'état initial 00, réduisant le nombre de chemins survivants à un seul.

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.

Méthode

Face à une épreuve portant sur les codes de convolution, la rigueur dans le suivi des états est essentielle :

1. Identification des paramètres : Notez immédiatement la longueur de contrainte K, le nombre de générateurs (qui détermine le rapport r), et déduisez le nombre d'états du treillis (2^(K-1)) ainsi que le nombre de bits de queue nécessaires (M = K-1).
2. Calcul méticuleux : Que vous utilisiez l'approche temporelle ou polynomiale, toutes les additions se font systématiquement modulo 2. Une erreur sur un seul bit se propage sur les K instants suivants, faussant la suite du treillis. Vérifiez vos résultats en croisant les deux méthodes (temporelle et polynomiale) si le temps le permet.
3. Viterbi : Ne tentez pas de deviner le chemin complet d'un seul coup. Avancez bloc par bloc, inscrivez la distance de Hamming cumulée à chaque nœud, et barrez clairement les chemins éliminés (les non-survivants) à chaque étape pour ne pas surcharger votre brouillon. L'ajout des zéros de queue à la fin est une étape souvent oubliée par les étudiants mais indispensable pour forcer la convergence du décodeur.