IT4B - Guide Pratique pour l'Examen

Concepts Fondamentaux

1. Source Sans Mémoire

  • Une source qui émet des symboles de façon indépendante

  • Caractérisée par les probabilités de ses symboles (p(A), p(B), etc.)

  • Débit symboles (DS) : nombre de symboles émis par seconde

2. Entropie

  • Mesure l'information moyenne par symbole

  • Pour une source binaire : H(S) = -p(A)log₂(p(A)) - p(B)log₂(p(B))

  • Débit d'entropie = H × DS

3. Canal Binaire Symétrique

  • Caractérisé par sa probabilité d'erreur (p)

  • Capacité du canal : C = 1 - H₂(p)

  • Débit d'utilisation (DC) en bits/sec

Méthodes de Codage

1. Codage de Huffman

  1. Classer les symboles par probabilités décroissantes

  2. Regrouper les deux plus petites probabilités

  3. Attribuer 0 à gauche, 1 à droite

  4. Répéter jusqu'à obtenir l'arbre complet

Performance

  • Longueur moyenne (n) des mots codes

  • Taux de réduction = nouveau_débit/ancien_débit

2. Codage Canal

  • Ajout de bits de contrôle pour détecter/corriger les erreurs

  • Distance minimale (dmin) : nombre minimum de positions différentes entre deux mots codes

  • Capacité de correction = ⌊(dmin-1)/2⌋

Matrices importantes

  1. Matrice génératrice (G)

    • Forme systématique : [Ik|P]

    • Génère tous les mots codes

  2. Matrice de contrôle (H)

    • Détecte les erreurs

    • HyT = syndrome

Méthode de Résolution

  1. Vérifier le théorème de Shannon :

    • Calculer H(S)

    • Calculer C

    • Vérifier H ≤ C

  2. Pour le codage source :

    • Calculer les probabilités des extensions

    • Construire l'arbre de Huffman

    • Calculer le taux de compression

  3. Pour le codage canal :

    • Déterminer les mots codes

    • Calculer dmin

    • Utiliser les matrices G et H

    • Corriger les erreurs avec la table des syndromes

Étapes de Résolution Systématique

1. Question Préliminaire (Théorème de Shannon)

  1. Calculer H(S) = -p(A)log₂(p(A)) - p(B)log₂(p(B))

  2. Calculer C = 1 - H₂(p) pour le canal

  3. Multiplier H(S) par DS pour avoir le débit d'entropie

  4. Multiplier C par DC pour avoir la capacité totale

  5. Vérifier si H ≤ C

2. Codage Source (Huffman)

  1. Pour trouver l'ordre d'extension M:

    • Utiliser H(S) ≤ n ≤ H(S) + 1/M

    • Si on veut réduire de X%, alors n ≤ (100-X)/100

    • En déduire M minimum

  2. Pour construire le code Huffman:

    • Calculer les probabilités: p(AAA) = p(A)³, etc.

    • Les classer par ordre décroissant

    • Regrouper les 2 plus petites

    • 0 à gauche, 1 à droite

  3. Calcul du taux de réduction:

    • Longueur moyenne = Σ(pi × longueur_moti)

    • Taux = longueur_moyenne/ordre_extension

3. Codage Canal

  1. Pour trouver les bits de contrôle:

    • Utiliser DC/DS = (k+r)/k où k = bits information, r = bits contrôle

  2. Pour la matrice de contrôle:

    • Écrire les équations de contrôle

    • Former G = [Ik|P]

    • En déduire H = [Pt|In-k]

  3. Pour corriger une erreur:

    • Calculer le syndrome S = HyT

    • Utiliser la table des syndromes

    • Corriger avec le vecteur de correction

Astuces pour l'Examen

  • Toujours commencer par vérifier Shannon

  • Pour Huffman, dessiner l'arbre proprement

  • Noter les puissances de 2 décroissantes dans les probabilités

  • Pour le canal, commencer par les mots codes simples (00000)

  • Vérifier la cohérence des résultats

Formules Importantes

  • H₂(p) = -p log₂(p) - (1-p)log₂(1-p)

  • Débit d'entropie = H × DS

  • Capacité = DC × (1 - H₂(p))

  • Taux de réduction = n/nombre_bits_original

Formules à Connaître

H(S) = -Σ pi log₂(pi)
C = 1 - H₂(p)
Taux réduction = longueur_moyenne/ordre_extension
dmin = minimum différences entre mots codes

## Exemples Pratiques

### Exemple 1: Vérification du Théorème de Shannon
Données:
- Source S{A,B} avec p(A)=0,98 et p(B)=0,02
- DS = 300K symboles/sec
- Canal avec p=0,05 et DC=280kbits/sec

1. Calcul de H(S):

H(S) = -(0,98 log₂(0,98) + 0,02 log₂(0,02)) H(S) = 0,1414 bits/symbole


2. Calcul de C:

H₂(0,05) = -(0,05 log₂(0,05) + 0,95 log₂(0,95)) C = 1 - H₂(0,05) = 0,7136 bits


3. Vérification finale:

Débit d'entropie = 300K × 0,1414 = 42,42 kbits/sec Capacité totale = 280K × 0,7136 = 199,8 kbits/sec 42,42K < 199,8K → Transmission possible


### Exemple 2: Codage Huffman d'ordre 3
Pour S{A,B} avec p(A)=0,98 et p(B)=0,02:

1. Calcul des probabilités d'ordre 3:

p(AAA) = 0,98³ = 0,941 p(AAB) = 0,98² × 0,02 = 0,019 p(ABA) = 0,98 × 0,02 × 0,98 = 0,019 p(ABB) = 0,98 × 0,02² = 0,00039 etc.


2. Arbre de Huffman résultant:

AAA → 1 AAB → 011 ABA → 010 BAA → 001 ABB → 00011 BAB → 00010 BBA → 00001 BBB → 00000


3. Taux de réduction:

n = (1×0,941 + 3×0,019×3 + 5×0,00039×4) = 1,118 taux = 1,118/3 = 0,373 → réduction de 62,7%


### Exemple 3: Codage Canal C(5,2)
Pour un code avec:

c₁ = i₁ c₂ = i₂ c₃ = i₁ + i₂


1. Mots codes:

00 → 00000 01 → 01011 10 → 10101 11 → 11110


2. Matrices:

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

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


3. Correction d'erreur:
Pour y = 11010

Syndrome = HyᵀT = 100 Vecteur correction = 00100 Mot corrigé = 11110