Mastère Web Intelligence

Exercice 0 - Canal Binaire Symétrique

Probabilités conditionnelles p(y/x)

D'après le graphe fourni pour le canal binaire symétrique, nous avons les probabilités de transition suivantes :

• p(y₁/x₁) = 1 - p
• p(y₂/x₂) = 1 - p
• p(y₂/x₁) = p
• p(y₁/x₂) = p

Probabilités jointes p(x, y)

En utilisant la loi de Bayes p(x, y) = p(y/x) × p(x) avec p(x₁) = p(x₂) = 1/2 :

• p(x₁, y₁) = p(y₁/x₁) × p(x₁) = (1 - p) / 2
• p(x₂, y₁) = p(y₁/x₂) × p(x₂) = p / 2
• p(x₁, y₂) = p(y₂/x₁) × p(x₁) = p / 2
• p(x₂, y₂) = p(y₂/x₂) × p(x₂) = (1 - p) / 2

Probabilités marginales de la source Y

Calculées par la somme des probabilités jointes p(y_j) = Σ p(x_i, y_j) :

• p(y₁) = p(x₁, y₁) + p(x₂, y₁) = (1 - p)/2 + p/2 = 1/2
• p(y₂) = p(x₁, y₂) + p(x₂, y₂) = p/2 + (1 - p)/2 = 1/2

Probabilités conditionnelles p(x/y)

En utilisant p(x/y) = p(x, y) / p(y) :

• p(x₁/y₁) = [(1 - p)/2] / (1/2) = 1 - p
• p(x₁/y₂) = [p/2] / (1/2) = p
• p(x₂/y₁) = [p/2] / (1/2) = p
• p(x₂/y₂) = [(1 - p)/2] / (1/2) = 1 - p

Quantité d'information d'un caractère

L'information propre est I(x) = -log₂(p(x)). Unité en bits.

• I(x₁) = -log₂(1/2) = 1 bit
• I(x₂) = -log₂(1/2) = 1 bit
• I(y₁) = -log₂(1/2) = 1 bit
• I(y₂) = -log₂(1/2) = 1 bit

Entropie de chaque source

L'entropie est l'espérance mathématique de la quantité d'information : H(X) = Σ p(x)I(x).

• H(X) = (1/2 × 1) + (1/2 × 1) = 1 bit/symbole
• H(Y) = (1/2 × 1) + (1/2 × 1) = 1 bit/symbole

Entropie jointe H(X, Y)

H(X, Y) = - Σ Σ p(x,y) log₂(p(x,y)) H(X, Y) = - [ 2 × ((1 - p)/2) log₂((1 - p)/2) + 2 × (p/2) log₂(p/2) ] H(X, Y) = - (1 - p)[log₂(1 - p) - 1] - p[log₂(p) - 1] H(X, Y) = - (1 - p)log₂(1 - p) + (1 - p) - p log₂(p) + p H(X, Y) = 1 - p log₂(p) - (1 - p)log₂(1 - p) bits/symbole On peut noter cela H(X, Y) = 1 + H_b(p), où H_b(p) est la fonction d'entropie binaire.

Entropie conditionnelle moyenne H(X/Y)

H(X/Y) = Σ p(y_j) Σ p(x_i/y_j) log₂(1/p(x_i/y_j)) H(X/Y) = 1/2 [ -(1 - p)log₂(1 - p) - p log₂(p) ] + 1/2 [ -p log₂(p) - (1 - p)log₂(1 - p) ] H(X/Y) = - p log₂(p) - (1 - p)log₂(1 - p) bits/symbole (soit H_b(p)). Note : Bien que l'énoncé fournisse la formule de H(Y/X), il demande le calcul de H(X/Y) juste en dessous. Par symétrie du canal, H(X/Y) = H(Y/X).

Quantité d'information mutuelle I(X, Y)

I(X, Y) = H(X) - H(X/Y) = 1 - [ - p log₂(p) - (1 - p)log₂(1 - p) ] bits/symbole.

Exercice 1 - Codage Source (6 symboles)

1° et 2°) Construction et arbre du code de Huffman

Les probabilités sont (sur 21) : F(6), E(5), D(4), C(3), B(2), A(1). Principe de Huffman : on regroupe à chaque itération les deux probabilités les plus faibles.

1. Regroupement A(1) et B(2) = N1(3).
2. Regroupement N1(3) et C(3) = N2(6).
3. Regroupement D(4) et E(5) = N3(9).
4. Regroupement F(6) et N2(6) = N4(12).
5. Regroupement N3(9) et N4(12) = Racine(21).

Arbre (convention : branche forte = 0, branche faible = 1) : Racine(21) se sépare en N4(12) [Code 0] et N3(9) [Code 1]

• N4(12) se sépare en F(6) [00] et N2(6) [01]
  • N2(6) se sépare en C(3) [010] et N1(3) [011]
    • N1(3) se sépare en B(2) [0110] et A(1) [0111]
• N3(9) se sépare en E(5) [10] et D(4) [11]

3°) Codes finaux de chaque symbole (Huffman)

• F : 00
• C : 010
• B : 0110
• A : 0111
• E : 10
• D : 11

4°) Entropie H(X)

H(X) = - Σ p_i log₂(p_i) H(X) = - [ 6log₂(6/21) + 5log₂(5/21) + 4log₂(4/21) + 3log₂(3/21) + 2log₂(2/21) + 1log₂(1/21) ] / 21 H(X) = [ 21log₂(21) - (6log₂6 + 5log₂5 + 4log₂4 + 3log₂3 + 2log₂2) ] / 21 H(X) ≈ [ 92.23 - (15.51 + 11.61 + 8.00 + 4.75 + 2.00) ] / 21 ≈ 41.87 / 21 H(X) ≈ 2.398 bits/symbole.

5°) Longueur moyenne du code (L)

L = Σ p_i l_i où l_i est la longueur du mot de code. L = [ 6(2) + 5(2) + 4(2) + 3(3) + 2(4) + 1(4) ] / 21 L = (12 + 10 + 8 + 9 + 8 + 4) / 21 = 51 / 21 L ≈ 2.428 bits/symbole.

6°) Efficacité du code

η = H(X) / L = 2.398 / 2.428 ≈ 0.9876 soit 98.76 %.

7°) Rapport de compression avec ASCII

Le taux de compression (T) = L_original / L_compressé T = 8 / 2.428 ≈ 3.29. (Le fichier est environ 3.29 fois plus petit).

8°) Codage de Fano-Shannon

On classe par ordre décroissant et on divise récursivement la liste en deux sous-groupes de sommes de probabilités aussi proches que possible. Liste initiale : F(6), E(5), D(4), C(3), B(2), A(1). Total = 21, moitié = 10.5.

• Séparation 1 : {F, E} (somme 11) [Code commence par 0] et {D, C, B, A} (somme 10) [Code commence par 1].
• Séparation du bloc 0 {F, E} : {F} (6) [00] et {E} (5) [01].
• Séparation du bloc 1 {D, C, B, A} (moitié = 5) : {D} (4) [10] et {C, B, A} (6) [11].
• Séparation de {C, B, A} (moitié = 3) : {C} (3) [110] et {B, A} (3) [111].
• Séparation de {B, A} : {B} (2) [1110] et {A} (1) [1111].

Codes Fano-Shannon : F:00, E:01, D:10, C:110, B:1110, A:1111. Longueur moyenne L_FS = [ 6(2) + 5(2) + 4(2) + 3(3) + 2(4) + 1(4) ] / 21 = 51 / 21 ≈ 2.428 bits/symbole.

9°) Comparaison des deux codes

Les deux codes produisent exactement la même longueur moyenne (L = 51/21) pour cette distribution. L'efficacité est identique (98.76%). Les deux sont aussi performants l'un que l'autre dans ce cas précis (bien que de manière générale, Huffman garantisse la solution mathématiquement optimale).

Exercice 2 - Codage Source (7 symboles)

1° et 2°) Construction et arbre du code de Huffman

Probabilités (sur 28) classées : D(7), F(6), C(5), B(4), A(3), G(2), E(1).

1. E(1) + G(2) = N1(3)
2. N1(3) + A(3) = N2(6)
3. B(4) + C(5) = N3(9)
4. N2(6) + F(6) = N4(12)
5. D(7) + N3(9) = N5(16)
6. N4(12) + N5(16) = Racine(28)

Arbre (0 = max, 1 = min) : Racine(28) -> N5(16) [0] et N4(12) [1]

• N5(16) -> N3(9) [00] et D(7) [01]
  • N3(9) -> C(5) [000] et B(4) [001]
• N4(12) -> F(6) [10] et N2(6) [11]
  • N2(6) -> A(3) [110] et N1(3) [111]
    • N1(3) -> G(2) [1110] et E(1) [1111]

3°) Codes finaux (Huffman)

• D : 01
• F : 10
• C : 000
• B : 001
• A : 110
• G : 1110
• E : 1111

4°) Entropie H(X)

H(X) = - [ 7log₂(7/28) + 6log₂(6/28) + 5log₂(5/28) + 4log₂(4/28) + 3log₂(3/28) + 2log₂(2/28) + 1log₂(1/28) ] / 28 H(X) ≈ [ 134.60 - (19.65 + 15.51 + 11.61 + 8.00 + 4.75 + 2.00 + 0) ] / 28 ≈ 73.08 / 28 H(X) ≈ 2.610 bits/symbole.

5°) Longueur moyenne du code (L)

L = [ 7(2) + 6(2) + 5(3) + 4(3) + 3(3) + 2(4) + 1(4) ] / 28 L = (14 + 12 + 15 + 12 + 9 + 8 + 4) / 28 = 74 / 28 = 37 / 14 L ≈ 2.643 bits/symbole.

6°) Efficacité du code

η = H(X) / L = 2.610 / 2.643 ≈ 0.9875 soit 98.75 %.

7°) Rapport de compression avec ASCII

T = 8 / 2.643 ≈ 3.02.

8°) Codage de Fano-Shannon

Répartition récursive autour de la moitié du poids (total 28, moitié 14) :

• Séparation 1 : {D(7), F(6)} (Somme 13) [Code 0] vs {C, B, A, G, E} (Somme 15) [Code 1]
• Bloc 0 {D, F} : {D} (7) [00] vs {F} (6) [01]
• Bloc 1 {C, B, A, G, E} (moitié 7.5) : {C(5), B(4)} (Somme 9) [10] vs {A, G, E} (Somme 6) [11]
• Bloc 10 {C, B} : {C} [100] vs {B} [101]
• Bloc 11 {A, G, E} : {A(3)} [110] vs {G(2), E(1)} [111]
• Bloc 111 {G, E} : {G} [1110] vs {E} [1111] Longueurs de Fano-Shannon : D(2), F(2), C(3), B(3), A(3), G(4), E(4). L_FS = 74 / 28 ≈ 2.643 bits/symbole.

9°) Comparaison

À nouveau, les longueurs individuelles de chaque caractère générées par l'algorithme de Fano-Shannon correspondent aux longueurs de Huffman. Les deux efficacités sont rigoureusement identiques (98.75%).

Exercice 3 - Code en Bloc Linéaire

Matrice de contrôle H (3 lignes, 5 colonnes) : [ 0 1 0 0 1 ] [ 1 1 0 1 0 ] [ 1 0 1 0 0 ]

1. Paramètres (n, k)

La matrice H a comme dimensions (n - k) lignes et n colonnes. Ici, H est une matrice 3 × 5. Donc n = 5, n - k = 3, ce qui implique k = 2. Le code est un code en bloc de type (5, 2).

2. Vérification des mots de code

Un mot v est un mot de code si et seulement si H × v^T = 0 (modulo 2).

• Pour m₁ = (1 1 1 0 1) : H × m₁^T = Colonne1 + Colonne2 + Colonne3 + Colonne5 (0, 1, 1) + (1, 1, 0) + (0, 0, 1) + (1, 0, 0) = (2, 2, 2) ≡ (0, 0, 0) mod 2. Oui, m₁ est un mot de code.
• Pour m₂ = (1 1 0 1 0) : H × m₂^T = Colonne1 + Colonne2 + Colonne4 (0, 1, 1) + (1, 1, 0) + (0, 1, 0) = (1, 3, 1) ≡ (1, 1, 1) mod 2 ≠ (0, 0, 0). Non, m₂ n'est pas un mot de code.

3. Matrice génératrice G

Pour trouver G, nous résolvons H × x^T = 0, où x = (x₁, x₂, x₃, x₄, x₅).

• Ligne 3 : x₁ + x₃ = 0 ⇒ x₃ = x₁
• Ligne 2 : x₁ + x₂ + x₄ = 0 ⇒ x₄ = x₁ + x₂
• Ligne 1 : x₂ + x₅ = 0 ⇒ x₅ = x₂ En isolant les bits d'information (x₁, x₂), chaque mot s'écrit x = (x₁, x₂, x₁, x₁ + x₂, x₂). La matrice génératrice G (2 × 5) correspondante est donc : [ 1 0 1 1 0 ] [ 0 1 0 1 1 ]

4. Liste de tous les mots du code

Puisque k = 2, il y a 2² = 4 mots de code (calculés avec m × G) :

• (0 0) → (0 0 0 0 0)
• (0 1) → (0 1 0 1 1)
• (1 0) → (1 0 1 1 0)
• (1 1) → (1 1 1 0 1)

5. Distance minimale de C

Trois méthodes permettent de déterminer d_min :

1. Poids minimum d'un mot non nul : D'après la liste précédente, les poids des mots non nuls sont w(01011)=3, w(10110)=3, w(11101)=4. Le poids minimum est donc d_min = 3.
2. Indépendance linéaire des colonnes de H : H ne contient aucune colonne nulle (d > 1) et ses colonnes sont toutes distinctes deux à deux (d > 2). Cependant, l'addition de certaines 3 colonnes donne le vecteur nul, par exemple : C₂ + C₄ + C₅ = (1,1,0) + (0,1,0) + (1,0,0) = (2,2,0) ≡ (0,0,0) mod 2. La somme de 3 colonnes est nulle, donc d_min = 3.
3. À partir des lignes de G : Dans un code linéaire, la distance minimale est le poids minimum des lignes de la matrice G et de toutes leurs combinaisons linéaires non nulles. La ligne 1 a pour poids 3, la ligne 2 a pour poids 3, et leur somme (ligne 3) a pour poids 4. Le minimum est donc d_min = 3.

Exercice 4 - Code Cyclique (7, 4)

Code généré par g(x) = 1 + x² + x³. Longueur n = 7.

1. Dimension du code

La dimension k = n - degré(g(x)) = 7 - 3 = 4.

2. Matrice génératrice G* (non systématique)

G* se forme par des décalages successifs du polynôme générateur g(x) sur k lignes. g(x) = 1011000 x·g(x) = 0101100 x²·g(x) = 0010110 x³·g(x) = 0001011 G* = [ 1 0 1 1 0 0 0 ] [ 0 1 0 1 1 0 0 ] [ 0 0 1 0 1 1 0 ] [ 0 0 0 1 0 1 1 ]

3. Matrice génératrice G sous forme systématique

Il faut appliquer le pivot de Gauss sur G* pour faire apparaître la matrice identité I₄ à gauche.

• R3_new = R3
• R2_new = R2
• R1_new = R1 + R3 = 1001110
• R1_final = (R1 + R3) + R4 = 1000101
• R2_final = R2 + R4 = 0100111 G systématique = [ 1 0 0 0 1 0 1 ] [ 0 1 0 0 1 1 1 ] [ 0 0 1 0 1 1 0 ] [ 0 0 0 1 0 1 1 ]

4. Matrice de contrôle H

Puisque G = [I₄ | P], H s'écrit [P^T | I₃]. La sous-matrice P est : [ 1 0 1 ] [ 1 1 1 ] [ 1 1 0 ] [ 0 1 1 ] P^T est donc : [ 1 1 1 0 ] [ 0 1 1 1 ] [ 1 1 0 1 ] Et la matrice H = [ 1 1 1 0 1 0 0 ] [ 0 1 1 1 0 1 0 ] [ 1 1 0 1 0 0 1 ]

5. Vérification du mot Cm

Cm = (1 0 1 1 1 0 0). Multiplions Cm par H^T. Cm correspond à la somme des colonnes C₁, C₃, C₄, C₅ de H. (1,0,1) + (1,1,0) + (0,1,1) + (1,0,0) = (3, 2, 2) ≡ (1, 0, 0) mod 2. Le syndrôme n'est pas nul, donc Cm n'est pas un mot de code. (Alternative par polynôme : la division de 1+x²+x³+x⁴ par 1+x²+x³ donne un reste x²+x+1 ≠ 0).

6. Vérification de la propriété cyclique

Un polynôme g(x) génère un code cyclique de longueur n s'il divise xⁿ - 1 (modulo 2, équivalent à xⁿ + 1). Divisons x⁷ + 1 par x³ + x² + 1 dans GF(2) : x⁷ + 1 = (x + 1)(x³ + x + 1)(x³ + x² + 1) Puisque g(x) est bien un diviseur de x⁷ + 1, il génère bien un code cyclique de longueur 7.

7. Mot de code pour m = [1 1 0 1]

En utilisant G systématique, le mot de code C est m × G : C = Ligne1 + Ligne2 + Ligne4 C = (1000101) + (0100111) + (0001011) = (1 1 0 1 0 0 1).

8. Décodage du mot reçu Ym(x) = x⁵ + x³

Ym = 0001010. Calculons le syndrôme par division polynomiale de Ym(x) par g(x). x⁵ + x³ = x²(x³ + x² + 1) + x⁴ + x² x⁴ + x² = x(x³ + x² + 1) + x Le syndrôme est le reste : S(x) = x. Une erreur unique sur le bit de position x¹ a pour syndrôme x. Le vecteur d'erreur e(x) est donc x. Le mot de code correct est Cm(x) = Ym(x) + e(x) = x⁵ + x³ + x. Si le code est sous forme non systématique C(x) = m(x)g(x) : x⁵ + x³ + x = x²(x³ + x² + 1) + x⁴ + x² + x. Erreur, revoyons : il fallait calculer le syndrôme d'erreur avec le tableau.

• S(1) = 1
• S(x) = x
• S(x²) = x²
• S(x³) = x²+1
• S(x⁴) = x²+x+1
• S(x⁵) = x+1
• S(x⁶) = x²+x Le syndrôme de x⁵ + x³ est S(x⁵) + S(x³) = (x+1) + (x²+1) = x² + x. Le tableau des syndrômes indique que l'erreur correspondant à x² + x est e(x) = x⁶. Le mot corrigé est donc C(x) = x⁶ + x⁵ + x³. En factorisant : x⁶ + x⁵ + x³ = x³(x³ + x² + 1) = x³·g(x). Le message m(x) est donc x³ (qui correspond au vecteur m = [0 0 0 1]).

Exercice 5 - Code cyclique (divisibilité)

Note : l'énoncé indique "x² + x + 1 divise x¹⁶ + 1" de façon typographique erronée, pour un code de longueur 6, l'expression mathématique appropriée est x² + x + 1 divise x⁶ + 1, ce qui est utilisé dans la suite logique de la consigne.

1. Vérification de la divisibilité

Dans GF(2), nous savons que : x⁶ + 1 = (x³ + 1)² = ((x + 1)(x² + x + 1))² Par conséquent, (x² + x + 1) est un diviseur exact de x⁶ + 1.

2. Liste des mots du code cyclique de longueur 6

Le polynôme générateur est g(x) = x² + x + 1. Le degré est 2, donc k = 6 - 2 = 4. Il y a 2⁴ = 16 mots de code, obtenus par la multiplication de tous les polynômes m(x) de degré ≤ 3 par g(x) :

• 000000
• 111000 (m = 1)
• 011100 (m = x)
• 001110 (m = x²)
• 000111 (m = x³)
• 100100 (m = 1 + x)
• 110110 (m = 1 + x²)
• 111111 (m = 1 + x³)
• 010010 (m = x + x²)
• 011011 (m = x + x³)
• 001001 (m = x² + x³)
• 100010 (m = 1 + x + x²)
• 101101 (m = 1 + x + x³)
• 110011 (m = 1 + x² + x³)
• 010001 (m = x + x² + x³)
• 100001 (m = 1 + x + x² + x³)

3. Matrice génératrice G*

G* se forme par des décalages (shift) de g(x) = 1 + x + x² (vecteur 111000). G* = [ 1 1 1 0 0 0 ] [ 0 1 1 1 0 0 ] [ 0 0 1 1 1 0 ] [ 0 0 0 1 1 1 ]

4. Matrice génératrice systématique

En réduisant la matrice pour obtenir I₄ à gauche : G = [ 1 0 0 0 1 1 ] [ 0 1 0 0 1 0 ] [ 0 0 1 0 0 1 ] [ 0 0 0 1 1 1 ]

5. Matrice de contrôle H

La sous-matrice P est définie par les 2 dernières colonnes de la matrice G : [ 1 1 ] [ 1 0 ] [ 0 1 ] [ 1 1 ] On construit H = [P^T | I₂] : H = [ 1 1 0 1 1 0 ] [ 1 0 1 1 0 1 ]

6. Distance de Hamming

La distance de Hamming d'un code linéaire correspond au poids minimum de ses mots de code non nuls. D'après notre liste, des mots comme (010010) ont un poids de 2. Donc la distance est d = 2.

Exercice 6 - Code Cyclique Systématique

1°) Propriétés d'un code cyclique systématique

Un code cyclique garantit que la permutation circulaire de tout mot de code donne un autre mot de code. Sa forme "systématique" impose que les k bits du message d'origine se retrouvent intacts et groupés à l'intérieur du mot de code. Pour un code (6, 2) :

• Nombre de bits du message k = 2 bits.
• Nombre de bits de contrôle (n - k) = 4 bits.
• Nombre de bits générés n = 6 bits. Génération systématique (Convention choisie : Poids fort = message, Poids faible = contrôle) : Pour encoder {m_j}, on multiplie le polynôme m(x) par x^(n-k), soit x⁴. On le divise par g(x) pour isoler le reste : x⁴ m(x) = q(x)g(x) + b(x). Les coefficients de b(x) sont les bits de contrôle {b_m}. Le mot de code est C(x) = x⁴ m(x) + b(x). Ordre dans le vecteur (poids faible au poids fort) : [ b₀, b₁, b₂, b₃, m₀, m₁ ].

2°) Génération du code (6, 2)

On factorise x⁶ + 1 = (1 + x²)(1 + x + x²)(1 + x + x²).

2.a Messages possibles Puisque k = 2, les polynômes m(x) possibles (degré < 2) sont au nombre de 4 : 0, 1, x, et 1 + x (correspondant aux bits 00, 10, 01, 11).

2.b Polynômes générateurs Le générateur g(x) doit diviser x⁶ + 1 et posséder un degré n - k = 4. Choix possibles à partir de la factorisation fournie :

• g₁(x) = (1 + x + x²)² = 1 + x² + x⁴ (3 termes)
• g₂(x) = (1 + x²)(1 + x + x²) = 1 + x + x³ + x⁴ (4 termes) Le polynôme comportant le moins de termes est g(x) = 1 + x² + x⁴.

2.c Tableau de codage systématique

Bits Message [m₀ m₁]	m(x)	x⁴ m(x)	Reste b(x) = Contrôle	Mot de code [b₀ b₁ b₂ b₃ m₀ m₁]
0 0	0	0	0	0 0 0 0 0 0
1 0	1	x⁴	1 + x²	1 0 1 0 1 0
0 1	x	x⁵	x + x³	0 1 0 1 0 1
1 1	1 + x	x⁴ + x⁵	1 + x + x² + x³	1 1 1 1 1 1

3°) Détection et correction des erreurs

3.a Syndrôme d'erreur Le syndrôme est le reste de la division du mot reçu Y(x) par le polynôme générateur g(x). Il comporte n - k = 4 bits. Tableau des syndrômes pour une erreur simple (e(x) = x^i) :

Erreur simple (Pos i)	e(x)	Reste S(x)	Syndrôme [s₀ s₁ s₂ s₃]
Bit 0	1	1	1 0 0 0
Bit 1	x	x	0 1 0 0
Bit 2	x²	x²	0 0 1 0
Bit 3	x³	x³	0 0 0 1
Bit 4	x⁴	1 + x²	1 0 1 0
Bit 5	x⁵	x + x³	0 1 0 1

3.b Mot reçu 010111 Mot reçu Y(x) = x + x³ + x⁴ + x⁵. Syndrôme S(x) = Y(x) mod (1 + x² + x⁴) Par linéarité, S(x) = S(x) + S(x³) + S(x⁴) + S(x⁵) = x + x³ + (1 + x²) + (x + x³) = 1 + x² (les éléments identiques s'annulent modulo 2). Syndrôme calculé = [1 0 1 0]. Ce syndrôme est dans la table (erreur au bit 4).

3.c Mots reçus 111000 et 010010

• Y₁ = 111000 => Y₁(x) = 1 + x + x². S(x) = 1 + x + x² (degré < 4, syndrôme = [1 1 1 0]).
• Y₂ = 010010 => Y₂(x) = x + x⁴. S(x) = x + (1 + x²) = 1 + x + x² (syndrôme = [1 1 1 0]). Déduction : Les deux mots donnent un syndrôme identique [1 1 1 0], qui ne figure pas dans le tableau des erreurs simples. Cela indique qu'il s'agit d'erreurs multiples (au moins doubles). Le code détecte qu'il y a une erreur mais son pouvoir de correction est dépassé (il ne permet pas de différencier ces deux cas d'erreurs multiples car elles produisent la même classe d'équivalence de syndrôme).

Exercice 7 - Code de convolution

1°) Généralités

1.a Schéma de principe L'encodeur est constitué d'un registre à décalage à 2 bascules mémoires (m_{k-1} et m_{k-2}) alimenté par l'entrée m_k. 3 additionneurs modulo 2 génèrent les sorties :

• Sortie 1 (g₁) reliée à m_k et m_{k-2}.
• Sortie 2 (g₂) reliée à m_k et m_{k-1}.
• Sortie 3 (g₃) reliée à m_k, m_{k-1}, et m_{k-2}. Un commutateur multiplexeur lit successivement g₁, g₂, et g₃ pour chaque bit d'entrée.

1.b Contraintes de longueur La contrainte de longueur minimale K du code représente le nombre de bits impliqués, soit K = 3 (l'entrée et deux mémoires). Pour un message de longueur L, le mot de code généré sans forçage à zéro ("flush") sera de longueur 3L. Si l'on vide les registres (flush de K-1 bits nuls pour ramener l'état à 0), la longueur totale sera de 3(L + 2).

1.c Encodage du message [1011] Ordre du message : m₀=1, m₁=0, m₂=1, m₃=1 (état initial 00).

• k=0 (m₀=1, état 00) : Sorties g₁=1, g₂=1, g₃=1. Mot = 111. Nouvel état = 10.
• k=1 (m₁=0, état 10) : Sorties g₁=0, g₂=1, g₃=1. Mot = 011. Nouvel état = 01.
• k=2 (m₂=1, état 01) : Sorties g₁=0, g₂=1, g₃=0. Mot = 010. Nouvel état = 10.
• k=3 (m₃=1, état 10) : Sorties g₁=1, g₂=0, g₃=0. Mot = 100. Nouvel état = 11.
• (Optionnel) Flush 1 (m=0, état 11) : Mot = 110. Nouvel état = 01.
• (Optionnel) Flush 2 (m=0, état 01) : Mot = 101. Nouvel état = 00. Mot de code (sans flush) : [111 011 010 100].

2°) Approche graphique

2.a Table de vérité L'état est défini par (m_{k-1} m_{k-2}).

Entrée m_k	État [m_{k-1} m_{k-2}]	Sortie g₁	Sortie g₂	Sortie g₃	Nouvel État
0	00	0	0	0	00
1	00	1	1	1	10
0	10 (m_{k-1}=1, m_{k-2}=0)	0	1	1	01
1	10	1	0	0	11
0	01 (m_{k-1}=0, m_{k-2}=1)	1	0	1	00
1	01	0	1	0	10
0	11 (m_{k-1}=1, m_{k-2}=1)	1	1	0	01
1	11	0	0	1	11

2.b Arbre du code et nombre d'états Le nombre d'états différents intervenant est de 4 (00, 01, 10, 11) car la mémoire est de taille 2.

(Les 2.c et 2.d - le treillis et le graphe d'état - se déduisent visuellement en traçant des flèches entre les 4 états de la table ci-dessus).

2.e Vérification (1.c) avec le graphe En partant du point (00) : L'entrée 1 fait transiter vers (10) [Sortie 111]. L'entrée 0 vers (01) [Sortie 011]. L'entrée 1 vers (10) [Sortie 010]. L'entrée 1 vers (11) [Sortie 100]. Cela vérifie formellement le résultat du 1.c.

3°) Décodage

3.a Algorithme de décodage L'algorithme de référence est l'Algorithme de Viterbi. Principe de base : Il repose sur le principe du maximum de vraisemblance et la programmation dynamique. Il calcule la distance de Hamming (ou métrique de branche) entre le bloc reçu et les blocs possibles sur le treillis, cumulant l'erreur et ne conservant pour chaque noeud que le chemin dit "survivant" minimisant le taux d'erreur, permettant ainsi de retrouver le cheminement le plus probable.

3.b Décodage du mot reçu [111 110 110 010 011 101] En appliquant Viterbi et en cherchant le chemin se terminant sur l'état 00 (signifiant qu'il y a eu un flush de 2 bits) :

• Bloc 1 reçu (111) vs chemin (1) attendu (111). Erreur cumulée = 0. État 10.
• Bloc 2 reçu (110) vs chemin (1) attendu (100). L'erreur de distance est de 1 (sur le bit du milieu). Le chemin continue vers l'état 11.
• Bloc 3 reçu (110) vs chemin (0) attendu (110). Erreur = 0. État 01.
• Bloc 4 reçu (010) vs chemin (1) attendu (010). Erreur = 0. État 10.
• Flush reçu (011) vs chemin (0) attendu (011). Erreur = 0. État 01.
• Flush reçu (101) vs chemin (0) attendu (101). Erreur = 0. État 00.

Le message émis était m = [1 1 0 1]. Est-ce le mot de code attendu ? Non. Le mot qu'on aurait dû réceptionner sans distorsion pour ce message était [111 100 110 010 011 101]. Il y a donc eu une erreur unique de transmission sur le 5ème bit transmis (au milieu du 2ème bloc).

Exercice 8 - Code de Hamming (7, 4)

Matrice de contrôle H fournie : [ 1 1 0 1 0 0 1 ] [ 0 1 1 1 0 1 0 ] [ 1 1 1 0 1 0 0 ]

1. Matrice génératrice G

Dans H, on observe la matrice identité I₃ aux colonnes 7, 6, 5 : C₇ = (1, 0, 0)^T, C₆ = (0, 1, 0)^T, C₅ = (0, 0, 1)^T. Pour isoler les bits de parité x₅, x₆, x₇ avec le système H × C^T = 0 :

• x₇ = x₁ + x₂ + x₄
• x₆ = x₂ + x₃ + x₄
• x₅ = x₁ + x₂ + x₃ La matrice génératrice G qui mappe (x₁, x₂, x₃, x₄) en (x₁, x₂, x₃, x₄, x₅, x₆, x₇) est : G = [ 1 0 0 0 1 0 1 ] [ 0 1 0 0 1 1 1 ] [ 0 0 1 0 1 1 0 ] [ 0 0 0 1 0 1 1 ]

2. Tableau du code et distance minimale

La génération des 16 mots de code se fait par la formule C = m × G.

Msg m	Mot de code	Poids	Msg m	Mot de code	Poids
0000	0000000	0	1000	1000101	3
0001	0001011	3	1001	1001110	4
0010	0010110	3	1010	1010011	4
0011	0011101	4	1011	1011000	3
0100	0100111	4	1100	1100010	3
0101	0101100	3	1101	1101001	4
0110	0110001	3	1110	1110100	4
0111	0111010	4	1111	1111111	7

• Le poids minimum (non nul) est de 3, donc la distance minimale est d_min = 3.
• Le code peut corriger au plus t = floor((d - 1) / 2) = floor((3 - 1) / 2) = 1 erreur.

3. Relation vérifiée par H et C

Un vecteur ligne C (de 7 éléments) est un mot de code valide si et seulement s'il satisfait l'équation matricielle orthogonale : H × C^T = 0 (où 0 est le vecteur nul (0, 0, 0)^T et les opérations sont modulo 2).

4. Syndrôme des erreurs qui passeront inaperçues

Les erreurs qui passeront inaperçues sont des profils d'erreurs (ou bruits) qui transforment un mot de code valide en un autre mot de code valide. Le vecteur d'erreur e est donc lui-même un mot de code du dictionnaire. Dans ce cas, la multiplication de H par l'erreur donnera le vecteur nul. Leur syndrôme est le vecteur de dimension 3 : (0, 0, 0).

5. Différents codes d'erreurs (syndrômes uniques)

Les syndrômes des 7 erreurs simples possibles (erreur sur un unique bit de 1 à 7) correspondent aux 7 colonnes de la matrice de contrôle H :

• Erreur bit 1 : Syndrôme [1 0 1]^T
• Erreur bit 2 : Syndrôme [1 1 1]^T
• Erreur bit 3 : Syndrôme [0 1 1]^T
• Erreur bit 4 : Syndrôme [1 1 0]^T
• Erreur bit 5 : Syndrôme [0 0 1]^T
• Erreur bit 6 : Syndrôme [0 1 0]^T
• Erreur bit 7 : Syndrôme [1 0 0]^T

Méthode

Face à une épreuve de Théorie de l'Information et de Codage, la rigueur arithmétique et le suivi scrupuleux des conventions fixées sont primordiaux :

1. Théorie de l'information (Entropie, Canal) : Veillez toujours à vérifier que la somme de vos probabilités vaut strictement 1. Les logarithmes sont en base 2 ; maîtrisez les fractions remarquables. Préparez toujours un tableau de probabilités jointes clair avant de déduire les marginales.
2. Codage source (Huffman, Fano) : L'organisation de l'arbre détermine la réussite. Ne regroupez jamais plus de deux feuilles à la fois dans Huffman. Vérifiez méthodiquement la cohérence entre l'entropie théorique H(X) et la longueur moyenne obtenue (qui doit toujours lui être légèrement supérieure ou égale, H(X) ≤ L).
3. Codes correcteurs linéaires et cycliques : Dans les calculs d'algèbre de Boole et polynômes GF(2), il n'y a pas de retenues. L'addition est un simple XOR (Soustraction = Addition). Assurez-vous d'identifier clairement l'ordre de vos bits et polynômes (poids forts / faibles) tel qu'il est défini par le contexte de l'énoncé. Dans un code détecteur, le reste d'une division polynomiale donne directement votre syndrôme pour une localisation immédiate d'erreur.