Télécommunications

Télécommunications
UNIVERSITE CHOUAIB
DOUKKALI
ENSA
ECOLE NATIONALE DES
SCIENCES APPLIQUEES D’EL JADIDA
DEPARTEMENT DE
TELECOMMUNICATIONS
Cours: T7
Codage correcteur d’erreurs
Présenté par
Prof. Dr. A. Berraissoul
2011-2012 ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
2
Télécommunications
Codage correcteur d’erreurs
Plan du Partie I

Notions générales

Codage Linéaire à Bloc.

Codage Cyclique.

Code Reed-Solomon

Code BCH.

Codage Convolutif

Notions générale sur les turbo codes et les codes TCM
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 3
Télécommunications
Codage correcteur d’erreurs
Plan du Partie II

Codes interconnectés: les turbo codes

TCM

Méthode adaptatives pour le contrôle d’erreurs
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
4
Codage correcteur d’erreurs
Chapitre 1
Prof. Dr. A. Berraissoul
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 5
Codage correcteur d’erreurs
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
6
Codage correcteur d’erreurs
1. Historique
2. Introduction et définitions
3. Définitions générales
4. Calcul de probabilité d’erreurs
5. Bits de parité
6. Distance Hamming
7. Représentation géométrique
8. Principe de détection et de correction
9. Théorème de Hamming
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 7
Notions générales
1.1. Historique
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
8
Notions générales
1.2 Introduction et définitions
1.2.1. Présentation de la chaîne de transmission

Dans un système de communication, on veut transmettre
l’information provenant d’un émetteur vers un récepteur, à travers
un canal de transmission. Ce dernier possède un certain nombre
de caractéristiques, notamment sa capacité, sa nature physique, et
le bruit qui va entacher l’information d’erreur.

Voici le schéma très général d’une liaison hertzien pour une
transmission numérique.
Perturbations: Bruit
Emetteur Récepteur
Canal continue
Canal discret Fig.1.1
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 9
Notions générales
Perturbations Information
Message
Source Destinataire
Fig.1.2

Source: Génération du message

Destinataire: Interprétation du message et acquisition
de Information, si:

Le message est interprétable

Le contenu de message n’est pas connu d’avance
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
10
Notions générales
Chaîne de transmission générale
Source Canal Modulateur
Source encoder encoder

Perturbations
Source numérique
Fig.1.3 canal
Source Canal Démodulateur
Destinataire decoder décoder
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 11
Notions générales
Exemple 1.1 : Chaîne de transmission Radio-Mobile
Fig.1.4
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
12
Notions générales
1.2.2. Description brève de la chaîne
◗ Source: Siège d’événement aléatoire qui constituent
le message émis naissance du message
 Description: Entropie
◗ Canal: Transmet et dégrade le message
 Description: Capacité
◗ Destinataire: Siège de naissance de l’information
 Description: Entropie
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 13
Notions générales
1.2.3. Les outils principaux de télécommunications
 Théorie des signaux: Description du message et perturbations.
 Modulations: Adaptation du signal au milieu de transmission.
 Electronique: Réalisation des fonctions.
 Théorie de l’information: Propose une mesure qualitative
de l’information et étudie sa représentation, sa transmission
et sa dégradation.
 Codage: optimisation et protection de l’information et du signal
portant de l’information.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
14
Notions générales
1.2.4. Bases mathématiques

La théorie du codage d’erreur s’appuie fortement sur certaine base
mathématique notamment les notions de structure algébrique des
ensembles finis:
 Groupes
 Corps ( corps de Galois )
 Espaces vectoriels
 Calculs matriciels
 Polynômes
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 15
Notions générales
1.3. Définitions générales
1.3.1. Codage du canal: Définition

Quelque soit la qualité des supports de communication et les
performances des techniques de transmission utilisées, des
perturbations vont se produire entraînant des erreurs sur les
données transmises.

Dans ces conditions, la suite binaire reçue ne sera pas identique à
la suite émise. Mise en œuvre de techniques de protection contre
les erreurs de transmission.

Transformer la séquence devant être transmise par le canal à
perturbations, dans une séquence plus longue, par appoint de
symboles supplémentaires destinés à réaliser, à la réception, une
opération de détection ou/et correction des erreurs; dans ce cas, on
dit qu’on fait le codage de canal (codage de protection).
Remarque:
 Le codage de la source, au contraire, transforme la séquence générée par
la source dans une séquence plus courte (optimisation!).
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
16
Notions générales
1.3.2. Types du Codage

Codage de la source: Réduction de la redondance

Le codage de source contient (s’il est bien spécifié) le nombre
minimal de symboles permettant la transcription de tous les
caractères possibles de la source.

Codage réversible (Hoffmann, Shano-Fanon, …)

Codage irréversible PCM, …

Codage du canal: Introduction de redondance

Le codage de contrôle d’erreur (ou codage de canal ou de
protection) va modifier le codage de source en apportant une
certaine redondance d’information.

Codage correcteur : Protection contre les erreurs par
l’introduction de redondance.

Codage de la ligne : Adaptation du signal portant de
l’information (Redondance physique).

Cette redondance permet de prévenir les erreurs de transmission
dues au bruit sur le canal, par détection et éventuellement
correction d’erreurs. ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 17
Notions générales
1.3.3. Stratégie de codage correction d’erreur:
A. Introduction

Selon la nature du canal, et d’une manière générale, selon les
considérations de coût, diverses stratégie peuvent être envisagées
pour la détection ou la correction des erreurs.
Types de stratégie de protection
Détecteur d’erreur
Codage Par retransmission
Correcteur d’erreur
Automatique
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
18
Notions générales
B. Détection des erreurs

Tout protocole de transmission doit protéger le destinataire de la
délivrance d’un message erroné. A cet effet, les protocoles mettent
en œuvre des mécanisme de détection d’erreur tel que le
destinataire puisse vérifier si les données reçues sont correctes. La
détection d’erreurs repose sur l’introduction d’une certaine
redondance* dans l’information transmise.

Quatre technique sont mises en œuvre pour détecter et corriger les
erreurs:

La détection par écho, le récepteur renvoie le message reçu, si
le message est différent de celui émis, l’émetteur retransmet le
message. Cette technique est utilisé dans les milieu asynchrone

La détection par répétition, chaque message émis est suivi de
sa réplique. Si les deux message sont différents, le récepteur
demande une retransmission. Cette technique est très utilisée
dans les milieux sécurisés et très perturbés.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 19
Notions générales

La détection par code, une information supplémentaire au niveau
du caractère (bit de parité) ou au niveau d’un groupe de
caractères (clé) est ajoutée à l’information transmise. Le récepteur
contrôle le bit de parité ou la clé, s’il détecte une erreur, il ignore
les données reçues et en demande la retransmission.

La détection et correction d’erreur par code, cette technique
consiste à substituer au code des caractères à transmettre, par
exemple le code ASCII, un autre codage qui autorise la détection
et l’autocorrection (code autocorrecteur)
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
20
Notions générales
Protection
Correction Détection
FEC
ARQ Forward Error Correction
Automatic Repeat Request
correction automatique
Retransmission avec Retransmission Retransmission avec
arrêt et attente continue répétition sélective
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 21
Notions générales
C. Principe général pour la détection des erreurs
de transmission

un émetteur veut transmettre un message (suite binaire
quelconque) à un récepteur,

l’émetteur transforme le message initial à l’aide d’un procédé de
calcul spécifique qui génère une certaine redondance des
informations au sein du message codé,

le récepteur vérifie à l’aide du même procédé de calcul que le
message reçu est bien le message envoyé grâce à ces
redondances,
 Par exemple la technique de détection par répétition

le message codé est un double exemplaire du message initial, le
récepteur sait qu’il y a eu erreur si les exemplaires ne sont pas
identiques
Note : certaines erreurs sont indétectables !
 ex. : une même erreur sur les deux exemplaires simultanément.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
22
Notions générales
D. Principe général pour la correction des erreurs
de transmission

Après détection d’une erreur, la redondance est suffisante pour
permettre de retrouver le message initial.
 Par exemple: la technique de correction par répétition.

Le message codé est un triple (message, détection, correction)
exemplaire du message initial, le récepteur suppose que le
message initial correspond aux deux exemplaires qui sont
identiques.
Note : certaines erreurs détectées ne sont pas corrigibles!
 ex. : une erreur différente sur au moins deux exemplaires
Note : Certaines erreurs sont détectées et mal corrigées!
 ex. : une même erreur sur deux exemplaires simultanément.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 23
Notions générales
E. Principe général pour la correction par retransmission
des erreurs de transmission *

Après détection d’une erreur, le récepteur demande à l’émetteur,
implicitement (temporisateur) ou explicitement de retransmettre une
nouvelle fois le message (codé).
 Par exemple: de très nombreux protocoles de télécommunication:
HDLC, X25, TCP, TP.
données à émettre données reçues
!
Récepteur
Emetteur

codage retransmission
(détection) (correction)
décodage
(erreur)

données codées transmission données transmises

Fig.1.5 ENSAJ
*Voir Codage correcteur II
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
24
Notions générales
F. Automatic Repeat Request ARQ

Codage du canal pour la détection d’erreur (CRC – Cyclic
Redundancy Check, utilisation pour ARQ-Méthode (Automatic
Repeat Request).
Codage
ARQ Canal Détection d’erreur ARQ
du canal
Information sur l’erreurs
Canal de retour
 Canal de retour obligatoire. Fig.1.6
 Introduction de la redondance adaptative.
 L’erreur résiduelle est indépendante de la qualité du canal.
 Débit le l’information dépend du canal.

Codage adaptatif (voir Partie II).
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 25
Notions générales

La correction par retransmission est préférée dans les réseaux où
le taux de perte est faible et le délai de retransmission tolérable, car
son surcoût est généralement plus faible que celui induit par les
codes auto correcteurs (voir Codage Correcteur II).

Estimation du surcoût (message de longueur moyenne = 1000 bits) :
 Par exemple: taux d’erreur typique = 10-9, taux de retransmission
 1000·10-9 = 10-6
 Par exemple: surcoût typique d’un code auto correcteur:
qq octets par message  8/1000 = 10-2
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
26
Notions générales
1.3.4. Théorème de Shannon

Les fondements de cette théorie furent développés par Claude
Shannon en 1948. Celui ci créa des outils de mesures
d’information, via des considérations probabilistes du message et
du canal de transmission.

Lorsque l’on conçoit une chaîne de communication numérique il est
naturel de se poser les questions suivantes :
Questions
1. peut-on transmettre une information sans erreurs sur
un canal bruité ?
2. si oui, est ce que cela implique que le rendement du codeur de
canal doit être nul ?*
3. sinon, y a t’il un rendement optimal, pour un niveau de bruit donné ?
* Voir très loin k/(k+r) ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 27
Notions générales
Réponses
1. Il existe une notion de capacité pour un canal, fonction du niveau de
bruit, i.e. de la loi du canal P(Y|X)
X Y
Canal bruité
P(Y|X)
Fig.1.7
Ct = max 2 B ⋅ I ( X ;Y ) 1.1
p( x )
2. Si l’on émet avec un code correcteur de rendement R > C, la
probabilité d’avoir des bits erronés au décodage reste strictement
positive.
3. Pour tout rendement R < C donné, on peut trouver un code de
rendement R et dont la probabilité d’erreur binaire est aussi proche
de 0 que l’on veut.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
28
Notions générales

Le rendement d’un code R = k/n mesure la proportion de bits utiles
transmis par utilisation du canal de transmission.
 Preuve “constructive” : on prend un code au hasard 2k mots de
n bits, avec k/n = R
 Résultat asymptotique : la longueur n du code doit tendre vers
l’infini
Problème : Ces codes ne sont décodables que par lecture de table...
(code-books géants)
Réponses apportées par Claude Shannon,
Publication en 1942.
Fondement de la théorie de l’information.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 29
Notions générales
1.3.5. Familles de codes correcteurs
A. Classification des codes

Objectif : structurer les codes, pour remplacer des code-books
géants par des algorithmes de codage et de décodage.

Essentiellement il y a deux grandes familles de codes :
 Les codes algébriques structurés (1948-1993)
1. Codes à bloc et les codes cycliques: Hamming, Reed Solomon,
BCH, Golay...: Le codage/décodage d’un bloc dépend uniquement
des informations de ce bloc.
2. Les codes en treillis (convolutifs, récursifs ou non): le
codage/décodage d’un bloc dépend des informations d’autres
blocs (généralement de blocs précédemment transmis). Il
s’applique sur une suite infinie de symboles et produit une suite
infinie.
 Les codes pseudo aléatoires (1993-2003)
1. Turbo Codes (1993)
2. LDPC (Low Density Parity Check Codes ) en 1963 ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
30
Notions générales
B. Correction automatique FEC: Forward Error Correction
Codes linéaires
Codes à bloc Codes cycliques Codes en arbre (Treillis)
Codes
Codes RS Codes
à parité simple
Convolutionnels
Codes Codes BCH
à parité croisé
Codes  Interleaving
de Hamming
 Concaténation
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 31
Notions générales
Les familles de codes (linéaires)
Codes sous forme
systématique
Codes
Codes Cycliques Convolutifs
(classiques)
BCH
Reed-Solomon
Modulations
codées
Turbo- Codes
Codes en blocs
(bits ou symboles : paquets de bits) Codes Convolutifs
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
32
Notions générales
C. Codes détecteur et ⁄ ou correcteur d’erreurs

Traitement de détection et ⁄ ou de correction par bloc de n bits
(n bits: mot)
 Les codes-Bloc sont ceux où le mot sont considérés comme
étant les éléments dans un espace vectoriel, à savoir des
vecteurs.
 Les codes cycliques sont ceux où les mots sont considérés
comme étant des élément dans une algèbre, à savoir des
polynômes.

Lorsque les symboles générés par la source ne sont pas traités par
des bloc mais d’une manière continue, on dit, qu’on an à faire avec
des codes convolutifs.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 33
Notions générales
D. Conclusion

Mécanismes de base de protection contre les erreurs :
- détection,
- autocorrection,
- retransmission

Amélioration de la fiabilité de la communication, mais (bien qu’avec
une faible probabilité) :
 certaines configurations d’erreur ne sont pas détectées !
 certaines configurations d’erreur ne peuvent pas être corrigées !
 certaines configurations d’erreur sont mal corrigées !!!

Ces mécanismes sont présents au sein de nombreuses couches
(protocoles), parmi lesquelles on peut citer :
 Liaison de données (ex. Ethernet, Token Ring, FDDI, HDLC, etc.)
 Réseau (p. ex. IP, etc. )
 Transport (p. ex. TP4, TCP, UDP, OFDM, TNT, GSM etc.)
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
34
Notions générales
1.4. Calcule de probabilité d’erreurs
1.4.1 Taux d’erreurs (BER: Bit Error Rate)
A. Erreurs isolées

Lorsque l’occurrence d’une erreur quelconque ne conditionne pas
celle des autres, on parle d’erreur isolée ⇒ probabilité
indépendante
B. Erreurs en paquet
110011110101101010 18 bits
110111011101101110 4 bits
Bits erronés
Paquet d’erreurs

Le message reçu diffère de 4 bits du message émis
4 1 0 −9 ≤ B E R ≤ 1 0 −4
BER = = 0, 2 2
18 FO RTC
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 35
Notions générales
1.4.2. Probabilité d’erreurs
 Canal AWGN  ε erreurs parmi n bits ⇒ P(ε ,n)
→ Pe : Probabilité d’erreurs
→ 1 − P Probabilité de la réception d’un bit sans erreur
e:
→ P ( ε = 0 ) = (1 − Pe ) ⋅ (1 − Pe ) ⋯ (1 − Pe ) = (1 − Pe )
n
: Probabilité de la réception de n bits sans erreur.
→ P (ε = 1) = Pe (1 − Pe ) n −1 :
: Probabilité de recevoir un mot avec une erreur dans
une position donnée.
→ Pe (ε = 1) = n ⋅ Pe (1 − Pe ) n −1
: 1 bit erroné dans n positions possibles dans un mot
 n
→ Pe (ε ) =   ⋅ Peε (1 − Pe ) n −ε
ε 
: ε bits erronés dans n positions possibles dans un mot ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
36
Notions générales
A. Configuration d’un mot avec n bits et ε erreurs:
n
P ( ε , n ) =   ⋅ P eε ⋅ (1 − P e ) n − ε
ε  1.2
n n!
  = ε = 0 , 1, 2 , . . . , n
ε  ε ! ( n − ε )!

Le système de protection contre les erreurs ne peut pas éliminer
toutes les erreurs.
Notion de taux d’erreurs résiduelles TER = PR
n n
PR = ∑
ε = E +1
P (n, ε ) = 1 − ∑ P ( n, ε )
ε =0
1.3
E : valeur maximale d’erreurs corrigible !
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 37
Notions générales
E
 n
Pcorrect ∑
=   ⋅ Peε ⋅ (1 − Pe ) n−ε
ε =0  ε 
1.4
E : Nombre maximale corrigeable
Perr = 1 − Pcorrect 1.5
Exemple 1.2
Transmission de 4 bits P = 0,01
Sans codage : Pcorrect = (1 − P ) 4 = 0, 961
PR = Perr = 1 − Pcorrect = 0, 039
Avec codage!! :
Pcor = (1 − P )8 + 8 P (1 − P )7 = 0,9973
PR = Perr = 1 − Pcor = 0, 0027
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
38
Notions générales

Si Pe est la probabilité pour qu’un bit soit erroné, la probabilité de
recevoir un bit correct est de (1- Pe), pour qu’un bloc de n bits soit
reçu correctement la probabilité est de (1- Pe)n.

Supposons une transmission de 100 caractères émis sur une
liaison en mode synchrone 4800 bit/s avec un taux d’erreur
BER = 10-4. Les erreurs sont supposées être distribuées
aléatoirement. Déterminons la probabilité pour qu’un message reçu
soit erroné :
2 n −1 < N ≤ 2 n ⇒ 28−1 < 130 ≤ 28

Le message de 100 caractères correspond à un bloc de
n = 8 → 130 × 8 = 1040 bits

La probabilité de réception d’un bloc correct Pcorr est de:
Pcorr = (1 − 0, 0001)1040 = (0,9999)1040 = 0,90

Soit la probabilité de recevoir un message erroné:
Pe = (1 − 0,90) = 0,1
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 39
Notions générales
Exemple 1.3
PR = 10 − 10
i
(Données) pour un débit de D = 9, 6 kbit / sec
Une erreur chaque 30 heurs
PR = 10 − 6 Pour le même débit
Une erreur chaque deux minutes
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
40
Notions générales
1.5. Bits de parité
1.5.1. Code à parité simple

Dans cet exemple, la redondance d’information est faible, on
introduit un bit supplémentaire tel que le nombre des bits, à un, à
transmettre soit pair (bit de parité) ou impaire (bit d’imparité).
Compte tenu de la faible redondance introduite, le contrôle ne porte
que sur un caractère.
Contrôle Information utile
Position 8 7 6 5 4 3 2 1
Bit 1 0 1 0 0 1 1 0
 1 1 1 1: Nombre paire des un. L’erreur peut être détectée mais pas
corrigée
 1 0 1 1 1 1 1 0 : Deux erreurs : nombre paire des un!
Examen de ou exclusif: Cette méthode est incapable de
détecter un nombre paire d'erreurs ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 41
Notions générales
1.5.2. Bits de parité croisée
0 0 0 0
Mots de code
à transmettre
0 1 1 0 Bits de contrôle
de parité verticale
1 0 1 0
1 1 1 1
0 0 1 1
Bit global
Bit de contrôle
de parité horizontale
Ce procédé permet de détecter deux erreurs
ou bien d'en corriger une
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
42
Notions générales
1.5.3. Code à parité entrelacée
 Extension bidimensionnelle des codes à parité simple
 Parité verticale et horizontale sont identiques  Pas d’erreur
◗ Ce procédé permet de détecter deux erreurs ou bien
d’en corriger une
Correction d’une erreur
A. Aucune erreur B. Une seule erreur
1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0
0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0
0 1 1 1 1 0 0 0 0 1 0 1 1 0 0 1
1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0
0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0
0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 43
Notions générales
A. Aucune erreur:

Toutes les lignes et les colonnes conservent un poids pair
1 0 0 1 1 1 0 0
0 1 0 0 1 0 0 0
0 1 1 1 1 0 0 0
1 0 1 0 1 1 0 0
0 0 1 1 0 1 1 0
0 0 1 1 0 1 1 0
0 0 0 0 0 0 0
 Les contrôles verticales et horizontale constatent la parité
dans les deux sens par zéros partout
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
44
Notions générales
B. Une seule erreur:

La parité est perturbée dans la ligne et dans la colonne où se
trouve le bit erroné
1 0 0 1 1 1 0 0
0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 1
1 0 1 0 1 1 0 0
0 0 1 1 0 1 1 0
0 0 1 1 0 1 1 0
0 0 1 0 0 0 0
 Les contrôles « désignent du doigt » l’endroit par les 1
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 45
Notions générales
C. Deux erreur dans les lignes et colonnes différentes
1 0 0 1 1 1 0 0
0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 1
0 ?, 0 ? 1 0 0 1 1 0 0
1
1 0 1 0 1 1 1
1
1 ?, 1 ? 0 0 1 0 1 1 0
1
1 0 0 0 0 0
1
Aucun moyen pour déterminer quels sont les deux bits
erronés parmi les quatre ainsi désignés !!
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
46
Notions générales
D. Deux erreurs dans une même ligne
1 0 0 1 1 1 0 0
0 1 0 0 1 0 0 0
0 1 1 1 1 0 0 0
1 0 1 0 1 1 0 0
0 0 1 1 0 1 1 0
1 0 0 1 0 1 1 0 ?
1 0 1 0 0 0 0
 La parité est perturbée dans deux colonnes, mais les
deux sur la même ligne ne peuvent pas être signalisées, on
ne sait pas donc dans quelle ligne se trouve l’erreur.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 47
Notions générales
1.5.4. Taux de codage
k : taille du mot d’information avant codage
n : taille du mot–code après codage
r : nombre de symboles de contrôle
n=k+r 1.6

Le taux de codage est définie par la relation suivante:
k
R= 1.7
n
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
48
Notions générales
1.6. Distance de Hamming
1.6.1. Définition

La distance de Hamming dmin : c’est le nombre minimum de
symboles différents entre deux séquence ou vecteurs.

Dans l’exemple suivant: La distance de Hamming (dmin = 3),
puisque il y a trois colonnes où les bits sont différents.
u : 1 0 1 0 1 0 1 0
v : 1 0 0 0 1 1 1 1
n
d ( u, v ) = ∑ (u j ⊕ v j ) 1.8
j =1
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 49
Notions générales

Le poids de Hamming w : est le nombre des symboles non nuls que
le mot contient.
w ( u ) = P (1 0 1 0 1 0 1 0 ) → w ( u ) = 4
w ( v ) = P (1 0 0 0 1 1 1 1) → w ( v ) = 5

La distance de Hamming entre deux mots est donc le poids de
leur somme.
d ( u, v ) = P ( u ⊕ v ) 1.9
Exemple 1.4
d (10101010,10001111) = w(10101010 ⊕ 10001111) = w(00100101) = 3
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
50
Notions générales
1.7. Représentation Géométrique et distance minimale
1.7.1. Présentation
0 0 0
110 111
0 0 1
0 0 y
0 1 0
01 11 010 101
0 1 0 1 1
100 011
1 0 0 z
1 0 y
1 0 1
1 1
1 1 0 x
000 001
1 1 1
x y 00 10 x
Fig.1.8 a Fig.1.8b
x y z
La distance minimale de Hamming entre deux mots correspond à la
longueur de chemin le plus court sur le hyper-cube de Boole entre
les sommets représentant les deux mots ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 51
Notions générales
1.7.2. Représentation hypercube
011 111
011 111
001 101
001 101
010 110
010 110
011 111 000 100
000 100
(b)
(a) 001 101
010 110
Fig.1.9 a,b,c
000 100
(c) ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
52
Notions générales
1.7.3. Exemples sur la distance minimale dmin

On suppose qu’on a une seule erreur pendant la transmission
dmin = 1
Mots Code
Emission Réception Correction
?
011 111 ?
101 111 ?
111 111 ?
110 111 ?
000 000 ?
100 000 ? dmin= 1
010 000 ?
100 000 ? Fig.1.10
dmin = 1 détection et correction impossible
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 53
Notions générales
1.8. Principe de détection et de correction d’erreurs
1.8.1. Détection d’erreurs SED: Single Error Detection
Information k Mot-code n
0 0 0 0 0
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
dmin= 2 dmin= 2 Fig.1.11
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
54
Notions générales
Exemple 1.5
 2² = 4 mots d’information
 23 = 8 mots-code
 Par exemple: 000, 011, 101, 110: parité paire

SED: Single Error Detection

Détection des parités impaires:
001, 010, 100, 111 dmin = 2
Emission Réception
Fig.1.12
101 100

Le mot erroné peut être venir d’un autre mot envoyé par exemple:
Emission Réception
110 100

Il y a une erreur, mais on peut pas identifier le mot-code erroné et
corriger! ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 55
Notions générales
1.8.2. Correction d’une erreur SEC: Single Error Correction
Maximum de vrais semblant
dmin = 3
Mots Code
Emission Réception Correction
011 111
111 101 111
110 111
001 000
000 100 000
010 000
dmin = 3 Fig.1.13

Condition c’est l’apparition d’une seule erreur pendant la
transmission !
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
56
Notions générales
1.8.3. Visualisation des propriétés de distance
par le Hyper-cube de Boole
dmin = 1 dmin = 2 dmin = 3
 Taux de codage =1  Taux de codage = 2⁄⁄ 3  Taux de codage = 1⁄⁄ 3
 Aucune erreur à détecter  Une erreur à détecter  Deux erreur à détecter
 Aucune erreur à corriger  Aucune erreur à corriger  Une erreur à corriger
Fig.1.14 a,b,c
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 57
Notions générales
1.9. Théorème de Hamming
1.9.1. Correction d’erreur par le principe de maximum
de vraisemblance
A. Probabilité d’apparition d’erreurs
Pe : Probabilité d’un bit erroné
Pe ≤ 1
(1 − Pe ) n > Pe (1 − Pe ) n −1 > Pe 2 (1 − Pe ) n − 2 > ⋯ > Pe a (1 − Pe ) n − a
Pas d’erreur Une erreur Deux erreurs
en n bits
. . . a erreurs
en n bits
en n bits
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
58
Notions générales
Il est donc raisonnable d’accepter que le mot-code erroné est
une déformation du mot code le plus proche
(au sens de Hamming).
C’est le principe de
décodage selon
Le principe de maximum de vraisemblance *

À la lumière de ces exemples, on peut prouver que pour
la détection de t’ erreurs, la distance dmin doit être
d min = t ′ + 1 1.10

Pour la correction de t erreurs la distance dmin doit être
 d min = 2 t + 1 pour d min impaire
 1.11
 d min = 2 t + 2 pour d min paire
Théorème de
Hamming
* Voir cours de traitement du signal avancé ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 59
Notions générales
B. Définitions

Le poids de Hamming d’un mot est le nombre de bits à 1 qu’il
contient. La distance de Hamming entre deux mots de même
longueur est définie par le nombre de positions binaires qui diffèrent
entre ces deux mots. On l’obtient par le poids de Hamming de la
somme binaire des 2 mots. La distance de Hamming d’un code est
la distance minimum entre tous les mots du code.
Exemple 1.6 ◗ Poids de Hamming (01001100) = 3
◗ Distance de Hamming (01001100, 01010101) = 3

La capacité de détection (de correction) d’un code est définie par
les configurations erronées qu’il est capable de détecter (corriger).
Une erreur simple (resp. double, ou d’ordre p) affecte une seule
(resp. 2, ou p) position(s) binaire(s) d’un mot. Pour qu’un code ait
une capacité de détection (resp. correction) des erreurs d’ordre t, il
faut que sa distance de Hamming soit supérieure à (1 + t)
(resp. (1 + 2t))
Exemple 1.7

Distance = 3  capacité de détection ≤ 2, capacité de correction ≤ 1.
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
60
Notions générales
C. Boucles de correction

Remarquons que sur l'hyper cube de Boole, le sommet
représentant un mot-code, ou le même mot-code avec un bit erroné
se trouve dans un "boule" de rayon 1 centré sur le sommet du mot-
code. De même, le sommet figurant un mot-code avec au plus t
erreurs se trouvera dans une boule de rayon t.
t =1 t =1
mot-code 1 mot-code 2
000 001 011 111
d min = 3
boule de correction 1 boule de correction 2
Fig.1.15
Correction d'une erreur t =1
d min = 2t +1 = 3
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 61
Notions générales

Lorsque la distance entre les mots-codes est grande, à l'exception
de la distance entre deux mots-code qui est petite, il est évident
que cette dernière distance limite le nombre d'erreurs détectables
ou corrigeables car les propriétés de détection et de correction
doivent être assurées pour toutes les configurations de t erreurs
possibles.
t t
mot-code 1 mot-code 2
5 4 3 2 1
1 2 3 4 5
d min = 5
boule de correction 1 boule de correction 2
Fig.1.16
Correction de deux erreurs t =2
dmin= 2t+1 = 5
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
62
Notions générales

Pour la correction de t erreurs et la détection de t' > t erreurs, la
distance minimale de Hamming doit être :
d min = t ′ + t + 1 1.12

On peut généraliser ces notions, on obtient ainsi le théorème de
Hamming:
L'efficacité du code de contrôle d'erreur croît avec la distance d.
Si l'on formalisme ce résultat, un code correcteur d'erreur, pour
corriger n'importe quel groupe de t erreurs dans une séquence de
longueur donnée, à condition que :
d min ≥ 2 t + 1 pour d min impaire
 1.13
d min ≥ 2 t + 2 pour d min paire

Pour un code détecteur d'erreur, on a : d min ≥ t ′ + 1
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 63
Notions générales
D. Propriétés
Nombre des Nombre des
dmin Propriétés erreurs détectées SED erreurs corrigées SEC
1 Nul 0 0
2 SED 1 0
3 SED ou SEC 2 1
4 SED et SEC 2 1
5 SED ou SEC 1,2,3 ou 4 2
6 SED et SEC 3 2
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
64
Notions générales
Exemple 1.8
dmin = 4
t t
mot-code 1 mot-code 2
d min= 4
boule de correction1 boule de correction 2
Fig.1.17
Correction d'une erreur t = 1 et Détection de deux erreurs t' =2
d min = t ′ + t + 1
Correction d'une erreur t = 1 ou Détection de trois erreurs t' = 3
d min = 2t + 2 d min = t ′ + 1
Même distance de mot-code 1 et 2
Décision aléatoire ! ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 65
Notions générales
Exemple 1.9
dmin = 5
t t
Mot-code 2 Mot-code 1
dmin = 5
boule de correction 1 Fig.1.18 boule de correction 2
Correction de deux erreurs t = 2
ou
Détection de quatre erreurs t' = 4
d min = 2t + 1
d m in = t ′ + t + 1 ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
66
Notions générales
Exemple 1.10
dmin = 6
t t
mot-code 1 mot-code 2
3SED 2SEC
dmin =6
boule de correction 1 boule de correction 3
Fig.1.19
t=1 t=2
et Ou et
t' = 4 t' = 3
d min = 2t + 2 d m in = t ′ + t + 1
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 67
Notions générales
E. Relation entre r et n

Pour la correction d'une seule erreur pour un code de longueur n et
de r bits de contrôle, le nombre des correcteurs 2r (*) doit être égal
à n + 1 ou même plus grand, afin de pouvoir indiquer une erreur
dans un des n symboles du mot réceptionné ou pour indiquer qu'il
n'y a pas d'erreur. Donc:
2 r
≥ 1 + n

Au moins 2r combinaisons pour indiquer la position non erronées
et les positions erronées (k → 2k mots d’information n→2k+r !)
 Ce que nous pouvons présenter dans le tableaux suivant:
r n k
1 1 0
r = n−k 2 3 1
3 7 4
4 15 11 2r ≥ 1 + r + k
r = lb(1 + n) 1.14
(*) voir très loin (syndrome!) ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
68
Notions générales
Remarques:

Nous savon bien que pour corriger une erreur il faut que la distance
minimale du code soit au moins de trois. Mais une condition
analogue sur les paramètres du codes peut rendre des services
intéressantes.

Dans le cas où, lors de la transmission, nous sommes sûrs de ne
pas trouver plus d’une erreur , l’erreur unique peut alternée chacun
des n bits du mots du code, ou le laisser invariant, lorsqu’il n’y a
pas d’erreurs. Cela nous donne n + 1 situations différentes
possibles.

Le vecteur syndrome (voir très loin) ayant r bits, il peut exister 2r
syndromes différents, y compris le syndrome nul (lequel désigne le
cas sans erreur). Ces 2r syndromes doivent pouvoir désigner
chacune des n + 1 situations mentionnées plus haut. On a donc
2r ≥ 1+ n
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 69
Notions générales

Pour la correction de deux erreurs (c'est-à-dire dmin = 5), pour un
code de longueur n, il y les possibilités suivantes :
1. Pas d'erreur
2. n possibilité pour un bit erroné
3.
n
  possibilités pour deux bits erronés
2

Ce qui donne la relation suivante
 n
2r ≥ 1 + n +   1.15
2

Pour la correction de t erreurs on a donc:
 n  n  n
2r ≥ 1 + n +   +   + ⋯ +   1.16
2 3 t 
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
70
Notions générales
Exemple 1.11
n = 20 ; t = 3; k?
 20   20   20   20 
r ≥ lb   + lb   + lb   + lb   = 10,4
0  1  2  3 
r ≥ 10,4 ⇒ r = 11
k = n − r ⇒ k = 2 0 − 11 = 9

Nombre des mots de l’information 29 = 512
d min = 2 t + 1 = 7 pour d min impaire
d min = 2 t + 2 = 8 pour d min paire
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications
 71
Notions générales
ENSAJ
Département
[Link] Cours T7: Codage correcteur, Chapitre 1 de Télécommunications