View
214
Download
0
Category
Preview:
Citation preview
1Cours n°10
UV_TI
AlexandrinaROGOZAN
UV Théorie de l’ Information
Cours n° 10 :
Codage de canal� Techniques courantes en codage de canal
− Codes en blocs
− Codes convolutifs
2Cours n°10
UV_TI
AlexandrinaROGOZAN
Techniques courantes en codage de canal� Classification :
⇒ Codes détecteurs d’erreurs permettant au destinataire seul ement de ne pas t eni r compt e du symbol e r eçu
• Remarque : Si le canal est bidirectionnel, le destinataire a la possibilité de demander la répétition du dernier symbole reçu.
⇒ Codes correcteurs d’erreurs permettant non−seul ement l a dét ect i on, mai s aussi l a cor r ect i on des er r eur s
� Évaluation des capacités de détection et correction des codes binaires : Di st ance mi ni mal e de Hammi ng
3Cours n°10
UV_TI
AlexandrinaROGOZAN
Classification des codes détecteurs et correcteurs d’erreurs
� Codes en blocs : traitements effectués par blocs de n symboles (appel és aussi mot s−code de l ongueur n)
⇒ Codes−groupes : mots−code considérés comme des éléments dans un espace vectoriel, à savoir des vecteurs
⇒ Codes cycliques : mots−code considérés comme des éléments dans une algèbre, à savoir des polynômes
� Codes convolutifs : traitements effectués de manière continue, c’est à dire un signe après un autre
4Cours n°10
UV_TI
AlexandrinaROGOZAN
Codes−groupes
� Codes q−aires : mots−code considérés comme des éléments d’un corps à q éléments
Codes binaire : mots−code considérés comme des éléments du corps de Galois à 2 éléments notés (0, 1).
⇒ Remarque : Les opérations d’addition et de soustraction étant identiques dans le cas d’un corps à 2 éléments, elles seront notées par le même symbole +
+ 0 10 0 11 1 0
* 0 10 0 01 0 1
Addition modulo 2 Multiplication
5Cours n°10
UV_TI
AlexandrinaROGOZAN
Codes−groupes binaires� Supposons un codeur de source qui émet à une cadence
d’émission
⇒ Le codeur de canal associe à chaque bloc de k bits, un nouveau bloc de n bits (n>k) contenant n−k bits de redondance
⇒ Le modulateur module une porteuse à partir du signal codé binaire
⇒Remarque : t emps r éel => t r ansmi ssi on des n bi t s pendant l e même i nt er val l e de t emps ∆T ( qu’ aupar avant l es k bi t s)
DS bits�s
Codeur de canal
ModulateurCodeur de source
DS bits�s DC bits
�s � DS
n
k
6Cours n°10
UV_TI
AlexandrinaROGOZAN
Codes−groupes binaires� Soit C(n,k) un code ayant une longueur de bloc n
dont k bits d’ information :
⇒ Ensemble de Mots−code : constitué de blocs de n bits, blocs issus du codeur de canal
⇒ Rendement du codage = k/n� Réalisation du codage/décodage à l’aide d’additions et
de multiplications sur des éléments binaires (OU et ET excl usi f )
⇒ Exemple : 1 bit de contrôle de parité correspondant à un OU exclusif sur l’ensemble des k bits
2k
7Cours n°10
UV_TI
AlexandrinaROGOZAN
Codes−groupes binaires� Soit C(n,k) un code ayant une longueur de bloc n
dont k bits d’ information : ⇒ Code linéaire : si les n−k bits de contrôle sont déterminés
par des sommes modulo 2 sur les k bits d’ information
⇒ Code systématique : si les n−k bits de contrôle ainsi obtenus sont rangés à la suite de k bits d’ information
• Exemple : Code de Hamming pour n=7 et k=4Symbole Codé binaire Bits de contrôle Décimal d1 d2 d3 d4 p1 p2 p3
0 0 0 0 0 0 0 01 0 0 0 1 1 1 12 0 0 1 0 0 1 1... ... ...15 1 1 1 1 1 1 1
p1 � d1 � d2 � d4
p2 � d1 � d3 � d4
p3 � d2 � d3 � d4
8Cours n°10
UV_TI
AlexandrinaROGOZAN
Matrice génératrice du codage
� Soit Gij (à k l i gnes et à n col onnes ), la matrice
génératrice d’un code C(n,k)
� Soit un bloc de k bits d’ information
⇒le mot−code associé est obtenu au moyen d’une relation matricielle :
m� m0 ,m1 , ...mk � 1
c � c0 ,c1 , ...cn � 1
c � mG
9Cours n°10
UV_TI
AlexandrinaROGOZAN
Matrice génératrice du codage
� La matrice génératrice d’un code linéaire n’étant pas unique, elle peut être écrite sous la forme : , où I
k est l a mat r i ce i dent i t é et P une mat r i ce de
di mensi on k* ( n−k)
� Cette matrice génératrice G engendre des mots−code de la forme : ; l es k bi t s d’ i nf or mat i on
et l es n−k bi t s de r edondance ét ant ai nsi sépar és
=> code systématique
G � I k ,P
c � m,mP
10Cours n°10
UV_TI
AlexandrinaROGOZAN
Matrice de contrôle de parité
� La matrice de contrôle de parité H d’un code linéaire, satisfait la relation matricielle :
� Cette matrice (à n−k l i gnes et à n col onnes) est donnée par : , où I
k est l a mat r i ce
i dent i t é et P une mat r i ce de di mensi on k* ( n−k)
� Tout mot−code c est orthogonal aux lignes de la matrice de parité H ( )
⇒ H permet de détecter si un message reçu r est un mot−code
GHT � 0
H � PT , I n � k
cHT � mGHT � 0
11Cours n°10
UV_TI
AlexandrinaROGOZAN
Détection et correction des erreurs� Supposons c le mot−code émis et r le vecteur reçu,
alors la règle de décodage doit tester :
⇒ si r est un mot−code et le cas échéant (r≠c) corriger les erreurs
� Le vecteur reçu r peut s’écrire sous la forme : où une composante du mot−erreur e égale à 1 indique la présence d’une erreur de transmission (sur l a posi t i on
cor r espondant e du mot −code c).⇒ Remarque : il faudrait que pour chaque mot −er r eur e
pouvant être généré par les perturbations du canal, i l y ai t un seul cor r ect eur di st i nct et ≠ 0
r � c � e
Canal
e
c r
12Cours n°10
UV_TI
AlexandrinaROGOZAN
Classification des erreurs
� Erreurs individuelles : apparaissant indépendamment les unes des autres (sous l ’ hypot hèse que chaque si gne t r ansmi s est per t ur bé de mani èr e i ndépendant e) comme suite à l’action des bruits de fluctuation
� Paquets d’erreurs : succession de signes (cor r ect s ou er r onés) dans laquelle le 1er et le dernier signes sont erronés comme suite à des perturbations (d’ impulsions ou des interruptions) dont la durée dépasse celle d’un signe
• Remarque : les signes corrects successifs apparaissent en groupes plus petits qu’un paramètre dépendant de la statistique du canal
13Cours n°10
UV_TI
AlexandrinaROGOZAN
Détection des erreurs
� Soit s le syndrome du mot−code reçu r
⇒ Si s ≠0 alors r n’est pas un mot−code (i l y a eu donc des er r eur s de t r ansmi ssi on)
� Remarque : Un syndrome nul ne signifie pas nécessairement une absence d’erreur.
⇒ Ex : transformation du mot−code émis c en un autre mot−code c’
s� rHT � c � e HT � eHT
14Cours n°10
UV_TI
AlexandrinaROGOZAN
Distance de Hamming
� Entre 2 vecteurs binaires u et v ( = nombr e de bi t s di f f ér ent s) :
⇒ ,
Où est le poids de leur vecteur somme � Poids d’un mot−code c ( = nombr e de bi t s
non−nul s)
⇒ ,
• C’est à dire la distance de Hamming entre ce mot et le vecteur nul
dH u,v PH u v
PH c PH c,VecteurNul dH c,VecteurNul
dH u,v
PH u v
PH c
15Cours n°10
UV_TI
AlexandrinaROGOZAN
Distance de Hamming et correction d’erreurs
� Règle de décodage en présence d’erreurs de transmission (syndr ome s non−nul ) :
⇒ Rechercher le mot−code le plus vraisemblable au mot−code reçu r :
• , pour l equel l a di st ance de Hammi ng est mi ni mal e
⇒ Remarque : mise en oeuvre difficile lorsque le nombre de mots−code (2k) est important
dH r, �c � PH r,c pour c ��c�c
16Cours n°10
UV_TI
AlexandrinaROGOZAN
Distance de Hamming et correction d’erreurs
� Règle de décodage en présence d’erreurs de transmission (syndr ome s non−nul ) :
⇒ Plusieurs configurations du mot−erreur e pouvant conduire à une même valeur du syndrome s (pui sque i l y a 2n−1 conf i gur at i on d’ er r eur et seul ement 2n−k
conf i gur at i ons du syndr ome)
⇒ Rechercher la configuration du vecteur d’erreur e de poids minimal, en terme de distance de Hamming, puis calculer
� Remarque : mise en oeuvre difficile lorsque le nombre de bits de redondance n−k excède seulement quelques unité
�c r � e modulo2
17Cours n°10
UV_TI
AlexandrinaROGOZAN
Pouvoir de détection et de correction
� Distance minimale de Hamming du code (= l a pl us pet i t e di st ance ent r e 2 mot s−code), c’est à dire le poids minimal des mots−code excluant le vecteur nul
� Pour détecter i erreurs pouvant intervenir dans une position quelconque du mot−code =>
� Pour corriger i erreurs pouvant intervenir dans une position quelconque du mot−code =>
� Pour corriger i erreurs et détecter d erreurs =>
dmin
dmin i 1
dmin 2 � i 1
dmin 2 � i 1 d
18Cours n°10
UV_TI
AlexandrinaROGOZAN
Choix d’un code binaire correcteur d’erreur� Code correcteur pour une erreur unique :
⇒ k premières colonnes de H doivent être différentes entre elles et différentes d’une colonne de la matrice unité et d’une colonne ne comprenant que des zéros.
⇒ n−k bits de redondance peuvent être rangés selon 2n−k possibilités
� Code correcteur pour Nc erreurs :
2n � k � n � k 1 � k � 2n � k � n 1
2n � k � �i � 0
i � Nc
C ni
19Cours n°10
UV_TI
AlexandrinaROGOZAN
Code−groupe binaire de parité� 1 seul bit de redondance par mot−code déterminé pour obtenir :
• , où les mi désignent les n bits du mot−code
� => détection d’une erreur isolée (ou un nombr e i mpai r e d’ er r eur ) par bloc ; pas de possibilité de correction
⇒ Règle de décodage : calcul de la somme des n bits du mot reçu ; si cette somme est paire il n’y a pas d’erreurs
•
�i � 0
i � n � 1
mi modulo2
dmin 2
G n � 1 � n �1 0 0 ... 0 10 1 0 ... 0 1... ... ... ... ... ...0 ... ... 0 1 1
H 1, n � 11...1
20Cours n°10
UV_TI
AlexandrinaROGOZAN
Code−groupe binaire à répétition� 1 seul bit d’ information les autre étant une répétition de celui−ci
� (longueur du mot−code) => détection de n−1 erreurs ; ou correction de (n−1)/2 erreurs
•
•
⇒ Règle de décodage : si le nombre de 1 dans le mot reçu est supérieur au nombre de 0 => le bit d’ information émis est 1 ; sinon le bit d’ information émis est 0
•
dmin n
H n � 1 � n �1 1 0 0 ... 0 01 0 1 0 ... 0 0... ... ... ... ... ... ...1 0 0 0 ... 0 1
G 1 � n � 11...1
21Cours n°10
UV_TI
AlexandrinaROGOZAN
Code−groupe binaire de Hamming
� 1a longueur n du mot−code et le nombre de bits d’ information k sont de la forme :
� => détection de 2 erreurs ou correction de 1 erreur
� Colonnes de la matrice de parité H = représentations binaires (sur n−k bits) des nombres de 1 à n
⇒ Règle de décodage : En présence d’une erreur, le syndrome prend la valeur de la colonne de la matrice de contrôle de parité H correspondant au rang de l’erreur => la position de l’erreur (que l ’ on peut ensui t e cor r i ger )
n � 2m 1et k � 2m m 1
dmin 3
!m"$#
22Cours n°10
UV_TI
AlexandrinaROGOZAN
Code binaire cyclique BCH
� Généralisation du code de Hamming (t>1) pour la correction d’erreurs multiples par bloc
� Fondé sur l’algèbre des corps de Galois
� les paramètres n , k et dmin
sont de la forme :
⇒ Mise en oeuvre : Facile à l’aide des registres de décalage et d’opérations logiques combinatoires
•
n � 2m 1,k � 2m m 1et dmin % 2 & t ' 1
!m,t "$#
23Cours n°10
UV_TI
AlexandrinaROGOZAN
Code q−aire de Reed−Solomon� Adapté à la correction de salves d’erreurs (er r eur s gr oupés)
⇒ Utilisé en code externe dans les codes concaténés pour corriger les paquets d’erreurs en sortie du décodeur interne
� Les paramètres n , k et dmin
sont de la forme :
• , où t = capacité de correction du code en nombre de signes q−aires
⇒ Remarque : Capacité de correction ≤ (n−k)* t [bits]
⇒ Ex : Un code à t =2 [ si gnes quat er nai r es] peut cor r i ger 8 bi t s er r onés , ssi ces bi t s sont bi en l ocal i sés sur 2 si gnes consécut i f s, ou un paquet de 4 bi t s consécut i f s dans un même mot −code
•
n � q 1,k � n 2 & t et dmin � 2 & t ' 1
Recommended