0% ont trouvé ce document utile (0 vote)
11 vues4 pagesCodage 002
Transféré par
Chaima BelhediCopyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
0% ont trouvé ce document utile (0 vote)
11 vues4 pagesCodage 002
Transféré par
Chaima BelhediCopyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
Deux vecteurs x = (X9...%j---%,-1) €t ¥=(No---Jj---Ynet) Sont orthogonaux (noté xLy)
si leur produit scalaire noté (x.y) = xy” est nul :
eh
xly © wy" = Yixpi=0 Qa
=
A chaque code en blocs linéaire C(n,k) on peut associer un code en blocs linéaire dual.
Tout mot du code dual est orthogonal a tout mot du code C(n,k). Le dual du code
C(n,k) est done un sous-espace vectoriel de Fy, de dimension (n—k) constitué de 2”~#
mots de n éléments binaires. Ainsi tout mot ¢ du code C(n,k) est orthogonal aux lignes
de 1a matrice génératrice H de son code dual :
cH” =0 (2.2)
Un vecteur y appartenant & FJ est donc un mot du code C(n,k) si, et seulement si, il est
orthogonal aux mots de son code dual c'est-2-cire si:
yHT=0 (2.3)
Le décodeur d'un code C(n,k) va done pouvoir utiliser la matrice génératrice H de son
code dual pour détecter la présence des erreurs de transmission. La matrice H est appelée
la matrice de contréle de parité du code C(n,k). .
Ce principe de détection des erreurs de transmission est illustré sur la figure II-1 o} les
mots d'un code en blocs linéaire C(3,2) et de son code dual C(3,1) appartiennent
respectivement au plan xoy et & la droite oz. Un vecteur y est un mot du code C(3;2) si et
seulement si sa projection sur l'axe oz est nulle.
CG.)
Projection de y
sur Taxe 0
Figure Il-1 Principe de ta détection des erreurs de transmission
En adoptant une représentation systématique du code C(n,k), il est alors facile de
déterminer la matrice génératrice H de son code dual. En effet, en tenant compte du fait
que ¢=mG, nous obtenons :
GHT =0 (2.4) En utilisant Texpression réduite (1.7) de la matrice G :
6= [1,2]
Ja résolution de l'équation matricielle (2.4) conduit @ une matrice H de la forme :
H=[P"1,-¢] (2.5)
Avant d'aborder le principe de la détection puis de la correction des erreurs de
transmission, considérons un exemple de code en blocs linéaire.
Exemple
Soit un code en blocs linéaire systématique C(7,3) ayant pour matrice génératrice :
1001101
G=|/0100111
0011110
Sa matrice de controle de parité est égale a:
1011000
1110100
“loi10010
1100001
etau bloc de & = 3 éléments binaires d'information m=[1 0 1}, il associe le mot
e=mG=[1 0 1 0 0 1 I}Le schéma de principe du codeur est représenté
sut la figure II-2, il utilise des opérateurs logiques "OU exclusif”.
mo
ia
os
Le a
* Figure 11-2 Schéma de principe d'un codeur linéaire en blocs C(7,3)
26 IL.3. Principe de la détection et de la correction des erreurs
Dans ce paragraphe, nous allons considérer que le canal de transmission est du type
binaire symétrique et que le décodeur fonctionne & partir de décisions fermes, en
synchronisme parfait avec le codeur. Cela signifie que le découpage en mots de n
41éments binaires & entrée du décodeur correspond 2 celui utilisé par le codeur. Ainsi, en
absence d'grreurs de transmission, le décodeur voit & son entrée des mots du code. Ce
probléme de la synchronisation entre le codeur et le décodeur est d'une grande importance
pratique. Il est généralement traité en émettant périodiquement un mot spécifique (mot de
synchronisation) & partir duquel le décodeur pourta se synchroniser. Le décodage des
codes en blocs & partir de décisions pondérées étant rarement utilisé, car difficile & mettre
en oeuvre, nous n'aborderons pas cette fagon de procéder dans cette introduction au
codage.
Supposons que le mot ¢ du code soit émis et soit r le vecteur ligne représentant le mot de
1n éléments binaires recu & Ventrée du décodeur. Le vecteur r peut toujours s‘écrire sous
la forme :
r=cte G.1)
ob e est un vecteur ligne, dont les composantes binaires représentent les éventuelles
erreurs de transmission, Une composante du vecteur e égale & 1 indique la présence -
d'une erreur de transmission sur la position correspondante du mot e.
La détection des erreurs de transmission se fait en utilisant la propriété d'orthogonalité de
la matrice de contréle de parité avec les mots du code et en calculant le syndrome s,
vecteur ligne & (n - k) composantes défini par : .
AT (3.2)
s=rH’ =(c+e)
Le syndrome s est nul si, et seulement si, r est un mot du code. Un syndrome non nul
implique la présence d'erreurs de transmission.
Notons toutefois qu'un syndrome nul ne signifie pas nécessairement l'absence derreur
de transmission car le mot r peut appartenir aux mots du code taut en étant différent dee. +
Il suffit pour cela que le vecteur e soit un mot du code. En effet, pour un code linéaire, la
somme de deux mots du code est encore un mot du code.
Retenons finalement que pour tout code en blocs linéaire, il existe des configurations
derreurs indétectables.
Avant d'aborder le probléme de la correction des erreurs, introduisons la notion de
distance entre deux mots binaires qui permet de mesurer la plus ou moins grande
différence existant entre eux. Une mesure de cette différence est égale au nombre
emplacements od les deux mots considérés possédent des éléments binaires différents.
Cette mesure s'appelle la distance de HAMMING entre les deux mots.
27 Si on définit le poids de HAMMING d'un mot, noté Py( ), comme le nombre de ses
éléments non nuls, la distance de HAMMING entre deux mots peut étre vue comme le
poids de HAMMING de la somme de ces mots :
dy (Vu) = Py(v+u) 63)
as Exemple
=<
Soient deuxmots v=[1 1 0 1 0 0 lJetu=[0 10 11 0 J], leur
distance de HAMMING , notée d(v,u) est égale & 2. On obtient alors?
Py(v+u)=Fy([1 0,0 0 1 0 0))=2
Régle de décodage : En présence d'erreurs de transmission (syndrome s non nul), la
Tegle de décodage va consister & rechercher le mot du code é le plus vraisemblable, c'est-
a-dire celui qui est & la distance de HAMMING minimale du mot regu r.
€tel que dy(r,@)