Corrigé Exercice Web Intelligence

Exercice 0 - Théorie de l'information

Question préliminaire - Définition des sources

Nous avons un canal de transmission binaire symétrique (BSC). La source d'entrée X a pour alphabet {0, 1} avec des probabilités équiprobables : p(x1 = 0) = 1/2 p(x2 = 1) = 1/2

La source de sortie Y a pour alphabet {0, 1}. Le canal introduit une probabilité d'erreur p. Les probabilités conditionnelles de transition p(y/x) sont données par le graphe : p(y1 / x1) = 1 - p (transmission correcte de 0) p(y2 / x2) = 1 - p (transmission correcte de 1) p(y2 / x1) = p (erreur : 0 devient 1) p(y1 / x2) = p (erreur : 1 devient 0)

Calcul des probabilités jointes et marginales

Les probabilités jointes p(x, y) se calculent par la loi de Bayes : p(x, y) = p(y / x) × p(x) p(x1, y1) = (1 - p) × 1/2 p(x2, y1) = p × 1/2 p(x1, y2) = p × 1/2 p(x2, y2) = (1 - p) × 1/2

Les probabilités marginales de la source de sortie Y s'obtiennent en sommant les probabilités jointes : p(y1) = p(x1, y1) + p(x2, y1) = (1 - p)/2 + p/2 = 1/2 p(y2) = p(x1, y2) + p(x2, y2) = p/2 + (1 - p)/2 = 1/2

Calcul des probabilités conditionnelles inverses

On utilise à nouveau Bayes : p(x / y) = p(x, y) / p(y) p(x1 / y1) = [ (1 - p)/2 ] / (1/2) = 1 - p p(x1 / y2) = [ p/2 ] / (1/2) = p p(x2 / y1) = [ p/2 ] / (1/2) = p p(x2 / y2) = [ (1 - p)/2 ] / (1/2) = 1 - p

Quantité d'information et Entropies simples

La quantité d'information d'un caractère est I(x) = log2(1 / p(x)). I(x1) = I(x2) = log2(2) = 1 bit I(y1) = I(y2) = log2(2) = 1 bit

L'entropie de chaque source est l'espérance de la quantité d'information : H(X) = 1 bit par symbole. H(Y) = 1 bit par symbole.

Calcul de l'entropie jointe H(X, Y)

L'entropie jointe est la somme de p(x, y) × log2(1 / p(x, y)) sur tous les (x, y) : H(X, Y) = (1/2)(1 - p)log2(2/(1 - p)) + (1/2)p log2(2/p) + (1/2)p log2(2/p) + (1/2)(1 - p)log2(2/(1 - p)) H(X, Y) = (1 - p)log2(2/(1 - p)) + p log2(2/p) En décomposant log2(a/b) = log2(a) - log2(b) et sachant que log2(2) = 1 : H(X, Y) = (1 - p)[1 - log2(1 - p)] + p[1 - log2(p)] H(X, Y) = 1 - (1 - p)log2(1 - p) - p log2(p)

Calcul de l'entropie conditionnelle moyenne H(Y/X)

L'entropie conditionnelle moyenne traduit l'incertitude restante sur Y quand on connaît X. Le calcul montre que H(Y/X) = H(X,Y) - H(X) : H(Y/X) = -(1 - p)log2(1 - p) - p log2(p) Étant donné la symétrie absolue de ce canal binaire, H(X/Y) a exactement la même expression.

Calcul de la quantité d'information mutuelle I(X, Y)

L'information mutuelle se calcule de plusieurs façons qui aboutissent toutes au même résultat : Méthode 1 : I(X, Y) = H(X) + H(Y) - H(X, Y) I(X, Y) = 1 + 1 - [1 - (1 - p)log2(1 - p) - p log2(p)] I(X, Y) = 1 + (1 - p)log2(1 - p) + p log2(p)

Méthode 2 : I(X, Y) = H(Y) - H(Y/X) = 1 + (1 - p)log2(1 - p) + p log2(p)

Analyse des cas particuliers remarquables

1. Si p = 0 : Aucune erreur de transmission. I(X,Y) = 1. Les sources sont identiques. H(X,Y) = H(X) = 1.
2. Si p = 1/2 : Pagaille complète. I(X,Y) = 0. Les sources sont indépendantes, la transmission est purement aléatoire. H(X,Y) = H(X) + H(Y) = 2.
3. Si p = 1 : Inversion déterministe (les 0 deviennent 1, et inversement). I(X,Y) = 1. L'information est intégralement préservée, il suffit d'inverser le signal reçu.

Exercice 1 - Codage de source

Note sur le document source : Le texte d'origine contient une erreur de reconnaissance de caractères (OCR). Dans la colonne des probabilités, les valeurs "216", "215", etc., correspondent en réalité aux fractions mathématiques 6/21, 5/21, etc. De même, le calcul de l'efficacité affiche "75.98 %" par erreur de frappe ou d'OCR, alors que le rapport donne 98,75 %.

Questions 1 à 3 - Arbre de codage et probabilités

On dispose d'un alphabet de 6 symboles dont les occurrences sont {F: 6, E: 5, D: 4, C: 3, B: 2, A: 1}. Le total des occurrences est 21.

Symbole	Codage	Longueur (nk)	Probabilité (pk)
F	00	2	6/21
E	10	2	5/21
D	11	2	4/21
C	010	3	3/21
B	0110	4	2/21
A	0111	4	1/21

Question 4 - Entropie de la source

H(X) = Σ (pk × log2(1 / pk)) pour k=1 à 6. H(X) = (6/21)log2(21/6) + ... + (1/21)log2(21/1) ≈ 2,3983 bits/symbole.

Question 5 - Longueur moyenne du code

R = Σ (pk × nk) R = (6/21×2) + (5/21×2) + (4/21×2) + (3/21×3) + (2/21×4) + (1/21×4) R = (12 + 10 + 8 + 9 + 8 + 4) / 21 = 51 / 21 ≈ 2,4286 bits/symbole.

Question 6 - Efficacité

Efficacité de Huffman = H(X) / R = 2,3983 / 2,4286 = 0,9875 soit 98,75 %. (Note : La mention 75.98 % dans la source est une erreur manifeste d'OCR ou de transcription d'un étudiant de la valeur 98.75%).

Question 7 - Rapport de compression

Si on encodait chaque symbole sur un octet standard (8 bits) : Taux de compression = R / 8 = 2,4286 / 8 = 0,3035 soit environ 30 %.

Questions 8 et 9 - Codes de Fano / Shannon

Un code alternatif (Shannon-Fano) construit par division récursive donne : F (00), E (01), D (10), C (110), B (1110), A (1111). Les longueurs nk et les probabilités pk associées sont strictement identiques au code de Huffman ci-dessus. L'efficacité est donc la même : Efficacité de Fano = H(X) / R = 0,9875 (98,75 %).

Exercice 2 - Codage de source (Variante)

Note : Même problème d'OCR, "287" signifie 7/28.

Questions 1 à 3 - Arbre de codage

Alphabet {G: 7, F: 6, E: 5, D: 4, C: 3, B: 2, A: 1}. Le total est 28.

Symbole	Codage	Longueur (nk)	Probabilité (pk)
G	01	2	7/28
F	10	2	6/28
E	000	3	5/28
D	001	3	4/28
C	110	3	3/28
B	1110	4	2/28
A	1111	4	1/28

Question 4 - Entropie

H(X) = Σ (pk × log2(1 / pk)) = 2,61 bits/symbole.

Question 5 - Longueur moyenne

R = Σ (pk × nk) = (14 + 12 + 15 + 12 + 9 + 8 + 4) / 28 = 74 / 28 ≈ 2,64 bits/symbole.

Questions 6 à 9 - Efficacité et compression

Efficacité = H(X) / R = 2,61 / 2,64 ≈ 0,9886 soit 98,86 %. Taux de compression (par rapport à 8 bits) = 2,64 / 8 = 0,33 soit 33 %. Comme pour l'exercice précédent, une variante de codage produisant les mêmes longueurs par symbole donnera la même efficacité mathématique.

Exercice 3 - Code en blocs linéaires

Question 1 - Paramètres du code

La matrice de contrôle H contient 3 lignes et 5 colonnes. Puisque le nombre de colonnes correspond à n et le nombre de lignes à (n - k) pour une matrice de parité indépendante : n = 5 n - k = 3, donc k = 2. Il s'agit d'un code de bloc (5, 2).

Question 2 - Validation de mots de code

Un vecteur m est un mot de code valide si et seulement si son syndrome est nul, c'est-à-dire si m × H^T = 0 (où H^T est la transposée de H).

Soit H^T la transposée de la matrice extraite de l'énoncé.

• Pour m1 = (01001) : m1 × H^T ≠ (000). Ce vecteur produit un syndrome non nul. m1 n'est pas un mot de code valide.
• Pour m2 = (11010) : m2 × H^T = (000). Le syndrome est nul. m2 est un mot de code valide.

Questions 3 et 4 - Matrice génératrice et dictionnaire de codage

La matrice génératrice G sous forme systématique G = [I_k | P]. Les 4 messages possibles (k=2 donne 2² = 4 messages) sont :

Message (mi)	Mot de code (Ci)	Poids de Hamming (wi)
00	00000	0
01	01101	3
10	11010	3
11	10111	4

Question 5 - Distance minimale

La distance minimale d'un code en blocs linéaires est calculable de trois manières :

• Méthode 1 : d_min est égal au plus petit poids de Hamming non nul d'un mot de code valide. Ici, min(wi) pour i > 0 est 3.
• Méthode 2 : d_min est la plus petite distance de Hamming entre deux mots de code valides distincts. En comparant chaque paire, on trouve min(d_ij) = 3.
• Méthode 3 : d_min est égale au nombre minimal de colonnes de la matrice H qui sont linéairement dépendantes. Ici, colonne 1 + colonne 2 + colonne 4 = 0, ce qui implique que 3 colonnes sont liées. Résultat : d_min = 3.

Exercice 4 - Code Cyclique (7, 4)

Question 1 - Paramètres

Polynôme générateur g(x) = 1 + x² + x³. Le degré de g(x) vaut n - k = 3. On nous donne n = 7, donc k = 7 - 3 = 4 bits de message.

Question 2 et 3 - Matrice génératrice systématique

Une matrice de base G* s'obtient en décalant le motif du polynôme (01101) :

G* = [ 0 0 0 1 1 0 1 ]  (L1)
     [ 0 0 1 1 0 1 0 ]  (L2)
     [ 0 1 1 0 1 0 0 ]  (L3)
     [ 1 1 0 1 0 0 0 ]  (L4)

Pour la rendre systématique (forme identité à gauche), on applique le pivot de Gauss sur GF(2) (l'addition est le XOR) :

• Nouvelle L2 = L2 + L1
• Nouvelle L3 = L3 + L2(nouvelle)
• Nouvelle L4 = L4 + L1 + L2(ancienne) + L3(ancienne) Matrice systématique G :

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

Question 4 - Matrice de parité

La matrice H s'en déduit directement :

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

Question 5 - Validation d'un mot par division polynomiale

Le mot reçu est m = (0 0 1 1 1 0 1). En notation polynomiale : m(x) = x² + x³ + x⁴ + x⁶. On vérifie si ce mot appartient au code cyclique en calculant le reste de la division euclidienne de m(x) par g(x). Le reste trouvé est r(x) = 1 + x. Puisque le reste n'est pas nul, m n'est pas un mot de code valide. (Une vérification matricielle m × H^T confirmerait ce résultat).

Question 6 - Propriété du polynôme générateur

Un polynôme g(x) engendre un code cyclique (n,k) si et seulement si g(x) divise (1 + x^n). Ici n=7. 1 + x^7 = (1 + x)(1 + x² + x³)(1 + x + x³). On constate bien que g(x) = 1 + x² + x³ est l'un des facteurs de (1 + x^7). Il est donc un polynôme générateur valide pour le code (7,4).

Question 7 - Encodage d'un message

Soit le message m = (1101), correspondant au polynôme m(x) = 1 + x + x³. L'encodage par produit donne le mot de code C(x) = m(x) × g(x) : C(x) = (1 + x + x³) × (1 + x² + x³) = 1 + x² + x³ + x + x³ + x⁴ + x³ + x⁵ + x⁶ Dans GF(2), l'addition est modulo 2 (les termes en double s'annulent) : C(x) = 1 + x + x² + x³ + x⁴ + x⁵ + x⁶. Mot de code C = (0011101) ? Attention, une opération systématique C(x) = x^(n-k)m(x) + r(x) donne le mot encodé systématique. Le document source trouve C = 0011101 pour ce message selon la méthode de décalage.

Question 8 - Décodage par syndrome

Si l'on reçoit Y = m + erreur. Le syndrome S(x) est le reste de Y(x) divisé par g(x). Ici S(x) = x. Selon la table de décodage des syndromes construite pour ce code, un syndrome égal à x correspond à une erreur sur le bit de poids x² (la 3ème position, erreur e = 0000100). On corrige le mot reçu en ajoutant l'erreur (XOR) : C*(x) = Y(x) + e(x). Mot corrigé C* = (0001011). Le message d'origine extrait est donc (1011).

Exercice 5 - Code cyclique

Question 1 et 2 - Table de codage

Le code utilise l'encodage polynomial classique de type : Mot de code C(x) = m(x) × g(x). Le générateur ici semble être g(x) = 1 + x + x³ d'après les divisions effectuées. On vérifiera que (1 + x + x³) divise (1 + x^7).

Question 3 et 4 - Matrices du code

La matrice de base G* est obtenue par décalage :

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

Après opérations sur les lignes pour obtenir la forme systématique :

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

Question 5 et 6 - Matrice H et distance minimale

La matrice H systématique correspondante est :

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

La distance minimale calculée est d_min = 2. Le code ne peut que détecter des erreurs simples, pas les corriger (il faut d_min ≥ 3 pour corriger 1 erreur).

Exercice 6 - Code Cyclique (6, 2)

Question 2 - Candidats pour le polynôme générateur

Pour un code (6, 2), n = 6 et k = 2. Le polynôme générateur g(x) doit être de degré n - k = 4. Il doit aussi diviser (1 + x⁶). Factorisation sur GF(2) : 1 + x⁶ = (1 + x²) × (1 + x + x²) × (1 + x + x²). Le choix du polynôme générateur de degré 4 est g(x) = (1 + x + x²)² = 1 + x² + x⁴. Il comporte le minimum de termes.

Messages et bits de contrôle (r(x) est le reste de x⁴ m(x) divisé par g(x)) :

Message m(x)	Bits de contrôle r(x)	Mot de code syst. C(x)
0	0	0
1	1 + x²	1 + x² + x⁴
x	x + x³	x + x³ + x⁵
1 + x	1 + x + x² + x³	1 + x + x² + x³ + x⁴ + x⁵

Question 3 - Table des syndromes

Méthode de calcul du syndrome S(x) = Y(x) mod g(x). Table de décodage pour les erreurs simples :

Erreur E(x)	Syndrome S(x)
0 (Pas d'erreur)	0
1	1
x	x
x²	x²
x³	x³
x⁴	1 + x²
x⁵	x + x³

Si l'on reçoit Y(x) correspondant à (0 1 0 1 1 1), soit Y(x) = x + x³ + x⁴ + x⁵. La division de Y(x) par g(x) (1 + x² + x⁴) donne un reste S(x) = 1 + x². Dans la table des syndromes, S(x) = 1 + x² correspond au motif d'erreur E(x) = x⁴ (erreur sur la position 4). Le mot corrigé est C*(x) = Y(x) + E(x) = x + x³ + x⁵. Le message d'origine était donc (01) ou (x).

Si l'on calcule les syndromes pour deux erreurs différentes comme Y1(x) = 1 et Y2(x) = 1 + x² + x³, il se peut qu'elles partagent le même syndrome. Cela indique l'existence d'erreurs détectables mais non corrigeables car elles introduisent des conflits de syndrome.

Exercice 7 - Code Convolutif

Question 1 - Paramètres et encodage

Soit un code avec n = 3, k = 1 et une longueur de contrainte K = 3. Le message m = [1 0 1 1] (de longueur L=4). La longueur du mot de code sera de n × (L + K - 1) = 3 × 6 = 18 bits. Les générateurs sont g1(x) = 1 + x², g2(x) = 1 + x, g3(x) = 1 + x + x². Par multiplication polynomiale, on trouve les sous-séquences C1, C2 et C3. C1 = 100111 C2 = 111010 C3 = 110001 Le flux de sortie est le multiplexage (entrelacement) de ces trois bits : C = 111 011 010 100 110 101.

Question 2 - Graphe et Treillis

Le système possède K - 1 = 2 bascules de mémoire, donc 2² = 4 états internes possibles : a = (00), b = (01), c = (10), d = (11). Les transitions dépendent du bit d'entrée (0 ou 1).

Question 3 - Algorithme de Viterbi

Pour décoder la séquence reçue : [111 110 110 010 011 101], on avance dans le treillis en accumulant la distance de Hamming (métrique de chemin) entre les bits reçus et les bits attendus sur chaque branche. À chaque nœud, l'algorithme de Viterbi ne conserve que le chemin survivant (celui avec la plus petite distance accumulée). La trace finale des survivants permet de remonter le treillis depuis la fin. Le chemin optimal traversé correspond au mot de code valide le plus proche : 111 100 110 010 011 101. Le message décodé d'origine qui correspond à ce chemin est m = 1 1 0 1.

Exercice 8 - Code de Hamming / Blocs

Question 1 et 2 - Construction du dictionnaire

Nous avons une matrice de parité H (3 lignes, 7 colonnes) définissant un code (7, 4). La matrice génératrice G déduite (4 lignes, 7 colonnes) permet d'encoder les 16 messages de 4 bits. En calculant le poids de Hamming (nombre de "1") de chaque mot de code non nul, on trouve que le poids minimal est 3. La distance minimale est donc d_min = 3.

La capacité de correction des erreurs est définie par e = partie_entière( (d_min - 1) / 2 ). Ici, e = partie_entière( (3 - 1) / 2 ) = 1. Le code corrige strictement 1 erreur.

Question 4 - Les erreurs doubles

Le syndrome est codé sur 3 bits (puisque H a 3 lignes). Il y a donc 2³ = 8 syndromes possibles. Le syndrome (000) est réservé au cas "pas d'erreur". Les 7 autres syndromes (001 à 111) couvrent exactement les 7 motifs d'erreurs simples (une erreur sur un des 7 bits). Tout l'espace des syndromes est exploité. Par conséquent, une erreur double produira forcément le même syndrome qu'une erreur simple ou que le cas sans erreur. Le récepteur se trompera et l'erreur double passera inaperçue (ou causera un faux décodage).

Question 5 - Table de décodage des erreurs simples

La table associe chaque motif d'erreur e(x) à la colonne correspondante de la matrice H :

• e = 1000000 -> S = 100
• e = 0100000 -> S = 010
• e = 0010000 -> S = 001
• e = 0001000 -> S = 110
• e = 0000100 -> S = 011
• e = 0000010 -> S = 111
• e = 0000001 -> S = 101

Méthode

Pour réussir les épreuves de théorie de l'information et de codage, voici la méthodologie à adopter :

1. Théorie de l'information (Canaux et Entropie) : Soyez très rigoureux sur les unités (bits/symbole). Tracez toujours le diagramme de transition du canal binaire avant de commencer les calculs. L'information mutuelle vérifie l'équation I(X,Y) = H(X) - H(X/Y) = H(Y) - H(Y/X). Utilisez les propriétés des logarithmes en base 2 pour simplifier vos expressions littérales avant de remplacer par les valeurs numériques.
2. Codes de source (Huffman/Shannon) : Classez scrupuleusement les probabilités par ordre décroissant. Dans la construction de l'arbre, indiquez toujours par convention le "0" sur la branche haute/gauche et le "1" sur la branche basse/droite. Pour calculer l'efficacité, n'oubliez pas que R (la longueur moyenne) ne doit pas descendre sous H(X).
3. Codes de blocs et Matrices : Maîtrisez le calcul matriciel binaire (opérations XOR). Une matrice sous forme systématique G = [I | P] donne immédiatement la matrice de parité H = [P^T | I]. Un syndrome nul est la condition sine qua non pour valider un mot reçu.
4. Codes cycliques : Les divisions polynomiales sur GF(2) sont analogues à des divisions euclidiennes avec des soustractions remplacées par des XOR (l'addition et la soustraction sont identiques). Alignez toujours les monômes de plus haut degré en premier.
5. Algorithme de Viterbi : Dessinez le treillis proprement. À chaque étape (itération de l'algorithme), calculez la distance de Hamming pour chaque branche entrante vers un nœud, ajoutez-la à la métrique de l'état d'origine, et "taillez" les branches en ne gardant que la valeur la plus faible (le chemin survivant). La rigueur dans la tenue des compteurs de distance vous garantira le bon mot de code en phase finale.