Bousmah chapit2_THInfo_Master_F.pdf

Théorie de l’information

Prof. M [email protected]

Université Chouaib DoukkaliMaster TR

Prof. M BOUSMAH 2

1. Théorie de l’Information 1. Th1. Thééorie de lorie de l ’’ Information Information 2. Modélisation d’une source2. Mod2. Mod éélisation dlisation d ’’une sourceune source

Plan du cours

6. Codage du canal (ECC)6. Codage du canal (ECC)6. Codage du canal (ECC)

3. Mesure de l’information3. Mesure de l3. Mesure de l ’’ informationinformation

4. Modélisation d’un canal4. Mod4. Mod éélisation dlisation d ’’un canalun canal 5. Codage de la source5. Codage de la source5. Codage de la source

Prof. M BOUSMAH 3

La « théorie de l’information » est une théorie qui s’intéresse à la transmission des messages d’une source vers un destinataire à travers un canal. Elle a été introduite en 1948 par l’ingénieur américain Claude Shannon qui affirmait qu’en codant l’information correctement, celle-ci peut être transmise à travers un canal parasité sans perte de son contenu à la réception. Elle se base sur une mesure quantitative de l’information, c’est àdire qu’elle ne s’intéresse pas au sens du message du point de vue sémantique, mais seulement à la quantité d’information que le message véhicule.

1. Th1. Thééorie dorie d’’ informationinformationcc’’ est est quoi?quoi?

Claude SHANNON(avr 1916-mar 2001)

Prof. M BOUSMAH 4

1948 : Shannon �Théorie de l'information

Source Discrète Brute

Encodeur de la source

Canal

Encodeur du canal

Modulateur Numérique

E

Mise en formeRéception

Décodeur de la source

Décodeur du canal

Démodulateur Numérique

R

Codage de la source Codage du canal


Prof. M BOUSMAH 5


Prof. M BOUSMAH 6

2. 2. MODELISATION DMODELISATION D’’ UNE UNE SOURCESOURCE

Il est possible de classer les sources en deux catégories selon les signaux ou messages qu’elles émettent :

Les sources analogiques

Les sources discrètes

Exemple: mic

Exemple: CD

Prof. M BOUSMAH 7

� Différentes types de sources d’information discrètes existent:

� Une source discrète dispose d'un "alphabet" constitué d'éléments ou symboles ou caractères {x1 , x2 , x3,…, xn}, n est la longueur de l'alphabet. Ces symboles sont associés pour constituer un message. Emettre un message revient à émettre une succession de symboles appartenant à une source. Chaque symbole xi de l'alphabet a une probabilité d'utilisation pi.

2. 2. MODELISATION DMODELISATION D’’ UNE UNE SOURCE: Cas de sources discrSOURCE: Cas de sources discrèètestes

Prof. M BOUSMAH 8

2. 2. MODELISATION DMODELISATION D’’ UNE UNE SOURCE: Cas de sources discrSOURCE: Cas de sources discrèètete

Prof. M BOUSMAH 9

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : QuantitQuantitéé d'informationd'information

A partir des remarques suivantes:

� La quantité d'information d'un symbole est d'autant plus grande que celui-ci est peu probable.

� La quantité d'information de deux symboles successifs est la somme de leurs quantités d'information.

La quantité d'information notée I est une fonction qui doit ainsi avoir les propriétés suivantes:

Prof. M BOUSMAH 10


� Une fonction mathématique remplit les conditions 1, 3 et 4 : log(pk)

� Pour obtenir la propriété 2, il suffit de prendre log(1/pk)= –log(pk)

� La quantité d'information d'un symbole xk de probabilitépk a ainsi étédéfinie par Shannon comme :

Prof. M BOUSMAH 11


Pour la suite du cours, log log �� loglog22

Prof. M BOUSMAH 12


Prof. M BOUSMAH 13


Prof. M BOUSMAH 14

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Entropie d'une sourceEntropie d'une source

Source SAlphabet: X={X1,X2, … ,XK}Entropie :H(X) ou H(S)

L’entropie H(X) mesure quoi?

Prof. M BOUSMAH 15


Prof. M BOUSMAH 16


Prof. M BOUSMAH 17


Cet exemple est un cas particulier d'une source ayant un alphabet de K symboles. On démontre que son entropie est maximaleentropie est maximale lorsque tous les symboles sont ééquiprobablesquiprobables : donc pk = 1/Kpk = 1/Ket l'entropie devient:

Ce qui montre le théorème suivant sur l'entropie d'une source:

Prof. M BOUSMAH 18

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Entropie conjointe entre deux sourcesEntropie conjointe entre deux sources

l'entropie conjointe ou réunie des deux sources est alors la quantité d'information moyenne jointe entre deux caractères de la source :

Prof. M BOUSMAH 19


Cas ou les deux sources sont indépendantes:

Les deux sources sont indépendantes �:

DDéémonstrationmonstration

Prof. M BOUSMAH 20

I( X , Y ) est définie comme étantLa quantitLa quantit éé d'information mutuelle d'information mutuelle entre les deux sourcesentre les deux sourcesou Transinformation :

Cas ou les deux sources sont dépendantes:


Prof. M BOUSMAH 21


Sachant que:

Alors ce terme est négatif. En définissant la quantité d'information mutuelle I( X , Y ) entre les deux sources comme une quantité positive.

DDéémonstrationmonstration

Prof. M BOUSMAH 22

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Entropie conditionnelleEntropie conditionnelle

Nous pouvons aussi définir à partir des densités de probabilité conditionnelles une quantité d'information conditionnelle:

puis une entropie conditionnelle :

et enfin une entropie conditionnelle moyenne :

Prof. M BOUSMAH 23


L'entropie conditionnelle permet d'obtenir d'autres formulations de ces quantités en utilisant la loi de Bayes :

Prof. M BOUSMAH 24


Un résultat semblable peut être établi en permutant le rôle de x et y d'où les deux expressions équivalentes de la quantité d'information mutuelle:

Ces expressions ajoutent deux nouvelles formulations de l'entropie jointe des deux sources :

Prof. M BOUSMAH 25

3. 3. MESURE DE L'INFORMATION : MESURE DE L'INFORMATION : Etude de casEtude de cas

Lors de la transmission par un canal, nous souhaitons récupérer l'information sans distorsion, autrement dit, l'alphabet de sortie du canal doit être le même que celui de l'entrée. Simplifions encore l'exemple à un canal qui doit transmettre des messages. Si nous appelons p la probabilité d'erreur nous pouvons schématiser le fonctionnement du canal par le graphe suivant :

Prof. M BOUSMAH 26


Prof. M BOUSMAH 27


Prof. M BOUSMAH 28


Prof. M BOUSMAH 29


Prof. M BOUSMAH 30


Prof. M BOUSMAH 31


Conclusion

Prof. M BOUSMAH 32

4. 4. ModModéélisation dlisation d’’ un canalun canal

Un canal de transmission reçoit un message d'entrée et restitue un message de sortie. D'un point de vue abstrait nous le considèrerons comme une entitéqui fait le lien entre deux alphabets : X X ��YY.

Canal discret :Canal discret : Le deux alphabets d'entrée et de sortie sont des alphabets discrets qui comportent un nombre fini de symboles.

Canal sans mCanal sans méémoire :moire :

Le symbole courant de sortie ne dépend que du symbole courant d'entrée et ne dépend pas des précédents ni des suivants.

ReprRepréésentation graphique :sentation graphique :

Le canal effectue donc le couplage entre deux alphabets. La donnée essentielle pour comprendre le fonctionnement du canal est ainsi l'ensemble des probabilités conditionnelles.

Prof. M BOUSMAH 33

4. 4. ModModéélisation dlisation d’’ un canal:un canal:Graphe de canalGraphe de canal

Le schéma complet du fonctionnement du canal est donné par un graphe ou une matrice de canal.

Chaque lien est pondéré par la probabilité conditionnelle p( yk / xj ). Si cette probabilité est nulle, nous ne plaçons pas de lien.

Prof. M BOUSMAH 34

4. 4. ModModéélisation dlisation d’’ un canal:un canal:Matrice de canalMatrice de canal

Matrice de canal :Matrice de canal :

Plutôt qu'un graphe le canal pet être modélisé par une matrice P des probabilitésconditionnelles ou matrice de canal.

Prof. M BOUSMAH 35

4. 4. ModModéélisation dlisation d’’ un canalun canalMatrice de canalMatrice de canal

Prof. M BOUSMAH 36

4. 4. ModModéélisation dlisation d’’ un canal:un canal:

CapacitCapacitéé de canalde canal

Un canal lie deux sources d'entrée X et de sortie Y. Pour comparer la similitude de ces deux sources, nous avons à notre disposition la quantitéd'information mutuelle qui est définie par :

Les probabilités marginales { p( xj ) } dépendent de la source d'entrée et donc du système de codage de canal utilisé. Nous pouvons rechercher un système de codage qui rende maximal cette quantité, c'est ce qui définit la capacité du canal

Prof. M BOUSMAH 37

Les probabilités marginales { p( xj ) } dépendent de la source d'entrée et donc du système de codage de canal utilisé.Nous pouvons rechercher un système de codage qui rende maximal cette quantité, c'est ce qui définit la capacité du canal :

La capacité s'exprime en bits/utilisateur de canal.Si la cadence d'utilisation du canal est d'un symbole toute les Tc secondes, le débit maximum du canal sera C/Tc bits/s.



Prof. M BOUSMAH 38



Relation de Shannon-Hartley

Remarque:Remarque: Un canal est caractUn canal est caractéérisriséé aussi par son Daussi par son Déébit binaire bit binaire D = R logD = R log22(V) (bit/s)(V) (bit/s)

R: RapiditR: Rapidit éé (Baud) V: valence ((Baud) V: valence (nbrenbre dd’é’états distincts prtats distincts préésents sur le signal)sents sur le signal)

( Capacit( Capacitéé maximale dmaximale d’’ un canal )un canal )maxmax

maxmax

canal

Prof. M BOUSMAH 39

4. 4. ModModéélisation dlisation d’’ un canal:un canal:PropriPropriééttééss

Prof. M BOUSMAH 40


I(X,Y)

H(X/Y)

H(X)

H(Y/X)H(Y)

Equivoque, Incertitude, PerteEquivoque, Incertitude, Perte

Bruit, InsignifiantBruit, Insignifiant

Prof. M BOUSMAH 41


I(X,Y)H(X) H(Y)

Pas de perturbations: Pas de perturbations: H(X/Y)=0 H(Y/X)=0 I(X,Y)=H(X)=H(Y)H(X/Y)=0 H(Y/X)=0 I(X,Y)=H(X)=H(Y)

Prof. M BOUSMAH 42


H(X/Y)

H(Y/X)H(Y)

Equivoque, Incertitude, PerteEquivoque, Incertitude, Perte

Bruit, InsignifiantBruit, Insignifiant

H(X)

Perturbation Forte: Perturbation Forte: I(X,Y)=0 H(X)= H(X/Y) H(Y)=H(Y/X)I(X,Y)=0 H(X)= H(X/Y) H(Y)=H(Y/X)

Prof. M BOUSMAH 43

4. 4. ModModéélisation dlisation d’’ un canal:un canal:Cas dCas d’’ un canal binaire symun canal binaire syméétriquetrique

Prof. M BOUSMAH 44


Prof. M BOUSMAH 45


Prof. M BOUSMAH 46


Prof. M BOUSMAH 47


Nous retrouvons les conclusions de l'illustration de la notion de quantité d'information mutuelle : lorsque la probabilité d'erreur est de 50%, la capacité du canal est nulle, lorsqu'elle est égale à0% ou 100% la capacité du canal est maximale (une erreur de 100% correspond à une simple inversion des bits "0" et "1" par le canal).

ConclusionConclusion

Prof. M BOUSMAH 48

4. 4. ModModéélisation dlisation d’’ un canal:un canal:Redondance et EfficacitRedondance et Efficacitéé

� La redondance du canal sera définie par :

RRcc=C =C -- I(X,Y) I(X,Y)

� La redondance relative du canal sera définie par :

ρρcc=1 =1 –– I(X,Y)/C I(X,Y)/C

� L’efficacité du canal sera définie par :

ηηcc=I(X,Y)/C =I(X,Y)/C ≤≤11

Prof. M BOUSMAH 49

5. 5. Codage de la source:Codage de la source:Codage avec mots de longueur fixeCodage avec mots de longueur fixe

Nous prendrons par la suite le cas d'un codage binaire.

L'égalité a lieu lorsque tous les symboles de la source sont équiprobables et lorsque K est une puissance de 2.

Prof. M BOUSMAH 50


Un codage est dit d'autant plus efficaceplus efficaceque le nombre de codes possibles inutilisés est faible. L'efficacité dépend aussi de la quantité d'information moyenne de la source. L'efficacitéη d'un codage sera ainsi définie par :

8

Prof. M BOUSMAH 51


Théorème du codage de source, 1er théorème de Shannon :

Prof. M BOUSMAH 52

5. 5. Codage de la source:Codage de la source:Codage, mots de longueur variableCodage, mots de longueur variable

� Lorsque tous les symboles de l'alphabet ne sont pas équiprobables, l'extension de source ne permettra pas d'augmenter jusqu'à 100% l'efficacité.

� Le codage avec mots de longueur variable consiste àutiliser un codage plus "long" pour les symboles peu utilisés (de probabilité faible) et un codage "court" pour les symboles les plus utilisés (de probabilité élevée).

Prof. M BOUSMAH 53


111111101/8I

011110011/8C

0110001/4T

0011/2S

Code3Code2Code1ProbabilitéSource

Voici un exemple:

Supposons que nous cherchions à transmettre le message TIC

Code non décodable de manière instantanéeTIC01111011Code3

Code décodable de manière uniqueTIC10111110Code2

Code non décodable de manière uniqueTSTS ou TIC001001Code1

ObservationDécodageCodage

Prof. M BOUSMAH 54


� Un code préfixe est, par définition, un code dont aucun code n'est le préfixe d'un autre.

� Un code préfixe est décodable de manière unique et instantanée.

�� Code prCode prééfixefixe

Exemple: code 2

Prof. M BOUSMAH 55


�� Arbre dArbre d’’ un codeun code

Un codage binaire peut être représenté de manière graphique par un arbre. Les arbres sont aussi des représentations commodes pour écrire les algorithmes de codage et de décodage. Voici les règles:

Pour les trois codages précédents nous obtenons :

• Un déplacement à gauche correspond à un "0".• Un déplacement à droite correspond à un "1".• Chaque déplacement crée un nœud de l'arbre.• Chaque nœud à un père (vers le haut) et peut avoir deux fils (vers le bas).• Le lien entre deux nœuds est une branche.• Un nœud qui n'a pas de fils est une feuille.

Prof. M BOUSMAH 56

101/8I

011/8C

001/4T

11/2S

Code1ProbabilitéSource

Arbre de code 1Arbre de code 1

TT CC II

SS


Prof. M BOUSMAH 57



1111/8I

1101/8C

101/4T

01/2S


SS

TT

CC IIUn code préfixe est un code dont les symboles codés sont des feuilles.

Prof. M BOUSMAH 58



1111/8I

0111/8C

011/4T

01/2S


SS

TT

CC II

Prof. M BOUSMAH 59


Longueur moyenne de code :

Pour une source X d'alphabet { Xk } de probabilités associées { Pk }, la longueur moyenne du code sera définie par :

où nk est la longueur du code associé au symbole Xk

Prof. M BOUSMAH 60

5. 5. Codage de la source:Codage de la source:Codage de Codage de HuffmanHuffman

Le codage de Huffman est un algorithme de compression de données sans perte élaboré par David Albert Huffman, lors de sa thèse de doctorat au MIT. L'algorithme a été publié en 1952 dans l'article:« A Method for the Construction of Minimum-Redundancy Codes».

Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier).

Un code de Huffman est optimal pour un codage par symbole, et une distribution de probabilité connue.

Prof. M BOUSMAH 61


Prof. M BOUSMAH 62


Exemple: code 2Exemple: code 2

SSTT

CC

II

SS�� 00 TT��1010 II��111111 CC��110110

Remarque :Remarque :Lors du classement des nœuds par probabilités décroissantes, il se peut que deux nœuds aient mêmes probabilités. Leur classement est alors arbitraire. Lors de l'implantation des algorithmes, le choix le plus simple au niveau programmation est d'attribuer, en cas d'équiprobabilité, la place la plus élevée au dernier nœud créé.

Prof. M BOUSMAH 63

5. 5. Codage de la source:Codage de la source:Codage de ShannonCodage de Shannon--FanoFano

Le codage de Shannon-Fano est un algorithme de compression de données sans perte élaboré par Robert Fano à partir d'une idée de Claude Shannon.Il s'agit d'un codage entropique produisant un code préfixe très similaire à un code de Huffman, bien que non-optimal, contrairement à ce dernier.

Prof. M BOUSMAH 64

5. 5. Codage de la source:Codage de la source:ShannonShannon--FanoFano

1ère étapeOn classe les symboles source (par exemple sur une colonne) par ordre de probabilité décroissante (par exemple de haut en bas),

2ème étapeOn divise l'ensemble des symboles en deux sous-ensembles de telle sorte que les probabilités cumulées des éléments constituant chacun des deux sous-ensembles soient les plus proches. On attribue l'élément binaire "1" (resp. "0") aux éléments du sous-ensemble situé en haut (resp. en bas),

3ème étapeOn procède comme à la première étape sur tous les sous-ensembles comportant au moins deux éléments. On s'arrête lorsque tous les sous-ensembles ne comportent plus qu'un élément.

Algorithme

Prof. M BOUSMAH 65

6. 6. Code Correcteur dCode Correcteur d’’ Erreur:Erreur:IntroductionIntroduction

Source Discrète Brute

Encodeur de la source

Canal

Encodeur du canal

Modulateur Numérique

E

Mise en formeRéception

Décodeur de la source

Décodeur du canal

Démodulateur Numérique

R

Codage de la source Codage du canal = Code Correcteur d’Erreur

Prof. M BOUSMAH 66

D’où le ::��Codage du canal Codage du canal ��ECC ECC ErrorError --CorrectingCorrecting Code, Code, traduit en français par

Code Correcteur dCode Correcteur d’’ ErreurErreur

Dans la grande majorité des cas, une transmission de données est attaqué par le bruit. Donc Il faut des mécanismes de détection et de correction des erreurs.

Parfois, le code correcteur dParfois, le code correcteur d’’ erreur se limite erreur se limite àà la la ddéétection des erreurstection des erreurs. La correction est alors r. La correction est alors rééalisaliséée e par une nouvelle demande de transmission du par une nouvelle demande de transmission du message (Protocole TCP).message (Protocole TCP).


Prof. M BOUSMAH 67

Historique


Prof. M BOUSMAH 68

Historique

1948 : Shannon (théorie de l’information).1950 : Hamming.1950-1970 : codes en blocs et codes cycliques, BCH (Bose-Chaudhuri-Hocquenghem) et RS (Reed-Solomon).1960-1970 : codes convolutifs (Fano, Forney, Viterbi).1980: Ungerboeck: Treillis Coded Modulations: mélange entre codage et modulation1990: Codage Conjoint Source/Canal: mélange entre codage source et canal1993: Berrou, Glavieux: Turbo codes, limite de Shannon atteinte dans canal AWGN2000: Turbo xxxx: décodage, égalisation2000: « Multiple Input Multiple Output » (MIMO) systèmes et « Space Time Coding » codes LDPC (Low Density Parity Check).


Prof. M BOUSMAH 69

Exemple de codeExemple de code


Prof. M BOUSMAH 70

Exemple de codeExemple de code


Prof. M BOUSMAH 71


Prof. M BOUSMAH 72


?

Prof. M BOUSMAH 73


DDééfinitions de base:finitions de base:

Prof. M BOUSMAH 74


Prof. M BOUSMAH 75


Prof. M BOUSMAH 76


Prof. M BOUSMAH 77


Exemple:Exemple:

Prof. M BOUSMAH 78


Prof. M BOUSMAH 79


Prof. M BOUSMAH 80


Prof. M BOUSMAH 81


Prof. M BOUSMAH 82


Prof. M BOUSMAH 83


Prof. M BOUSMAH 84


Prof. M BOUSMAH 85


Prof. M BOUSMAH 86


Prof. M BOUSMAH 87


Prof. M BOUSMAH 88


Prof. M BOUSMAH 89


Prof. M BOUSMAH 90


Prof. M BOUSMAH 91


Prof. M BOUSMAH 92


Prof. M BOUSMAH 93


Prof. M BOUSMAH 94


Prof. M BOUSMAH 95


Prof. M BOUSMAH 96

6. 6. Code Correcteur dCode Correcteur d’’ Erreur:Erreur:Les codes linLes codes linééaires en blocsaires en blocs

Prof. M BOUSMAH 97


Prof. M BOUSMAH 98


Prof. M BOUSMAH 99


Prof. M BOUSMAH 100


Prof. M BOUSMAH 101


Prof. M BOUSMAH 102


Prof. M BOUSMAH 103


Prof. M BOUSMAH 104


Prof. M BOUSMAH 105


Prof. M BOUSMAH 106


Prof. M BOUSMAH 107


Prof. M BOUSMAH 108


Prof. M BOUSMAH 109


Prof. M BOUSMAH 110


Prof. M BOUSMAH 111


ProcProcéédure de Ddure de Déécodagecodage

Prof. M BOUSMAH 112


ProcProcéédure de ddure de déécodagecodage

Deux méthodes existent:�Décodage par tableau standard�Décodage par syndrome

Prof. M BOUSMAH 113

ProcProcéédure de ddure de déécodagecodage

�Décodage par tableau standard

Cette méthode reste encore très complexe


Prof. M BOUSMAH 114

ProcProcéédure de ddure de déécodagecodage�Décodage par syndrome


Prof. M BOUSMAH 115

Exercice :Considérons le code C4 (5,2,dmin) défini par la matrice génératrice suivante :



1. Déterminer dmin

2. Calculer la capacité de détection et de correction d’erreur3. Déterminer la matrice de contrôle H4. Supposons que le mot de code c=(11110) soit transmis et que le

mot reçu soit y = (11100). Calculer le syndrome s5. Estimer l’erreur6. Déduire le code transmis7. Conclure.

Prof. M BOUSMAH 116



1. dmin=3

2. Capacité de détection d’erreur=2 Capacité de correction d’erreur=1

3. La matrice de contrôle H:

41111011

31010110

30101101

00000000

PoidsCUCorrigé:

Prof. M BOUSMAH 117



Corrigé:4. Supposons que le mot de code c=(11110) soit transmis et que le

mot reçu soit y = (11100). Calculer le syndrome s

= (010)5. Estimer l’erreur �construire la table de syndromeNous calculons le syndrome correspondant à chaque vecteur d’erreur.6. En utilisant cette table de décodage par syndrome on trouve e = [00010]. En ajoutant le vecteur d’erreurs estimé e au mot reçu, le mot corrigé est alors

7. On peut voir que ce code permet de corriger tous les motifs d’erreurs simples.

Prof. M BOUSMAH 118


Prof. M BOUSMAH 119


Prof. M BOUSMAH 120


Prof. M BOUSMAH 121


Prof. M BOUSMAH 122


Prof. M BOUSMAH 123


Prof. M BOUSMAH 124


Prof. M BOUSMAH 125


Exemple du code de Hamming [7,4,3]

Prof. M BOUSMAH 126



Prof. M BOUSMAH 127



Prof. M BOUSMAH 128


Prof. M BOUSMAH 129


La matrice génératrice systématique du code de Golay

Prof. M BOUSMAH 130


ConclusionConclusion

Prof. M BOUSMAH 131


Codes cycliquesCodes cycliques

Prof. M BOUSMAH 132



Prof. M BOUSMAH 133



g(p) est le polynôme générateur du code de degré (n-k)

Prof. M BOUSMAH 134


Codes cycliquesCodes cycliquesExemple de code polynomial: C(n,k,dmin) avec n=8 k=6

Message:1 1 0 1 1 1 Polynôme associé:

On veut ajouter deux bits de redondance: on multiplie par x2

On choisit un polynôme générateur de degré 2 (n-k)

Les bits de redondance ajoutés au message sont les coefficients du

polynôme reste de la division euclidienne du polynôme Message. x2par le polynôme générateur.

Prof. M BOUSMAH 135


Codes cycliquesCodes cycliquesExemple de code polynomial: C(n,k,dmin) avec n=8 k=6

Prof. M BOUSMAH 136


Pour détecter la présence d’erreurs dans un mot reçu, la majoritédes protocoles utilisent une technique baptisée CyclicRedundancy Check (CRC). Cette technique consiste à utiliser un code cyclique. Il faut souligner que cette technique ne permet pas de corriger les erreurs. On peut cependant demander une réémission du mot de code Automatic Repeat Request (ARQ) en anglais.

Codes cycliques: ExempleCodes cycliques: Exemple

Prof. M BOUSMAH 137



Prof. M BOUSMAH 138



Prof. M BOUSMAH 139



Prof. M BOUSMAH 140



Prof. M BOUSMAH 141

La table suivante présente les polynômes générateurs des codes BCH corrigeant jusqu’à 3 erreurs avec N ≤ 63.



Prof. M BOUSMAH 142



Le code de Reed – Solomonest un code de détection et de correction d’erreurs publié en 1960 - in Journal of the Society for Industrial and Applied Mathematics -

Ce code a une propriété importante, il est linéaire et fait partie des codes BCH. Le codeur prend k symboles de donnée et calcule les informations de contrôle pour construire n symboles, ce qui donne n-k symboles de contrôle. Le décodeur peut corriger au maximum t symboles, ou 2t=n-k � dmindmin=2t+1=2t+1.

Le diagramme ci-dessous montre une trame constituée avec le codeur Reed – Solomon :

Prof. M BOUSMAH 143



Prof. M BOUSMAH 144



En général

Prof. M BOUSMAH 145



Prof. M BOUSMAH 146

6. 6. Code Correcteur dCode Correcteur d’’ Erreur:Erreur:Les codes convolutifsLes codes convolutifs

Prof. M BOUSMAH 147


Le principe des codes convolutifs, inventés par Peter Elias en 1954, est non plus de découper le message en blocs finis, mais de le considérer comme une séquence semi-infinie de symboles qui passe à travers une succession de registres à décalage, dont le nombre est appelé mémoire du code. Le taux de codage est R= k/nLe codage se fait alors avec des registres à décalage et des ou exclusif.

Exemple :

Prof. M BOUSMAH 148


1110001

1100010

1001100

1110001

Sortiex1x2

Etat Finals1 s2

Etat initials1 s2

un

À chaque arrivée d’un élément binaire, une sortie est générée puis juste après,le codeur passe à l’état suivante

s1=un-1

s2=un-2

x1=un + un-1+ un-2

x2=un + un-2

Prof. M BOUSMAH 149


Prof. M BOUSMAH 150


Prof. M BOUSMAH 151


Partant, par exemple de l’état 00, l’arrivée d’un 0 mène le codeur à l’état 00 (transition en pointillé pour l’arrivée d’un 0) et l’arrivée d’un 1 mène le codeur à l’état 10 (transition en trait plein pour l’arrivée d’un 1). A chaque branche on peut associer le mot codé soit les 2 bits de code ici.

Prof. M BOUSMAH 152


Prof. M BOUSMAH 153


Prof. M BOUSMAH 154


Décodage : algorithme de Viterbi

Le décodage le plus courant est basé sur l’algorithme de Viterbi. Il consiste à rechercher dans l’arbre le chemin qui correspond à la séquence la plus probable, c’est-à-dire celle qui est à la distance minimale de la séquence reçue ou encore la séquence la plus probable.

Prof. M BOUSMAH 155


Décodage : algorithme de Viterbi

Soit le codeur convolutif non récursif non systématique suivant:

Exemple:

Prof. M BOUSMAH 156


Décodage : algorithme de ViterbiExemple:

Prof. M BOUSMAH 157



Prof. M BOUSMAH 158



Prof. M BOUSMAH 159



Prof. M BOUSMAH 160



Prof. M BOUSMAH 161



Prof. M BOUSMAH 162



Prof. M BOUSMAH 163



Prof. M BOUSMAH 164



Prof. M BOUSMAH 165



Prof. M BOUSMAH 166



Prof. M BOUSMAH 167



Prof. M BOUSMAH 168



Prof. M BOUSMAH 169



Prof. M BOUSMAH 170


Deux catégories de codes convolutifs existent:

Les codes non systématiques ou NSC (Non Systematic Convolutional codes)

Les codes systématiques récursifs ou RSC (RecursiveSystematic Convolutionalcodes)

Prof. M BOUSMAH 171


Les codes non systématiques ou NSC (Non SystematicConvolutional codes)

Un code convolutif est dit systématique si l’un des bits de sortie est identique au bit d’entrée.Les codes NSC, présentent l’avantage par rapport aux codes systématiques de fournir plus d’information : tout bit de sortie du codeur renseigne sur plusieurs bits du message codé. Le décodeur dispose donc de plus d’éléments dans un code NSC, et permet donc de corriger plus d’erreurs.Pour cette raison, ce sont les codes NSC qui ont été principalement étudiés et utilisés jusqu’au début des années 1990. On constate expérimentalement que la puissance d’un code (sa capacité àcorriger les erreurs) augmente plus ou moins linéairement avec la mémoire n de ce code. On s’est donc attaché à augmenter n ce qui pose des problèmes au niveau du décodage (complexité du décodeur est en 2n)

Prof. M BOUSMAH 172


Les codes systématiques récursifs ou RSC (RecursiveSystematicConvolutional codes)

On a constaté expérimentalement grâce aux travaux sur les turbo-codes (et une équipe de chercheurs australiens s’attache à le démontrer) que seuls les codes RSC sont susceptibles d’atteindre la limite de Shannon.

Un code convolutif est dit récursif si la séquence passant dans les registres àdécalages est « alimentée » par le contenu de ces registres.

Prof. M BOUSMAH 173


Turbo code

Prof. M BOUSMAH 174

Merci de votre attention

Prof. M BOUSMAH 175

RRééfféérencesrences

• G.BINET. "THEORIE DE L’INFORMATION", Université de Caen

• Richard G. TERRAT. "Théorie de l’information". Université Montpellier II, Faculté des Sciences, Département Informatique, Master

• T. Grenier. "Théorie de l’information". INSA de Lyon

•Marc Chaumont. Codes Correcteurs d’Erreurs

•Didier LE RUYET. CODE CONVOLUTIF ET ALGORITHME DE VITERBI. CNAM Paris

• RIOUL Olivier. "Théorie de l'information et du codage". Hermes Science - Lavoisier

• Thomas M. Cover (Author), Joy A. Thomas. "Elements of Information Theory"

Documents

Bousmah chapit2_THInfo_Master_F.pdf