Sommaire

Théorie de l’information
Cours 7 - Introduction au codage canal Capacité d’un canal de communication
Capacité d’un canal
Capacité d’un canal binaire symétrique
Cas d’un message de longueur n
Laurent Oudre
[Link]@[Link]
Deuxième théorème de Shannon (hors programme)
Principe du codage canal
Quelques notions de codage canal
Université Paris 13, Institut Galilée Deuxième théorème de Shannon
Master Ingénierie et Innovations en Images et Réseaux - 1ère année
2017-2018

Laurent Oudre Théorie de l’information 2017-2018 1 / 46 Laurent Oudre Théorie de l’information 2017-2018 2 / 46

Capacité d’un canal de communication Capacité d’un canal de communication Capacité d’un canal

Sommaire Cadre du cours

◮ Dans le chapitre précédent, on a représenté chaque symbole (ou groupe de

symboles) de la source sous forme d’une série de 0 et de 1.
Capacité d’un canal de communication
Capacité d’un canal ◮ En utilisant les propriétés de la source (notamment les probabilités
Capacité d’un canal binaire symétrique
Cas d’un message de longueur n d’apparition des symboles), on a pu faire en sorte de compresser au maximum
les données
Deuxième théorème de Shannon (hors programme)
◮ Nous allons maintenant étudier la suite de la communication, c’est à dire la
transmission à travers le canal.
◮ On sait que la transmission à travers le canal va être source d’erreurs et de
pertes.
◮ La question que l’on doit se poser est : comment à partir de la sortie d’un
canal, retrouver le message que l’on avait envoyé ?

Laurent Oudre Théorie de l’information 2017-2018 3 / 46 Laurent Oudre Théorie de l’information 2017-2018 4 / 46
 Capacité d’un canal de communication Capacité d’un canal Capacité d’un canal de communication Capacité d’un canal

Contexte Information mutuelle

X Canal Y
◮ Dans un canal non bruité, on a exactement Y = X , et les variables X et Y
contiennent exactement la même information
◮ Dans le cas général, on a vu que l’information mutuelle I (X ; Y ) représentait
Bruit la quantité d’information commune à X et Y .
◮ I (X ; Y ) nous permet donc de quantifier le lien entre l’entrée et la sortie du
canal
◮ On considère un canal discret sans mémoire. ◮ Si I (X ; Y ) est très élevée, cela signifie que Y a beaucoup d’information en
◮ On se place après l’étape de codage source, ce qui fait que l’on traite commun avec X : il sera donc facile d’estimer X à partir de Y
maintenant une nouvelle source X , plus nécessairement sans mémoire, dont ◮ En revanche si I (X ; Y ) est très faible, il n’y a pas ou peu de liens entre X et
l’alphabet est X = {0, 1} Y , et on aura du mal à retrouver l’entrée X à partie de la sortie Y
◮ On note Y la variable aléatoire liée à la sortie du canal. Elle prend ses valeurs
dans Y qui n’est pas nécessairement identique à X

Laurent Oudre Théorie de l’information 2017-2018 5 / 46 Laurent Oudre Théorie de l’information 2017-2018 6 / 46

Capacité d’un canal de communication Capacité d’un canal Capacité d’un canal de communication Capacité d’un canal

Information mutuelle Capacité d’un canal

◮ Intuitivement, la quantité I (X ; Y ) dépend du niveau du bruit, donc des

Capacité d’un canal
propriétés du canal
◮ On peut donc se demander : étant donné un canal, quelle est la valeur Étant donné un canal discret sans mémoire, ayant pour entrée X ∈ X , et
maximale de I (X ; Y ), c’est à dire celle permettant d’avoir le lien maximal pour sortie Y ∈ Y, on appelle capacité du canal et on note C la quantité :
entre l’entrée et la sortie ?
◮ On va donc définir une quantité, dépendant uniquement du canal (et pas de C = max I (X ; Y )
pX (x)
l’entrée), représentant l’information mutuelle maximale, c’est à dire le
meilleur cas de figure possible.

Laurent Oudre Théorie de l’information 2017-2018 7 / 46 Laurent Oudre Théorie de l’information 2017-2018 8 / 46
 Capacité d’un canal de communication Capacité d’un canal Capacité d’un canal de communication Capacité d’un canal binaire symétrique

Interprétation Calcul de la capacité d’un canal binaire symétrique

1−ǫ
0 0
ǫ
◮ La capacité d’un canal quantifie le lien maximal possible entre l’entrée et la
sortie du canal
◮ Le terme de capacité fait donc sens, car le canal ne peut pas créer plus de
lien entre X et Y , il n’en est pas capable ǫ

◮ Nous verrons dans la deuxième partie du cours que grâce au théorème de 1 1

1−ǫ
Shannon, on peut donner une autre interprétation à cette quantité
◮ Nous allons maintenant voir comment calculer en pratique la capacité d’un ◮ On suppose que pX (0) = p et pX (1) = 1 − p
canal.
◮ On va calculer I (X ; Y ) et regarder pour quelle valeur de p (donc pour quelle
distribution de X ) elle est maximale
◮ La valeur maximale de I (X ; Y ) sera la capacité du canal

Laurent Oudre Théorie de l’information 2017-2018 9 / 46 Laurent Oudre Théorie de l’information 2017-2018 10 / 46

Capacité d’un canal de communication Capacité d’un canal binaire symétrique Capacité d’un canal de communication Capacité d’un canal binaire symétrique

Calcul de la capacité d’un canal binaire symétrique Calcul de la capacité d’un canal binaire symétrique
1−ǫ
0 0
1−ǫ ǫ
0 0
ǫ

ǫ 1 1
1−ǫ
1 1
1−ǫ
H(Y |X ) = −(1 − p)ǫ log2 (ǫ) − pǫ log2 (ǫ) − p(1 − ǫ) log2 (1 − ǫ) − (1 − p)(1 − ǫ) log2 (1 − ǫ)
= −ǫ log2 (ǫ) − (1 − ǫ) log2 (1 − ǫ)
◮ pY (0) = pY |X (0|0)pX (0) + pY |X (0|1)pX (1) = (1 − ǫ)p + ǫ(1 − p) = p + ǫ − 2pǫ
◮ pY (1) = 1 − p − ǫ + 2pǫ ◮ On a :
I (X ; Y ) = H(Y ) − H(Y |X )
◮ Donc :
H(Y ) = −(p + ǫ − 2pǫ) log2 (p + ǫ − 2pǫ) − (1 − p − ǫ + 2pǫ) log2 (1 − p − ǫ + 2pǫ)
I (X ; Y ) = −(p+ǫ−2pǫ) log2 (p+ǫ−2pǫ)−(1−p−ǫ+2pǫ) log2 (1−p−ǫ+2pǫ)
+ǫ log2 (ǫ) + (1 − ǫ) log2 (1 − ǫ)
Laurent Oudre Théorie de l’information 2017-2018 11 / 46 Laurent Oudre Théorie de l’information 2017-2018 12 / 46
 Capacité d’un canal de communication Capacité d’un canal binaire symétrique Capacité d’un canal de communication Capacité d’un canal binaire symétrique

Calcul de la capacité d’un canal binaire symétrique Calcul de la capacité d’un canal binaire symétrique

◮ Pour calculer le maximum, on annule la dérivée par rapport à p On a donc :

dI (X ; Y ) C = 1 + ǫ log2 (ǫ) + (1 − ǫ) log2 (1 − ǫ)

=0 ⇐⇒ −(1 − 2ǫ) log2 (p + ǫ − 2pǫ) + (1 − 2ǫ) log2 (1 − p − ǫ + 2pǫ) = 0
dp
⇐⇒ log2 (p + ǫ − 2pǫ) = log2 (1 − p − ǫ + 2pǫ) ◮ Si ǫ = 0, il n’y a aucune erreur et C = 1 bit
⇐⇒ p + ǫ − 2pǫ = 1 − p − ǫ + 2pǫ ◮ Si ǫ = 12 , les bits sont indifféremment transmis sous forme de 0 ou de 1. On a
⇐⇒ 2p(1 − 2ǫ) = 1 − 2ǫ
donc C = 0 bit et les variables d’entrée et de sortie sont indépendantes
1
⇐⇒ p= ◮ Si ǫ = 1, les 0 deviennent 1 et inversement, on a C = 1 bit. Y est
2
1 exactement l’inverse de X !
La valeur de p = 2 est ici logique, car le canal est symétrique

Laurent Oudre Théorie de l’information 2017-2018 13 / 46 Laurent Oudre Théorie de l’information 2017-2018 14 / 46

Capacité d’un canal de communication Capacité d’un canal binaire symétrique Capacité d’un canal de communication Cas d’un message de longueur n

Calcul de la capacité d’un canal binaire symétrique Cas d’un message de longueur n

◮ On aurait pu éviter un long calcul en remarquant que comme H(Y ) est le X (1) X (2) . . . X (n) Canal Y (1) Y (2) . . . Y (n)
seul terme dépendant de p, il suffit pour que I (X ; Y ) soit maximale que
H(Y ) le soit
◮ Or H(Y ) est l’entropie d’une variable aléatoire binaire dans un alphabet Bruit
{0, 1} à M = 2 éléments, elle est donc maximale pour

1
pY (0) = pY (1) = et vaut dans ce cas H(Y ) = log2 (2) = 1 bit ◮ Nous avons pour le moment considéré l’envoi, la transmission et la réception
2
d’un unique bit
◮ On a donc ◮ Nous allons maintenant étudier le cas où l’on transmet un message contenant
I (X ; Y ) ≤ 1 + ǫ log2 (ǫ) + (1 − ǫ) log2 (1 − ǫ) n bits
et l’on retrouve donc naturellement la capacité du canal ◮ X (t) représente la variable aléatoire liée au symbole émis au temps t
◮ Y (t) représente la variable aléatoire liée au symbole reçu au temps t

Laurent Oudre Théorie de l’information 2017-2018 15 / 46 Laurent Oudre Théorie de l’information 2017-2018 16 / 46
 Capacité d’un canal de communication Cas d’un message de longueur n Capacité d’un canal de communication Cas d’un message de longueur n

Cas d’un message de longueur n Information mutuelle

I (X , Y ) = H(Y ) − H(Y |X )
◮ On notera pour simplifier les notations :
X X     
(1) (n) (1) (n) H(Y |X ) = − pX Y x, y log2 pY |X y |x
Y =Y ...Y X =X ...X
x∈X n y ∈Y n
n
!
◮ Comme le canal est sans mémoire, on a : X X   Y  
= − pX Y x, y log2 pY |X y (t) |x (t) canal sans mémoire
  n   x∈X n y ∈Y n t=1
Y
(1) (n) (1) (n)
pY |X y ...y |x ...x = pY |X y (t) |x (t) n X X
X     
= − pX Y x, y log2 pY |X y (t) |x (t)
t=1
t=1 x∈X n y ∈Y n

◮ On a vu que l’information mutuelle pouvait nous aider à évaluer la proximité n

X X X     
= − pXY x (t) , y (t) log2 pY |X y (t) |x (t)
de l’entrée et la sortie du canal.
t=1 x (t) ∈X y (t) ∈Y
◮ Que peut-on dire sur I (X ; Y ), l’information contenue à la fois dans X et Y ? n
X
= H(Y (t) |X (t) )
t=1

Laurent Oudre Théorie de l’information 2017-2018 17 / 46 Laurent Oudre Théorie de l’information 2017-2018 18 / 46

Capacité d’un canal de communication Cas d’un message de longueur n Capacité d’un canal de communication Cas d’un message de longueur n

Information mutuelle Information mutuelle

◮ On a donc :
N
X n
X
(t)
I (X ; Y ) = H(Y ) − H(Y |X ) I (X ; Y ) ≤ H(Y )− H(Y (t) |X (t) )
t=1 t=1

◮ Donc finalement :
n
H(Y ) = H(Y (1) . . . Y (n) ) X
I (X ; Y ) ≤ I (X (t) ; Y (t) )
= H(Y (1) , . . . , Y (n) ) t=1
n
X ◮ Or par définition on a :
≤ H(Y (t) )
t=1
∀t I (X (t) ; Y (t) ) ≤ C

◮ Donc finalement :
I (X ; Y ) ≤ n × C

Laurent Oudre Théorie de l’information 2017-2018 19 / 46 Laurent Oudre Théorie de l’information 2017-2018 20 / 46
 Capacité d’un canal de communication Cas d’un message de longueur n Deuxième théorème de Shannon (hors programme)

Cas d’un message de longueur n Sommaire

◮ La capacité d’un canal limite donc le lien possible entre le message de sortie
et le message d’entrée Capacité d’un canal de communication
◮ Connaissant cette contrainte, on peut se demander : si la capacité du canal
Deuxième théorème de Shannon (hors programme)
est très faible, pourra-t-on tout de meme retrouver X à partir Y sans faire Principe du codage canal
aucune erreur ? Quelques notions de codage canal
Deuxième théorème de Shannon
◮ Intuitivement, on a envie de répondre non et de dire que s’il y a trop de bruit,
la tache sera impossible.
◮ Shannon a au contraire prouvé que cela était possible, à condition
d’introduire avant l’envoi sur le canal une étape supplémentaire, appelée
codage canal, qui va rajouter des bits supplémentaires. C’est le deuxième
théorème de Shannon.

Laurent Oudre Théorie de l’information 2017-2018 21 / 46 Laurent Oudre Théorie de l’information 2017-2018 22 / 46

Deuxième théorème de Shannon (hors programme) Principe du codage canal Deuxième théorème de Shannon (hors programme) Principe du codage canal

Émetteur Travaux de Shannon

Source Emetteur Canal Recepteur Destinataire

La théorie de l’information et les travaux de Shannon ont permis de répondre à

deux questions fondamentales sur les sytèmes de communication :
Bruit ◮ Codage source : étant donnée une source, à quel point peut-on compresser
les données lors du codage, tout en faisant en sorte que le destinataire puisse
toujours déchiffrer les messages que l’on envoie ?
L’émetteur prend ce message numérique et réalise les étapes suivantes : Premier théorème de Shannon
◮ Codage source : compression des données pour qu’elles prennent le moins de ◮ Codage canal : étant donné un canal de communication bruité, jusqu’à quel
place possible. Cela revient à remplacer le message à envoyer par un message débit d’information peut-on envoyer les données en conservant une
le plus court possible, souvent représenté sous forme d’une série de 0 et de 1. probabilité d’erreur à la sortie qui soit limitée ?
◮ Codage canal : rajout de bits d’information supplémentaires dans le message Deuxième théorème de Shannon
pour permettre de corriger les éventuelles erreurs de transmission
◮ Transformer le message numérique en un signal physique (onde
électromagnétique, signal électrique, etc...) qui puisse être transmis sur le
canal de transmission

Laurent Oudre Théorie de l’information 2017-2018 23 / 46 Laurent Oudre Théorie de l’information 2017-2018 24 / 46
 Deuxième théorème de Shannon (hors programme) Principe du codage canal Deuxième théorème de Shannon (hors programme) Principe du codage canal

Principe du codage canal Code à répétition

◮ Après l’étape de codage source, le message à envoyer est représenté sous

forme d’une série de 0 et de 1 dont la taille a été optimisée. ◮ Pour comprendre le principe du codage canal, nous allons dérouler un
exemple simple.
◮ Le canal de transmission étant bruité, le récepteur va recevoir un message où
certains bits auront été perdus ou modifiés
◮ Imaginons une salle extrêmement bruyante, avec une personne à chaque bout
de la salle. Comment faire en sorte que le message transmis de l’une à l’autre
◮ Lorsqu’on décodera le message, il y a donc certains symboles qu’on ne pourra soit transmis sans erreur ?
pas retrouver ◮ Idée 1 : Parler plus fort ou crier. Cela revient à augmenter la puissance
◮ Pour éviter ou limiter ces erreurs, on va introduire des bits supplémentaires d’émission (cf cours de Télécommunications)
dont le rôle va être de détecter ou de corriger les éventuelles erreurs de ◮ Idée 2 : Répéter plusieurs fois jusqu’à ce que le message passe. Cela revient à
transmission introduire une redondance dans le message envoyé.
◮ Avec le codage source on a essayé de limiter le plus possible le nombre de ◮ Formalisons maintenant cet exemple par un schéma de communication.
bits... avec le codage canal on va au contraire en rajouter

Laurent Oudre Théorie de l’information 2017-2018 25 / 46 Laurent Oudre Théorie de l’information 2017-2018 26 / 46

Deuxième théorème de Shannon (hors programme) Principe du codage canal Deuxième théorème de Shannon (hors programme) Principe du codage canal

Code à répétition Code à répétition

◮ Considérons une source, qui après l’étape de codage source, peut être vue
comme une variable aléatoire X à valeurs dans {0, 1} où les deux symboles
sont équiprobables.
◮ On considère le canal de transmission suivant : ◮ On suppose que la source répète deux fois chaque bit
0.9 ◮ Lorsque le destinataire reçoit 00, il peut supposer que c’est 0 qui a été envoyé
0 0 ◮ Idem pour 11
0.1 ◮ Mais si le destinataire reçoit 01 ou 10, c’est impossible à trancher
◮ Une meilleure solution est que la source répète trois fois chaque bit
◮ Il suffit dans ce cas de compter le nombre de 0 et de 1 reçus
◮ S’il y a plus de 0 que de 1, on suppose que c’est 0 qui a été envoyé
0.1
◮ Idem pour 1

1 1
0.9
Le bruit est modélisé par une probabilité d’erreur de 0.1
On appellera Y la sortie (ce que recevra le destinataire) à valeurs dans {0, 1}

Laurent Oudre Théorie de l’information 2017-2018 27 / 46 Laurent Oudre Théorie de l’information 2017-2018 28 / 46
 Deuxième théorème de Shannon (hors programme) Principe du codage canal Deuxième théorème de Shannon (hors programme) Principe du codage canal

Code à répétition Code à répétition

Quelle est la probabilité de faire une erreur sur le bit envoyé ?

◮ Ce sera la même pour 0 et 1 car le canal est symétrique ◮ En multipliant par 3 le nombre de bits envoyés, on a divisé par 3.6 la
◮ Si on a une erreur, c’est par exemple que l’on a plus de 1 que de 0 dans le probabilité d’erreur (0.1 → 0.028)
message reçu, alors qu’on avait envoyé un 0 ◮ On peut faire la même chose en considérant 5 répétitions au lieu de 3, et
◮ Si on suppose que tous les bits envoyés successivement sont indépendants et dans ce cas, on a une probabilité d’erreur de 0.0086, ce qui revient à diviser
identiquement distribués, le nombre d’erreur dans un groupe de 3 bits suit par 11.7 la probabilité d’erreur (0.1 → 0.0086)
une loi binomiale avec n = 3 et p = 0.1. ◮ Le codage canal utilise ce principe : il s’agit d’introduire de la redondance,
◮ Faire une erreur revient à avoir soit 2, soit 3 bits erronés dans le groupe. qui va augmenter la longueur des messages envoyés, mais permettre de
diminuer (ou annuler) la probabilité d’erreur.
Perr = C32 p 2 (1 − p) + C33 p 3 = 0.028

Laurent Oudre Théorie de l’information 2017-2018 29 / 46 Laurent Oudre Théorie de l’information 2017-2018 30 / 46

Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal

Quelques notions de codage canal Codes détecteurs, codes correcteurs

◮ Le but de cette partie n’est pas d’étudier en détail les techniques de codage
canal, mais de donner quelques définitions et d’introduire quelques concepts
permettant de comprendre le principe du codage canal. Il existe plusieurs types de codages canal :
◮ Pour de plus amples informations, on se reportera au cours CDCE optionnel ◮ Ceux qui vont introduire de la redondance pour diminuer la probabilité

au second semestre d’erreur (par exemple code à répétition que nous avons traité en exemple)
◮ Le principe du codage canal est toujours le même : on va transformer un ◮ Ceux qui vont détecter la présence d’erreurs pour pouvoir éventuellement

message binaire en un autre message binaire de taille plus élevée, afin de le demander à la source de ré-envoyer le message : codes détecteurs d’erreurs
rendre plus robuste aux erreurs. ◮ Ceux qui vont détecter et corriger les bits erronés : codes correcteurs d’erreurs
◮ Si on code de façon astucieuse, on peut réduire ou annuler la probabilité
d’erreur, c’est à dire faire en sorte qu’on puisse retrouver parfaitement ou
presque le message émis à partir du message reçu

Laurent Oudre Théorie de l’information 2017-2018 31 / 46 Laurent Oudre Théorie de l’information 2017-2018 32 / 46
 Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal

Quelques exemples (M, n)-code : définition

Quelques exemples (M, n)-code (HP)

Message à envoyer : 011000 On appelle (M, n)-code un sous ensemble de M mots-code de longueur n
réalisés avec l’alphabet X = {0, 1}
◮ Code à répétition de longueur 3 : On divise en bloc de taille 1 et on repète chaque
bloc 3 fois : C = {x 1 , . . . , x M } ⊂ X n
011000 −→ 0 1 1 0 0 0 −→ 000 111 111 000 000 000
On a M = 2 mots-code possibles : 000 et 111
Ce code nous permet de diminuer la probabilité d’erreur. Pour l’annuler
◮ M est le nombre de mots-code constituant le code
totalement, il faudrait répéter le bit une infinité de fois ◮ n est la longueur moyenne du code (appelée parfois simplement
◮ Code de parité de longueur 2 : On divise en bloc de taille 2 et on ajoute un 3 ème longueur car tous les mots-code on la même longueur !)
bit égal à la somme binaire des deux bits du bloc : ◮ Le taux (ou rendement) du code est noté R et est défini par :
011000 −→ 01 10 00 −→ 011 101 000
log2 (M)
On a M = 4 mots-code possibles : 000, 110, 101, 011 R=
Ce code est un détecteur d’erreurs : si on ne reçoit pas l’un de ces 4 mots-codes, n
on sait qu’il y a eu une erreur sur au moins 1 bit
Attention ici un mot-code x ∈ C est un message contenant n bits

Laurent Oudre Théorie de l’information 2017-2018 33 / 46 Laurent Oudre Théorie de l’information 2017-2018 34 / 46

Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal

(M, n)-code : définition (M, n)-code : définition

◮ On va par exemple diviser le message à envoyer en blocs de k bits, puis

chaque bloc de taille k sera codé avec un mot-code de n bits avec n > k Code à répétition
pour introduire de la redondance
Dans notre exemple du code à répétition :
◮ Il faut dans ce cas définir M mots-code avec :
011000 −→ 0 1 1 0 0 0 −→ 000 111 111 000 000 000
M = 2k
◮ On divise en blocs de taille 1, et on affecte à chaque bloc un mot-code de taille 3
◮ Le taux (ou rendement) du code vaut dans ce cas :
◮ On a considéré 2 mots-code de longueur 3
log2 (M) k C = {000, 111}
R= =
n n
◮ (2, 3)-code avec un rendement R = 1
3
◮ R peut donc être interprété comme un débit d’information. Sur les n bits
envoyés sur le canal, il n’y en a symboliquement que k qui contiennent de
l’information : les n − k autres sont juste de la redondance.

Laurent Oudre Théorie de l’information 2017-2018 35 / 46 Laurent Oudre Théorie de l’information 2017-2018 36 / 46
 Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal

(M, n)-code : règle de décodage (M, n)-code : règle de décodage

Code à répétition

Dans notre exemple du code à répétition :

◮ A la sortie du canal, à cause des erreurs, le récepteur reçoit un message de ◮ On a Y = X = {0, 1}
taille n, mais qui n’est plus nécessairement celui qui a été envoyé.
◮ Lorsqu’on reçoit un message de 3 bits, on compte le nombre de 0 et de 1.
◮ Il appartient maintenant à Y n et non à X n ! Et ce n’est plus nécessairement ◮ Si on a plus de 0 que de 1, on suppose qu’on a envoyé le bit 0, associé au
un des mots-code de C mot-code 000.
◮ On introduit une règle de décodage, associant à chaque élément de Y n un ◮ Idem pour 1.
mot-code de C ◮ On a donc :

000 → 000, 001 → 000, 010 → 000, 100 → 000

Φ: Yn 7→ C
110 → 111, 011 → 111, 101 → 111, 111 → 111
!

y 7 → x̂ = Φ y
◮ La règle de décodage est donc :
   111 si nombre de 1 dans y > nombre de 0 dans y
Φ y =
000 si nombre de 0 dans y > nombre de 1 dans y

Laurent Oudre Théorie de l’information 2017-2018 37 / 46 Laurent Oudre Théorie de l’information 2017-2018 38 / 46

Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal

(M, n)-code : probabilité d’erreur (M, n)-code : probabilité d’erreur

◮ On considère un mot-code x ∈ C, qui à la sortie du canal devient y ∈ Y n . La

probabilité d’erreur associée à x est la probabilité qu’il y ait une erreur lors de Code à répétition
son décodage donc la probabilité :
X Dans notre exemple du code à répétition :
!

Perr (x) = pY |X y |x ◮ Perr (000) = pY |X (110|000) + pY |X (001|000) + pY |X (101|000) + pY |X (111|000)
n
y ∈Y
◮ Or : pY |X (110|000) = pY |X (1|0) 2 pY |X (0|0) = p 2 (1 − p)


Φ(y )6=x
◮ Si on suppose que la probabilité d’erreur sur un bit est p = 0.1, on a

◮ On peut également définir une probabilité d’erreur maximale comme étant : max
Perr (000) = Perr (111) = Perr = 0.028

max
Perr = max Perr (x i )
1≤i ≤M

Laurent Oudre Théorie de l’information 2017-2018 39 / 46 Laurent Oudre Théorie de l’information 2017-2018 40 / 46
 Deuxième théorème de Shannon (hors programme) Quelques notions de codage canal Deuxième théorème de Shannon (hors programme) Deuxième théorème de Shannon

Utilisation des (M, n)-codes Exemple introductif

◮ Un choix astucieux d’un (M, n)-code et d’une règle de décodage peut

permettre de diminuer ou d’annuler la probabilité d’erreur maximale ◮ On considère un canal sans mémoire de capacité C , et un (M, n)-code C de
taux R, qui permet d’avoir une probabilité d’erreur maximale nulle.
◮ La probabilité d’erreur n’est cependant pas le seul critère lorsque l’on conçoit
un codage canal. ◮ Supposons (pour simplifier) que les mots-code x 1 , . . . , x M sont équiprobables
◮ Il faut également faire en sorte que le taux R du code ne soit pas trop faible. ◮ On va s’interesser à la transmission d’un mot-code le long du canal
Par exemple, si pour annuler la probabilité d’erreur il faut envoyer 1010 bits ◮ Notons X ∈ C la variable aléatoire associée à l’entrée du canal et Y ∈ Y n
au lieu de 3, cela n’est plus rentable du point de vue télécommunications. celle associée à la sortie du canal
◮ Le but est donc d’avoir un code avec le taux le plus élevé possible, et ◮ Calculons I (X ; Y ) pour évaluer l’information contenue à la fois dans X et
permettant tout de même d’annuler la probabilité d’erreur dans Y
◮ Malheureusement, ceci n’est pas toujours possible...

Laurent Oudre Théorie de l’information 2017-2018 41 / 46 Laurent Oudre Théorie de l’information 2017-2018 42 / 46

Deuxième théorème de Shannon (hors programme) Deuxième théorème de Shannon Deuxième théorème de Shannon (hors programme) Deuxième théorème de Shannon

Exemple introductif Exemple introductif

I (X ; Y ) = H(X ) − H(X |Y )

◮ Comme la probabilité d’erreur maximale est nulle, il ne reste aucune

◮ Dans cet exemple on a vu que si l’on veut annuler la probabilité d’erreur
incertitude sur X lorsque l’on connait Y : maximale, le taux du code R ne peut pas dépasser C .
◮ La capacité peut donc s’interpréter comme le taux maximal permettant de
H(X |Y ) = 0 définir un code et une règle de décodage annulant la probabilité d’erreur
maximale
◮ Comme tous les mots-code de C sont équiprobables, on a :
◮ Nous avions vu que le taux d’un code pouvait être interprété comme un débit
H(X ) = log2 (M) = n × R d’information
◮ On retrouve donc ici un des résultats du deuxième théorème de Shannon : la
◮ D’après ce que nous avons vu au début du cours sur la transmission d’un capacité d’un canal correspond au débit maximal d’information permettant
message de n bits sur un canal discret sans mémoire, on a : d’annuler la probabilité d’erreur maximale
I (X ; Y ) ≤ n × C

◮ On a donc :
R≤C
Laurent Oudre Théorie de l’information 2017-2018 43 / 46 Laurent Oudre Théorie de l’information 2017-2018 44 / 46
 Deuxième théorème de Shannon (hors programme) Deuxième théorème de Shannon Deuxième théorème de Shannon (hors programme) Deuxième théorème de Shannon

Deuxième théorème de Shannon Interprétation

Deuxième théorème de Shannon ou Théorème du codage canal (HP) ◮ Contrairement au premier théorème, la démonstration de ce théorème (hors
programme) ne fournit aucun indice sur comment construire un tel code...
◮ Étant donné un réel ǫ > 0, un canal discret sans mémoire de capacité ◮ On découvre ici une deuxième interprétation du terme de capacité : le canal
C et un réel R < C , il est possible de construire un code de taux (ou
n’est pas capable de transmettre sans erreur avec un taux supérieur à C
rendement) R et une règle de décodage Φ, tels que :
◮ En pratique, pour annuler réellement la probabilité d’erreur, il faut considérer
max des valeurs extremement élevées de n, qui ne sont donc pas implémentables
Perr <ǫ
dans la pratique
◮ Corollaire : Étant donné un canal discret sans mémoire de capacité C , ◮ Le deuxième théorème de Shannon décrit donc plutot des propriétés
il n’existe aucun code de taux (ou rendement) R > C permettant asymptotiques que des résultats utilisables dans la vie réelle
d’avoir
max ◮ Néanmoins, il founit des bornes utiles pour évaluer les performances des
Perr =0
codes détecteurs et correcteurs d’erreurs.

Laurent Oudre Théorie de l’information 2017-2018 45 / 46 Laurent Oudre Théorie de l’information 2017-2018 46 / 46