Introduction Aux Communications Numériques

ait connaître avant la transmission L’incertitude au niveau du récepteur s’est réduite quand l’information a été reçue. L’information est donc associée à la stochasticité/aléatoirité de l’événement. Exemples :

un événement déterministe ne contient aucune information un événement probabiliste en communications : un train binaire produit par un flux audio/vidéo, etc.

Philippe Ciblat

Introduction aux communications numériques

5 / 37

Introduction Théorie de l’information Conception d’un système

Fonction mesurant l’information

L’information portée par l’événement scalaire S = s doit vérifier les propriétés intuitives suivantes : I(S = s) doit décroire de manière monotone quand la probablité P(S = s) augmente. I(S = s) = 0 quand P(S = s) = 1. I(S = s) doit être une fonction continue de P(S = s). Si deux événements indépendants S1 = s1 et S2 = s2 sont observés, alors l’information totale reçue vaut I(S1 = s1 ) + I(S2 = s2 ) ⇒ I(S = s) = − log2 (P(S = s)) = log2 1 P(S = s)

Philippe Ciblat

Introduction aux communications numériques

6 / 37

Introduction Théorie de l’information Conception d’un système

Entropie (discrète)

Soit X une variable aléatoire discrète scalaire prenant les valeurs dans {x1 , · · · , xM }. On note pm = P(X = xm ). L’information contenue dans la v.a. X , nommée entropie, est la moyenne de celle présente dans chaque événement Entropie

M

H(X ) = Ex [I(X = x )] = −

m=1

pm log2 (pm )

Base 2 du logarithme : bits d’information par symbole de source émis (si X est un N-vecteur, alors H(X ) = Ex [I(X = x )]/N) Entropie ne dépend que de

M

p(x ) =

m=1

pm δ(x − pm )

La valeur sémantique de la source n’a aucune importance en théorie de l’information.

Philippe Ciblat Introduction aux communications numériques 7 / 37

Introduction Théorie de l’information Conception d’un système

Exemples

Source binaire : A = {0, 1} avec P(X = 0) = p et P(X = 1) = 1 − p. Alors H(X ) = −p log2 (p) − (1 − p) log2 (1 − p)

1 0.9 0.8 0.7 Entropie (bits/symbol) 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.1 0.2 0.3 0.4 0.5 Probabilite p 0.6 0.7 0.8 0.9 1

Source quaternaire : A = {a, b, c, d} avec P(X = a) = 1/2, P(X = b) = 1/4, P(X = c) = 1/8 et P(X = d) = 1/8. Alors H(X ) = 1, 75

Philippe Ciblat Introduction aux communications numériques 8 / 37

Introduction Théorie de l’information Conception d’un système

Autres entropies

Entropie conjointe : soient X1 , · · · , Xn des variables aléatoires. H(X1 , · · · , Xn ) = −

x1 ∈A1

···

xn ∈An

p(x1 , · · · , xn ) log2 (p(x1 , · · · , xn ))

Entropie conditionelle H(Y |X ) est l’information présente dans Y une fois que X a été observée et est donc connue. H(Y |X ) = = −EX [

y ∈Ay

p(y |x ) log2 (p(y |x ))] p(x , y ) log2 (p(y |x ))

−

x∈Ax y ∈Ay

Philippe Ciblat

Introduction aux communications numériques

9 / 37

Introduction Théorie de l’information Conception d’un système

Information mutuelle

Soit I(X ; Y ) l’information mutuelle qui correspond à l’information commune à X et Y . On peut montrer que I(X ; Y ) = H(X ) − H(X |Y )

.

H(X, Y )

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

H(Y ) H(X)

.

Exemple : Si Y = X , alors I(X , Y ) = H(X ) Si Y et X ind., alors I(X , Y ) = 0

Philippe Ciblat

Introduction aux communications numériques

10 / 37

Introduction Théorie de l’information Conception d’un système

Séquence typique

Soit X = [X1 , · · · XN ] un vecteur de variables aléatoires/séquence aléatoire i.i.d. d’entropie H(X ). Théorème Quand N → ∞, il y a approximativement 2NH(X ) valeurs probables de X sur les M N possibles. Exemple : Xn suit une loi binaire de paramètre p. Soit ζ l’ensemble des séquences composées de Np ’0’ et N(1-p) ’1’. La loi forte des grands nombres indique que seules ces séquences vont apparaitre On rappelle que n! ∝ (n/e)n pour n grand

N −(p log2 (p) Np card(ζ) = CN

+ (1 − p) log2 (1 − p))

H(X )

N! =2 = p!(N − p)!

Philippe Ciblat

Introduction aux communications numériques

11 / 37

Introduction Théorie de l’information Conception d’un système

Théorème de la compression

dès que la séquence est grande, on ne rencontre que des séquences typiques. le nombre de séquences typiques est de 2NH(X ) chaque séquence typique est représentable par H(X ) bits par symbole Théorème Si le nombre de bits par symbole utilisé pour représenter la source est inférieur à H(X ), il y a nécessairement perte d’information (théorie de la distorsion). Dans le contrainte, une compression sans perte est théoriquement réalisable. Soit la source quaternaire de la planche 8. On envoie C(1) = 0 , C(2) = 10 , C(2) = 110 et C(3) = 111 . La longueur moyenne est de 1,75 bits par symbole.

Philippe Ciblat Introduction aux communications numériques 12 / 37

Introduction Théorie de l’information Conception d’un système

Capacité de canal (I)

Définition La capacité d’un canal est égal au nombre maximal de bits d’information par utilisation de canal offrant une communication fiable (sans erreur). A une valeur de l’émetteur X correspond 2NH(Y |X ) séquences typiques au récepteur Le récepteur admet 2NH(Y ) séquences typiques Par conséquent 2NH(Y ) /2NH(Y |X ) séquences de l’émission sont discernables au récepteur Or 2NH(Y ) /2NH(Y |X ) = 2N(H(Y )−H(Y |X )) = 2NI(X ,Y ) , ce qui implique que on peut émettre I(X , Y ) bits par symbole sans faire d’erreur.

Philippe Ciblat

Introduction aux communications numériques

13 / 37

Introduction Théorie de l’information Conception d’un système

Capacité de canal (II)

Définition mathématique Soit C la capacité d’un canal, alors C = max I(X , Y )

p(X )

Théorème de la capacité Il existe un codage de taux d’information T et de longueur N tel que T < C pour lequel lim Pe = 0

N→∞

La limite fondamentale est le débit et non la performance Théorème non constructif (a priori entrelacement long nécessaire)

Philippe Ciblat

Introduction aux communications numériques

14 / 37

Introduction Théorie de l’information Conception d’un système

• Exemple : canal BSC (I)

Canal binaire symétrique

.

1−p

’0’ ’0’

p p

’1’