Détection et correction d’erreurs | Exercices corrigés

Concepts & Exercices

\(H = [I_k | P]\)

Matrice de Hamming

Parité

1 bit

Détection simple

CRC

Polynôme

Correction puissante

Hamming

d=3

Correction 1 bit

🎯

Détection : Identifier la présence d'erreurs dans les données.

📋

Correction : Non seulement détecter mais aussi corriger les erreurs.

🔍

Redondance : Bits supplémentaires pour la détection/correction.

⚙️

Distance de Hamming : Nombre de bits différents entre deux mots.

Exercice 1

Calculer la parité d'un mot binaire

Exercice 2

Calculer un checksum simple

Exercice 3

Comprendre le code de Hamming (7,4)

Exercice 4

Appliquer un CRC simple

Exercice 5

Corriger une erreur avec Hamming

Corrigé : Exercices 1 à 3

1 Parité

Définition :

Bit de parité : Bit supplémentaire ajouté à un mot de données pour détecter les erreurs de transmission.

Méthode de calcul de la parité :

Compter le nombre de bits à 1 dans le mot
Si parité paire : ajouter 0 si pair, 1 si impair
Si parité impaire : ajouter 1 si pair, 0 si impair
Le mot avec parité doit respecter la règle

Calcul de la parité paire pour 1011010 :

Nombre de bits à 1 : 4 (pair)

Parité paire : ajouter 0

Résultat : 10110100

Parité paire :

Nombre total de 1 doit être pair

Parité impaire :

Nombre total de 1 doit être impair

Implémentation :

XOR de tous les bits

Limitations :

Détecte 1 erreur, pas plus

Étape 1 : Compter les bits à 1

1011010 → 1+0+1+1+0+1+0 = 4 bits à 1

Étape 2 : Appliquer la règle de parité

Parité paire : 4 est pair → ajouter 0

Étape 3 : Former le mot complet

1011010 + 0 = 10110100

1011010 → 10110100 (parité paire)

Réponse finale :

Mot original : 1011010

Bit de parité paire : 0

Mot avec parité : 10110100

Règles appliquées :

• Simple à implémenter : XOR de tous les bits

• Détecte erreurs simples : Mais pas les doubles

• Utilisation : Mémoires RAM, transmissions série

2 Checksum

Définition :

Checksum : Somme des octets d'un message, utilisée pour la détection d'erreurs.

Calcul du checksum pour [45, 23, 78, 12] :

Somme = 45 + 23 + 78 + 12 = 158

Modulo 256 = 158

Checksum = 256 - 158 = 98

Calcul :

Somme des octets modulo 256

Vérification :

Checksum + données ≡ 0 (mod 256)

Limitation :

Moins robuste que CRC

Applications :

Protocoles IP, UDP, fichiers

Étape 1 : Sommer tous les octets

45 + 23 + 78 + 12 = 158

Étape 2 : Calculer le complément

Checksum = 256 - (somme % 256) = 256 - 158 = 98

Étape 3 : Vérification

45 + 23 + 78 + 12 + 98 = 256 ≡ 0 (mod 256) ✓

Checksum = 98

Réponse finale :

Données : [45, 23, 78, 12]

Checksum : 98

Vérification : 45+23+78+12+98 = 256 ≡ 0 (mod 256)

Règles appliquées :

• Simple mais limité : Moins efficace que CRC

• Détection d'erreurs : Basée sur la somme des données

• Utilisation : Protocoles réseau et fichiers

3 Code de Hamming (7,4)

Définition :

Code de Hamming (7,4) : Code correcteur qui encode 4 bits de données en 7 bits avec correction d'une erreur.

Encodage Hamming (7,4) pour 1011 :

Positions des bits de données : 3, 5, 6, 7

Positions des bits de parité : 1, 2, 4

Calcul des bits de parité selon la matrice de contrôle

Bits de parité :

p1, p2, p4 (positions 1, 2, 4)

Bits de données :

d3, d5, d6, d7 (positions 3, 5, 6, 7)

Calcul parité :

p1 = d3 ⊕ d5 ⊕ d7, p2 = d3 ⊕ d6 ⊕ d7, p4 = d5 ⊕ d6 ⊕ d7

Capacité :

Correction 1 erreur, détection 2 erreurs

Étape 1 : Placer les bits de données

Position 3: 1, Position 5: 0, Position 6: 1, Position 7: 1

Étape 2 : Calculer les bits de parité

p1 = 1 ⊕ 0 ⊕ 1 = 0

p2 = 1 ⊕ 1 ⊕ 1 = 1

p4 = 0 ⊕ 1 ⊕ 1 = 0

Étape 3 : Former le mot de code

p1 p2 d3 p4 d5 d6 d7 = 0 1 1 0 0 1 1

1011 → 0110011 (Hamming (7,4))

Réponse finale :

Position	1	2	3	4	5	6	7
Valeur	0	1	1	0	0	1	1

Bits de parité : positions 1, 2, 4

Bits de données : positions 3, 5, 6, 7

Règles appliquées :

• Positions de parité : Puissances de 2 (1, 2, 4, 8...)

• Calcul de parité : XOR des bits couverts

• Capacité : Correction d'une erreur, détection de deux

Corrigé : Exercices 4 à 5

4 CRC (Cyclic Redundancy Check)

Définition :

CRC : Technique de détection d'erreurs basée sur la division polynomiale.

Calcul CRC-4 avec polynôme x⁴ + x + 1 pour 1101011 :

Polynôme : 10011 (degré 4)

Message : 1101011

Division binaire pour obtenir le reste

Principe :

Division polynomiale modulo 2

Polynôme générateur :

Définit la longueur du CRC

Robustesse :

Meilleure que checksum

Applications :

Trames Ethernet, disques durs, fichiers

Étape 1 : Ajouter des zéros

1101011 → 11010110000 (ajout de 4 zéros)

Étape 2 : Division binaire par 10011

11010110000 ÷ 10011 = quotient avec reste

Étape 3 : Calcul du reste

Reste = 1010 (CRC de 4 bits)

CRC = 1010

Réponse finale :

Message : 1101011

Polynôme : x⁴ + x + 1 (10011)

CRC : 1010

Message avec CRC : 11010111010

Règles appliquées :

• Division modulo 2 : XOR au lieu de soustraction

• Polynôme standard : Utilisé pour la compatibilité

• Robustesse : Meilleure détection des erreurs

5 Correction d'erreur Hamming

Définition :

Correction d'erreur Hamming : Processus de détection et correction d'une erreur unique dans un mot de code.

Correction d'une erreur dans 0111011 (devrait être 0110011) :

Calcul des syndromes pour les positions de parité

Position de l'erreur = somme des positions avec syndrome ≠ 0

Syndrome :

Résultat de la multiplication H·r^T

Position erreur :

Valeur binaire du syndrome

Correction :

Inverser le bit à la position trouvée

Limite :

Uniquement 1 erreur corrigeable

Étape 1 : Calcul des syndromes

s1 = r1 ⊕ r3 ⊕ r5 ⊕ r7 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0

s2 = r2 ⊕ r3 ⊕ r6 ⊕ r7 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0

s4 = r4 ⊕ r5 ⊕ r6 ⊕ r7 = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1

Étape 2 : Position de l'erreur

Syndrome = s4s2s1 = 100₂ = 4₁₀

L'erreur est en position 4

Étape 3 : Correction

Inverser le bit en position 4 : 0111011 → 0110011

0111011 → 0110011 (corrigé)

Réponse finale :

Mot reçu : 0111011

Syndrome : 100₂ (position 4)

Mot corrigé : 0110011

Données originales : 1011

Règles appliquées :

• Syndrome nul : Aucune erreur détectée

• Syndrome non nul : Position de l'erreur

• Capacité limitée : Une seule erreur corrigeable

Cours bien détaillé

\(d_H = \sum_{i=1}^{n} (x_i \oplus y_i)\)

Distance de Hamming

🎯

Distance de Hamming : Nombre de positions où deux mots diffèrent.

📋

Capacité de détection : d-1 erreurs pour distance d.

🔍

Capacité de correction : ⌊(d-1)/2⌋ erreurs pour distance d.

⚙️

Redondance : Bits supplémentaires pour la correction.

💡

Conseil : La distance de Hamming mesure la capacité de détection/correction

🔍

Attention : Plus de redondance = meilleure correction mais plus de bande passante

⚡

Astuce : Les codes de Hamming sont optimaux pour la correction d'une erreur

📋

Méthode : Toujours vérifier les syndromes pour la correction

✅

Vérification : Le mot corrigé doit avoir un syndrome nul

Types de codes :

Parité simple : 1 bit de redondance, détection d'une erreur
Checksum : Somme des données, détection multiple
CRC : Division polynomiale, robuste
Hamming : Correction d'une erreur, détection de deux
Reed-Solomon : Correction de plusieurs erreurs

Règles importantes :

La détection d'erreurs repose sur l'ajout de redondance aux données
La correction d'erreurs nécessite suffisamment de bits de redondance
La distance de Hamming détermine la capacité de détection/correction
Les codes correcteurs sont essentiels pour les transmissions fiables
Le compromis existe entre redondance et efficacité

Applications :

Parité : Mémoires RAM, transmissions série
CRC : Trames Ethernet, disques durs, fichiers
Hamming : Mémoires ECC, transmissions spatiales
Reed-Solomon : CDs, DVDs, QR codes, transmissions
LDPC : Communications modernes, WiFi, satellites

Comparaison des codes :

Parité : Simple, 1 bit, détection simple
Checksum : Modéré, quelques bits, détection multiple
CRC : Complexe, plusieurs bits, robuste
Hamming : Équilibré, correction 1 erreur
Reed-Solomon : Complexité moyenne, correction multiple

Détection et correction d’erreursExercices corrigés

Détection et correction d’erreurs
Exercices corrigés