Exercices
Exercices
Exercices
Exercices et problèmes
Laurent Oudre
laurent.oudre@ens-paris-saclay.fr
1 Théorie de l’information 3
Schéma de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Calculs d’entropies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Divergence de Kullback-Leibler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Entropies conjointes et conditionnelles - Information mutuelle et information mutuelle conditionnelle 5
Propriété asymptotique d’équirépartition (AEP) . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Codage source 8
Classes de codes source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Inégalité de Kraft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Code de Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Codage source pour les nombres entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Codage canal 13
Principe du codage canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Inégalité de Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Calculs de capacités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Opérations sur les codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Bornes théoriques de codage et codes MDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Codes de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 Théorie du signal 19
Rappels sur l’analyse de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Produit de convolution et filtrage linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Distribution de Dirac et peigne de Dirac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Analyse spectrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Transformées de Fourier au sens des distributions . . . . . . . . . . . . . . . . . . . . . . . . . 23
Conversion analogique/numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Echantillonneur idéal et théorème de Shannon-Nyquist . . . . . . . . . . . . . . . . . . . . . . 26
5 Problemes 31
Problème 1 : Taux d’entropie d’un processus stochastique . . . . . . . . . . . . . . . . . . . . 31
Problème 2 : Autour de l’ensemble des séquences typiques . . . . . . . . . . . . . . . . . . . . 35
Problème 3 : Codes de Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Problème 4 : Deuxième théorème de Shannon ou Théorème du codage canal . . . . . . . . . . 40
Problème 5 : Identité de MacWilliams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Problème 6 : Echantillonnage et reconstruction physiquement réalisables . . . . . . . . . . . . . 46
Problème 7 : Capacités des canaux gaussiens réels . . . . . . . . . . . . . . . . . . . . . . . . 49
6 Séance de révisions 53
2
1 Théorie de l’information
Pour les applications numériques, on utilisera les approximations suivantes :
x 1 2 3 4 5 6 7 8 9 10
log2 (x) 0.0 1.0 1.6 2.0 2.3 2.6 2.8 3.0 3.2 3.3
Schéma de Shannon
Exercice 1.1 (♣). Probabilité d’erreur sur un paquet de bits. On considère un paquet de données
contenant 16 bits. On suppose que la probabilité d’erreur pour l’envoi d’un bit est de 0.1 et que les erreurs
sur les différents bits du paquet sont indépendantes.
2. Déterminer la probabilité que le nombre d’erreurs par paquet soit supérieure ou égale à 5. Pour cela
on donne ci-dessous les premiers termes de la loi de probabilité de Z :
z 0 1 2 3 4 5 6 7 ···
PZ (Z = z) 0.1853 0.3294 0.2745 0.1423 0.0514 0.0137 0.0028 0.0004 ···
Exercice 1.2 (♣). Probabilités d’erreur sur un canal bruité. On considère un système de communication
binaire bruité. On désigne par X la variable aléatoire associée à l’entrée et Y celle associée à la sortie du
système. On suppose que la probabilité qu’un 0 soit envoyé est de 0.75, que la probabilité de recevoir un
0 alors qu’un 0 a été envoyé est de 87 , et que la probabilité de recevoir un 1 alors qu’un 1 a été envoyé est
de 0.75.
4. Si l’on reçoit un 1, quelle est la probabilité qu’un 1 ait effectivement été envoyé ?
Calculs d’entropies
Exercice 1.3 (♣). Entropie d’une phrase. Calculer l’entropie de la phrase ENS_PARIS_SACLAY
3
Exercice 1.4 (♣). Sources d’entropie nulle. Soit X une source discrète avec un alphabet source X de
cardinal M . Lister toutes les distributions de probabilité pX telles que H(X) = 0 (entropie minimale)
Exercice 1.5 (♣♣♣). Entropie d’un jeu. On considère deux joueurs de même niveau qui jouent à un
jeu où le vainqueur est le premier qui remporte 4 parties. On note X la variable aléatoire représentant le
nombre de parties jouées jusqu’à une victoire : calculer H(X)
1. Montrer que
p2 p3 pM
H(p) = H(p1 , 1 − p1 ) + (1 − p1 )H , ,...,
1 − p 1 1 − p1 1 − p1
Exercice 1.7 (♣♣♣). Entropie d’un tirage à pile au face biaisé. On considère une pièce de monnaie
biaisée où p est la probabilité de faire face. On tire la pièce jusqu’à obtenir une face et on note X la
variable aléatoire correspondant au nombre de tirages nécessaires.
1. Calculer l’entropie de X.
Exercice 1.8 (♣♣♣♣). Stratégie de pesée basée sur l’entropie. On considère 12 boules dont l’une est
soit plus légère, soit plus lourde que les autres. On considère une balance qui permet de fournir les trois
informations suivantes: Le plateau gauche est plus lourd, Les deux plateaux font le même poids, Le plateau
droit est plus lourd. Concevoir une stratégie permettant, en un minimum de pesées de savoir quelle balle
a un poids différent des autres ET si elle est plus lourde ou plus légère.
4
Divergence de Kullback-Leibler
Exercice 1.9 (♣). Cas de symétrie. Donner un exemple de deux distributions de probabilité p et q
associées à une variable aléatoire binaire telle que p 6= q et DKL (p||q) = DKL (q||p)
2. Montrer que DKL (p||q) est convexe en la paire (p, q), c’est à dire que pour tout λ ∈ [0, 1],
DKL (λp1 + (1 − λ)p2 ||λq1 + (1 − λ)q2 ) ≤ λDKL (p1 ||q1 ) + (1 − λ)DKL (p2 ||q2 )
HH Y
HH 1 2 3 4
X HH
1 1 1 1
1 8 16 16 4
1 1
2 16 8 ??? 0
1 1 1
3 32 32 16 0
1 1 1
4 32 32 16 0
5
Compléter la valeur manquante, calculer les quantités H(X), H(Y ), H(X, Y ), H(Y |X), H(X|Y ) et
I(X; Y ) et les représenter sur un diagramme de Venn.
Exercice 1.12 (♣♣). Entropies de variables aléatoires à alphabets disjoints. On considère deux
variables aléatoires X et Y respectivement sur un alphabet X et Y. On suppose les deux alphabets
disjoints. On considère un réel 0 ≤ α ≤ 1 et la variable aléatoire Z définie par :
(
X avec la probabilité α
Z=
Y avec la probabilité 1 − α
Exercice 1.13 (♣♣). Une mesure de corrélation. Soient deux variables aléatoires discrètes X1 et X2
identiquement distribuées mais pas nécessairement indépendantes. On considère la quantité
H(X2 |X1 )
ρ=1−
H(X1 )
Montrer que 0 ≤ ρ ≤ 1 et préciser les cas extrêmes.
Exercice 1.14 (♣♣). Décroissante d’incertitude. On considère une variable aléatoire X sur un alphabet
X = {1, . . . , M }. On considère un ensemble S ⊆ X et on note α = P(X ∈ S). Calculer la décroissance
d’incertitude liée à la question Est-ce que x est dans S ?.
2. Montrer que I(X; Y ) est une fonction concave de pX (x) à pY |X (y|x) fixé, c’est à dire que pour
tout λ ∈ [0, 1], si I1 = I(X; Y ) avec (X, Y ) ∼ (p1 (x), p(y|x)), I2 = I(X; Y ) avec (X, Y ) ∼
(p2 (x), p(y|x)), alors I = I(X; Y ) avec (X, Y ) ∼ (λp1 (x) + (1 − λ)p2 (x), p(y|x)) vérifie
I ≥ λI1 + (1 − λ)I2
6
3. Montrer que I(X; Y ) est une fonction convexe de pY |X (y|x) à pX (x) fixé, c’est à dire que pour
tout λ ∈ [0, 1], si I1 = I(X; Y ) avec (X, Y ) ∼ (p(x), p1 (y|x)), I2 = I(X; Y ) avec (X, Y ) ∼
(p(x), p2 (y|x)), alors I = I(X; Y ) avec (X, Y ) ∼ (p(x), λp1 (y|x) + (1 − λ)p2 (y|x)) vérifie
I ≤ λI1 + (1 − λ)I2
Exercice 1.17 (♣♣♣). Quelques relations pour trois variables aléatoires formant une chaîne de
Markov. Soient X, Y , Z trois variables aléatoires formant une chaîne de Markov X → Y → Z. Montrer
que
1. Z → Y → X forment également une chaîne de Markov
3. H(X|Y ) ≤ H(X|Z)
4. I(X; Y ) ≥ I(X; Z) et I(Z; Y ) ≥ I(X; Z) (nous reverrons cette propriété comme étant le théorème
du traitement de l’information)
Exercice 1.18 (♣♣♣). Information mutuelle conditionnelle. Trouver des variables aléatoires binaires
X, Y , Z telles que :
1. I(X; Y |Z) < I(X; Y )
Exercice 1.19 (♣). Taille de l’ensemble des séquences typiques. On considère une source binaire sans
mémoire telle que pX (0) = 14 . Calculer approximativement la taille de l’ensemble des séquences typiques
de longueur n et montrer et la comparer à celle de l’ensemble des séquences possibles.
2. Pour n suffisamment grand, P (x̃1:n , ỹ1:n ) ∈ Tϵ (X, Y ) ≥ (1 − ϵ)2−n(I(X;Y )+3ϵ)
(n)
3. Comparer les résultats obtenus à ceux vus dans leQcours lorsque x̃1:n et ỹ1:n sont générées selon le
modèle source/canal sans mémoire (x̃1:n , ỹ1:n ) ∼ ni=1 pXY (xi , yi )
7
2 Codage source
1. Dire pour chacun de ces codes, s’ils sont non singuliers, déchiffrables et/ou instantanés.
Exercice 2.2 (♣♣♣). Code binaire instantanté optimal pour des symboles équiprobables On con-
sidère une source X sur un alphabet X à M éléments et où tous les symboles sont équiprobables.
1. Montrer que pour code binaire instantané optimal de cette source, le mot-code le plus long a au plus
un bit supplémentaire que le mot-code le plus court
Exercice 2.3 (♣♣♣). Codes binaires instantanés optimaux avec des mots-code de longueurs dif-
férentes Trouver une distribution de probabilité {p1 , p2 , p3 , p4 } avec pi > 0 telle qu’il existe deux codes
binaires instantanés optimaux qui assignent des longueurs différentes aux mots code.
1. Pour chacun des claviers, quelles sont les heures qui peuvent être codées sur deux symboles ? sur
trois symboles ?
8
2. Pour chacun des claviers, donner un horaire qui peut être codé sur quatre symboles alors que l’autre
clavier ne peut pas
3. Ces claviers sont-ils de bons encodeurs pour l’usage courant d’un micro-ondes ?
Inégalité de Kraft
Exercice 2.6 (♣♣♣). Inégalité de McMillan Nous allons dans cette exercice montrer l’inégalité de
McMillan qui est la version de l’inégalité de Kraft pour les codes déchiffrables. Soit c : X → {0, 1}+ un
code binaire déchiffrable, alors on a X
2−lc (x) ≤ 1
x∈X
Considérons un code binaire déchiffrable c : X 7→ {0, 1}+ et son extension d’ordre n notée
où c(x1 )c(x2 ) . . . c(xn ) est la concaténation des mots c(x1 ), c(x2 ), etc... On note lmax = maxi li et N (i)
le nombre de séquences de mots-codes de c(n) de longueur i.
1. Montrer que
X
n
lc(n) (x1 , x2 , . . . , xn ) = lc (xi )
i=1
2. En déduire que !n
X X
2−lc (x) = 2−lc(n) (x)
x∈X x∈X n
où x = (x1 , x2 , . . . , xn )
9
3. Montrer que
X X
nl max
Code de Huffman
2. On considère dans un premier temps un code binaire de Gray : −3 → 00, −1 → 01, 1 → 11, 3 → 10.
Calculer la longueur moyenne, le rendement et la redondance du code. Coder le message y et donner
sa taille (en bits).
4. Conclure.
10
1 2 3 4 5 6
8 6 4 2 2 1
23 23 23 23 23 23
1. Stratégie 1 : vous allez goûter les bouteilles une par une dans un ordre le plus adéquat possible. On
s’arrête lorsque l’on sait laquelle est bouchonnée.
2. Stratégie 2 : cette fois, vous avez le droit de faire des mélanges avant la dégustation.
Exercice 2.10 (♣♣♣). Quelques petites propriétés des codes de Huffman On considère une source
X sur un alphabet X = {x1 , . . . , xM } et l’on note pi = pX (xi ). On suppose que p1 > p2 ≥ . . . ≥ pM .
2
1. Montrer que pour tout code de Huffman binaire, si p1 > 5 alors le symbole x1 doit être codé sur un
bit.
1
2. Montrer que pour tout code de Huffman binaire, si p1 < 3 alors le symbole x1 doit être codé sur au
moins deux bits.
4. Quelle est la taille de bloc minimale que l’on doit utiliser pour être sur que la longueur moyenne du
code pour coder un symbole soit inférieure à 0.82 ?
Exercice 2.12 (♣♣♣). Quelques codes pour les nombres entiers On s’interesse dans cet exercice à
plusieurs codes permettant de coder l’ensemble des nombres entiers strictements positifs.
11
1. Le code binaire classique. On considère le code binaire classique cb , qui encode un entier n par sa
représentation en base 2.
(a) En remarquant que tous les entiers ont un mot-code commençant par 1, et en introduisant λ
comme le mot-vide, construire un nouveau code cB avec une meilleure longueur moyenne
(b) Quelle information supplémentaire faudrait-il rajouter pour que cb ou cB soient déchiffrables ?
3. Le code unaire. Le code unaire cu consiste à écrire n − 1 fois le bit 0, suivi du bit 1.
4. Le code γ d’Elias. Le code γ d’Elias cγ consiste à concaténer le codage du nombre de bits nécessaires
pour représenter l’entier grâce à cb avec un codage unaire cu , suivi du codage de l’entier grâce au
code binaire tronqué cB .
cγ (n) = cu (lb (n)) cB (n)
5. Le code δ d’Elias. Le code δ d’Elias cδ consiste à concaténer le codage du nombre de bits nécessaires
pour représenter l’entier grâce à cb avec un codage γ d’Elias cγ , suivi du codage de l’entier grâce au
code binaire tronqué cB .
cδ (n) = cγ (lb (n)) cB (n)
12
3 Codage canal
Exercice 3.1 (♣). Exemple introductif. On considère une source ne pouvant émettre que les 4 mots-codes
suivants: 000000, 001111, 110011 et 111100. Ces 4 mots-codes sont envoyés avec la même probabilité sur
un canal binaire symétrique de probabilité d’erreur p. Si le receveur ne reçoit pas l’un de ces mots-codes,
il sait qu’une erreur a eu lieu. Quelle est la probabilité qu’une erreur ait eu lieu sans avoir été détectée ?
Exercice 3.2 (♣♣♣). Approximation de la probabilité d’erreur d’un code à répétition. On considère
un code à répétition avec n un entier impair et p la probabilité d’erreur sur un bit.
(n)
1. Montrer que la probabilité d’erreur Pe vaut
X
n
Pe(n) = Cni pi (1 − p)n−i
i= n+1
2
2. En supposant p = 0.1, quel terme de cette somme est le plus grand ? Le comparer au deuxième plus
grand terme.
3. On rappelle la formule de Stirling n n
√
n! ∼ 2πn
e
Montrer que
i
Cni ∼ 2nh( n )
où h(z) = −z log2 (z) − (1 − z) log2 (1 − z)
(n)
4. En déduire une grossière approximation de la probabilité d’erreur Pe
Inégalité de Fano
Exercice 3.3 (♣♣♣). Proximité de la borne de Fano. On considère un système de communication avec
X = {1, 2, 3} et Y = {a, b, c}. On donne la loi conjointe pXY (x, y) :
HH Y
H a b c
X HH H
1 1 1
1 6 12 12
1 1 1
2 12 6 12
1 1 1
3 12 12 6
13
On souhaite retrouver X à partir de Y grâce à une fonction déterministe : X̂ = f (Y ). On note Pe =
P(X̂ 6= X).
1. Quelle fonction f doit-on choisir pour minimiser la probabilité d’erreur ? Calculer Pe pour cette
fonction.
2. En reprenant la preuve de la formule de Fano, montrer que
H(X|Y ) − 1
Pe ≥
log2 (|X | − 1)
Calculs de capacités
Exercice 3.4 (♣♣). Canal binaire en Z. On considère le système de communication binaire en Z suivant,
où X est la variable aléatoire associée à l’entrée et Y celle associée à la sortie.
1
0 0
1
2
1 1
1
2
Exercice 3.5 (♣♣). Canal binaire à effacement. On considère le système de communication binaire à
effacement suivant, où X est la variable aléatoire associée à l’entrée et Y celle associée à la sortie.
1−ϵ
0 0
ϵ
e
ϵ
1 1
1−ϵ
14
1. En notant p = pX (X = 1), montrer que
I(X; Y ) = (1 − ϵ)h(p)
Exercice 3.6 (♣♣). Canal bruité par un bruit additif uniforme. On considère une source X sur un
alphabet X = {0, 1} qui émet sur un canal tel que la sortie Y s’écrit Y = X +Z où Z est tiré aléatoirement
et uniformément dans l’alphabet Z = {0, a}. Calculer la capacité C du canal en fonction de la valeur de
a.
Exercice 3.7 (♣♣♣). Capacité d’un canal produit. Soient un canal sans mémoire caractérisé par X1 ,
pY1 |X1 (y1 |x1 ) et Y1 et de capacité C1 et un canal sans mémoire caractérisé par X2 , pY2 |X2 (y2 |x2 ) et Y2 et de
capacité C2 . On considère un nouveau canal sans mémoire caractérisé par X1 ×X2 , pY1 Y2 |X1 X2 (y1 , y2 |x1 , x2 ) =
pY1 |X1 (y1 |x1 )pY2 |X2 (y2 |x2 ) et Y1 × Y2 . Trouver la capacité de ce canal.
Exercice 3.8 (♣♣♣). Canal bruité par un bruit multiplicatif de Bernouilli. On considère une source
X sur un alphabet X = {0, 1} qui émet sur un canal tel que la sortie Y s’écrit Y = X × Z où Z suit une
loi de Bernouilli de paramètre α 6= 0 (PZ (Z = 1) = α). Calculer la capacité C du canal en fonction de la
valeur de α.
Codes linéaires
Exercice 3.9 (♣♣). Construire un code binaire sur F82 contenant M = 4 mots-codes et de distance
minimale égale à 5.
Exercice 3.10 (♣♣). Montrer qu’il n’existe aucun code binaire sur F12 7
2 contenant M = 2 mots-codes et
de distance minimale égale à 5.
15
1. Vérifier que toute matrice génératrice G d’un code linéaire de paramètres [n, k, d] peut se mettre
sous la forme systématique
G = Ik | B
en utilisant exclusivement les opérations suivantes
(a) 111001
(b) 010100
(c) 101100
(d) 110111
(e) 100001
2. Lesquels peuvent être corrigés ? Les corriger grâce au décodage par syndrome.
Exercice 3.15 (♣♣). Décodage par syndrome On considère un canal binaire symétrique sans mémoire
de probabilité d’erreur p < 12 . Montrer que le décodage par syndrome est équivalent à un décodage par
maximum de vraisemblance, c’est à dire que le mot-code estimé â ∈ C à partir d’une séquence reçue b
estimé est
â = argmaxa∈C P(b|a)
16
Opérations sur les codes linéaires
Exercice 3.16 (♣♣). Extension d’un code. Soit C un code binaire linéaire de paramètres [n, k, d]. On
appelle extension d’un code linéaire, le code linéaire obtenu en rajoutant à la fin de chaque mot-code
un bit de parité ( )
X
n
C ext = (c1 , c2 , . . . , cn , ci ), c ∈ C
i=1
Exercice 3.17 (♣♣♣). Rallongement d’un code, sélection d’un sous-code, perforation d’un code.
Montrer que, s’il existe un code binaire linéaire de paramètres [n, k, d], alors
Exercice 3.18 (♣♣♣). Borne de Plotkin. On considère un code linéaire binaire de paramètres [n, k, d]
tel que 2d > n. Montrer que
2d
M≤
2d − n
X
Indice : minorer et majorer la quantité d(a, a′ )
(a,a′ )∈C 2
a̸=a′
Exercice 3.19 (♣♣♣). Caractérisation des codes MDS. Soit C un code q−aire linéaire C de paramètres
[n, k, d] à distance séparable maximale. Montrer que:
17
4. Si la matrice génératrice G = Ik | B est sous forme systématique, alors chaque sous-matrice
carrée de B est non singulière
1. Montrer qu’il n’existe aucun code MDS non trivial tel que 2 ≤ k ≤ n − q
2. En utilisant le résultat des exercices précédents sur le code dual, montrer qu’il n’existe aucun code
MDS non travial tel que q ≤ k ≤ n
2 ≤ k ≤ q − 1 et 2 ≤ n − q ≤ q − 1
4. En conclure que les seuls codes MDS binaires sont les codes triviaux
Codes de Hamming
Exercice 3.22 (♣♣). Probabilité d’erreur avec un code de Hamming On utilise un code de Hamming
H[7, 4, 3] sur un canal binaire sans mémoire où p est la probabilité d’erreur sur un bit. Calculer la probabilité
d’erreur P1 par bloc lors de l’envoi d’un bloc de 4 bits et la comparer à celle P2 par bloc obtenue si l’on
avait pas utilisé de codage canal. A quelle condition sur p a-t-on P2 > P1 ?
Exercice 3.23 (♣♣). Codes de Hamming q−aires Dans le cours, nous avons traité le cas des codes de
Hamming binaires, mais on peut en construire également sur Fnq . Il s’agit d’un code dont la matrice de
contrôle contient l’ensemble maximal de colonnes linéairement indépendantes deux à deux.
q r −1
1. En déduire qu’on a dans ce cas n = q−1 , k = n − r et d = 3
18
4 Théorie du signal
Dans la suite des exercices, on appelle espace de Schwartz l’ensemble des fonctions C ∞ à décroissance
rapide n o
S(R) = x ∈ C ∞ (R) | ∀(k, l) ≥ 0 supt∈R |t|k |x(l) (t)| < +∞
2. Vérifier que la fonction tk x(l) (t) appartient également à S(R) et que pour tous k, l ∈ N, la fonction
tk x(l) (t) admet bien une transformée de Fourier
x(t) = e−αt
2
On rappelle que Z +∞ √
e−u du =
2
π
−∞
19
Exercice 4.3 (♣). Changement d’amplitude, translation et changement d’échelle. Soient t0 , A, T >
0 des réels, et x un signal dans L1 (R) ∩ L2 (R). On considère le signal
t − t0
y(t) = Ax
T
1. Calculer Ey en fonction de Ex
|x̂(f )|2
px̂ (f ) =
kx̂k2L2
• On peut définir pour ces deux densités de probabilités une notion de moyenne statistique et de
variance:
20
(c) En conclure que
1
σx2 σx̂2 ≥
16π 2
et interpréter ce résultat. On appelle cette inégalité, l’inégalité d’Heisenberg (ou principe
d’incertitude).
(d) Pour quelles fonctions x(t) a-t-on un cas d’égalité ?
Exercice 4.5 (♣). Fonction de transfert d’un filtre biphase Manchester On considère un réel T > 0
et le filtre de réponse impulsionnelle h(t) définie par
0.8
0.6
0.4
0.2
0.2
0.4
0.6
0.8
1
0 T/2 T
Exercice 4.6 (♣♣). Fonctions rectangle et triangle. On considère les signaux suivants :
( (
1 − |t| si − 1 < t < 1 1 si − 12 < t < 12
tri(t) = rect(t) =
0 sinon 0 sinon
21
Exercice 4.7 (♣). Réponse impulsionnelle d’un filtre passe-bas idéal Soit fc > 0. Calculer la réponse
impulsionnelle d’un filtre passe-bas idéal de fonction de transfert
(
1 pour |f | < f2c
H(f ) =
0 sinon
h(t) = e−α|t|
3. Transformée de Fourier
F {δt0 } = e−j2πf t0
Exercice 4.10 (♣♣). Convolution et multiplication par un peigne de Dirac. On considère le signal
x(t) = Π2 (t − 2) + 2Π4 (t + 1) − Π2 (t − 1)
1. x1 = x × X1
2. x2 = x ∗ X2
Exercice 4.11 (♣♣). Produit de convolution entre distributions tempérées. Calculer le produit de
convolution x ∗ y entre les distributions tempérées suivantes
22
X
+∞
1. x(t) = (−1)k δ(t − kT ) et y(t) = δ(t) − δ(t − T ) + δ(t − 2T ) où T > 0
k=0
X
4
2. x(t) = δ(t − kT1 ) et y(t) = XT2 (t) où 5T2 = 4T1 et T1 , T2 > 0
k=0
Analyse spectrale
Exercice 4.12 (♣♣). Analyse spectrale d’une fonction sinusoïdale observée sur une durée finie.
On considère un réel f0 > 0 et le signal x(t) = cos (2πf0 t) que l’on observe sur l’intervalle [t0 − τ2 , t0 + τ2 ].
On notera xτ (t) ce signal à durée limitée τ .
1. Calculer la transformée de Fourier Xτ (f ) du signal xτ (t) en fonction de τ , t0 et f0
1
2. Tracer l’allure de |Xτ (f )|2 dans le cas où f0 et t0 = 0 et commenter.
τ
Exercice 4.13 (♣♣). Fenêtre de Hanning Soit T > 0, on appelle fenêtre de Hanning la fonction
(
1
2 − 12 cos 2π Tt pour 0 ≤ t ≤ T
w(t) =
0 sinon
2. En traçant l’allure de |W (f )|, et en se basant sur l’exercice précédent, commenter l’utilité de multiplier
un signal par cette fenêtre avant analyse.
23
Exercice 4.15 (♣♣♣). On considère un réel u qui n’est pas un entier, et le signal x(t), périodique de
période 2π, et défini sur [−π, π[ par :
Exercice 4.16 (♣♣♣). On considère un signal x(t) périodique de période T = 6 et défini sur [−3, +3[
par
1
x(t)
-1
-2
-3
-4
-5 -4 -3 -2 -1 0 1 2 3 4 5
Temps (s)
Exercice 4.17 (♣♣♣♣). Une autre démonstration de la transformée de Fourier d’un peigne de
Dirac. On notera ĉ(f ) la distribution définie par
X
+∞
ĉ(f ) = e−j2πnf T
n=−∞
1. Montrer que
X
+N
sin 2πf T N + 1
−j2πnf T 2
e =
sin (πf T )
n=−N
1
2. Soit une fonction test φ̂ ∈ S(R) à support inclus dans − 2T 1
, + 2T . Grâce au théorème de Parseval,
montrer que
Z +1 X +N Z 1
2T
−j2πnf T 1 +T (N + 2 )
e φ̂(f )df = ψ(t)dt
− 1 T −T (N + 1 )
2T n=−N 2
24
3. En passant à la limite, montrer que
Z +∞ X
+N
1
hĉ, φ̂i = lim e−j2πnf T φ̂(f )df = φ̂(0)
N →+∞ −∞ T
n=−N
1
4. En déduire que la restriction de ĉ à l’intervalle − 2T 1
, + 2T vaut
1
ĉ[− 1 1
,+ 2T ] = δ
2T T
et donc que
1 X
+∞
F {XT } = δn
T n=−∞ T
Conversion analogique/numérique
Exercice 4.18 (♣). L’exercice le plus simple du monde. On considère le signal continu x(t) suivant,
défini pour t ∈ [0, 1[
1
0.8
0.6
0.4
0.2
-0.2
-0.4
-0.6
-0.8
-1
-0.2 0 0.2 0.4 0.6 0.8 1 1.2
t (secondes)
En supposant que chaque valeur quantifiée est associée à un message binaire croissant selon la valeur (ex :
000 pour la valeur la plus basse, 001 pour la suivante, ..., 111 pour la valeur la plus haute), donner le
message binaire obtenu après conversion analogique/numérique de paramètres Fe = 10 Hz et b = 3 bits.
25
Exercice 4.19 (♣). Dimensionnement de la quantité de stockage d’un CD audio (ok boomer)
Quelle est la fréquence d’échantillonnage minimale et le nombre de bits minimal que l’on doit utiliser pour
numériser un signal audio, sachant que :
Quel sera alors le débit minimal d’un tel signal (en kbits par seconde) ?
Exercice 4.20 (♣♣). Echantillonnage idéal d’un signal en bande de base. On considère un signal
x(t), dont la transformée de Fourier X(f ) (supposée réelle) est donnée ci-dessous.
2.5
2
X(f)
1.5
0.5
0
-140 -120 -100 -80 -60 -40 -20 0 20 40 60 80 100 120 140
Frequence (Hz)
Exercice 4.21 (♣♣). Echantillonnage idéal d’un signal modulé. On considère le signal x(t), dont la
transformée de Fourier X(f ) est représentée ci-dessous
26
2.5
1.5
X(f)
0.5
0
-10 -8 -6 -4 -2 0 2 4 6 8 10
Frequency (Hz)
1. D’après le critère de Nyquist, quelle est la fréquence Fe que l’on doit utiliser pour échantillonner sans
perte ce signal ?
2. Montrer que pourtant, pour Fe ∈ [6 Hz, 8 Hz], alors il n’y a pas de repliement de spectre
3. Proposer une stratégie pour échantillonner et reconstruire parfaitement ce genre de signaux, tout en
respectant pas le critère de Nyquist
Exercice 4.22 (♣♣♣). Influence du filtre anti-repliement de spectre On considère un signal x(t) réel,
à énergie finie, en bande de base et à largeur de bande finie B. On suppose également que sa transformée
de Fourier est réelle et positive.
3. On réitère ce processus, mais cette fois en appliquant un filtre anti repliement de spectre avant de
réaliser l’échantillonnage. Ce filtre est appliqué en amont avant l’échantillonnage afin de supprimer
toutes les fréquences supérieures à F2e . La fonction de transfert de ce filtre a pour expression
(
1 si |f | < F2e
HAA (f ) =
0 sinon
27
x(t) x′ (t) x′e (t) x2 (t)
hAA (t) × hLP (t)
∑
+∞
Te δ(t −
n=−∞
nTe )
Signaux aléatoires
où f0 > 0 est une constante et A et ϕ deux variables aléatoires indépendantes. On suppose que A suit
une loi normale centrée réduite et que ϕ est uniformément distribuée sur [0, 2π].
28
Exercice 4.25 (♣♣♣♣). Densité spectrale de puissance des signaux en communications numériques.
Soit A[n] un processus stochastique de moyenne nulle où les v.a. A[n] sont i.i.d. Soit un filtre de réponse
impulsionnelle h(t) et X(t) le signal aléatoire défini par
X
X(t) = A[n]h(t − nT0 )
n∈Z
1. En calculant rX (τ, t) = E [X(t)X(t − τ )], montrer que le signal X(t) n’est pas stationnaire au sens
large
2. Un signal aléatoire est dit cyclostationnaire s’il existe T0 > 0 tel que les propriétés statistiques de
X(t) se répétent avec la période T0 . En particulier, un signal est cyclostationnaire d’ordre 2 si
(a) En repartant de la définition initiale de la puissance moyenne, montrer qu’on peut définir la
puissance moyenne d’un signal cyclostationnaire par
Z
1
PX = E |X[t]|2 dt
T0 (T0 )
(b) En repartant de la définition initiale de la densité spectrale de puissance, montrer qu’on peut
définir la densité spectrale de puissance d’un signal cyclostationnaire par
ΓX (f ) = F {rX (τ )}
4. A partir des résultats précédents, calculer la fonction rX (τ ) pour le signal aléatoire X(t)
b(t)
29
X
X(t) = A[n]he (t − nT )
n∈Z
On cherche à maximiser le rapport signal sur bruit à la sortie du récepteur, c’est à dire à trouver le filtre de
réception hr (t) permettant de limiter le plus possible l’influence du bruit. On supposera que le bruit blanc
additif gaussien B(t) a une densité spectrale de puissance égale à N20 . On notera h = he ∗ hr et n = b ∗ hr
et on supposera que h est un filtre de Nyquist, c’est à dire que h(kT ) = δk pour k ∈ Z.
1. Calculer Z[n] en fonction des A[n] et des autres paramètres de la chaîne de transmission. Identifier
les différents termes de l’expression.
2. On cherche à maximiser nos chances de retrouver A[n] à partir de Z[n]. Pour cela, on va tenter de
maximiser le rapport signal sur bruit SN R défini par :
h(0)2
SN R =
Pn
où Pn est la puissance moyenne totale du signal aléatoire n(t).
30
5 Problemes
Problème 1 : Taux d’entropie d’un processus stochastique
Dans le cadre du cours, nous n’avons considéré presque que des sources sans mémoire. On va s’intéresser
ici à un type de source avec mémoire : les sources markoviennes stationnaires. Nous allons étudier les
propriétés de ces sources et nous verrons qu’il est possible de définir une notion d’entropie, même pour
les sources avec mémoire où des dépendances existent entre les symboles émis successivement. Nous
utiliserons ensuite le modèle des processus de Markov stationnaires pour revisiter le second principe de la
thermodynamique.
Avant toute chose on rappelle la définition d’un processus stochastique stationnaire
• On dit qu’un processus de Markov est invariant temporellement si les probabilités de tran-
sition P (Xn = xn |Xn−1 = xn−1 ) ne dépendent pas de n
∀n, ∀x, x′ , P Xn+1 = x′ |Xn = x = P Xn = x′ |Xn−1 = x
• Pour un processus de Markov invariant temporellement, la matrice de terme Πi,j telle que
π∞Π = π∞
31
Questions
Soit (Xn )n∈N∗ un processus de Markov invariant temporellement
1. Montrer que, si la distribution initiale des états π 1 est une distribution stationnaire, alors le
processus est stationnaire
(a) Quelle distribution initiale d’états doit-on utiliser pour que le processus soit stationnaire ?
(b) Dans ce cas, calculer l’entropie H(Xn ) de l’état Xn au temps n
Dans la partie précédente, on a réussi, dans le cas d’un processus de Markov stationnaire, à calculer
l’entropie H(Xn ). En revanche, à cause de l’effet de mémoire, il est difficile d’estimer H(X1:n ) et no-
tamment d’évaluer le comportement de ce terme quand n → +∞. Pour cela, nous allons introduire une
nouvelle notion d’entropie:
Questions
1. Processus i.i.d. Montrer que pour un processus stochastique i.i.d. de loi pX (x), on a
H(X ) = H(X)
2. Processus stationnaire
existe
(b) En utilisant le lemme de Césaro, montrer que le taux d’entropie H(X ) existe et qu’on a
H(X ) = H ′ (X )
Ainsi pour une source stationnaire, le taux d’entropie correspond à la valeur limite de l’incertitude sur
32
le futur connaissant le passé.
Questions
Soit (Xn )n∈N∗ un processus de Markov invariant temporellement, π ∞ une distribution stationnaire.
On suppose que X1 ∼ π ∞ .
2. Montrer que le taux d’entropie pour le processus de Markov à deux états décrit dans la Partie
I est
β α
H(X ) = h(α) + h(β)
α+β α+β
où h(p) = −p log2 (p) − (1 − p) log2 (1 − p)
La notion d’entropie n’existe pas qu’en théorie de l’information. Elle est également utilisée en physique
et notamment en thermodynamique, comme la mesure du degré de désordre d’un système au niveau
microscopique. En particulier, le célèbre second principe de la thermodynamique énonce que l’entropie
d’un système isolé ne peut qu’augmenter ou rester constante. Nous allons illustrer ici ce principe grâce
aux quantités que nous avons décrites dans le cours, à savoir l’entropie, l’information mutuelle et l’entropie
conditionnelle. Le système isolé que nous allons utiliser correspond à un processus de Markov stationnaire.
A chaque temps, le système évolue de façon aléatoire et sans connaissance du passé : seul le présent donne
une information sur le futur.
Questions
1. Soit (Xn )n∈N∗ un processus de Markov stationnaire
(a) Montrer que H(Xn ) est une constante qui ne dépend pas de n. En déduire que notre
parallèle tombe complètement à l’eau car avec notre définition de l’entropie, elle reste
toujours constante...
(b) Montrer qu’en revanche H(Xn |X1 ) ≥ H(Xn−1 |X1 ). Ainsi, notre parallèle ne tombe
pas complètement à l’eau : avec notre définition ce n’est pas l’entropie qui augmente
mais notre degré d’incertitude sur l’état du système, en connaissant l’état initial. Plus
on laisse le système évoluer, moins la connaissance de l’état initial nous est utile
(c) Montrer que I(X1 ; Xn−1 ) ≥ I(X1 ; Xn ), c’est à dire qu’il y a plus d’information en
commun entre X1 et Xn−1 qu’entre X1 et Xn . C’est à dire que plus on s’éloigne de
l’état initial, moins il y a d’information commune avec cet état.
33
(d) Montrer que H(X1 |Xn ) ≥ H(X1 |Xn−1 ). A l’inverse, plus le système évolue, plus il est
difficile de retrouver l’état initial.
(a) On considère deux distributions d’états π1n et π2n à l’instant n, et π1n+1 et π2n+1 les
distributions associées à l’instant n + 1. Montrer que
Les distributions possibles tendent à devenir de plus en plus similaires avec le temps.
(b) En déduire que si π ∞ est une distribution stationnaire, on a
34
Problème 2 : Autour de l’ensemble des séquences typiques
(n)
Nous avons étudié dans le cours l’ensemble des séquences typiques Tϵ (X). Nous avons
Qn vu en par-
ticulier, que pour une séquence x̃1:n ∈ X générée par une source sans mémoire x̃1:n ∼ i=1 pX (xi ), on
n
a:
P x̃1:n ∈ Tϵ(n) > 1 − ϵ′ lorsque n → ∞
et que cet ensemble avait une taille environ égale à 2n(H(X)±ϵ) . Il s’agit donc d’un ensemble de cardinal
plutot petit, qui regroupe la majorité de la probabilité.
On pourrait se demander s’il n’existe pas un ensemble de cardinal plus petit regroupant la majorité de
la probabilité. Dans la première partie de ce problème nous allons construire un ensemble de ce type et
montrer qu’en réalité ces deux ensembles se ressemblent et que leurs cardinaux sont du même ordre de
(n)
grandeur. Ainsi, même si Tϵ n’est pas le plus petit ensemble concentrant la majorité de la probabilité, il
est suffisamment petit pour qu’on puisse travailler dessus (notamment pour l’étape de codage source que
nous verrons prochainement)
Dans la deuxième partie du problème, nous allons considérer l’ensemble des séquences dont la moyenne
empirique est proche de la moyenne statistique de la loi, et calculer le cardinal de son intersection avec
l’ensemble des séquences typiques. Là encore nous verrons qu’asymptotiquement ces ensembles se con-
fondent.
(n)
En d’autres termes, cet ensemble regroupe les |Bδ | séquences de X n ayant les probabiltés individuelles
les plus élévées.
Questions
Soit ϵ > 0
(n) (n)
1. Donner un exemple de séquences appartenant à Bϵ et pas à Tϵ
′ > 0 et x̃
Qn
2. Soit
δ < 1
2 , δ 1:n ∼ i=1 pX (xi ). Soit Z ⊂ X . En minorant et majorant
n
(n)
P x̃1:n ∈ Z ∩ Tϵ , montrer que si P (x̃1:n ∈ Z) > 1 − δ, alors pour n suffisamment grand
on a
1
log2 (|Z|) ≥ H(X) − δ ′
n
(n) (n)
3. En déduire que Bδ a environ la même taille que Tϵ
35
Partie II : Ensemble des séquences à moyennes typiques
On s’interesse maintenant à un autre ensemble de séquences, qui sont celles dont la moyenne empirique
est très proche de la moyenne statistique. Nous verrons que lorsque n est suffisamment grand ces deux
ensembles se confondent.
Questions
Qn
1. Soit ϵ > 0, et x̃1:n ∼ i=1 pX (xi ).Montrer que
P x̃1:n ∈ M(n)
ϵ ∩ Tϵ
(n)
> 1 − ϵ lorsque n → ∞
(n) (n)
2. Montrer que |Mϵ ∩ Tϵ | ≤ 2n(H(X)+ϵ)
(n) (n)
3. Montrer que pour n suffisamment grand on a |Mϵ ∩ Tϵ | ≥ (1 − ϵ)2n(H(X)−ϵ)
36
Problème 3 : Codes de Lempel-Ziv
Nous avons montré dans le cours que les codes d’Huffman sont optimaux, lorsque l’on suppose connue la
distribution de probabilité de la source. Ceci n’est malheureusement pas toujours le cas, notamment lorsque
l’on souhaite encoder des sources en streaming où les symboles arrivent à la volée. On va s’intéresser dans
ce problème à une classe de codes sources dits universels, c’est à dire capables d’obtenir des performances
asymptotiques optimales, tout en ne faisant aucune supposition sur les distributions et/ou dépendances
des symboles entre eux. L’un des premiers codes de ce type est le code de Lempel Ziv (du nom de ses
inventeurs Abraham Lempel et Jacob Ziv), dont nous allons étudier la variante LZ78 (qui comme son nom
l’indique, a été créée en 1978). Les codes de Lempel Ziv et leurs variantes sont très utilisés en compression
de données, par exemple pour l’encodage des images .GIF.
Le code de Lempel-Ziv est basé sur un partitionnement de la séquence à encoder et la création itérative
d’un dictionnaire. Etant donné un message du type AABABBBABAABABBBABBABBA, l’encodage se
fait de la façon suivante:
A|AB|ABB|B|ABA|ABAB|BB|ABBA|BBA
On peut noter que ce partitionnement se fait à la volée et de façon causale: on a juste besoin de
savoir les phrases qui ont déjà été formées.
Numéro de phrase 0 1 2 3 4 5 6 7 8 9
i
Phrase i ∅ A AB ABB B ABA ABAB BB ABBA BBA
Encodage (P, S) 0,A 1,B 2,B 0,B 2,A 5,B 4,B 3,A 7,A
Encodage binaire ,0 1,1 10,1 00,1 010,0 101,1 100,1 011,0 0111,0
Chaque nouvelle phrase va être encodée sous la forme (P, S) où P est le numéro de la phrase
correspondant aux premiers symboles de la nouvelle phrase et S est le symbole que l’on rajoute
pour former la nouvelle phrase (voir ligne Encodage (P, S)). Le ième couple (P, S) va ensuite être
encodé de façon binaire de la façon suivante: le numéro P va être encodé dans la base binaire sur
k = dlog2 (i)e bits et le symbole S va simplement être codé avec la convention A → 0 et B → 1 par
exemple.
Prenons le premier couple à encoder (0, A) : on a k = 0 donc 0 va être encodé sur 0 bits, et A → 0,
on a donc l’encodage (0, A) → 0. Pour le deuxième couple à encoder (1, B), on a k = 1, et donc
tous les numéros de phrases suivants seront encodés sur au moins k = 1 bits. Comme B = 1, on
obtient l’encodage (1, B) → 11. Pour le troisième couple à encoder (2, B) il faut passer à k = 2,
37
donc on obtient (2, B) → 101, etc... On remarque que le fait que le numéro de phrase soit encodé
sur un nombre toujours croissant de bits est la raison qui rend ce code décodable.
Questions
1. On considère le message ABAABBAABBBABABBB. L’encoder et le décoder grâce à
l’algorithme de Lempel-Ziv.
Dans cette partie, nous allons montrer que pour tout message binaire de longueur n, et quel que soit
le type de processus ayant généré ce message, on a
n
lmax (n) = n + O
log2 (n)
On se place dans la suite dans le cas binaire où X = {0, 1}
Questions
1. Se convaincre que le pire message possible à encoder est celui contenant toutes les séquences
possibles de longueur l avec 1 ≤ l ≤ k.
En déduire que
nk
c(nk ) ≤
k−1
3. On considère maintenant un message de longueur n, tel que n = nk + ∆ et où nk est le plus
grand élément de {nl }l tel que n ≥ nl . Montrer que
n
c(n) ≤
log2 (c(n)) − 3
4. Montrer que
lmax (n) ≤ n + Ac(n)
où A est une constante
5. Montrer que c(n) = O logn(n) et en déduire le résultat
2
Cette égalité pourrait paraître mauvaise, mais en réalité, elle nous suggère déjà l’optimalité asymptotique
du code. Considerons par exemple un message de longueur n généré par une source sans mémoire binaire
38
où les symboles sont équiprobables. Le première théorème de Shannon nous dit qu’on ne peut pas l’encoder
avec un nombre de bits strictement inférieur à nH(X) = n. Donc que le pire cas soit encodable avec
beaucoup plus de n bits est déjà une très bonne nouvelle !
On considère maintenant une source sans mémoire sur un alphabet X fini. On notera H(X) l’entropie
de la source. Etant donnée une séquence x1:n , on notera
Y
n
Q(x1:n ) = pX (xi )
i=1
Question
Montrer que X
log2 (Q(x1:n )) ≤ − cj log2 (cj )
j
L’intéret de cette inégalité est qu’elle lie la probabilité d’apparition d’une séquence à la façon dont on
va pouvoir la découper en phrases distinctes. Cette inégalité est la base de la démonstration de l’optimalité
du code de Lempel-Ziv, qui dépasse malheureusement le cadre du programme du cours (il faut notamment
définir une nouvelle notion d’entropie pour les variables aléatoires discrètes à support infini, un peu sur le
modèle de ce qui a été fait dans le Problème 1).
39
Problème 4 : Deuxième théorème de Shannon ou Théorème du codage canal
Enoncé comme ceci, cela semble très simple, et pourtant la démonstration n’est pas triviale du tout.
Contrairement à la preuve du premier théorème de Shannon, on ne pourra pas explicitement construire un
tel code. Nous allons procéder de façon particulièrement astucieuse décrite avec les mains ci-dessous.
Supposons que l’on dispose de 1000 sacs et d’une seule balance, et que l’on souhaite prouver qu’il existe
au moins un sac de poids inférieur à 1kg. La première stratégie consiste à peser tous les sacs jusqu’à ce que
l’on tombe sur un sac vérifiant cette propriété. L’autre solution est de peser tous les sacs simultanément:
si on s’aperçoit que leur poids total est inférieur à 1000kg, alors on pourra prouver l’assertion sans avoir
besoin de savoir précisément lequel des sacs la vérifie. C’est exactement le raisonnement que nous allons
utiliser, en construisant (de façon d’ailleurs très naïve) un très grand nombre de codes et montrer que leur
probabilité d’erreur en moyenne est suffisamment petite.
L’autre pilier de cette démonstration est l’AEP. Nous avions vu qu’étant données deux séquences
x1:n et y1:n de grande taille, alors leur probabilité d’appartenir à l’ensemble des séquences conjointement
(n)
typiques
Qn Tϵ (X, Y ) dépendait fortement de leur mode de génération. Si elles sont créées selon la loi
i=1 pXY (xQi ,nyi ), alors leur probabilité d’y appartenir est environ égale à 1, alors que si elles sont générées
selon la loi i=1 pX (xi )pY (yi ), cette probabilité est de l’ordre de 2 −nI(X;Y ) (voir les théorèmes du cours).
Ainsi, si on reçoit une séquence y1 : n et qu’on sait qu’il y a parmi les mots-code une séquence x1:n qui
est conjointement typique avec elle, alors on est quasiment sûr de ne pas faire d’erreur dans le décodage
(ce qui est toujours bon à prendre).
Afin de simplifier les raisonnement, on supposera dans la suite que nR est un entier, et que tous les
messages envoyés sont équiprobables.
• Une régle de décodage basée sur les séquences conjointement typiques. Si l’on reçoit la séquence y
le décodage fonctionne de la façon suivante:
(n)
– S’il existe un mot-code UNIQUE x(w) dans C, tel que (x(w) , y) ∈ Tϵ (X, Y ), alors on décode
y en x(w)
40
– Sinon, on renvoit un message d’erreur
Questions
1. Soit C un code et w le message envoyé (donc le mot-code envoyé est x(w) ). Montrer que la
probabilité d’erreur Perr (C, w) est majorée par
X X X ′
Perr (C, w) ≤ 1 − ∆(x(w) , y) pY |X (y|x(w) ) + ∆(x(w ) , y)pY |X (y|x(w) )
y∈Y n w′ ̸=w y∈Y n
On notera X
α1 (C, w) = 1 − ∆(x(w) , y) pY |X (y|x(w) )
y∈Y n
et X ′
α2 (C, w) = ∆(x(w ) , y)pY |X (y|x(w) ) avec w′ 6= w
y∈Y n
2. Ces quantités sont difficiles à estimer car elles dépendent fortement du code utilisé. En utilisant
la technique de la balance donnée ci-dessous, nous allons donc travailler sur la valeur moyenne
de ces quantités pour tous les codes donc sur
X
EC [Perr (C, w)] = Perr (C, w) p(C)
C
3. En déduire que
EC [Perr (C, w)] ≤ ϵ + (2nR − 1)2−n(I(X;Y )−3ϵ)
On vérifie au passage que le majorant ne dépend pas du message w envoyé (ce qui est logique
vu la construction du code)
4. Montrer que si R < I(X; Y ) − 3ϵ alors, pour n suffisamment grand, la probabilité d’erreur
Perr moyennée sur tous les codes C et tous les symboles w vérifie l’ingéalité
41
Nous avons réussi la première étape: montrer qu’en moyennant sur tous les codes, et sur tous les
symboles envoyés, la probabilité d’erreur pouvait être rendue aussi petite que possible. Il nous reste
maintenant à prouver qu’il existe bien un code qui vérifie également ce résultat !
On appelera p∗X (x) = argmaxpX (x) I(X; Y ), la distribution de probabilité sur X permettant de max-
imiser l’information mutuelle I(X; Y ) : pour ce choix de distribution d’entrée on a donc I(X; Y ) = C où
C est la capacité du canal.
Questions
1. On suppose que la loi pX utilisée pour les codes est pX = p∗X . Montrer que si R < C − 3ϵ
alors, pour n suffisamment grand, la probabilité d’erreur moyennée sur tous les codes C et
tous les symboles w est
Perr ≤ 2ϵ
n o
(1) (M )
2. Montrer qu’il existe au moins un code C⋆ = x⋆ , . . . , x⋆ tel que pour n suffisamment
grand
Perr (C⋆ ) ≤ 2ϵ
λw = Perr (C⋆ , w)
∀w > 2nR−1 , λw ≤ 4ϵ
4. En déduire qu’en considérant le code C⋆ et en supprimant la moitié des mots codes qui a la
probabilité d’erreur la plus élevée, on peut construire un code de taux R − n1 → R tel que
maxw λw → 0 quand n → +∞
42
Problème 5 : Identité de MacWilliams
Parmi les thèmes qui ont fasciné (et fascinent encore !) les chercheurs en codage et cyroptographie,
se trouve l’étude des propriétés des codes linéaires. En particulier, l’étude de la distribution des poids des
mots-code d’un code linéaire est toujours un sujet actuel de recherche. En 1961, Jessie MacWilliams a
démissionné de son emploi de programmeur aux Bell Labs pour se lancer dans une thèse (qu’il a finie en...
un an), et durant laquelle il a démontré cette identité qui est l’un des fondements pour l’étude des codes
correcteurs d’erreurs.
Afin d’étudier la distribution des poids, on utilise en général une formulation sous forme de polynôme
énumérateur :
X X
n
w(c)
WC (z) = z = ci z i
c∈C i=0
1 X ⊥ i
n
WC (z) = ci z (1 − (q − 1)z)n−i (1 − z)i
kC ⊥ k
i=0
Dans la suite du problème, afin de simplifier, on se limitera au cas des codes binaires (q = 2). La
démonstration (ultra élégante) proposée dans ce problème a été conçue en 1980 par Chang & Wolf dans :
Chang, S. C., & Wolf, J. (1980). A simple derivation of the MacWilliams’ identity for linear codes
(Corresp.). IEEE Transactions on Information Theory, 26(4), 476-477.
Partie I : Quelques résultats préliminaires sur les poids des mots-code d’un code linéaire
Avant de rentrer dans le vif du sujet, nous allons démontrer quelques propriétés qui vont nous donner
des intuitions sur les distributions de poids. Soit a ∈ Fk2 tel que a 6= 0, on définit l’application fa comme
fa : Fk2 7→ F2
X
k
x → ai xi
i=1
43
Questions
1. Pour k = 1, montrer que cette fonction est bijective (oui, c’est trivial)
2. Montrer que pour tout b ∈ F2 , l’ensemble f −1 (b) contient exactement 2k−1 éléments
3. En déduire que pour tout code binaire linéaire de paramètres [n, k, d], soit tous les mots-code
sont de poids pair, soit exactement la moitié des mots-code sont de poids pair.
Indice : étant donnée une matrice génératrice G ∈ Fk×n
2 on considèrera l’application
g: Fk2 7→ F2
x → xG(1, 1, . . . , 1)t
Soit C un code binaire linéaire C de paramètres [n, k, d]. On considère un canal binaire symétrique
avec une probabilité d’erreur p. Lors de l’envoi d’un mot-code c ∈ C, le récepteur reçoit une séquence
r = c + e ∈ X n où e ∈ X n est un vecteur d’erreur.
Trois événements peuvent arriver:
1. e = 0 : décodage correct
2. e ∈
/ C : erreur détectée (événément D de probabilité PD )
3. e ∈ C et e 6= 0 : erreur non détectée et décodage incorrect
Question
Montrer que la probabilité PD de détecter une erreur est
PD = 1 − WC (1 − p, p)
On appelle C⊥ la matrice de taille n × 2n−k qui énumère tous les mots codes de C ⊥ : chaque colonne
représente un mot-code. Pour e ∈ X n (que l’on suppose être un vecteur ligne), on définit
S(e) = eC⊥
S(e) est un vecteur ligne de longueur 2n−k qui stocke le produit scalaire de e avec tous les mots codes de
C ⊥ . On appelle Sj (e) le j ème coefficient de S(e), et Ej l’évenement {Sj (e) 6= 0}.
44
Questions
1. Montrer que le nombre de coefficients non nuls de S(e) est soit 0, soit 2n−k−1
2. En déduire que
2X
n−k
1
P (S(e) 6= 0) = P(Ej )
2n−k−1
j=1
4. En déduire que
1 X
n
PD = 1 − c⊥
i (1 − 2p)
i
2n−k
i=0
5. En paramétrisant p = 1+z z
avec z ≥ 0, et en combinant les résultats des parties II et III,
montrer le résultat final.
45
Problème 6 : Echantillonnage et reconstruction physiquement réalisables
Dans le cours, nous avons décrit les propriétés théoriques de l’échantillonnage grâce à la distribution
de Dirac. Néanmoins il s’agit uniquement d’une modélisation idéale, car un Dirac n’est bien entendu pas
physiquement réalisable. On va donc remplacer le Dirac idéal δ(t) par un Dirac physiquement réalisable
δϵ (t) qui aura la forme d’une fonction porte causale de durée très courte et d’amplitude élevée. Nous
allons voir que l’utilisation de ces signaux physiques va nous permettre de définir deux nouvelles stratégies
d’échantillonnage (échantillonneur suiveur et bloqueur), mais également de reconstruction du signal à partir
des échantillons (bloqueur d’ordre 0 et bloqueur d’ordre 1).
On utilisera la définition des fonctions rectangulaires et triangulaires
( (
1 − |t| si − 1 < t < 1 1 si − 12 < t < 12
tri(t) = rect(t) =
0 sinon 0 sinon
On définit donc :
Questions
1. Dessiner ces deux signaux et vérifier visuellement que limϵ→0 δϵ (t) = δ(t) et limϵ→0 ∆ϵ (t) =
Te XTe (t)
3. Calculer la transformée de Fourier (au sens des distributions) du signal ∆ϵ (t) et vérifier que
son spectre est bien constitué de raies fréquentielles
46
L’équivalence entre ces deux termes est liée aux propriétés du Dirac. En revanche, lorsque l’on va
remplacer δ(t) par sa version physiquement réalisable δϵ (t), les deux termes ne seront plus équivalents, ce
qui nous permettra de définir deux stratégies d’échantillonnage.
X
+∞
xb (t) = Te x(nTe )δϵ (t − nTe )
n=−∞
Questions
1. Etude de l’échantillonneur suiveur
X
+∞
t − nTe
x̃(t) = x[n] sinc
n=−∞
Te
Déjà, générer une fonction sinus cardinal est quasiment impossible physiquement (support temporel infini).
Ensuite pour reconstruire une seule valeur x̃(t0 ) on a besoin en théorie de tous les x[n] ce qui rend les
calculs impossibles. Enfin, même si on suppose que l’on peut négliger l’influence des x[n] trop éloignés
du temps que l’on veut reconstruire (ce qui est raisonnable vu la forme du sinus cardinal), on aura au
minimum besoin par exemple des 10 échantillons avant et après, ce qui implique une reconstruction non
47
causale. C’est à dire que l’on ne peut pas reconstruire x̃(t0 ) avant d’avoir reçu les 10 échantillons qui
viendront après. Ceci est très problématique car cela empêche une génération du signal à la volée. On
va donc remplacer le sinus cardinal par des fonctions h(t) causales (c’est à dire telles que h(t) = 0 pour
t < 0) ou nécessitant moins d’échantillons, et surtout plus simples à réaliser.
Questions
1. On considère un signal numérique à 5 échantillons x[0] = 1, x[1] = 2, x[2] = −1, x[3] = 2,
x[4] = 1. Tracer l’allure de x̃0 (t) et x̃1 (t) pour Te = 1 s
2. Calculer les transformées de Fourier X̃0 (f ) et X̃1 (f ) des signaux reconstruits en fonction de
X(f )
48
Problème 7 : Capacités des canaux gaussiens réels
X[n] Y [n]
+
B[n]
où les B[n] sont des variables i.i.d. suivant une loi normale de moyenne nulle et de variance σ 2 ,
décorrélées des X[n]
Ce canal ressemble beaucoup à ceux que nous avons vu dans le chapitre sur le codage canal : le
canal transforme des symboles d’entrée en symboles de sortie. La principale différence est que les valeurs
d’entrées X[n] (et donc les valeurs de sorties Y [n]) sont réelles et non prises dans un alphabet fini. Nous
ne pouvons donc utiliser aucune des notions classiques d’entropie ou d’information mutuelle pour travailler
sur ce canal. Fort heureusement, la théorie de l’information a également été étendue au cas de variables
aléatoires réelles, avec des définitions relativement similaires.
Questions
1. En considérant une variable aléatoire suivant une loi uniforme sur [0, a], montrer que l’entropie
différentielle n’est pas nécessairement toujours positive
2. Montrer que l’entropie différentielle d’une variable aléatoire suivant une loi normale de moyenne
nulle et de variance σ 2 est égale à
√
h(X) = log2 (σ 2πe)
49
3. Soit α une constante. Montrer que
h(X + α) = h(X)
Ceci justifiera que dans la suite, on supposera que toutes les variables aléatoires ont une
moyenne nulle.
La divergence de Kullback-Leibler et l’inégalité de Gibbs (qui nous a été si utile pour démontrer de
nombreux théorèmes) trouvent également leur parallèle pour les variables aléatoires réelles à densité.
Questions
1. Montrer que DKL (pX ||pY ) ≥ 0 avec égalité si et seulement si pX (.) et pY (.) sont égales
presque partout
2. Soit X une variable aléatoire réelle de moyenne nulle et de variance σ 2 . Montrer que
√
h(X) ≤ log2 (σ 2πe)
avec égalité si et seulement X suit une loi normale de moyenne nulle et de variance σ 2
Toujours sur le même principe on peut définir (lorsqu’elles existent et ont la bonne propriété de ne pas
être infinies...) des entropies conditionnelles et des informations mutuelles pour des variables aléatoires
réelles, de la forme Z Z
h(X|Y ) = pXY (x, y) log2 pX|Y (x|y) dxdy
• X et B sont décorrélées
50
• B ∼ N(0, σ 2 )
• E [X] = 0 et E |X|2 ≤ P
Questions
1. Montrer que la capacité du canal définie comme
C= min
pX
I(X; Y )
E[|X| ]≤P
2
est égale à
1 P
C = log2 1 + 2 bits par transmision
2 σ
Partie IV : Capacité d’un canal gaussien réel à temps continu et à bande passante limitée
On considère maintenant un canal gaussien réel à temps continu et à bande passante limitée:
X(t) Filtre de Y (t)
+
canal hc (t)
B(t)
où
H(f ) = Π2W (f )
On suppose que le signal X(t) est à largeur de bande finie égale à la bande passante du canal, c’est à
dire que ΓX (f ) = 0 pour |f | > W . On notera Γb (f ) = N20 et Px la puissance moyenne de X(t).
Questions
1. Montrer que la puissance moyenne du bruit filtré B(t) ∗ h(t) vaut σ 2 = N0 W
2. En suivant le raisonnement du cours sur les liens entre les deux types de canaux, en déduire
que la capacité C du canal gaussien réel à temps continu et à bande passante limitée est égale
51
à
Px
C = W log2 1+ bits par seconde
N0 W
52
6 Séance de révisions
Exercice 6.1. On considère le signal x(t) dont la transformée de Fourier est donnée par :
(
j sin(πf ) si − 1 < f ≤ 1
X(f ) =
0 sinon
3. Quelle est la fréquence d’échantillonnage minimale Fe qu’on l’on peut choisir afin de respecter le
critère de Nyquist ?
4. On choisit Fe = 2 Hz.
(a) Tracer l’allure de la partie imaginaire du spectre Xe (f ) obtenu après échantillonnage idéal.
(b) En déduire le signal échantillonné correspondant xe (t)
(c) Quel est l’expression du signal x̂(t) reconstruit par filtrage passe-bas idéal de fréquence de
coupure fc = F2e ? En déduire l’expression de x(t)
Exercice
T 6.2. On considère un réel A > 0 et le signal x(t) périodique de période T > 0 et défini sur
− 2 , + T2 par (
A − T4 ≤ t < + T4
x(t) =
−A sinon
Calculer la transformée de Fourier du signal x(t) au sens des distributions.
Exercice 6.3. 1. Soit X une variable aléatoire, ϕ une fonction déterministe et Y = ϕ(X). Montrer
que
H (ϕ(X)) ≤ H(X)
et précisez le cas d’égalité.
(a) Y = cos(X)
(b) Y = 2X
Exercice 6.4. Une distance ρ(x, y) est une application vérifiant les propriétés suivantes:
53
1. Montrer que
ρ(X, Y ) = H(X|Y ) + H(Y |X)
vérifie les trois premières assertions.
2. Dans quel cas a-t-on ρ(X, Y ) = 0 ? Comment faut-il modifier la quatrième assertion pour que
ρ(X, Y ) soit une distance ?
Exercice 6.5. On considère un canal binaire symétrique sans mémoire avec une probabilité d’erreur p = 0.1
et une source binaire sans mémoire uniforme. On note X l’entrée et Y la sortie du canal.
4. Montrer qu’on peut retrouver la même loi de probabilité en supposant Y = X + Z mod 2 où Z est
une variable de Bernouilli égale à 1 avec la probabilité p et indépendante de X.
5. Montrer que deux séquences x1:n et y1:n sont conjointement typiques si et seulement si la séquence
z1:n = y1:n − x1:n est typique
6. On donne ci-dessous les propriétés de la loi binomiale avec p = 0.1 et n = 25. En déduire le nombre
(25)
de séquences dans T0.2 (X, Y )
54
Exercice 6.6. Dans cet exercice, on souhaite définir l’information mutuelle pour trois variables aléatoires
X, Y , Z.
1. Dessiner un diagramme de Venn et en déduire que si une telle quantité devait exister, on pourrait la
définir par :
I(X; Y ; Z) = I(X; Y ) − I(X; Y |Z)
2. Montrer que
Exercice 6.7. Soient X et Y des variables aléatoires discrètes et ϕ une fonction déterministe. A quelle
condition a-t-on H(X|ϕ(Y )) = H(X|Y ) ?
2. Montrer qu’il existe deux distributions de longueurs lc optimales possibles: (1, 2, 3, 3) et (2, 2, 2, 2)
Exercice 6.9. On considère une source X sur un alphabet X = {x1 , . . . , xM } et l’on note pi = pX (xi ).
On suppose que p1 ≥ p2 ≥ . . . ≥ pM . On note
X
i−1
Fi = pk
k=1
1. Tester cette stratégie sur la source de loi (0.5, 0.25, 0.125, 0.125)
Exercice 6.10. Calculer les longueurs des mots-codes binaires du code binaire optimal de la source de loi
1 1 1
,
100 100 , . . . , 100 .
55
Exercice 6.11. On considère un canal sans mémoire où l’entrée X et la sortie Y sont dans un alphabet
X = Y = {0, . . . , 10}. On suppose que Y = X + Z mod 11 où Z est une variable aléatoire indépendante
de X et de loi uniforme sur l’alphabet Z = {1, 2, 3}. Calculer la capacité du canal ainsi que la loi de
probabilité p∗ (x) qui permet de l’atteindre.
Exercice 6.12. On considère un canal donc la loi de probabilité conditionnelle est donnée par :
Y |X Y =1 Y =2 Y =3 Y =4
1 1
X=1 2 2 0 0
1 1
X=2 0 2 2 0
1 1
X=3 0 0 2 2
1 1
X=4 2 0 0 2
Exercice 6.13. On considère deux canaux en série. Le premier canal, de capacité C, part d’un alphabet
X vers un alphabet Y. Le deuxième canal efface les symboles reçus avec une probabilité α. Il part ainsi de
l’alphabet Y vers l’alphabet Z = {Y, e} et on a :
(
(1 − α)P (Y = z|X = x) pour z ∈ Y
P (Z = z|X = x) =
α pour z = e
3. On suppose que l’on reçoit le message m1 = [1101101], encodé par G′ . Réaliser un décodage par
syndrome pour retrouver le message envoyé.
Exercice 6.15. Juxtaposition de deux codes. On considère deux codes linéaires C1 et C2 sur F2 de
même longueur n. On appelle G1 (resp. G2 ), H1 (resp. H2 ), k1 (resp. k2 ) et d1 (resp. d2 ) les matrices
génératrices, matrices de contrôle, nombres de bits par bloc et distances minimales des deux codes. On
considère le code
C3 = {[c1 , c2 ] : c1 ∈ C1 , c2 ∈ C2 }
56
1. Montrer que C3 est un code linéaire
2. Calculer G3 en fonction de G1 et G2
3. Calculer H3 en fonction de H1 et H2
4. Calculer k3 en fonction de k1 et k2
5. Calculer d3 en fonction de d1 et d2
57