Rhouma Rhouma https://sites.google.com/site/rhoouma
École Supérieure d’Économie Électronique
Avril 2015
1 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
2 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
3 / 48
4 / 48
Problématique
Canal de transmission : C’est l’élément physique par lequel les informations de la source
seront transmises au récepteur. La transmission de l’information a deux impératifs
contradictoires : 1) Transmettre le plus vite possible le maximum d’information et 2) Eviter
les erreurs de transmission.
Atmosphère : ondes électromagnétiques ou ondes Herteziennes. Cable coaxial, paire torsadée : signaux électriques (tensions, courants). Fibre optique : ondes optiques (lumière visible, infra-rouge,. . .).
Source : C’est elle qui fournit le signal. Celui-ci peut être analogique (microphone,. . ..) ou discret (CD,....). Nous nous intéresserons aux communications dites "numériques" le signal est donc discret et converti en binaire (numérisation). La source fourni un message qui est une séquence de bits.
Encodeur de source : Son rôle est de représenter le message sur un minimum de bits (compression de données). Ceci permettra de transmettre le maximum d’informations dans le minimum de temps. Source -> encodeur de source -> message
Encodeur de canal : Il doit structurer le message pour permettre au récepteur de pallier aux erreurs de transmission. Cette modification du message génère un mot de code qui est une séquence de bits plus longue que celle du message. Cela peut se faire par simple adjonction de bits redondants mais aussi par des méthodes d’encodage plus élaborées. message -> encodeur de canal -> mot de code
5 / 48
Problématique
Modulateur : mot de code -> modulateur -> ondes Si ( t )
Modulation binaire : Le mot de code généré est une succession de "0" et de "1". Afin de transmettre l’information il est nécessaire de les transformer en un signal physique adapté au canal de transmission. Chaque signal élémentaire est appelé une forme d’onde. Ainsi 0 → S 0( t ) et 1 → S 1( t ). nous obtenons une modulation binaire c’est-à-dire faisant intervenir deux formes d’onde. Modulation M-ary : Plutôt que de transmettre le code bit par bit, il est possible de le transmettre par paquets de b bits. Nous aurons donc M = 2 paquets possibles ce qui nécessite M formes d’ondes Si ( t ) différentes.
Démodulateur : Rôle inverse de celui du modulateur, il reçoit les ondes éventuellement perturbées et les transforme en paquets de bits pour reconstituer le code sur lequel peut se trouver des erreurs de transmission. Ondes Si ( t ) -> démodulateur -> mot de code
Décodeur de canal : Grâce au codage il peut soit détecter une erreur de transmission et dans ce cas éventuellement réinterroger l’émetteur mais certains codages permettent dans une certaine mesure de détecter et de corriger les erreurs de transmission. En général les codes correcteurs ne peuvent pas tout corriger sinon ils demanderaient trop de bits redondants, ils se contentent de corriger les erreurs les plus probables. mot de code -> décodeur -> message
Décodeur de source : Ayant la séquence binaire ou message associée à l’information, ce décodeur doit reconstituer l’information qui a été transmise. c’est la décompression.
6 / 48
La description du système révèle bien la position du problème qui se résume en deux points contradictoires :
Transmettre le plus vite possible le maximum d’informations :
Peu de bits de codage Modulation astucieusement choisie Vitesse de transmission élevée : bon choix du canal
Transmettre sans erreur :
Augmenter le nombre de bits du codage Modulation bien choisie Bon choix d’un canal de transmission
Chaque problème demande un compromis !
7 / 48
On peut schématiser le comportement du récepteur par un graphe qui montre comment les niveaux de tensions sont mappés en 0 ou 1.
si le voltage reçu entre V 0 et [0][+] [1] le symbole reçu est 0 sinon
2 c’est un 1
8 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
9 / 48
supposons que durant la transmission, le "1" est reçu et interprété comme un "0" et vice versa avec une probabilité p.
p est appelé la probabilité d’erreur
le canal dans ce cas est appelé canal binaire symétrique
ce type de canal est très significatif quant à la modélisation d’un canal de transmission.
10 / 48
I ( X , Y ) = H ( X ) − H ( X /Y )
I(X,Y) veut dire : Quel est notre incertitude sur X réduite en sachant Y ? I(X,Y) mesure aussi la similitude entre X et Y H(X /Y) est liée à l’existence d’une probabilité d’erreur de transmission. En généralisant cette notion, H(X/Y) est due à l’existence de bruit sur le canal et révèle le fait que celui-ci ne transmet pas parfois l’information. H(X/Y) est en quelque sorte une mesure de la quantité d’information perdue. I(X,Y) devient ainsi la quantité d’information correcte transmise par le canal. La capacité du canal doit s’entendre au sens de la capacité de transmission sans erreur.
11 / 48
Modèle : Canal Binaire symétrique
m
- 1
p ( xi /yj ) log 2( p ( xi /yj ) [)] i =1
H ( X /Y = yj ) =
H ( X /Y ) =
m
H ( X /Y = yj ) p ( yj )
i =1
H ( X , Y ) = H ( X ) + H ( Y /X ) = H ( Y ) + H ( X /Y )
puisque p ( xi , yj ) = p ( xi ) p ( yj /xi ) = p ( yj ) p ( xi /yj ), donc
I ( X , Y ) = I ( Y , X )
= ⇒ l’information mutuelle est symétrique ! La formule de I(X,Y) est donné par :
p ( xi , yj ) log ( [(] [,][ y] [)]
p ( xi ) p ( yj
i,j
I ( X , Y ) =
Publicité
p ( xi ) p ( yj ) [)]
Pour un canal binaire symétrique, l’information mutuelle est donné par : I ( X , Y ) = 1 + (1 − p ) · log (1 − p ) + p · log ( p )
12 / 48
Modèle : Canal Binaire symétrique
Puisqu’on a
I ( X , Y ) = 1 + (1 − p ) · log (1 − p ) + p · log ( p ) = 1 − H ( X )
1 si p = 0 ce qui veut dire pas d’erreur de transmission alors I ( X , Y ) = 1. Similitude parfaite entre les deux sources, la transmission se passe bien. H ( X , Y ) = 1.
2 si p = 0.5, pagaille complète lors de la transmission. Dans ce cas I ( X , Y ) = 0, plus du tout de similitude entre les deux sources. Tout se passe comme si les deux sources étaient indépendantes.
3 si p = 1, à nouveau I ( X , Y ) = 1. Les deux sources sont à nouveau tout à fait semblables. Le fait qu’il y a dans ce cas permutation du "0" et du "1" n’ayant pas d’importance.
13 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
14 / 48
L’information mutuelle peut etre redefinie en utilisant les probabilités conditionnelles qui définissent le canal :
p ( yj /xi ) · p ( xi ) · log ( [(] [/] [)]
p ( xi )
i,j
I ( X , Y ) =
p ( xi ) [)]
Les probabilités marginales {p ( xi ) } 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 :
C = maxp ( xi ) {I ( X , Y ) } = max{H ( X ) − H ( X /Y ) }
Si la cadence du canal est d’un symbole toute les Tc secondes, le débit maximum du canal sera
Tc [/] [.] La capacité du canal doit s’entendre au sens de la capacité de transmission sans erreur.
15 / 48
Pour que la transmission soit performante, il faut fournir au récepteur la quantité d’information manquante qui est H(X/Y ). Pour cela il est imaginé d’introduire une redondance dans l’information qui permettra de détecter et de corriger les erreurs dues à la transmission.
Exemples simples :
Ajouter un bit de parité et, en cas d’erreur à la réception, interroger de nouveau l’émetteur. Transmettre l’information en trois exemplaires et, en cas de désaccord, faire confiance à la majorité.
Ces méthodes proviennent d’une analyse empirique de la situation et, d’après le modèle de Shannon, elles ont pour effet de diminuer la quantité d’information perdue et donc d’augmenter la capacité du canal. Grâce à cette analyse, il est possible de mettre au point des méthodes de codage plus efficaces pour atteindre cet objectif.
un codage de canal performant est d’autant plus nécessaire que le canal est bruité et perd de l’information.
16 / 48
A mathematical theory of communication. Octobre 1948
Soit un canal discret de capacité C et une source discrète d’entropie H.
Puisque H ( X /Y ) = H ( X ) − C
17 / 48
Shannon a montré theoriquement qu’on peut transmettre l’information (bits) à un taux de codage (débit) R < C avec une probabilité d’erreur tres faible
Il a aussi montré que la transmission à un taux de codage (débit) R ≥ C va certainement incorporer des erreurs de transmissions
son secret : coder un bloc de k-bits en un mot de code de n-bits (avec n>k) pour réduire le débit R = k /n
le fait de coder un message de k-bits en un mot de code de n-bits s’appelle le codage canal
18 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
19 / 48
Soit x = [ x 1 x 2 . . . xn ] et y = [ y 1 y 2 . . . yn ] deux msg de longueur n.
Ex : Si x = 10110 et y = 00101, alors d ( x, y ) = 3 et w ( x ) = 3 et w ( y ) = 2.
20 / 48
Le poids Wi d’un mot de code Ci est par définition le nombre de caractères non nuls que contient ce mot.
ex : 11001000 est de poids W=3
ex : 10011010 est de poids W=4
00000000 est de poids nul
21 / 48
La distance de Hamming dij entre deux mots de code est le nombre de bits dont ils diffèrent. ex 11001000 et 10011010 ont une distance de 3. La distance minimale du code est le minimum de l’ensemble des distances entre codes :
dmin = min{dij }
la distance de Hamming entre un mot de code valide et erroné de e erreurs est e si on n’a pas de codage : les deux mots de codes "0" et "1" ont une distance egale à 1. donc une erreur change un code valide à un autre code valide ! On peut montrer que dmin = min{Wi }
22 / 48
on veut coder de façon à que les mots de codes soient assez éloignés pour que les erreurs ne changent pas un code valide à un autre code valide !
23 / 48
Le rôle du correcteur d’erreurs peut être limite à la simple détection (et localisation ) d’erreurs.
La correction s’effectue alors par une nouvelle requête de transmission du message, ou seulement des parties erronées. ex TCP par sommes de contrôle (checksum) pour la vérification
Cela peut se reveler insuffisant, ou inadaptée suivant le contexte (GSM par exemple)
24 / 48
Supposons que l’on ait des mots de 7 bits à envoyer (code ASCII par exemple), et que l’on s’intéresse simplement à la détection d’une erreur.
Un moyen et de coder chacun des mots sur 8 bits, en ajoutant un 8eme bit, appelé bit de parité, de telle sorte que dans tous les mots le nombre de 1 soit pair.
le message 1011001 est codé 1011001 0
et le message 0110100 est codé 0110100 1
permet de detecter un nb impair d’erreur
ne permet pas de localiser donc de corriger les erreurs détéctés
25 / 48
Codeur : Dispositif qui associe à une suite de k bits d’information une suite de n bits. Code : Un code est un ensemble de mots de n bits. Distance minimale d’un code C :
dmin = min {d ( x, y ) /x, y ∈C}
on peut montrer que
dmin = min {w ( x ) /x ∈C et x = [−→] 0 }
26 / 48
1 Problématique
Publicité
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
27 / 48
Messages de 4 bits : 16 messages possibles
La distance de Hamming minimale dmin = 1
Aucune erreur ne peut être détecté ou corrigé
On ne peut remarquer si une erreur s’est passé
28 / 48
Messages de 4 bits + 1 bit de contrôle :
16 codes possibles représenté par 5 bits
La distance de Hamming minimale dmin = 2
Une seule erreur peut être détectée
aucune erreur ne peut être corrigée
On sait qu’il y a une erreur mais on ne peut la localiser (corriger)
29 / 48
Code de Hamming (7,4) : 4 bits de données + 3 bits contrôle
La distance de Hamming minimale dmin = 3
Une seule erreur peut être détectée et corrigée
les erreurs doubles sont confondu avec les erreurs simples : on peut détecter 2 erreurs mais on ne corr qu’une
30 / 48
Nb max des erreurs détectables : eD = dmin − 1
tous les erreurs appartenant à une sphere sont corrigeables
tous les erreurs appartenant à l’intersection des spheres sont non corrigeables
Donc Nb max des erreurs corrigeables : eC = E [ 2 [1] [(] [−] [1][)]]
31 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
32 / 48
Codes de bloc (n,k) : un bloc de n-bits noté C = b 0 b 1 bn−k − 1 m 0 m 1 . . . mk − 1 construit à partir d’un message de k-bits noté m = m 0 m 1 . . . mk − 1.
on peut note le code aussi comme code (n,k,d) avec d est la distance de hamming minimale.
b consitués par n-k bits redondants ou bits de parité. b = b 0 b 1 . . . bn−k − 1
linéaire : soit deux codes Ci et Cj alors Ci + Cj = Ck est un mot de code
le code "0" (les n bits à 0) est un mot de code dans chaque code (n,k). (parceque 1+1=0)
codage : C = m × G
G est la matrice génératrice de taille ( k × n ). Le code est dit :
Systématique : Si G = [ P Ik ] avec Ik est l’identité de taille ( k × k ). P est dite la matrice de parité de taille ( k × n − k ). Le code dans ce cas est formé des bits de parité suivis par les bits de message. Non-systématique si G = [ P M ] avec M quelconque de taille ( k × k ).
33 / 48
1 0 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1
Soit G =
donner les propriétés de ce code (n,k) ?
donner toutes les possibilités du message m
donner les mots de codes si b 0 b 1 b 2 sont les bits redondants du mot de code, donner leurs formules en fonction des bits de message m 0, m 1, m 2
34 / 48
Matrice de contrôle : H = [ In−k P ]
avec In−k est l’identité de ( n − k ) × ( n − k ) et P est la transposé de la matrice de parité P
On peut vérifier facilement que G · H = 0.
H de l’exemple précédent est : H =
1 0 0 1 1 1 0
0 1 0 0 1 1 1 0 0 1 1 1 0 1
35 / 48
Pour chaque mot de code C :
C · H = m · G · H = 0
si le mot de code est erroné, donc il s’écrit comme suit : Code reçu = Code emis + erreur = ⇒ Y = C + E En effectuant le controle à la reception :
S = Y · H = C · H + E · H = E · H
Le syndrome S ne depend que de l’erreur commise et non du message ou le mot de code Remarque : Deux erreurs qui diffèrent d’un mot de code ont même syndrome ce theorème nous indique qu’il y a ambiguïté lors de la détection d’erreur
36 / 48
soit M = C · H
Chaque élément de la matrice M est une combinaison linéaire sur une ligne j de tous les éléments des colonnes = ⇒ M est une combinaison linéaire des colonnes de la matrice H et cette combinaison linéaire est nulle. les colonnes de H sont linéairement dépendantes. Le nombre de colonnes intervenant dans la combinaison est égale au nombre de "1" du code Cm ce qui est le poids de Hamming du mot de code. La distance de Hamming du code étant le poids minimal de ce code = ⇒ La distance minimale de Hamming dmin d’un code est égale au nombre minimal de colonnes de la matrice H dont la somme est nulle. Le nombre de colonnes de H linéairement indépendantes est dmin − 1 et le rang maximal de cette matrice est n − k ce qui établi la relation :
Si dmin est la distance de Hamming :
détecter au plus t erreurs SSI dmin ≥ t + 1
corriger au plus t erreurs SSI dmin ≥ 2 t + 1
Détecter au plus tD erreurs mais ne corriger qu’au plus tC erreurs avec tC < tD SSI dmin ≥ tC + tD + 1
38 / 48
1 Reception d’un mot de code Y.
2 calcul du syndrome associe S = Y · H .
3 construction d’une table d’erreur/syndrome par S = E · H
4 avec la table d’erreurs, calcul de l’erreur la plus vraisemblable E [∗]
associée au syndrome.
Publicité
5 calcul du mot de code le plus vraisemblable : C [∗] = Y + E [∗]
6 Extraction du message X [∗] de C [∗] .
39 / 48
- 1 0 1 1 0
Code(5,2) avec G = 0 1 1 0 1
H est donc donnée par H =
1 0 0 1 0
0 1 0 0 1 0 0 1 1 1
Le syndrome est donc de longueur 5 − 2 = 3. On peut coder tous les erreurs simples (5) + le cas pas d’erreur. il reste deux combinaisons pour les erreurs doubles (2 = 2 [−] − n − 1).
Syndrome Erreur commentaire 000 00000 Pas d’erreur 001 00100 Erreur ds le bit 2 010 01000 Erreur ds le bit 1 011 00001 Erreur ds le bit 4 100 10000 Erreur ds le bit 0 101 00010 Erreur ds le bit 3 110 ? ? 111 ? ?
40 / 48
Codes de bloc Linéaires
le syndrome 110 peut être associé à une erreur double du type (bit 0 + bit 1) soit 11000 mais aussi à une erreur du type (bit 3 + bit 4) soit 00011. Il y a ici ambiguïté entre deux erreurs doubles.
Pour le syndrome 001 associé à une erreur bit 2 il pourrait être associé à une erreur type ( bit 1 +bit 4 ) mais ici l’ambiguïté est entre une seule erreur simple et d’autres erreurs doubles, triples,. . .
H a au plus trois colonnes linéairement indépendantes donc dmin = 3. donc eD = 2 et eC = 1
Si nous affectons la solution la plus vraisemblable, toutes les erreurs simples peuvent être corrigées.
Les erreurs doubles, elles sont détectables mais nous pouvons soit les confondre entre elles, soit les confondre avec une erreur simple. Dans le second cas le maximum de vraisemblance corrige comme une erreur simple (c’est effectivement ce qui a la plus forte probabilité d’arriver ) et dans le premier elle tranche en faveur de la solution la plus probable qui, pour un code donné est toujours la même.
Qu’arrive-t-il pour des erreurs triples ? Au sens du critère, elles sont toujours systématiquement confondues soit avec une erreur simple soit une erreur double, elles sont de ce fait non détectables et par la même non corrigeables.
41 / 48
Codes de bloc Linéaires
soit m = [1 0].
Le mot de code correspondant est
- 1 0 1 1 0
C = m · G = [1 0] · 0 1 1 0 1
= [1 0 1 1 0]
à la reception le bit n˚3 a été interprété par le récepteur d’une manière fausse. Donc Y = [1 0 1 0 0]
Le récepteur calcule le syndrome associé : S = Y · H = [1 0 1]
Par la table d’erreur Le recepteur fait correspondre le syndrome calculé et trouve l’erreur la plus vraisemblable E [∗] = [0 0 0 1 0]
Correction : C [∗] = Y + E [∗] = [1 0 1 0 0] + [0 0 0 1 0] = [1 0 1 1 0]
extraction du message : les k dernier bits de C [∗] qui sont m [∗] = [1 0]
remarquer que S = Y · H = E [∗] · H = [1 0 1]
42 / 48
Repeter la meme demarche pour erreur dans le bit n˚4
43 / 48
erreur dans le bit n˚0 et 1 : Y = [0 1 1 1 0]
Syndrome S = Y · H = [1 1 0]
d’apres la table ceci correspond à E [∗] = [1 1 0 0 0] (ou [0 0 0 1 1]).
si par ex le recepteur choisi la deuxième possibilité d’erreur. C [∗] = Y + E [∗] = [0 1 1 1 0] + [0 0 0 1 1] = [0 1 1 0 1]
et donc m [∗] = [0 1] qui est different du message original
avec ces exemple on voit que le code a un pouvoir de detection qui ne peut le dépasser et a un pouvoir de correction qui ne peut le dépasser aussi
44 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
45 / 48
Code de Hamming
Les codes de Hamming sont des codes binaires qui ont la propriété : ( n, k , dmin ) = (2 − 1 , 2 − 1 − m, 3)
ex code (7,4,3) ; code (15,11,3)
La matrice de contrôle de Hamming H est de taille ( n − k × n ) = ( m × 2 − 1). Une colonne est donc constituée de m éléments binaires et nous avons 2 − 1 colonnes c’est-à-dire toutes les combinaisons possibles moins une (la combinaison "000..." ). Ceci nous permet pour ces codes de construire très rapidement la matrice de contrôle H et d’en déduire la matrice de génération de code G.
Commencer à remplir la matrice H en utilisant les combinaisons linéaires de m bits faisant apparaître la matrice In−k . Compléter cette matrice par les combinaisons de m bits non encore utilisées code "0" exclu.
46 / 48
1 Problématique
2 Modèle : Canal Binaire symétrique
3 Capacité du canal et role du codage
4 Métriques
5 Pouvoir de détection et Pouvoir de Correction
6 Codes de bloc Linéaires
7 Code de Hamming
8 Code de Hadamard
47 / 48
Code de Hadamard
Les codes de Hadamard sont constitués par des matrices, par
- _Mn_ _Mn_
itération : M 2 n = Mn Mn
complementaire de Mn
avec Mn est la matrice
- 0 0 M 2 = 0 1
0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0
M 4 =
Les Matrices Mn ou Mn contiennent dans leurs lignes ou colonnes les 2 n mots de codes.
La structure de la matrice permet donc de détecter les erreurs de transmissions il est montré que dmin = n/ 2
48 / 48