SUPPORT DE COURS

THEORIE DE L’INFORMATION
ET CODAGE CANAL

BEN HADJ SLAMA Larbi

SUPCOM

1
 Sommaire
Notions de théorie de l’information
• Entropie
• Codage source
• Capacité de canal

Codage détecteur et correcteur d’erreurs ou codage canal

• Introduction
• Codage convolutif
• Codage en bloc et codage cyclique

Principe des turbo-codes et du codage en treillis

Annexe : Rappel sur les structures algébriques des codes
Travaux dirigés
2
Notions de théorie de
l’information

3
 Introduction
Structure d ’une chaîne de communication :

Distorsion
Bruit aléatoire

Source Milieu de
d’information Emetteur Récepteur Destinataire
transmission

Message Signal Signal Message

émis émis reçu reçu

Canal

Source : sélectionne et transmet des symboles à partir d ’un alphabet donné

Canal : modifie le message émis (distorsion et bruit aléatoire)
Système statistique  Performance en terme probabiliste

4
 Théorie de l ’information
Méthodes à mettre en œuvre pour transmettre l’information
- le plus rapidement possible
- sans perte ou avec le minimum de perte (minimum d’erreurs)
- avec le minimum de coût (équipement, consommation d’énergie,…)

Critères contradictoires  faire un compromis selon l’application

Notions importantes
 Durée : fonction du nombre de symboles à transmettre et de la rapidité de transmission
Minimiser le nombre de symboles à transmettre et faire en sorte que chaque symbole
transporte sa charge maximale ( en terme de quantité d’information)
 Compression de données
Quelle est la limite de la compression de données?  Entropie de la source
 La rapidité se mesure par le débit d’information transmise
Quelle est la limite du débit de transmission avec une probabilité d’erreur aussi faible que
l’on désire?  Capacité de Canal
 Protéger l’information contre les imperfections de la chaîne de transmission et les
perturbations externes pour satisfaire à cette probabilité  Codage Canal
5
 Théorie de l’information

Concepts fondamentaux :
 mesure de l’information : liée à l’incertitude
 capacité de canal : aptitude du canal à faire passer la quantité
d ’information injectée en son entrée
 codage de l ’information :
- Codage source : techniques qui permettent d’adapter avec le
canal, l’information à transmettre à travers ce dernier
- Codage canal : techniques qui permettent d’affecter un certain
degré de protection de l’information à transmettre contre les
imperfections de la chaîne de transmission et les perturbations
externes

6
 Notion d’information
Considérons une expérience qui donne des résultats xi dans un ensemble X
Avant d’observer la valeur de X, il y a un certain degré d’incertitude, concernant la
valeur prise par X. Après l’observation de X, on reçoit l’information.

Incertitude Information

L’information est donc liée à la notion d’imprévisibilité ou d’incertitude

• Evénement xi de probabilité p(xi) : plus la réalisation de l’évènement est
improbable (p(xi) faible), plus elle contient de l’information

• Cas extrêmes:

 Evènement certain : p(xi)=1  quantité d’information nulle

 Evènement impossible : p(xi)=0  quantité d’information infinie

7
 Mesure quantitative de l’information

• La quantité d’information obtenue par la réalisation de l’évènement xi

est fonction de sa probabilité p(xi) et sera notée h(xi) ou I(xi).
• h(xi) est une fonction f(p(xi)) qui doit satisfaire les hypothèses suivantes:
– f(p(xi)) ≥0
– f(p(xi)) est continue en p(xi)
– Si les évènements xi et xj sont indépendants alors l’information
obtenue à partir de la réalisation simultanée de xi et xj doit être égale
à la somme de f(p(xi)) et f(p(xj))

f(p(xi , xj ))= f(p(xi))+ f(p(xj))

8
 Mesure quantitative de l’information
• Théorème : Une fonction définie pour tout 0 < p  1 satisfait les trois
hypothèses précédentes si et seulement si elle est de la forme

 1 
f ( p( x i ))  C log   où C est une constante positive
 p( x i )

 On définit ainsi la quantité d’information appelée : information

intrinsèque apportée par la réalisation de l’évènement xi, par :

 1 
h( x i )  log     log( p( x i ))
 p( x i ) 

La base du logarithme définit l’unité d’information :

base 2 : bit (binary unit) ou Sh (Shannon )
base e : nat (natural unit)
base 10 : Hartley

9
 Propriétés de l’information intrinsèque

• Information intrinsèque par paire de deux événements xi et yj de

probabilité conjointe p(xi ,yj ) :
h(xi ,yj )=-log(p(xi ,yj ))

• Information conditionnelle de xi sachant yj

h(xi /yj )=-log(p(xi / yj ))

c ’est la quantité d’information restante sur xi après l’observation de yj.

• si xi et yj sont indépendants
h(xi /yj )= h(xi)

10
 Notion d’entropie

• X Source discrète, aléatoire, finie et stationnaire

• Alphabet généré : x1,…..,xN avec des probabilités respectives p1,…..,pN
telles que : N
 pi 1
i 1
N
Entropie : quantité d’information moyenne H(X)  Eh (X)   p i log( p i )
i 1

Exemple1 : Source binaire

X={0,1}, p=P(X=0)

 1   1 
H ( X )  P ( X  1 ) log   P ( X  0 ) log 
 P( X  1 )   P( X  0 ) 
  p log( p )  ( 1  p ) log( 1  p )

Exemple 2 : X={a, b, c, d}
P(a)=1/2, P(b)=1/4, P(c)=P(d)=1/8
H(X)=? 11
 Notion d’entropie
• Débit d’information:
Si le débit de transmission des symboles de la source X d’entropie H(X) a pour valeur r
(symboles/secondes), le débit d’information R de la source X est
R = r H(X) (bits/s)
• Entropie conjointe de la variable aléatoire (X,Y)

 
N M
H ( X ,Y )  E h( X ,Y )     p( x i , y j ) log p( x i , y j )
i 1 j  1

• Entropie conditionnelle de la variable aléatoire (Y/X=xi)


H (Y X  x i )  E h(Y X  x i )    p( y j / x i ) log p( y j x i ) 
M

j 1

C’est la quantité d’information moyenne obtenue en observant Y tout en ayant X=xi.

12
 Notion d’entropie

Entropie conditionnelle de Y sachant X

N
H( Y X )   p( x i )H( Y X  x i )
i 1

/ x i )logp( y x i )
N M
   p( x i ) p( y j j
i 1 j 1

)logp( y x i )
N M
    p( x i , y j j
i 1 j 1

 Graphiquement
H(Y) H(X/Y)
H(X)

X X Y X Y
Y

H(Y/X) H(X,Y)

X Y 13
X Y
 Notion d’entropie
Exemple:
X et Y deux v.a. dont la distribution conjointe est la suivante:

1 2 3 4
Y X

1 1/8 1/16 1/32 1/32

2 1/16 1/8 1/32 1/32

3 1/16 1/16 1/16 1/16

4 1/4 0 0 0

Calculer, H(X), H(Y), H(Y|X) et H(X |Y)

14
 Propriétés de l’entropie
• 0  H(X)  log(N) , N : cardinal de X

• H(X) = log(N) , pour une distribution uniforme

Relations entre entropie conjointe et conditionnelle

• H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X|Y)

• H(Y|X)  H(Y), on n’a l’égalité que si X et Y sont indépendantes

• H(X,Y)  H(X)+H(Y)

• H(X,Y) =H(X)+H(Y) si X et Y sont indépendantes

n
• H ( X 1 , X 2 ,..., X n )   H ( X i X i 1 ,..., X 1 )
i 1
n
• H ( X 1 , X 2 ,..., X n )   H( X i )
i 1

15
 Codage Source
Position du problème

Source S Canal
alphabet à
? Entrée: alphabet X de Q symboles
Destination
N symboles M: matrice de transition
Sortie: alphabet Y de U symboles

En général : Q<N  impossible d ’injecter directement les messages de la source

sur le canal
 intercaler un codeur  codage source
• Code C={c1, c2, ….., cN} : sous ensemble de l ’ensemble des mots de longueur
finie formés avec les symboles (Q-aires) de l’entrée du canal :
 ck de longueur nk
 Codage : symbole source sk  mot de code source ck
 Décodage : ck  sk

16
 Codage Source

• Le codage de source essaie de représenter le plus efficacement une source

• Assigner des mots de code plus courts aux évènements les plus fréquents et des
mots de code plus longs pour les évènements rares (e.g. code Morse)
• Types de codage :
- sans perte (données, texte,…)
- avec perte (voix, image,…)
• Types de codes:
- longueur fixe (ASCII,…)
- longueur variable (Morse, Braille, …)
• Le codage dépend du modèle de la source
• Cas binaire:

Séquence Codeur Source Séquence Canal à

Source
symboles Binaire entrée binaire
binaire
17
 Définitions et Propriétés
Phrases: Soit S={s1,s2,…sn} un ensemble fini non vide appelé alphabet. Une phrase ou
un mot sur S est une séquence finie d’éléments de S.
Si une phrase est de la forme z=xy, on dit que x est un préfixe de z.

Code: Un code est un ensemble de phrases sur un certain alphabet.

Code non singulier ( régulier) : à chaque mot de code on associe un seul message :
si sj alors ci cj
Exemple : A=0 , B=10 , C=001
Problème : texte : 0010 c’est CA ou AAB ?

Code déchiffrable (séparable ou à décodage unique) : code où toute suite de mots ne

correspond qu’à un seul massage

Code instantané: un mot peut être décodé instantanément, sans utilisation de

renseignements fournis par la suite du texte

Code préfixe ou irréductible si aucun mot de code n’est le préfixe d’un autre (ne
constitue le début d’un autre)
Remarque : Une condition nécessaire et suffisante pour qu’un code soit un code
instantané est qu’il soit préfixe.
18
 Définitions et Propriétés

 Bilan:
Codes non singuliers
( réguliers)
Codes
Codes déchiffrables
Codes
instantanés

 Exemples :
source Code A Code B Code C Code D Code E A : est un code singulier

s1 0 0 00 0 0 B : non singulier mais non déchiffrable

s2 11 11 01 10 01 C : non singulier et déchiffrable ( même longueur)

s3 00 00 10 110 011 D : non singulier, déchiffrable et instantané

s4 11 01 11 1110 0111 E : non singulier, déchiffrable mais pas instantané

19
 Définitions et Propriétés
• Inégalité de Mac Millan: Condition nécessaire et suffisante d’existence d ’un code
déchiffrable de N mots à symboles Q-aires (les éléments du mot pouvant prendre
leurs valeurs dans {0,1,… Q-1} ) de longueurs respectives n1,n2,…,nN:
N
 Q n k
1
k 1

• Inégalité de Kraft : Condition nécessaire et suffisante d’existence d ’un code

instantané de N mots à symboles Q-aires de longueurs respectives n1,n2,…,nN :
N
 Q n k
1
k 1

Exemples : Code ternaire (Q=3) : peut on construire un code instantané avec :

Ex1 1 mot de longueur 1 Ex2 1 mot de longueur 1

5 mots de longueur 2 6 mots de longueur 2
2 mots de longueur 3 2 mots de longueur 3
2 mots de longueur 4 1 mot de longueur 4
20
 Définitions et Propriétés
Longueur moyenne d ’un code : N
n  n
k 1
k pk

• n doit être la plus faible possible.

• Plus petite valeur possible ?  n optimale
• Pour des codes déchiffrables, n optimale est bornée par :

H (S ) H (S )
n 1
log Q  log Q 

• Cas binaire : H( S )  n  H( S )  1
Code compact : Un code déchiffrable est dit compact (relativement à la source S) si sa longueur
moyenne est inférieure ou égale à tout autre code déchiffrable de la même source et avec le
même alphabet.
H( S )
Code optimal : C’est le code de longueur moyenne satisfaisant n 
logQ 
21
 Définitions et Propriétés
H( S )
• Rendement ou efficacité d’un code :  
n log( Q )

• Redondance : R=1-η

__
n
• Taux de compression : Rs 
log( N )

22
 Premier théorème de Shannon

Premier théorème de Shannon :

Pour toute source stationnaire, il existe un procédé de codage

déchiffrable pour lequel la longueur moyenne équivalente des mots est
aussi voisine que l’on veut de sa limite inférieure:
H( S ) H( S ) 1
Pour tout entier m :  n  
logQ logQ m

• Dans le cas où la source délivre des messages statistiquement

indépendants avec une distribution de probabilité identique d’un
message à un autre (source sans mémoire), il est possible de réduire la
longueur moyenne n des messages pour atteindre la limite inférieure :
H (S )
n 
log Q
• Construction ?
23
 Construction des codes préfixes

• Méthode de l’arbre : seuls les nœuds terminaux constituent des

mots code
0
1
x1 : 00
0 x1
x2 : 010
0 1 0
x2 x3 : 100
1
1 0 x4 : 110
0 x
1 3 x5 : 111
1 0
0 1 x6 : 11  non
x4
x6 ? 1 0 x6 : 101  oui
1
x5 x6 : 011  oui

24
 Méthode de Shannon-Fano
• Classer les éléments de la source par ordre de probabilité décroissante
• Diviser l’ensemble de ce messages en deux sous ensembles de
probabilité aussi proche que possible
• Attribuer 0 par exemple au premier et 1 au second
• Recommencer la subdivision

• Exemple :

xi x1 x2 x3 x4 x5 x6 x7 x8 x9
pi 0.49 0.14 0.14 0.07 0.07 0.04 0.02 0.02 0.01

25
 Méthode de Huffman
Procédure de codage systématique qui conduit toujours à un code instantané et
compact :
• ranger les n probabilités par ordre décroissant
• Reclasser les messages en fin du tableau {xn-1xn }de prob (pn-1 + pn) dans un
nouveau tableau
• Refaire jusqu’à ce qu’il ne reste que deux messages
• on revient en arrière en attribuant à chacun des deux derniers éléments des
tableaux construits (0,1)
• déduire les valeurs attribuées à chaque éléments

• Exemple :

xi A B C D E F
pi 0.40 0.25 0.15 0.09 0.07 0.04

26
 Procédure de Huffman
0.40 A 0.25 B 0.15 C 0.09 D 0.07 E 0.04 F

0.40 A 0.25 B 0.15 C 0.09 D 0.11

E F

0.40 A 0.25 B 0.15 C 0.11 0.09 D

E F

0.40 A 0.25 B 0.20 0.15 C

0.11 0.09 D

E F
27
 Procédure de Huffman
0.40 A 0.35 0.25 B

0.15 C
0.20

0.11 0.09 D 0 1

E F
A: 1 0
1 A
B: 00
B
C: 011 1
0
D: 0101
C
E: 01000
F: 01001 0 1

La longueur moyenne d’un mot de code D

est 2.32. L’entropie =2.2063 0 1
28
E F
 Exemple

On dispose d’une source X sans mémoire délivrant des symboles xi avec

des probabilités pi comme c’est indiqué dans le tableau ci-dessous.
 Calculer l’entropie de la source X
 Faire le codage selon Huffman puis Shannon-Fano
 Calculer l’efficacité de chaque code obtenu
 Conclure.

xi A B C D E F G H

pi 0.40 0.18 0.1 0.1 0.07 0.06 0.05 0.04

29
 Annexe

Codage source
&
Compression

30
 Autres types de codage source
Codes d’ Huffman adaptatifs Souvent, on ne connaît pas les fréquences (probabilités) d
chaque symbole avant d’avoir entièrement lu le message à transmettre. Pour éviter
d’effectuer un codage à deux passes (peu efficace), la méthode développe un code
d’Huffman basé sur les statistiques des symbole déjà lus. Il faut faire cela en minimisant
les calculs pour mettre à jour l’arbre lorsqu’un nouveau symbole est lu et donc les
fréquences changent.
Code RLE (Run Length Encoding) Un run est une suite de valeurs toutes égales entre
elles.
Principe : Si une donnée d apparaît n fois consécutives, alors remplacer d...d {n fois} par
nd.
Compression de texte par RLE : la chaîne "attendre 2 secondes avant de passer "
devient "a2tendre 2 secondes avant de pa2ser " (ambigu, pas de gain)
Avec un meta-symbole @ : "a@2tendre 2 secondes avant de pa@2ser« (pas ambigu,
mais perte)
Il convient de remplacer seulement les occurrences de 3 répétitions, ou plus.
Application : texte et image 31
 Autres types de codage source
Codage arithmétique: Contrairement aux deux algorithmes précédents, le code est associé à la
séquence et non à chaque symbole pris individuellement. On associe à chaque symbole à coder un
intervalle [ak,bk [ de [0,1[ On itère ce processus jusqu'à ce que toute la séquence soit traitée. La
séquence est alors codée par un réel de l'intervalle [0,1[
Algorithme de codage : Cet algorithme comporte 5 étapes successives :
1- On initialise l'intervalle de codage [ac,bc[ avec les valeurs ac=0 et bc=1, cet intervalle a une
largeur L=bc-ac=1
2- cet intervalle est partitionné en N sous-intervalles ( N nombre de symboles de l'alphabet de la
source) proportionnellement aux probabilités p(sk) de chaque symbole sk. cette partition est
constituée de sous-intervalles [ak,bk[ tels que : bk-ak=p(sk)
avec ak=ac+largeur x∑i=1k1p(si) et bk=ac+largeur x∑i=1kp(si)
3- On choisit le sous-intervalle correspondant au prochain sk à coder dans la séquence et on met
à jour les valeurs ac et bc de la manière suivante :ac=ac+largeur x ak et bc=ac+largeur x bk
4- Avec le nouvel intervalle [ac,bc[ on recommence le processus de l'étape 2.
5- Les étapes 2,3 et 4 sont répétés jusqu'à épuisement des symboles de la séquence et
obtention du dernier intervalle [ac,bc[
La représentation binaire de tout réel xc de l'intervalle [ac,bc[ est un code de la séquence.

32
 Autres types de codage source

Codage par dictionnaire

Lempel-Ziv 1977 (LZ77)
La compression LZ77 remplace des motifs récurrents par des références à leur première
apparition. Elle donne de moins bons taux de compression que d'autres algorithmes (PPM, CM),
mais a le double avantage d'être rapide et asymétrique (c'est-à-dire que l'algorithme de
décompression est différent de celui de compression, ce qui peut être exploité pour avoir un
algorithme de compression performant et un algorithme de décompression rapide).
LZ77 est notamment la base d'algorithmes répandus comme Deflate (ZIP, gzip) ou LZMA (7-Zip,
xz)
Lempel-Ziv 1978 et Lempel-Ziv-Welch (LZ78 et LZW)
LZW est basée sur la même méthode, mais Welch a constaté que, en créant un dictionnaire
initial de tous les symboles possibles, la compression était améliorée puisque le décompresseur
peut recréer le dictionnaire initial et ne doit donc pas le transmettre ni envoyer les premiers
symboles. Elle a été brevetée par UNISYS et librement utilisée actuellement (norme de
compression internationale pour les modems).
La compression Lempel-Ziv-Welch est dite de type dictionnaire. Elle est basée sur le fait que
des motifs se retrouvent plus souvent que d'autres et qu'on peut donc les remplacer par un
index dans un dictionnaire. Le dictionnaire est construit dynamiquement d'après les motifs
rencontrés.

33
 Compression

Compression sans perte ou compactage

La compression est dite sans perte lorsqu'il n'y a aucune perte de données sur l'information d'origine. Il y a
autant d'information après la compression qu'avant, elle est seulement réécrite d'une manière plus concise
(c'est par exemple le cas de la compression gzip pour n'importe quel type de données ou du format PNG pour
des images synthétiques destinées au Web).
L'information à compresser est vue comme la sortie d'une source de symboles qui produit des textes finis selon
certaines règles. Le but est de réduire la taille moyenne des textes obtenus après la compression tout en ayant
la possibilité de retrouver exactement le message d'origine.
Il n'existe pas de technique de compression de données sans perte universelle, qui pourrait compresser
n'importe quel.
Les formats de fichier de compression sans perte sont connus grâce à l'extension ajoutée à la fin du nom de
fichier (« nomdefichier.zip » par exemple), d'où leur dénomination très abrégée.
Les formats les plus courants sont :
7z, ace, arc, arj, bz, bz2 ,CAB (utilisé par Microsoft) ,gzip, gz (qui est un fichier à une seule entrée)
Lzh, rar, RK, uha, xz, Z (surtout sous Unix), Zip, zoo, APE (pour les flux audio), FLAC (pour les flux audio)

Les standards ouverts les plus courants sont décrits dans plusieurs RFC :
RFC 1950 (ZLIB, flux de données compressées)
RFC 1951 (système de compression par blocs « Deflate », utilisé par Zip et gz)
RFC 1952 (format de fichier compressé gzip)

34
 Compression
Compression avec pertes : La compression avec pertes ne s'applique qu'aux données «
perceptibles », en général sonores ou visuelles (audio, image, vidéo), qui peuvent subir une
modification, parfois importante, sans que cela soit perceptible par un humain. La perte
d'information est irréversible( compression irréversible ou non conservative).
• Les techniques sont donc spécifiques à chaque média et ne sont pas utilisées seules mais
combinées pour fournir un système de compression performant
• Ces techniques sont fondées sur le fait que seul un sous-ensemble très faible de toutes les
images possibles possède un caractère exploitable et informatif pour l'œil. Ce sont donc ces
images-là qu'on va s'attacher à coder de façon courte.
• Les programmes de compression s'attachent à découvrir ces zones et à les coder de la façon
aussi compacte que possible. La norme JPEG 2000, par exemple, arrive généralement à coder
des images photographiques sur 1 bit par pixel sans perte visible de qualité sur un écran, soit
une compression d'un facteur 24 à 1.
• De même, seul un sous-ensemble très faible de sons possibles est exploitable par l'oreille, qui a
besoin de régularités engendrant elles-mêmes une redondance . Un codage éliminant cette
redondance et la restituant à l'arrivée reste donc acceptable, même si le son restitué n'est pas en
tout point identique au son d'origine.
• On peut distinguer trois grandes familles de compression avec perte :
Les formats MPEG sont des formats de compression avec pertes pour les séquences vidéos.
Ils incluent à ce titre des codeurs audio, comme les célèbres MP3 ou AAC, qui peuvent
parfaitement être utilisés indépendamment, des codeurs vidéos 35
 Compression
•Compression des images
Une image est représentée par une collection (matrice 2D) de pixels, chaque pixel étant décrit par
un entier unique (plages de gris ou adresse dans une table de sélection de couleurs) ou par
plusieurs entiers (composantes RVB, ou luminance et chrominances)
La norme JPEG (Joint Photographics Expert Group) a été adopté en 1992 et utilise deux étapes
dans la compression:
1°Une transformation cosinus discrète appliquée sur des blocs de 8×8 pixels sur chaque
composante de l'image (luminance Y, chrominance U, chrominance V) et donne 64 coefficients de
fréquence par composante.
2°Les coefficients TCD sont divisés par des valeurs présentes dans une table de quantification et
les valeurs sont arrondies à des entiers. C'est dans cette étape que certaines informations sont
éliminées.
3°Les coefficients obtenus à l'étape antérieure sont comprimés par un algorithme de Huffman
dynamique (adaptatif) à partir de tables de codes connues (afin d'éviter le stockage d'un en-tête
pour chaque bloc)
36
 Compression

•Compression des sons

Les sons sont représentés par une suite d'échantillons obtenus à une certaine cadence (par
exemple, pour les CD audio la fréquence d'échantillonnage est de 44 KHz et les échantillons
sont codés sur 16 bits).
Méthode PASC (Precision Adaptive Sub-band Coding): la compression se déroule selon les
étapes suivantes :
1°Le signal subit une division spectrale sur 32 bandes de 750 Hz de largeur et sur chacune on
calcule le niveau moyen.
2°En utilisant les connaissances sur les courbes dynamiques d'audibilité, on détermine dans
quelles bandes le signal peut être éliminé.
3°Dans chaque bande retenue, le signal est codé en utilisant un nombre variable de bits
répartis entre les sous-bandes selon la différence entre le niveau de la sous-bande et le niveau
moyen dans la bande.

37
Capacité d’un canal

38
 Information mutuelle

Exemple : Entrée : X Sortie : Y

Canal
p(xi)=P(X=xi) : probabilité a priori de xi
p(yj /xi) : probabilité de transition du canal
p(xi|yj) la probabilité a posteriori que xi ait été émis sachant que yj a été reçu
Information mutuelle entre messages xi et yj : quantité d’information fournie sur
l’événement X=xi par l ’apparition de Y=yj


I ( xi ; y j )  log 
 
 p xi y j 
  
 p xi , y j 
 log    h( xi )  h( xi y )
p ( xi )   p( xi ) p( y j )  j
   
Information mutuelle entre l’entrée et la sortie du canal (Quantité d’information
transmise à travers le canal) :
I( X ,Y )    p( x i , y j ) I( x i ; y j ) H(X|Y) H(Y|X)
i j

 H( X )  H( X /Y )  H( Y )  H( Y / X )
H(X) H(Y)
H(Y/X) : entropie a posteriori
I(X,Y)
39
 Canal discret sans mémoire

• Entrée: V. A discrète dont l ’alphabet est : X={x1, x2, . . . , xQ}

• Sortie : V. A discrète dont l ’alphabet est : Y={y1, y2, . . . , yR}

• Matrice de transition M=[mij] avec :

mij  p j i  P(Y  y j X  xi )

• Canal sans mémoire : La sortie à l’instant t ne dépend que de

l’entrée à cet instant là
• Canal Binaire Symétrique (BSC) : diagramme en treillis

0 1-p 0
p p : probabilité d ’erreur
Entrée Sortie du canal BSC
p
1 1
1-p

40
 Capacité d’un canal
• Définition : Quantité d'information maximale moyenne pouvant
être transmise à travers le canal ( que chacun de ses symboles
d'entrée peut apporter en sa sortie)
C  max I X ; Y 
• Exemple d ’un BSC :
I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)
• Probabilités de X : p1 et p2 (p2 = 1-p1)
• Matrice de transition
1  p p  q p
    
 p 1  p  p q 

• H(Y/X)=-plog(p)-(1-p)log(1-p) : dépend uniquement du canal

•  C correspond à H(Y) max.  P(Y=0)=P(Y=1)=1/2
•  C=1+plog p +(1-p)log (1-p)

41
 Entropie d'une source continue sans mémoire

Entropie différentielle : On cherche à généraliser la notion d'entropie :

1
En discret : H( X )  
i
pi
pi
log( )

Pour passer du discret au continu, il suffit de faire la correspondance : pi → p(xi) dx en

recherchant la limite lorsque dx → 0 :

 1
h( X )  lim  p( x i )dx log( )
dx  0 i    p( x i )dx

 1   
 1 
  p( x ) log   dx  lim  p( x i )dx log( dx )   p( x ) log   dx  lim log( dx )
-  p( x ) dx  0 i    -  p( x ) dx  0

Un problème provient du second terme car il tend vers -∞ et donc H( X ) → +∞

⇒ l'entropie d'une variable aléatoire continue est infinie.

Ce résultat est intuitif car une variable aléatoire continue peut prendre une infinité de valeurs sur
IR et cela implique que la probabilité sur une valeur tend vers 0 et donc l'entropie vers l' ∞.

42
 Entropie d'une source continue sans mémoire

• Pour contourner ce problème, on envisage d'utiliser l'entropie non en absolu mais pour
comparer deux sources.
• On travaille ainsi en relatif en effectuant des différences d'entropies et dans ce cas seul le
premier terme est intéressant. Il est défini comme étant l'entropie différentielle Hd( X) d'une
source continue (notée aussi h(X))

 1 
H(X)   p( x )log dx  h( X )
 p( x
d
 )

• Rq. : Tous les calculs menés dans le cas discret restent valables en continu en utilisant les
entropies différentielles.

43
 Entropie d'une source continue sans mémoire

Maximum de l'entropie différentielle d'une source : Quelle est la loi de probabilité

p( x ) pour laquelle l'entropie différentielle est maximale ?
• p( x ) est une densité de probabilité et elle a deux caractéristiques ou deux
contraintes :


 la règle classique :  p(
-
x ) dx  1


 la variable aléatoire a une moyenne µ et une variance σ2 soit : (

-
x   )2 p( x ) dx   2

• C'est un problème d'optimisation sous contrainte ( multiplicateurs de Lagrange).

 La valeur optimale de p(x) est donc : p( x )  1  -(x -  )2 
exp 2

2 2
  
 l'entropie différentielle maximale d'une source continue est :
1
h( X )  log2 2e 2 
2
L'entropie différentielle d'une source continue sans mémoire est maximale
lorsque la source a une densité de probabilité gaussienne.
44
 Information mutuelle des sources continues
sans mémoire
Quantité d'information mutuelle : On ne prend qu'une quantité d'information
différentielle.
• Par généralisation du cas discret :
 p( x , y ) 
I( X ,Y )   p( x , y )log2   dx dy
 p
( x )p( y ) 
ou, en utilisant les densités de probabilité conditionnelles :
 p( y / x )
I( X ,Y )   p( y / x )p( x )log2   dx dy
 p( y ) 

• I(X,Y) = h(X) - h(X/Y) = h(Y) - h(Y/X)

45
 Capacité d’un canal continu à Bruit Blanc
Additif Gaussien
Hypothèses :
• signal reçu en sortie du canal : r(t) = x(t) + n(t) ,
où :
 x(t) : signal utile émis (aléatoire stationnaire), réel, de bande limitée B (support
spectral [-B ; +B]), de puissance moyenne finie P, de moyenne nulle.
 n(t) : bruit additif Gaussien, réel, stationnaire, centré (E{n(t)}= 0), indépendant du
signal x(t), blanc ( de DSP bi-latérale N0/2 constante pour f ∈ ] - ∞ ; + ∞ [ )

• Le signal x(t) ayant une bande limitée B, on peut travailler avec un modèle de signal
obtenu après filtrage passe-bas idéal de r(t) :
signal reçu après limitation de la bande à B : y(t) = x(t) + b(t) ,
où :
 b(t) : bruit additif Gaussien, réel, stationnaire, centré (E{b(t)}= 0), indépendant du
signal x(t), de DSP bi-latérale N0/2 constante pour f ∈ [ - B ; + B ] , donc de
puissance (ou variance) : σb 2 = N0.B.
46
 Capacité d’un canal continu à Bruit Blanc
Additif Gaussien
• Théorème d’échantillonnage : la connaissance de x(t) est équivalente à la donnée d’une suite
d’échantillons X de x(t), pris à la fréquence 2B (fréquence d’échantillonnage minimale respectant le
théorème d’échantillonnage). Pour traiter le cas d’un signal analogique (c’est à dire à amplitude et
temps continus), on peut donc se ramener au cas du signal continu en amplitude, mais discret en
temps :
• Modèle pour les échantillons : Y = X + Z,
Z : échantillons du bruit équivalents à une V.A. Gaussienne de moyenne nulle, de variance
(puissance du bruit) : σZ2= σb 2.
• Information mutuelle : I(X,Y) = Hd(Y) – Hd(Y/X),
• (Y = X + Z) et (X et Z indépendants) => Hd (Y/X) = Hd (Z)
d’où : I(X ;Y) = Hd (Y) – Hd (Z)

 Capacité : C  Max I(X,Y)   Max H(Y)

d  - H(Z)
d
p(x) p(x)

47
 Capacité d’un canal continu à Bruit Blanc
Additif Gaussien
• Le maximum de I(X ;Y) est obtenu pour une densité de probabilité sur X rendant Hd(X)
(et donc Hd (Y)) maximale .
On l’obtient pour :
 X : V.A. Gaussienne de moyenne nulle et de variance (puissance du signal) : σX2 .
 Y : V.A. Gaussienne de moyenne nulle et de variance (ou puissance) : σY 2 = σX 2 + σZ 2.

• En développant les calculs de l’entropie différentielle sur une distribution Gaussienne à

moyenne nulle , on vérifie facilement que:

1 1
H d( Y )  log2 2eY 2  et H d( Z )  log2 2e Z 2 
2 2

1 1 1   X2 
 C  log2 2eY 2
 - 2 log2 2e Z   2 log2  1   2
2


2  b 

48
 Capacité d’un canal continu à Bruit Blanc
Additif Gaussien

• La capacité par symbole (c’est à dire par échantillon à amplitude continue) peut ainsi s’exprimer
en fonction du rapport Signal à Bruit (RSB) à l’entrée, intégrée sur la bande du signal [-B ;B],
soit : RSB = P / N = P / (N0.B) :

1  P 
C  log2 
 1  
 sh/symb
2  N 0B 

• Un symbole étant émis tous les 1/(2B) sec, la quantité d’information maximale que le canal bruité
peut transmettre par seconde, qui correspond à la capacité Ct par seconde, est obtenue en
multipliant par la fréquence d’échantillonnage :

 P 
C  B log2  1  
 sh/s
 N 0B 

49
50