Théorie de l’information

primitifs : x n + 1 = P1(x)P2(x) . . .

2 choix de g(x) : on forme le polynôme g(x) de degré n-k

le reste des produits des polynômes est h(x) de degré k

3

8 / 29

Exemple

Contrôle de Parité

pour un code ( 7 ,4 ) :

x 7 + 1 = (x + 1)(x 3 + x 2 + 1)(x 3 + x + 1)

Nous avons ici deux possibilités de choix de g(x) et donc de h(x) :

1 g(x) = (x 3 +x 2 +1) =⇒ h(x) = (x +1)(x 3 +x +1) = (x 4 +x 3 +x 2 +1)

2 g(x) = (x 3 +x +1) =⇒ h(x) = (x +1)(x 3 +x 2 +1) = (x 4 +x 2 +x +1)

9 / 29

Syndrome

Contrôle de Parité

En cas d’erreur de transmission, nous recevons un mot de code

Y(x) qui ne correspond à aucun message.

Y (x) = C(x) + E(x) où E(x) est le polynôme de l’erreur.

Syndrome :

S(x) = Y (x) · h(x)mod(x n + 1) = E(x) · h(x)mod(x n + 1)

Une table des erreurs permet de remonter au polynôme d’erreur

de transmission et la correction des erreurs se fait toujours au

sens du maximum de vraisemblance : C∗(x) = Y (x) + E ∗(x).

10 / 29

exemple

Contrôle de Parité

En poursuivant avec l’exemple déjà utilisé code (7,4) et :

g(x) = 1 + x + x 3

h(x) = 1 + x + x 2 + x 4

et m = [1011] =⇒ m(x) = 1 + x 2 + x 3 =⇒ C(x) =

1 + x 3 + x 5 + x 6 =⇒ C = [1001011]

vérification :

C(x) · h(x) = (1 + x 3 + x 5 + x 6) · (1 + x + x 2 + x 4) =

1 + x 3 + x 5 + x 6

+x + x 4 + x 6 + x 7

+x 2 + x 5 + x 7 + x 8

+x 4 + x 7 + x 9 + x 10 = 0 mod (x 7 + 1)

11 / 29

Supposons une erreur de transmission

Contrôle de Parité

E = [0001000] =⇒ Y = [1000011] =⇒ Y (x) = 1 + x 5 + x 6

calcul du syndrome :

Y (x) · h(x) = (1 + x 5 + x 6).(1 + x + x 2 + x 4) = 1 + x + x 2 + x 4

+x 5 + x 6 + x 7 + x 9

+x 6 + x 7 + x 8 + x 10 = 1 + x 3 + x 4 + x 5 = S(x)

= E(x) · h(x) = x 3 · (1 + x + x 2 + x 4)

on voit bien que le syndrome dépend seulement de l’erreur et non

du message ou mot de code : S(x) = E(x) · h(x) = Y (x) · h(x)

on peut dessiner une table d’erreur/syndrome pour accélérer la

décision du récepteur.

donc même Alg de décodage que les codes de bloc linéaire,

seulement le calcul est polynomial

12 / 29

Remarque à propos du syndrome

Contrôle de Parité

Le syndrome est décrit par :

S(x) = Y (x) · h(x)mod(x n + 1) = E(x) · h(x)mod(x n + 1)

on peut utiliser un autre syndrome équivalent si on divise toute

l’égalité par le polynôme h(x) :

le nouveau syndrome est noté S(cid:48)(x) :

S(cid:48)(x) = Y (x) mod g(x) = E(x) mod g(x)

on peut travailler avec l’une des deux définitions

on définit donc deux algorithmes de décodage : l’un avec S(x) et

l’autre avec S(cid:48)(x).

13 / 29

Décodage

Plan

1 Codage

2 Contrôle de Parité

3 Décodage

4 Matrice génératrice d’un code cyclique

5 Codes cycliques usuels

6 Erreurs en Rafales

14 / 29

Algorithme de décodage 1

Décodage

1 Reception d’un mot de code Y (x).

2 calcul du syndrome associe S(x) = Y (x) · h(x)mod(x n + 1).

3 construction d’une table d’erreur/syndrome par

S(x) = E(x) · h(x)mod(x n + 1)

4 avec la table d’erreurs et le syndrome calculée à l’étape 2), calcul

de l’erreur la plus vraisemblable E ∗(x).

5 calcul du mot de code le plus vraisemblable :

C∗(x) = Y (x) + E ∗(x) et donc sous forme binaire C∗

6 Extraction du message X ∗ de C∗.

15 / 29

Algorithme de décodage 2

Décodage

1 Reception d’un mot de code Y (x).

2 calcul du syndrome associe S(x) = Y (x) mod g(x).

3 construction d’une table d’erreur/syndrome par

S(x) = E(x) mod g(x)

4 avec la table d’erreurs et le syndrome calculée à l’étape 2), calcul

de l’erreur la plus vraisemblable E ∗(x).

5 calcul du mot de code le plus vraisemblable :

C∗(x) = Y (x) + E ∗(x) et donc sous forme binaire C∗

6 Extraction du message X ∗ de C∗.

16 / 29

Exemple avec algorithme de décodage 2

Décodage

1 Reception de Y (x) = 1 + x 5 + x 6

2 Calcul du syndrome : S(cid:48)(x) = Y (x) mod g(x) = x + 1

3

table d’erreur :

Erreur

1

x

x 2

x 3

x 4

x 5

x 6

4 D’après la table d’erreur, S(cid:48)(x) = x + 1 correspond à E ∗(x) = x 3

5 Le mot de code correct est C∗(x) = Y (x) + E ∗(x) = 1 + x 3 + x 5 + x 6. D’où

Syndrome

1

x

x 2

x + 1

x 2 + x

x 2 + x + 1

x 2 + 1

Position

0

1

2

3

4

5

6

C∗ = [1001011]

le message est donc les k=4 derniers bits m∗ = 1011

6

17 / 29

Matrice génératrice d’un code cyclique

Plan

1 Codage

2 Contrôle de Parité

3 Décodage

4 Matrice génératrice d’un code cyclique

5 Codes cycliques usuels

6 Erreurs en Rafales

18 / 29

Matrice génératrice d’un code cyclique

Matrice génératrice d’un code cyclique

Puisque le décalage circulaire d’un mot de code est un mot de

code, on peut générer une matrice génératrice G∗ d’un polynôme

générateur g(x) :

G∗ =

















← g(x) →

← x · g(x) →

← x 2 · g(x) →

← x 3 · g(x) →

. . .

. . .

















comme exemple avec g(x) = 1 + x + x 3 :

G∗ =









1 1 0 1 0 0 0

0 1 1 0 1 0 0

0 0 1 1 0 1 0

0 0 0 1 1 0 1









19 / 29

Matrice génératrice d’un code cyclique

pour faire apparaître un code systématique, faire une combinaison

linéaire des lignes de G∗ :

Ligne 1 ←− Ligne 1

Ligne 2 ←− Ligne 2

Ligne 3 ←− Ligne 3 + Ligne 1

Ligne 4 ←− Ligne 4 + Ligne 1 + Ligne 2

Ce qui va donner

G =









1 1 0 1 0 0 0

0 1 1 0 1 0 0

1 1 1 0 0 1 0

1 0 1 0 0 0 1









on peut verifier que g(x) et G génèrent le même mot de code

C(x) = 1 + x 3 + x 5 + x 6 ou C = [1001011] du message m=[1011]

ou m(x) = 1 + x 2 + x 3

20 / 29

Codes cycliques usuels

Plan

1 Codage

2 Contrôle de Parité

3 Décodage

4 Matrice génératrice d’un code cyclique

5 Codes cycliques usuels

6 Erreurs en Rafales

21 / 29

Code de Golay

Codes cycliques usuels

c’est un code (n,k) = (23,12)

x 23 + 1 = (1 + x)(1 + x + x 5 + x 6 + x 7 + x 9 + x 11)(1 + x + x 4 + x 5 + x 6 + x 10 + x 11)

le polynôme générateur est :

g(x) = 1 + x + x 5 + x 6 + x 7 + x 9 + x 11

sa distance minimale dmin = 7

il peut donc détecter et corriger les erreurs triples !

le code de Golay est unique dans son groupe et ne peut être généralisé

22 / 29

Codes BCH (Bose-Chaudrui-Hocquenqhem)

Codes cycliques usuels

code avec n = 2m − 1 basé sur le calcule dans le corps de Galois

k est choisi de façon à que k ≥ n − m · t avec t est le nombre des

erreurs détéctables et corrigeables

la distance minimale sera toujours dmin ≥ 2t + 1

Ces codes permettent des longueurs de code très variées et

offrent de nombreuses possibilités d’efficacité de code k/n.

. Les coefficients des polynômes générateurs sont tabulés dans

de nombreux ouvrages, la longueur des polynômes générateur

devenant très grande, ces tables fournissent les jeux de

coefficients en utilisant un format octal par ordre décroissant

Exemple : code (31,26 ), t = 1 , coefficients 45 en octal soit 100

101 donc g(x) = x 5 + x 2 + 1

utilisé dans les CD, DVD, disque dur, les codes à bare

23 / 29

Codes RS (Reed-Solomon)

Codes cycliques usuels

Codes non binaire

n=k+2t et n = 2m − 1. avec m : nombre de bits par symbole et k :

nb de symbole d’information. 2t=nombre de symboles de controle

Reed solomon peut corriger (n-k)/2 erreurs

utilisé dans le stockage de données en CD avec RS(32, 28) et en

DVD avec RS(182,172)

utilisé en transmission par satellite en DVB avec RS( 204,188)

utilisé en ADSL avec RS(204,188)

24 / 29

Erreurs en Rafales

Plan

1 Codage

2 Contrôle de Parité

3 Décodage

4 Matrice génératrice d’un code cyclique

5 Codes cycliques usuels

6 Erreurs en Rafales

25 / 29

Erreurs en Rafales

Erreurs en Rafales

Les codes de bloc linéaires et cycliques sont efficaces pour

corriger des erreurs simples ou doubles dans un mot de code

et ils peuvent corriger des erreurs multiples dans un mot de code

Mais si pendant la transmission (ou dans un CD erroné ) il peut y

arriver des erreurs en rafale (burst errors), tout le mot de code est

erroné ou effacé : canal sans fils avec évanouissement, cassure

ou brûlure dans un CD. Les corrections des bits simples ou

doubles ne peuvent pas trop aider

26 / 29

Solution : entrelacement

Erreurs en Rafales

ne pas transmettre les données dans leur ordre normal

dans la fig à gauche, les bits sont transmis séquentiellement. et

donc des erreurs en rafales (B-its) vont domager tout le mot de

code transmis en continu (B Bits erronés)

dans la fig à droite, le fait d’entrelacer les bits des mots de codes

va séparer les erreurs en rafales en des erreurs simples (1 seule

erreur dans B mot de codes differents chacun) !

27 / 29

Interleaving : Entrelacement

Erreurs en Rafales

Autre utilisation de l’entrelacement entre le codage canal et la modulation

le canal mobile présente deux caractéristiques :

présence de Rafale d’erreurs (burst)

le codeur de convolution ne peut gérer les burst d’erreurs (due au

fading multi-trajets, ou disque défectueux ds le cas de CDROM)

entrelacer ou brasser l’ordre des bits encodés après le codeur canal pour rompre les burst

d’erreurs durant la transmission.

28 / 29

Erreurs en Rafales

Demonstration de l’effet de linterleaving sur un burst d’erreurs

29 / 29