Coding
Théorie de l’information pour ingénieurs
19 Nov 2024
RB - ISITCom - Sousse
Noisy Typewriter
Channel:
Calculez sa Capacité.
RB - ISITCom - Sousse
Forme systématique
RB - ISITCom - Sousse
Codes linéaires
RB - ISITCom - Sousse
CODES LINEAIRES
Matrice génératrice d’un code linéaire systématique
Sous forme normale, une matrice génératrice G peut prendre la forme
suivante : ou bien encore I k
G = Ik P P
Où Ik est la matrice identité k × k et P une matrice quelconque k × (n-k)
1 0 0 1 1 0
G = 0 1 0 0 1 1
0 0 1 1 0 1
Matrice identité k × k Matrice quelconque k × (n-k)
Formée par des bits de redondance
5
Matrice de contrôle de Parité
H est matrice de contrôle de parité du code linéaire permettant de définir les n-k bits
de contrôle en fonction des bits d’information et du transposé du vecteur CD formé
des bits codés.
G = Ik P H = P I n−k
t
• n c’est la taille du code
• k la taille de la donnée
• n-k c’est la taille des bits de contrôle
qu’on va rajouter dans le code
6
Matrice de contrôle de Parité
G = Ik P
H = P I n−k
t
Exemple :
1 0 0 1 1 0 1 0 1 1 0 0
G = 0 1 0 0 1 1
H = 1 1 0 0 1 0
0 0 1 1 0 1 0 1 1 0 0 1
7
Exercice 1:
Soit le code linéaire donné par sa matrice génératrice suivante: k=3, n=6
1) Ce code contient combien de bits d’information et de contrôle?
2) Trouver le vecteur de code CD , pour une vecteur de données
D={011001010101110001} : Cd= [011110,
3) Calculez sa matrice de parité H
4) Quelles sont les images par H des mots 100000, 010000, 001000,
000100, 000010, 000001? Que pouvez vous déduire sur le pouvoir de
correction de ce code?
8
Solution de l’exercice 1
Suite de la solution de l’exercice 1
Exercice 2
Rappel sur le code de Hamming
DECODAGE D’UN CODE LINEAIRE
Syndromes
Pour un code code CD linéaire (n,k) , si Y est le
^
mot de code transmis et
une erreur survient, le mot reçu est alors Y = Y + . Si H est une
matrice de contrôle de parité pour le code C utilisé, alors :
^
C .H t = (C + ).H t = C.H t + .H t = 0 + .H t = .H t
^
Définition (Syndrome) : Le syndrome d'un mot
^
Y relatif à une matrice
de contrôle H est le produit. t
C .H
^
Ce syndrome dépend de l’erreur = C − C et non du mot codé C.
16
DECODAGE D’UN CODE LINEAIRE
Décodage par Syndromes
Exemple: Soit un code linéaire dont la matrice génératrice G est donnée par :
1 0 1 0 1 1 1 1 0 0
G= H = 0 1 0 1 0
0 1 1 1 1
1 1 0 0 1
Il s’agit d’un code linéaire (5,2). Si le message (bits d’information) à envoyer est 10.
Alors le code généré sera C=(10101) . Supposant que le code reçu présente un bit
erroné soit (00101).
^
^
Le calcul du syndrome donne : s C = C .H t , soit s=……..
Le correcteur sera donc =
Ainsi le mot décodé sera : ……… + ………..= ………. Les deux premiers bits du code corrigé
représentent le message original à savoir …….
17
DECODAGE D’UN CODE LINEAIRE
Décodage par Syndromes
Exemple: Soit un code linéaire dont la matrice génératrice G est donnée par :
1 1 1 0 0
1 0 1 0 1
G= H = 0 1 0 1 0
0 1 1 1 1 1 1 0 0 1
Il s’agit d’un code linéaire (5,2). Si le message (bits d’information) à envoyer est 10.
Alors le code généré sera C=(10101) . Supposant que le code reçu présente un bit
erroné soit (00101). ^ ^ t
Le calcul du syndrome donne : s C =^ C .H , soit s=101
Le correcteur sera donc =10000=C- C
Ainsi le mot décodé sera : 00101 + 10000 = 10101. Les deux premiers bits du code
corrigé représentent le message original à savoir 10
18
