Détection et Correction d'Erreurs | Sciences de l'Ingénieur 1ère
Introduction à la détection et correction d'erreurs
Découvrez les techniques pour garantir l'intégrité des données transmises
Définition des erreurs
Qu'est-ce qu'une erreur ?
Une erreur est une modification involontaire d'un ou plusieurs bits d'un message durant sa transmission ou son stockage.
Elle peut être causée par des interférences, des bruits, des défauts matériels, ou des perturbations électromagnétiques.
Les erreurs compromettent l'intégrité des données transmises.
- Erreur simple : modification d'un seul bit
- Erreur multiple : modification de plusieurs bits
- Erreur en rafale : modification de bits consécutifs
Les principales causes d'erreurs sont :
- Interférences électromagnétiques
- Brutalité des signaux
- Défauts matériels
- Température excessive
- Humidité
Codes de parité
Détection simple d'erreur
Le code de parité ajoute un bit supplémentaire pour détecter les erreurs simples.
Deux types de parité : paire et impaire.
Parité paire : le nombre total de 1 est pair.
Parité impaire : le nombre total de 1 est impair.
Message : 1011
Nombre de 1 : 3 (impair)
Bit de parité paire : 1 (pour rendre le total pair)
Message transmis : 10111
- Ne peut pas corriger les erreurs
- Ne détecte pas les erreurs doubles (ou multiples)
- Simple méthode de détection
CRC (Cyclic Redundancy Check)
Vérification cyclique
Le CRC (Cyclic Redundancy Check) est un code de détection d'erreur basé sur la division polynomiale.
Utilise un polynôme générateur prédéterminé.
Le reste de la division est ajouté au message.
- Ajouter n zéros au message (n = degré du polynôme)
- Diviser le message par le polynôme générateur
- Prendre le reste de la division
- Remplacer les zéros ajoutés par le reste
- Détecte la plupart des erreurs
- Très efficace pour les erreurs en rafale
- Implémentation matérielle simple
- Utilisé dans Ethernet, USB, disques durs
Code de Hamming
Correction d'erreurs
Le code de Hamming permet de détecter et corriger une erreur simple.
Utilise des bits de parité placés à des positions spécifiques (puissances de 2).
Capable de corriger une erreur unique et de détecter deux erreurs.
Les bits de parité sont placés aux positions : 1, 2, 4, 8, 16, ... (puissances de 2).
Les autres positions contiennent les bits de données.
Exemple pour (7,4) : positions 1, 2, 4 sont des bits de parité.
Chaque bit de parité couvre des positions spécifiques :
- Bit 1 : positions 1, 3, 5, 7, 9, 11, ...
- Bit 2 : positions 2, 3, 6, 7, 10, 11, ...
- Bit 4 : positions 4, 5, 6, 7, 12, 13, 14, 15, ...
Applications concrètes
Utilisation des techniques
Utilisation de CRC pour vérifier l'intégrité des paquets.
Le récepteur rejette les paquets avec erreurs détectées.
Retransmission automatique des paquets erronés.
Utilisation de codes de correction d'erreurs (ECC).
Correction automatique des erreurs mineures.
Prévention de la corruption des données.
- RAM : ECC pour correction d'erreurs simples
- CD/DVD : Reed-Solomon pour correction d'erreurs
- Bluetooth : codes de Hamming pour correction
- Satellites : codes convolutifs pour transmission fiable
Exercice 1 : Parité
Exercice d'application
1. Ajouter un bit de parité paire au message 1010110.
2. Ajouter un bit de parité impaire au message 1100101.
3. Si le message reçu avec parité paire est 10110100, y a-t-il une erreur ?
Solution exercice 1
Correction détaillée
Message : 1010110
Nombre de 1 : 4 (pair)
Bit de parité paire : 0 (pour garder le total pair)
Message : 1100101
Nombre de 1 : 4 (pair)
Bit de parité impaire : 1 (pour rendre le total impair)
Message reçu : 10110100 (avec parité paire)
Bits de données : 1011010
Bit de parité reçu : 0
Nombre de 1 dans les données : 4 (pair)
Le bit de parité devrait être 0 (pair) ✓
Exercice 2 : Code de Hamming
Exercice sur le code de Hamming
1. Encoder le message 1011 avec le code de Hamming (7,4).
2. Si le message reçu est 1100101, y a-t-il une erreur ? Si oui, corrigez-la.
Solution exercice 2
Correction détaillée
Positions : 1 2 3 4 5 6 7
Bits : p1 p2 d1 p3 d2 d3 d4
Message : 1011 → d1=1, d2=0, d3=1, d4=1
p1 couvre positions 1,3,5,7 → p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0
p2 couvre positions 2,3,6,7 → p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1
p3 couvre positions 4,5,6,7 → p3 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0
Message reçu : 1100101
Positions : 1 2 3 4 5 6 7
Bits : 1 1 0 0 1 0 1
Calcul des syndromes :
s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1
s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4 = 1 ⊕ 0 ⊕ 0 ⊕ 1 = 0
s3 = p3 ⊕ d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
Syndrome = s3s2s1 = 001₂ = 1₁₀ → erreur en position 1
Synthèse
Points clés
- Parité : simple mais limité
- CRC : très efficace pour les erreurs en rafale
- Utilisés dans la transmission de données
- Hamming : correction d'une erreur simple
- Reed-Solomon : correction d'erreurs multiples
- Utilisés dans le stockage et la transmission fiable
- Quantité d'erreurs attendues
- Complexité de mise en œuvre
- Redondance acceptable
- Vitesse de traitement requise
Conclusion
Félicitations !
Continuez à pratiquer pour renforcer vos compétences