Théorie de l’information et applications

TPs d’Agnès Desolneux, Eva Wesfreid, Sébastien Li Thiao Té

Jean-Michel Morel.

September 1, 2009
2

Introduction
Notre civilisation a rendu trois types de données numériques omniprésents dans la communi-
cation humaine: les sons digitaux, les images digitales et les données alpha-numériques (les
textes). Ils représentent désormais trois des cinq vecteurs principaux de la communication
humaine. (Les deux autres sont la conversation et la gestuelle, quand les communiquants sont
en présence l’un de l’autre). Les recherches sur les trois modes de représentation digitaux,
très complexes, ayant chacun sa structure propre, ne font encore que commencer. Toute-
fois, la théorie de l’information et l’analyse de Fourier ont permis de délimiter un champ
scientifique suffisant pour qu’on puisse, entre autres, traiter très rigoureusement d’un des
problèmes les plus cruciaux: la compression des données transmises sous l’une quelconque de
ces trois formes.
Dans ce cours, nous allons présenter toutes les bases mathématiques utiles pour compren-
dre comment un texte, une image, ou un son digitaux sont créés, quelles sont les distorsions
inhérentes à la nature de l’image ou du son digital d’une part, et celles qui sont entraı̂nées
par une ”mauvaise” digitalisation, enfin comment mesurer la quantité d’information qu’elles
contiennent et enfin comment les comprimer.
Le cours ira de la théorie à la pratique la plus commune. On commencera avec l’analyse
de Fourier, les ondelettes, et la théorie de l’information et de la communication de Shannon.
Et on en arrivera à détailler les formats de compression les plus courants en informatique
et sur le web pour textes, images et sons.
La théorie de la communication de Shannon, publiée en 1948, rebaptisée ensuite théorie
de l’information est le texte fondateur, que nous analyserons en détail. Cette théorie propose
une chaı̂ne complète pour coder, comprimer et transmettre tous messages entre humains,
et particulièrement les signaux (voix et images). Les théories mathématiques sous-jacentes
sont d’une part la théorie des probabilités discrètes à laquelle s’ajoute une notion issue de
la thermodynamique des gazs, la notion d’entropie et d’autre part l’analyse de Fourier, qui
permet de formaliser le passage d’un signal ou d’une image vus comme des fonctions à leur
représentation discrète par échantillonnage.

La théorie de Shannon: compression sans perte : les textes

Nous traiterons d’abord de la théorie de Shannon, qui définit la quantité d’information con-
tenue dans un message et traite de sa compression optimale. La notion centrale de cette
partie est celle d’entropie. Les codages les plus usités: Shannon, Huffman, Lempel-Ziv,
seront expliqués, démontrés mathématiquement, et testés.
Des expériences sur des textes de divers types seront menées pour vérifier la validité des
algorithmes de compression, et mener quelques expériences de synthèse automatique de texte
et de comparaison entropique de textes variés.

Les images
Bien que notre civilisation ait multiplié la présence des signaux, images et sons, et surtout
des images et sons digitaux (ou numériques), leur nature est mal connue du public, et même
des spécialistes. En effet, ceux-ci sont rarement à la source de l’image : ils ne savent pas com-
ment l’image a été enregistrée, transmise, comprimée. La vision correcte de l’image demande
une connaissance approfondie de la structure des images digitales et de toutes les distorsions
 3

entrainées par leur caractère d’images digitales. Dans ce texte, nous allons présenter toutes
les bases mathématiques utiles pour comprendre comment une image ou un son digitaux
sont créés, quelles sont les distorsions inhérentes à la nature de l’image ou du son digital
d’une part, et celles qui sont entrainées par une “mauvaise” digitalisation. Nous décrirons
ensuite les méthodes classiques et nouvelles de restauration, c’est-à-dire les méthodes qui
visent, partant d’un signal abimé, à retrouver une image conforme à une acquisition cor-
recte. Nous commencerons par un long exposé des notions d’analyse de Fourier nécessaires
pour comprendre l’échantillonnage de l’image, i.e. sa réduction à un tableau fini de valeurs
numériques. Nous expliquerons la théorie de Shannon, qui fixe les règles d’échantillonnage
correct, et nous décrirons les manipulations élémentaires que permet l’usage correct de cette
théorie : translation, rotation et zoom de l’image notamment. Toutes ces manipulations
seront illustrées d’exemples réalistes. Ensuite, nous aborderons les distorsions “nécessaires”,
celles qu’entraine la nature même des images numériques, à savoir le phénomène de Gibbs
ou “ringing”, la quantification et le flou. Pour chacun de ces phénomènes, nous montrerons
aussi des exemples, et nous traiterons ensuite le problème de la restauration, c’est-à-dire de
l’élimination des distorsions, notamment quand elles sont plus poussées que ne le permet la
théorie de Shannon (trop de bruit, trop de flou, trop de quantification, trop d’aliasing...) En-
fin, utilisant les éléments d’analyse de Fourier détaillés l’an dernier et la théorie de Shannon,
en arrivera à expliquer en détail comment marche l’algorithme de compression d’images du
web: l’algorithme JPEG (format .jpg de toutes les images courantes).

Les sons
La dernière partie en vient au son et donne les éléments du vaste programme de décomposition
d’un son en atomes temps-fréquence, ou ”notes”. L’outil principal est la transformée de
Fourier à fenêtre, avec une ouverture sur la théorie des ondelettes.

Le cours
Principe du cours
Le but de ce cours est donc de donner les outils mathématiques, mais toujours en les reliant
à des expériences visuelles ou auditives permettant au lecteur de voir l’effet des opérations
sur les textes, images et signaux.
Un polycopié sera distribué.
Les travaux pratiques associés à ce cours sont essentiels et mettront en oeuvre pratique-
ment, sur des images, des sons et des textes, toutes les notions introduites.
La note sera basée sur un rapport de travaux pratiques et un devoir où les élèves devront
résoudre les exercices mathématiques les plus illustratifs.

Déroulement du cours
Le cours dure 16 heures suivies de 16 heures de travaux dirigés. Le cours ne demande que des
connaissances de licence (séries de Fourier et probabilité discrète). Ces notions sont de toutes
façons rappelées dans le polycopié. Son but est de décrire une des théories mathématiques
majeures du XX-ème siècle, la théorie de la communication de Shannon.
4

– Premier et deuxième cours de quatre heures qui introduisent aux notions d’entropie
et d’entropie relative d’une variable aléatoire discrète et expliquent la théorie de la
communication de Shannon. Après une explication du modèle markovien du langage,
le codage optimal théorique par la méthode du décompte des messages typiques est
démontré. Ensuite, cette méthode est étendue aux couples entrée-sorties typiques pour
démontrer le grand théorème de Shannon, à savoir l’existence de communication sûre
malgré le bruit. Enfin un algorithme de codage universel, Lempel-Ziv, sera expliqué.

– Troisième cours de quatre heures. Dans les deux premières heures on revient sur la
théorie de l’information en donnant la théorie des codes préfixe, l’inégalité de Kraft et
en prouvant l’optimalité du code de Huffman et la quasi-optimalité du code de Shannon.
Dans la deuxième partie on revient sur la théorie de l’échantillonnage en expliquant la
transformée de Fourier à fenêtre et sa variante orthogonale, les ondelettes de Malvar-
Wilson.

– Quatrième cours de quatre heures. Entièrement consacré à la réduction du continu au

discret, à savoir la théorie de l’échantillonnage de Shannon appliquée aux signaux et
images. Le lien entre transformée de Fourier discrète et série de Fourier est mis au
clair par la formule d’aliasage. L’utilisation de la FFT pour diverses manipulations
d’images est ensuite décrite (zoom sans aliasage, translation, rotation). Le phénomène
de Gibbs sera aussi commenté. La représentation en Fourier permet un premier abord
des questions de débruitage, de déflouage, et en général de filtrage des images. Le
standard de compression JPEG sera décrit en détail, car il présente un usage intégré
de toutes les notions de traitement d’images et de théorie de l’information introduites
précédemment.

– Les quatres travaux pratiques illustrent directement le cours : après une introduction
à Matlab, génération de phrases par modèle markovien, entropie d’une phrase et com-
pression par le code de Huffman, échantillonnage des images et diverses manipulations,
enfin segmentation d’un signal de voix en intervalles par le choix d’une base de Malvar-
Wilson d’entropie minimale. C’est dans ce dernier travail que les deux aspects (Fourier
et entropie) sont utilisés conjointement.

– Le contrôle de travail et de connaissances consiste en la remise par les étudiants d’un

devoir contenant les solutions des exercices ainsi que d’un rapport de travaux pratiques.
Les deux copies sont notés sur dix.

– Le cours oral a ajouté quelques commentaires sur le filtrage et la restauration qu’il

faudra ajouter au chapitre ”le cas discret”.

Le devoir
Le devoir consiste à rendre tous les exercices du cours, auquels vous pouvez ajouter tout
commentaire de lecture, critique du cours, expérience ou correction. Ils seront très bienvenus.
Les exercices dits de lecture où on vous demande de lire le texte de Shannon, de commenter
et de comparer avec les preuves apportées sont optionnels et donc en bonus. Le texte de
Shannon se trouve à l’adresse suivante sur le site des Bell labs, laboratoire où il fut écrit :
[Link] .
Contents

1 La modélisation probabiliste discrète (révision) 7

1.1 Probabilité conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1 Indépendance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.2 Modèles, exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Distributions discrètes de probabilité (révision) 13

2.1 Espérance et variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 La convergence en probabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Codes préfixes 17
3.1 Théorie des codages préfixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.1 Un premier exemple: le code de Shannon . . . . . . . . . . . . . . . . 22

4 Le codage de Huffman 27
4.1 Exercices et implémentations Matlab . . . . . . . . . . . . . . . . . . . . . . . 30

5 Langage et communication selon Shannon 33

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.2 Exercices d’implémentation en Matlab . . . . . . . . . . . . . . . . . . . . . . 35

6 Messages répétés et entropie 37

6.1 Messages typiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.2 Exercices et implémentations Matlab . . . . . . . . . . . . . . . . . . . . . . . 41

7 La communication sûre est possible malgré le bruit 43

7.1 Transmission dans un canal bruité . . . . . . . . . . . . . . . . . . . . . . . . 43
7.2 Le théorème fondamental pour un canal discret bruité . . . . . . . . . . . . . 46

8 Séries de Fourier (Révision) 49

8.1 Convolution des fonctions périodiques et séries de Fourier . . . . . . . . . . . 52
8.1.1 Autres bases de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . 54
8.2 Bases de Fourier en dimension 2 . . . . . . . . . . . . . . . . . . . . . . . . . 55
8.3 Décroissance des coefficients de Fourier et problèmes de compression du signal 56
8.4 Phénomène de Gibbs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5
6 CONTENTS

9 Le cas discret (Révision) 63

9.1 Transformée de Fourier Discrète, applications . . . . . . . . . . . . . . . . . . 63
9.1.1 La dimension 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
9.1.2 La dimension 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
9.1.3 Le phénomène du repliement de spectre ou aliasage . . . . . . . . . . . 67
9.1.4 La transformée de Fourier rapide . . . . . . . . . . . . . . . . . . . . . 71
9.1.5 L’utilisation de la transformée de Fourier discrète pour définir zoom,
translations et rotations des images . . . . . . . . . . . . . . . . . . . . 74
9.1.6 Importances relatives de la phase et du module de la TFD pour une
image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
9.2 Lien avec la théorie de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . 80

10 La compression des images et la norme JPEG 85

10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
10.2 L’algorithme avec pertes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
10.3 JPEG, codage sans pertes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
10.4 Exercices et implémentation Matlab . . . . . . . . . . . . . . . . . . . . . . . 91

11 Ondelettes de Malvar-Wilson et segmentation de la voix 93

Chapter 1

La modélisation probabiliste
discrète (révision)

On part d’un ensemble d’évènements élémentaires ou atomiques Ω, par exemple les résultats
d’un match de football, Ω = {(0, 0), (0, 1), (1, 0), . . . , (40, 40)}. Plus généralement Ω = IN×IN.
Un évènement en général est un sous-ensemble de Ω. Par exemple A = {(m, n) | m > n}
caractérise le fait que l’équipe 1 gagne, et B = {(m, n) | m = n} caractérise le match nul. Si
ω = (m, n) est æ en A, s’écrit que “ω est une réalisation de A.”
Définition 1.1 Algèbre d’ensembles “intéresants”: C’est un ensemble A d’ensembles de Ω
que satisfait les axiomes suivants:
– ∅, Ω ∈ A

– A ∈ A ⇒ Ac ∈ A

– A, B ∈ A ⇒ A ∩ B ∈ A (et donc aussi A ∪ B ∈ A).

Définition 1.2 Variable aléatoire discrète. C’est une application X : Ω → E où E est un
ensemble fini ou dénombrable et tel que les ensembles {ω ∈ Ω | X(ω) = e} soient tous dans
A. Dans le cas où E ⊂ R, on parle de variable aléatoire real.

Dans l’exemple du football, M (ω) = M ((m, n)) := m est une variable aléatoire réelle qui
peut s’appeler “nombre de buts de l’équipe 1”. Regardons un exemple de Ω plus général
qui est aussi un grand classique de théorie des probabilités, le jeu de pile ou face. On code
face par 0 et pile par 1. Une suite infinie de tirages appartient à l’ensemble d’évènements
Ω := {0, 1}IN . Chaque élément de Ω s’écrit ω = (ω(1), . . . , ω(n), . . . ) et l’application Xn :
ω → ω(n) est un variable aléatoire qu s’interprète comme le “résultat du n-ième tirage”.
Aussi nous pouvons considérer l’ensemble des N premiers tirages, ΩN := {0, 1}N . D’une
certaine manière ΩN est contenu dans Ω mais pour le formaliser il faut associer à chaque
élément ωN = (ω(1), . . . , ω(N )) ∈ ΩN l’ensemble de toutes les suites qui commencent par
ωN , que nous appellerons Ω(ωN ). Nous pouvons considèrer l’algèbre engendrée par les Ω(ωN )
quand ωN varie dans ΩN et N varie dans IN. Il s’agit de l’algèbre la plus petite contenant
tous ces évènements. Cette algèbre s’appelle “algèbre d’évènements en temps fini”.

Exercice 1 Démontrer que tout élément de l’algèbre A des évènements en temps fini est une
union finie d’évènements de type Ω(ωN ). Pour le prouver, il suffit d’appeler à cet ensemble

7
8 CHAPTER 1. LA MODÉLISATION PROBABILISTE DISCRÈTE (RÉVISION)

d’unions finies et de prouver qu’elle a la structure d’une algèbre. S’il en est ainsi, elle est
forcément l’algèbre la plus petite contenant les Ω(ωN ).

En fait l’algèbre des évènements en temps fini ne nous dit rien sur ce qui se passe à l’infini.
Par exemple l’ensemble : A := {ω ∈ Ω | limn Xn (ω) = 0} n’est pas dans A. Pour le voir, il
suffit de remarquer que s’il était dans A, on aurait A = ∪n∈I Ω(ωn ) où I est un sous-ensemble
fini de IN et ωn ∈ ΩN . Appelons k l’indice le plus grand qui apparaı̂t dans I. Alors on vérifie
immédiatement que si ω ∈ A et si on considère un autre élément ω 0 ∈ Ω tel que ω 0 (i) = ω(i)
pour i ≤ k, alors ω 0 est en A. Donc nous pouvons imposer que ω 0 (n) = 1 pour n ≥ k, et celà
implique que ω 0 n’est pas dans A, une contradiction. C’est pourquoi Kolmogorov a étendu la
notion d’algèbre à celle de σ−algèbre, ce qui permet de considérer un évènement comme A.

Définition 1.3 Une σ-algèbre F de Ω est une algèbre telle que si An est dans F, alors
∪n An est aussi dans F. Etant donné un ensemble A de parties de Ω, on appelle σ-algèbre
engendrée par A et on écrit σ(A) l’intersection de toutes las σ-algèbres contenant A.

Une telle intersection existe parce qu’il y a au moins une σ-algèbre qui contienne A :
l’ensemble P(Ω) de toutes les parties de Ω est en effet une σ-algèbre.

Exercice 2 Démontrer que l’ensemble A := {ω ∈ Ω | limn Xn (ω) = 0} est dans σ(A), où A
désigne l’algèbre d’évènements en temps fini. Indication: prouver que
[ \
A= {ω | Xm (ω) = 0.}
n≥1 m≥n

En pratique on commence par connaı̂tre la valeur de la probabilité de quelques évènements.

Donc, on déduit la probabilité des évènements de l’algèbre A engendrée par ces évènements,
et finalement on déduit la probabilité des évènements de σ(A). Les règles pour déduire ces
probabilités les unes des autres sont:

Définition 1.4 Soit Ω un espace de probabilité muni d’une une σ-algèbre F. On dit que P
est une probabilité sur (Ω, F) si pour tout A dans F et pour toute suite disjointe An dans F,

– 0 ≤ P(A) ≤ 1, P(Ω) = 1
S P
– P( n An ) = n P(An ).

La dernière propriété s’appelle “σ-additivité” de la probabilité.

Exercice 3 déduire les conséquences suivantes:

– si A ⊂ B, alors P(A) ≤ P(B).

P
– Si An ∈ F, P(∪n An ) ≤ n P(An ).
1.1. PROBABILITÉ CONDITIONNELLE 9

1.1 Probabilité conditionnelle

En réalité très souvent les probabilités auxquelles on a accès sont des probabilités condition-
nelles.

Définition 1.5 Etant donné un espace de probabilité (Ω, F, P) et A, B ∈ F , on appelle

probabilité conditionnelle de A sachant B

P(A ∩ B)
P (A | B) := si P(B) 6= 0, = 0 si P(B) = 0.
P(B)

Exercice 4 Démontrer que pour tout B dans F, l’application A → P(A | B) est une prob-
abilité sur (Ω, F). Démontrer également la “règle des causes totales” : si les Bi , i ∈ IN sont
des évènements formant une partition de Ω, alors
∞
X
P(A) = P(A | Bi )P(Bi ).
i=1

1.1.1 Indépendance

Définition 1.6 Soit (Ω, F, P) un espace de probabilité.

A et B sont indépendantes si P(A | B) = P(A), ce qui est équivalent à P(A ∩ B) =
P(A)P(B).

– Une famille (Ai )i∈I est une famille d’évènements indépendants si pour toute sous-
famille finie Ai1 , . . . , Ain , P(Ai1 ∩ · · · ∩ Ain ) = P(Ai1 ) . . . P(Ain ).

– Une suite (Xn )n≥1 de variables aléatoires discrètes Xn : Ω → E est indépendante si

pour tout (e1 , . . . , en , . . . ) ∈ E IN , les évènements (Xn = en ) sont indépendants.

– Une suite (Xn )n≥1 de variables aléatoires réelles Xn : Ω → R est indépendante si

pour toute suite d’intervalles de R, (I1 , . . . , In , . . . ) les évènements (Xn ∈ In ) sont
indépendants.

Exercice 5 Deux exemples importants:

– Soit Ω = [0, 1]N , P(A) = volume(A) par A ⊂ Ω. Démontrer que les coordonnées
Xi : ω = (ω1 , . . . , ωn ) ∈ Ω → ωi sont des variables aléatoires indépendantes.

– Si par contre Ω = B(0, 1) est la boule de centre 0 et de rayon 1 et P est la mesure de

Lebesgue multipliée par un facteur λ tel que P(B(0, 1)) = 1, montrer que les variables
Xi ne sont pas indépendantes.

1.1.2 Modèles, exemples

Problème des trois prisonniers
Trois prisonniers A, B et C sont enfermés sans communication dans la prison d’un régime
totalitaire. Ils savent que deux d’entre eux sont condamnés à mort mais ils ignorent lesquels.
Bien sûr, le geôlier n’est pas autorisé à le leur faire savoir. Un des prisonniers, A, propose
10 CHAPTER 1. LA MODÉLISATION PROBABILISTE DISCRÈTE (RÉVISION)

alors au geôlier le raisonnement suivant : “Je sais déjà que l’un de B ou de C est condamné.
Tu ne me donneras donc aucune information utile sur mon sort si tu me communiques que
l’un de B ou de C est condamné. S’il te plaı̂t, donne-moi le nom d’un des deux, B ou C, qui
est condamné.” Le geôlier réfléchit un moment et répond : “-tu as raison. Je t’annonce que
B est condamné. Mais ne va pas croire qu’avec cette information tu va pouvoir tirer quoi
que ce soit d’utile sur ton propre sort” Le prisonnier répond “- tout le contraire ; avant j’avais
une probabilité de 2/3 d’être condamné ; maintenant tout se joue entre C et moi, n’est-ce
pas? Donc ma probabilité de mourir est devenue 1/2 et non plus deux tiers. Je peux dormir
un peu plus tranquille!!”. Le geôlier hausse les épaules et s’en va.
Qui a raison, du prisonnier A ou du geôlier? Le prisonnier A a-t-il raison de penser qu’il
a gagné un peu de tranquillité, ou est-il victime d’une illusion?

Solution
Pour formaliser cet type de problème, il faut chercher les évènements atomiques, c’est-à-dire
énumérer chaque suite de probabilités et ensuite essayer de chercher sa probabilité. Une
fois calculées les probabilités de ces évènements atomiques, toue autre probabilité devient la
probabilité d’un évènement qui est une union d’évènements atomiques. Donc elle devient une
somme de probabilités, facile à calculer. Selon cette description la manière de procéder est:

– énumérer et nommer tous les évènements distincts (en général des suites d’évènements);

– donner un nom aux variables aléatoires d’intérêt;

– exprimer les probabilités indiquées par le problème: très souvent nous verrons que ce
sont des probabilités conditionnelles;

– prendre en compte toutes les indépendances implicites dans l’énoncé;

– formaliser les évènements dont on veut calculer les probabilités et les exprimer en fonc-
tion des évènements élémentaires;

– finalement calculer la probabilité cherchée.

Notre problème montre deux évènements aléatoires consécutifs: d’abord le choix des
prisonniers condamnés: AB, BC ou AC. Ensuite le choix éventuel effectué par le geôlier
de B ou de C dans le cas où il lui faut effectivement choisir, quand B et C sont tous deux
condamnés. De plus, il faut prendre en compte un grand principe des probabilités que parfois
on appelle principe de probabilité subjective, suivant lequel quand de plusieurs possibilités 1,
2, ... n on ignore tout, on attribue la même probabilité à chacune des possibilités, c’est-à-dire
1/n. Dans notre cas la probabilité que AB, ou BC, ou AC soient condamnés doit donc être
fixée à un tiers. De la même manière, si B et C sont condamnés le geôlier doit choisir entre
eux pour donner un nom. Comme A ignore quel critère le geôlier adopte pour choisir entre
B et C, il doit considérer que les probabilités que le geôlier nomme B ou C sont égales à 1/2.
Les évènements atomiques sont ABC, ACC, BCB et BCC, où les deux premières lettres
indiquent les condamnés, et la dernière est le choix du condamné nommé par le geôlier. Les
variables aléatoires naturelles sont X, Y , Z, où XY est la liste ordonnée des condamnés
et Z le condamné indiqué par le geôlier. Par exemple XY (ABC) = AB et Z(ABC) = C.
Maintenant, nous pouvons exprimer les probabilités subjectives qui sont nos seules données:
1.2. EXERCICES 11

1
– P(XY = AB) = P(XY = BC) = P(XY = AC) = 3

– P(Z = C | XY = BC) = P(Z = B | XY = BC) = 12 .

Deux des probabilités auxquelles nous avons accès sont des probabilités conditionnelles. Celà
est tout-à-fait naturel car cela correspond à des questions du type : “quelle est la probabilité
de tel évènement si tel autre se produit?” Maintenant, nous pouvons traduire la question
que se pose le prisonnier : “quelle est ma probabilité d’être sauvé sachant que le geôlier m’a
indiqué que B est condamné?” Nous devons donc calculer:

p = P(XY = BC | Z = B)

Par définition de la probabilité conditionnelle,

P(XY = BC & Z = B)
p= .
P(Z = B)
Mais en utilisant ce que nous savons et de nouveau la probabilité conditionnelle.
11 1
P((XY = BC) & (Z = B)) = P(Z = B | XY = BC)P(XY = BC) = = .
23 6
Pour calculer P(Z = B) nous pouvons utiliser la règle des causes totales:

P(Z=B) = P(Z=B|XY =AB)P(XY =AB) + P(Z=B|XY =AC)P(XY =AC)

+P(Z=B|XY =BC)P(XY =BC)
1 1 1 1
= +0+ . = .
3 2 3 2
=

Finalement nous obtenons

1
6 1
p= 1 = .
2
3
L’estimation de sa propre probabilité de survie par A n’a pas été changée par l’information
donnée par le geôlier.

Exercice 6 La conclusion antérieure dépend strictement de l’hypothèse que le prisonnier ne

connait rien sur le critére de sélection par le geôlier entre B et C. Supposons que le prisonnier
devine que le geôlier préfère nommer B si B et C sont condamnés. Alors q = P(Z = B |
XY = BC) > 12 . Reprendre les calculs précédents et démontrer que le prisonnier gagne alors
de l’information grâce à la réponse du geôlier.

1.2 Exercices
Exercice 7 Un modèle discret pour gagner à un jeu très simple et moins sinistre. Il y a trois
cartes. La première a deux faces rouges et nous l’appellerons RR. La seconde a deux faces
vertes (V V ) et la troisième a une face rouge et une autre verte (RV ). On tire une carte au
hasard et on tire aussi au hasard le coté exposé de la carte. Les joueurs observent cette face
exposée et font des paris sur la couleur de l’autre face.
12 CHAPTER 1. LA MODÉLISATION PROBABILISTE DISCRÈTE (RÉVISION)

Supposons par exemple que la face exposée soit rouge. Quelle est la probabilité que l’autre
face soit rouge? Et verte? Supposons que chaque joueur parie pour une couleur. Si l’autre
joueur place 100 euros sur la table en pariant pour rouge, combien devrais-je placer sur la
table, en pariant sur vert, pour que mon espérance de gain soit positive?

Exercice 8 Soit An une suite croissante (An ⊂ An+1 ) d’algèbres de Ω. Démontrer que
S
n An est une algèbre.

Exercice 9 Soit Ai , i ∈ IN une partition de Ω. Décrire l’algèbre engendrée par les Ai et la

σ-algèbre engendrée par les Ai .

Exercice 10 Démontrer que P(A | B&C)P(B | C) = P(A&B | C).

Exercice 11 Si A1 , . . . An sont indépendants alors Ãi sont indépendants, où Ãi peut être
arbitrairement Ai ou Aci .

Exercice 12 Soit un espace Ω à quatre elements {ω1 , ω2 , ω3 , ω4 ). Soit P la probabilité définie

par P(ωi ) = 14 , i = 1, . . . , 4. Considérons les évènements A = {ω1 , ω2 }, B = {ω2 , ω3 },
C = {ω1 , ω3 }. Vérifier que A et B sont indépendants, B et C aussi, C et A aussi, mais que
A, B, C ne sont pas indépendants.

Exercice 13 Trois touristes tirent en même temps sur un éléphant. L’animal meurt, touché
par deux balles. La valeur de chaque chasseur est mesurée par la probabilité qu’il atteigne sa
cible. Ces probabilités sont 1/4, 1/2, 3/4. Calculer pour chacun des chasseurs sa probabilité
d’avoir raté l’éléphant. (Cette probabilité dépend de l’évènement observé: si l’éléphant avait
reçu trois balles, nous saurions par exemple que la probabilité d’avoir raté est zéro pour
chaque chasseur).

Exercice 14 Le professeur Peplluis Serra Balaguer voyage de Toronto à Paris en passant

par New York et Francfort. La probabilité que la valise se perde est identique dans chacun de
ces aéroports et égale à p. Quand le professeur Balaguer arrive à Paris, sa valise a disparu.
Quelles sont les probabilités que la valise soit restée à Toronto, Londres et Paris?
Chapter 2

Distributions discrètes de
probabilité (révision)

Définition 2.1 Soit (Ω, F, P) un espace de probabilité, X un ensemble fini ou dénombrable

et X : Ω → X tel que les ensembles {ω ∈ Ω | X(ω) = x} soient tous dans la tribu F. Alors
on dit que X est une variable aléatoire sur (Ω, F, P).

Par exemple une suite de tirages à pile ou face, qui se formalise comme une suite de
variables de Bernoulli, X1 , ..., Xn avec Xi = 0 (pile) où Xi = 1 (face) et P(Xi = 1) = p,
P(Xi = 0) = 1 − p. Si les tirages sont indépendants, nous avons

P(X1 = x1 , . . . , Xn = xn ) = P(X1 = x1 ) . . . P(Xn = xn ) pour tout (x1 , . . . , xn ) ∈ {0, 1}n .

Alors en écrivant X = (X1 , . . . , Xn ) et x = (x1 , . . . , xn ),

n
X
h(x) n−h(x)
P(X = x) = p (1 − p) , où h(x) := xi .
i=1

La fonction h(x) s’appelle “poids de Hamming” de x.

P Pn k k
Exercice 15 Vérifier que x∈{0,1}n p(x) = k=0 Cn p (1 − p)n−k = 1.

Définition 2.2 Si X est un ensemble dénombrable et (p(x)), x ∈ X une fonction sur X

satisfaisant:

1. 0 ≤ p(x) ≤ 1
P
2. x∈X p(x) = 1,

on dit que (p(x)), x ∈ X , est une distribution de probabilité sur X .

Exemple fondamental: Si X est une variable aléatoire définie sur (Ω, F, P) et à valeurs dans
X , on considère pour tout A ⊂ X ,
X X
PX (A) := P(X ∈ A) = P(X = x) = PX (x).
x∈A x∈A

Posant p(x) = PX (x), on dit que (p(x)), x ∈ X est la distribution (ou loi) de la variable X.

13
14 CHAPTER 2. DISTRIBUTIONS DISCRÈTES DE PROBABILITÉ (RÉVISION)

Donnons quelques exemples de distributions classiques.

Si X := {0, 1}n , alors p(x) := ph(x) (1 − p)n−h(x) s’appelle distribution de Bernoulli d’ordre
n et paramètre p. C’est la loi de la variable aléatoire X := (X1 , . . . , Xn ) où Xi sont des
variables aléatoires de Bernoulli de paramètre p et ordre P 1. Donc on peut considérer la
distribution sur {0, 1, . . . , n) de la variable aléatoire Sn := ni=1 Xi . C’est facile de vérifier que
P(Sn = k) = Cnk pk (1 − p)n−k = pk . Cette distribution sur {0, 1, . . . , n} s’appelle distribution
binomiale.

2.1 Espérance et variance

Soit X une variable aléatoire discrète avec valeurs dans X , de distribution p(x), x ∈ X . Soit
f : X → R ∪ {+∞, −∞} une application.
P
Définition 2.3 – Si f ≥ 0, on définit E[f (X)] := x∈X P(X = x)f (x). (Cette quantité
peut être infinie).
P
– Si E[|f (X)|] < +∞, se define E[f (X)] := x∈X P(X = x)f (x) et on dit que f (X) est
intégrable.

– E est linéaire et monotone (∀x f (x) ≤ g(x) ⇒ Ef (X) ≤ Eg(X).)

Dans le cas où X est elle-même une variable à valeurs réelles, on définit:

– moyenne de X : m(X) = mX := EX;

– Si X 2 est intégrable, variance de X: σ 2 (X) = σX

2 := E(X 2 ) − (EX)2 .

σ(X) = σX s’appelle la déviation typique de X.

Exercice 16 Vérifier que σX 2 = E[(X − m )2 ]. Vérifier que si X est Bernoulli d’ordre 1 et

X
2
paramètre p, mX = p et σX = p(1 − p). Dans le cas de la binomiale de paramètre p et ordre
n, vérifier que mX = np et σX2 = np(1 − p).

2.2 La convergence en probabilité

Commençons par quelques inégalités. L’inégalité de Markov dit que si X est une variable
aléatoire et f une fonction mesurable telle que f (X) soit intégrable,

E|f (X)|
P(|f (X)| ≥ a) ≤ .
a
On en tire la fameuse inégalité de Tchebychev, qui dit que pour une variable aléatoire réelle
et pour tout ε > 0,
σ 2 (X)
P(|X − EX| ≥ ε) ≤ .
ε2
La démonstration consiste à appliquer l’inégalité de Markov à f (X) = |X − EX|2 .

Exercice 17 Démontrer ces deux inégalités!

2.3. EXERCICES 15

Nous allons appliquer l’inégalité de Tchebychev pour prouver une loi fondamentale, la loi
faible des grands nombres.

Théorème 2.1 Soit uneP suite de variables de Bernoulli indépendantes Xi de paramètre p,

i = 1, . . . , n, . . . et Sn := ni=1 Xi . Alors P(| Snn − p| ≥ ε) → 0 quand n → ∞.

En effet l’espérance (ou moyenne) de Sn est np et la variance de Sn est np(1 − p). Donc la
moyenne de Snn est p et sa variance est σ 2 = p(1−p)
n . Appliquons l’inégalité de Tchebytchev
pour obtenir
Sn p(1 − p)
P(| − p| ≥ ε) ≤ → 0 quand n → ∞.
n nε
Définition 2.4 Soit Yn des variables aléatoires réelles définies sur le même espace de prob-
abilité. On dit que Yn → Y en probabilité si limn→∞ P(|Yn − Y | > ε) = 0 for all ε > 0.

La loi faible des grands nombres s’étend facilement à une situation légèrement plus
générale. Considérons une suite de variables aléatoires Xn indépendantes, équidistribuées
et de variance bornée σ 2 (X) et d’espérance EX. Alors avec le même raisonnement que
précédemment (additivité des variances
P et des espérances et inégalité de Tchebychev), on
obtient le même résultat pour Sn = nk=1 Xk .

2.3 Exercices
Exercice 18 Un lot de montres identiques pour touristes arrive chez un marchand de Barbès.
Ce lot peut provenir de deux usines: l’une à Singapour et l’autre à Hong Kong. Le marchand
sait qu’en moyenne l’usine de Singapour produit un pourcentage de montres défectueuses de
1/200 tandis que l’usine de Hong Kong a un pourcentage de 1/1000. Le marchand teste une
première montre et vérifie qu’elle marche. Quelle est la probabilité que la seconde montre
qu’il va tirer fonctionne?

Exercice 19 On tire au hasard deux points dans [0, 1], indépendamment. Le plus petit des
nombres obtenus est plus grand que 1/3. Quelle est la probabilité que l’autre soit supérieur
à 3/4?

Exercice 20 Pour λ > 0 on définit la loi de Poisson sur IN par

λk
p(k) = e−λ , k = 0, 1, . . . , .
k!
P
Vérifier que k p(k) = 1 et calculer la moyenne et la variance de cette distribution.

Exercice 21 Calculer la moyenne et la variance d’une loi binomiale d’ordre n et de paramètre

p.

Exercice 22 Soient X1 , . . . , Xn n des variables aléatoires discrètes indépendantes, identique-

ment distribuées de variance commune σ 2 . Calculer la variance et l’écart type de X1 +···+Xn
n
.

Exercice 23 On dit qu’une variable aléatoire X à valeurs dans IN suit une loi géométrique de
paramètre p ∈ [0, 1] si P(T = n) = p(1−p)n−1 , n ≥ 1. Calculer la moyenne et la variance de T .
Démontrer que T “n’a pas de mémoire”, c’est-à-dire que P(T ≥ n0 + n | T > n0 ) = P(T ≥ n),
n ≥ 1.
16 CHAPTER 2. DISTRIBUTIONS DISCRÈTES DE PROBABILITÉ (RÉVISION)

Exercice
P∞ 24 Soit X une variable aléatoire avec valeurs en IN. Démontrer que EX =
n=1 P(X ≥ n).
Chapter 3

Codes préfixes

Considérons une distribution discrète de probabilité, (p1 , . . . , pk ). On définit l’entropie de

cette distribution par
k
X
H(p1 , . . . , pk ) := − pi log pi .
i=1
En général le logarithme est en base 2, c’est-à-dire log 2 = log2 2 = 1. L’interprétation de
cette formule par Shannon est la suivante: en théorie de la communication le récepteur ignore
ce que l’émetteur va lui écrire, mais il a néanmoins une idée claire de la probabilité de chaque
message possible. Par exemple p = (p1 , . . . , pk ) peut être la distribution de probabilité des
mots d’un dictionnaire X := {x1 , . . . , xk }. Le degré de communication est supérieur quand
l’incertitude sur le message croı̂t. Pour Shannon, H(p) mesure cette incertitude. Par exemple
si p1 = 1 et si les autres probabilités sont nulles, on vérifie que H(p) = 0, ce qui signifie qu’il
n’y a pas d’incertitude. Si tous les pi sont égaux à k1 , l’entropie est log2 k et doit être maximale.
Nous verrons que cette intuition est juste. L’incertitude ou entropie (Shannon utilise ces deux
mots comme deux équivalents) se mesure en bits, une abbréviation de BInary digiT, terme
créé par John W. Tukey. (Tukey est aussi l’inventeur avec James Cooley de la Fast Fourier
Transform et c’est lui qui inventa le néologisme software). Le bit, unité fondamentale de
l’informatique se définit comme la quantité d’information reçue par un récepteur qui attend
un message 0 ou 1 et qui attribue la même probabilité 21 aux deux possibilités. Effectivement
si p = ( 12 , 12 ), on vérifie que H(p) = 1.

Définition 3.1 Etant donné un ensemble de messages X = {x1 , . . . , xk } nous appellerons

codage de ces messages une application h : X → {0, 1}(IN ) , ensemble des suites finies de zéros
et de uns. Nous écrirons li := l(h(xi )), la longueur du code de xi .

Le code le plus élémentaire que l’on puisse faire est d’énumérer les messages de i = 0 à k,
convertissant i en un nombre binaire. Alors h(x1 ) = 0, h(x2 ) = 1, h(x3 ) = 10, h(x4 ) = 11,
etc. La longueur maximale lk des codes vérifie

[log k] ≤ lk := l(h(xk )) ≤ [log k] + 1.

Shannon démontre de plusieurs manières que, étant donnée une source émettrice d’entropie
p, la longueur minimale moyenne des messages codés en bits est exactement H(p). En d’autres
termes il est possible de transmettre ce qu’émet la source en codant ses messages avec des
nombres faits de zéros et de uns de longueur moyenne H(p). Pour comprendre mieux, nous

17
18 CHAPTER 3. CODES PRÉFIXES

devrons spécifier ce que nous entendons par codage. Nous allons commencer avec une théorie
légèrement plus restrictive, la théorie des codages dits préfixes.

3.1 Théorie des codages préfixes

Un problème technique surgit. Si nous émettons des messages répétés, nous ignorerons où
termine l’un et où commence le suivant: nous observons une suite de zéros et de uns et ne
savons comment la couper. Si de toute suite observée h(xi1 ) . . . h(xin ) on peut déduire de
manière unique les xi1 , . . . , xin , nous dirons que le codage est uniquement déchiffrable. Une
manière très simple d’obtenir des codages déchiffrables est de leur imposer la propriété de
préfixe.

Définition 3.2 Un codage est appelé préfixe si pour tout i, 1 ≤ i ≤ k, chaque code h(xi )
n’est le préfixe d’aucun autre code h(xj ).

Exercice 25 Démontrer qu’un codage préfixe est uniquement déchiffrable.

La théorie des codages préfixes est merveilleusement simple. Nous allons caractériser tous
les codages préfixes et donner quelques exemples optimaux.

Théorème 3.1 (Inégalité de Kraft). Si h est un codage préfixe, notons l1 , . . . , li , . . . , lk

les longueurs des codes pour chaque symbole xi . Si h est préfixe, alors
k
X
2−li ≤ 1. (3.1)
i=1

Réciproquement, soient (li ), 1 ≤ i ≤ k entiers positifs tels que (3.1) soit vérifiée. Alors
il existe un codage h avec la propriété du préfixe, dont les codes ont pour longueurs (li ),
1 ≤ i ≤ k.

Démonstration La démonstration se fait de manière très intuitive en dessinant un arbre

binaire complet de profondeur n dont les feuilles sont les nombres binaires de n chiffres, de
00. . . 00 à 11. . . 11 (Voir la figure 3.1.) La racine de l’arbre est le mot vide. Ses fils sont
0 et 1. Le premier, 0, a pour fils 00 et 01 et le second, 1, a 10 et 11, etc. Les noeux de
l’arbre donnent tous les codes possibles de longueur inférieure ou égale à n. Chaque noeud de
l’arbre est la racine d’un sous-arbre. Dans ce sous-arbre il y a tous les codes qui ont sa racine
comme préfixe. De cette remarque on déduit qu’un codage préfixe h est tel qu’aucun code
n’appartienne au sous-arbre d’un autre code. En d’autres termes, les sous-arbres des h(xi )
sont disjoints. Il est aussi facile de voir que comme h(xi ) a une longueur li , son sous-arbre a
une profondeur n − li et le nombre de feuilles du sous-arbre de h(xi ) est 2n−li . Comme ces
ensembles de feuilles sont tous disjoints, et comme le nombre total de feuilles est 2n on arrive
à l’inégalité X
2n−li ≤ 2n
i

qui implique l’inégalité de Kraft.

3.1. THÉORIE DES CODAGES PRÉFIXES 19

Figure 3.1: Arbre binaire complet des chiffres de moins de trois symboles. Chaque noeud de
l’arbre représente un code. Si un codage est préfixe, il correspond à une sélection de noeuds
tels qu’aucun noeud ne soit la racine d’un sous-arbre dont un autre noeud serait racine.
Exemple: 00, 011, 10, 110 est un codage préfixe.

Maintenant voyons la réciproque. Si les nombres (li )1≤i≤k vérifient l’inégalité de Kraft,
pourrons nous définir un codage préfixe h tel que li = h(xi )? La construction est semblable
au raisonnement précédent (voir la figure 3.2). On considère de nouveau l’arbre complet
binaire de profondeur n = maxi li . On ordonne les li par ordre croissant, l1 ≤ · · · ≤ li ≤ . . . lk
et on considère les 2n−l1 premières feuilles de l’arbre : ce sont les feuilles d’un sous-arbre dont
la racine a pour longueur l1 : on décide que cette racine soit le code de x1 . Ensuite voyons les
2n−l2 feuilles suivantes. De nouveau ce sont les feuilles d’un sous-arbre de racine de longueur
l2 et cette racine devient le code de x2 . Nous pouvons itérer tant que la quantité de feuilles
utilisées n’excède pas 2n , mais celà est exactement ce que nous garantit l’inégalité de Kraft!
La figure 3.2 traite l’exemple suivant :

l1 = 2, l2 = l3 = 3, l4 = 5.

Dans cet exemple n = 5 et nous avons 25−2 = 8, 25−3 = 4, 25−5 = 1, ce que nous donne la
taille de chaque sous-arbre. Los codes obtenus pour x1 , x2 , x3 , x4 sont 00, 010, 011 et 10000.
◦

Exercice 26 Démontrer de manière plus formelle que le codage obtenu dans la seconde
partie de la démonstration du théorème 3.1 est préfixe. Pour comprendre mieux, tenter la
même construction avec le même exemple, mais cette fois en ordonnant les sous-arbres avec
des tailles qui croissent de haut en bas. Que se passe-t-il? Pourquoi ça ne marche pas?

Exercice 27 Important! vérifier que la construction du code de la seconde partie du théorème

3.1 se résume par l’algorithme suivant:
Algorithme calculant un codage préfixe h(xi )
pour une suite l1 ≤ · · · ≤ li ≤ · · · ≤ lk de longueurs fixées et vérifiant l’inégalité de Kraft.
20 CHAPTER 3. CODES PRÉFIXES

On écrit tous les nombres binaires entre 0 et 2m − 1 avec exactement n chiffres (0 ou 1) en

ajoutant à gauche les zéros nécessaires. Alors

1. n = maxi li ;

2. h(x1 ) = les l1 premiers bits de 0 (soit 0 . . . 0 l1 fois);

3. h(xi ) = les li premiers bits de 2n−l1 + · · · + 2n−li−1 , i ≥ 2.

Le théorème précédent nous donne une condition nécessaire sur les longueurs des codes
pour qu’un codage préfixe permette de coder k messages. Maintenant notre problème, c’est
que les longueurs li des codes soient les plus petites possible. Pour celà considérons de nouveau
un ensemble X = (x1 , . . . , xk ) de k messages avec une distribution p = (p1 , . . . , pk ). Si h est
un codage des k messages avec li = h(xi ), nous voulons minimiser la longueur moyenne, c’est-
à-dire l’espérance de la longueur des codes. Cette longueur moyenne est, exprimée comme
une espérance,
Xk X
L(h) := pi l(h(xi )) = pi li = E(l(h(X))).
i=1 i

Théorème 3.2 Appelons Linf := inf h L(h), la longueur moyenne minimale que l’on peut
obtenir avec un codage préfixe. Alors

H(p) ≤ Linf ≤ H(p) + 1.

Lemme 3.1 Soit p = (p1 , . . . , pk ) une distribution de probabilité. La solution unique du

problème où les inconnues sont les qi ,
( P
− ki=1 pi log qi =min!
Pk (3.2)
i=1 qi ≤ 1, qi ≥ 0.

est qi = pi .

P
Démonstration Si p = (pi ) est une distribution de probabilité et qi ≥ 0 satisfait i qi ≤ 1,
en utilisant la concavité du logarithme,
k
X k
X
qi
pi log ≤ log qi ≤ log 1 ≤ 0,
pi
i=1 i=1

ce qui nous donne

k
X k
X
− pi log pi ≤ − pi log qi . (3.3)
i=1 i=1

Donc
P q := p réalise le minimum dans le problème (3.1). L’inégalité est stricte à moins que
q
i i = 1 et pi = qi par tout i. ◦
3.1. THÉORIE DES CODAGES PRÉFIXES 21

Figure 3.2: Dans un arbre binaire de profondeur 5 on construit un codage préfixe pour la
suite de longueurs l1 = 2, l2 = l3 = 3, l4 = 5. C’est facile de voir que cette série vérifie
l’inégalité de Kraft. Dans la figure on voit de haut en bas les codes obtenus, correspondant
à des sous-arbres disjoints et de taille décroissante. Chacun a un nombre de feuilles 25−lj et
la racine du sous-arbre devient le code de xj .
22 CHAPTER 3. CODES PRÉFIXES

Preuve du théorème 3.2. Le problème que nous voulons résoudre est de minimiser la
longueur moyenne d’un code sous la condition donnée par l’inégalité de Kraft, c’est-à-dire
chercher (li )i=1,...,k telles que
( P
− ki=1 pi li =min!
Pk −li ≤ 1. (3.4)
i=1 2

Résolvons d’abord le problème sans nous préoccuper du fait que les li doivent être entiers.
On cherche donc une solution telle que l’on ait seulement li ≥ 0. Alors en posant yi := 2−li
le problème (3.4) est équivalent au problème (3.2). Donc sa solution est li∗ = − log pi et
P
nous obtenons que le minimum ki=1 pi lk∗ = H(p) est l’entropie. Toutefois les li∗ ne sont
généralement pas entiers et le mieux que puissions faire est de fixer li := dli∗ e, l’entier le plus
petit supérieur à li∗ . Comme li ≥ li∗ la condition de Kraft est vérifiée
k
X k
X ∗
2−li ≤ 2−li ≤ 1.
i=1 i=1

Donc il existe un codage préfixe dont les codes ont pour longueur li et en plus
k
X k
X k
X
H(p) = pi li∗ ≤ pi li = El(h(X)) ≤ pi (li∗ + 1) = H(p) + 1.
i=1 i=1 i=1
◦

3.1.1 Un premier exemple: le code de Shannon

Soit X une source avec des symboles X = {x1 , . . . , xn } et une distribution de probabilité
p = (p1 , . . . , pn ). Selon le théorème 3.2 nous pouvons construire des codes préfixes presque
optimaux pour une source p = (p1 , . . . , pi , . . . , pk ) en prenant li := dlog pi e comme longueur
du code de xi .
Algorithme de codage de Shannon
1. Ordonner les pi de façon décroissante: p1 ≥ p2 ≥ · · · ≥ pn ;
P
2. soit Pi := i−1
k=1 pi (en particulier P1 = 0);

3. h(xi ) est composé des li = d− log pi e premiers chiffres du développement binaire de Pi .

En d’autres termes, on écrit Pi = 0, a1 a2 . . . ali . . . et on garde a1 . . . ali .
Nous allons vérifier directement que le code est préfixe et quasi optimal.
En effet, comme nous avons − log pi ≤ li ≤ − log pi + 1, on obtient
X X X
H(p) = − pi log pi ≤ pi li ≤ − pi (log pi + 1) = H(p) + 1.
i i i

Cela implique que la longueur moyenne (c’est-à-dire l’espérance de la longueur) des codes,
El, vérifie
H ≤ El ≤ H + 1.
3.1. THÉORIE DES CODAGES PRÉFIXES 23

Cette relation signifie que le codage est quasi optimal. En effet, il vérifie la même inégalité
qu’un codage optimal et on perd tout au plus un bit par symbole. Reste à démontrer que
le codage ainsi défini a la propriété du préfixe. Observons que si j ≥ 1, alors Pi+j − Pi ≥
pi ≥ 2−li . Si les li premiers bits de Pi coı̈ncidaient avec ceux de Pi+j , celà impliquerait
Pi+j − Pi < 2−li . Donc ils ne coı̈ncident pas et le codage est préfixe.

Exercices et implémentations Matlab

Exercice 28 Comparer le code de Shannon avec le code de l’algorithme 27.

Exercice 29 Expériences à faire. Implémenter en Matlab un algorithme qui:

1. étant donné un texte extrait les fréquences (probabilités empiriques) de tous les car-
actères (y compris les espaces et les chiffres). Ainsi on déduit une distribution empirique
de ces caractères p = (p1 , . . . , pk );

2. calcule l’entropie binaire de p, qui indique combien de bits il faut payer par caractère;

3. déduit quelle est la longueur théorique prévue pour le texte en bits (produit de l’entropie
par le nombre de caractères);

4. calcule les codes de Shannon associés avec p;

5. génère le code binaire du texte, calcule sa longueur et la compare avec la longueur

théorique prévue.

Exercice 30 D’un codage x ∈ X → h(x) ∈ {0, 1}(IN ) on dit qu’il est uniquement déchiffrable
si on a l’implication:

h(xi1 ) . . . h(xin ) = h(xj1 ) . . . h(xjk ) ⇒ n = k et xi1 = xj1 , . . . , xin = yjk .

Démontrer que si h est un codage avec la propriété de préfixe, alors le codage qui consiste à
inverser l’ordre de chaque h(xi ) est uniquement déchiffrable. En conclusion, il y a des codes
uniquement déchiffrables qui n’ont pas la propriété du préfixe.

Exercice 31 Trouver un codage optimal pour la distribution

p := (0.01; 0.04; 0.05; 0.07; 0.09; 0.1; 0.14; 0.2; 0.3).

Exercice 32 Soient p = (p1 , . . . , pn ) et q = (q1 , . . . , ql ) deux distributions discrètes et p ⊗ q

leur produit tensoriel défini par

p ⊗ q = (p1 q1 , . . . , p1 ql , p2 q1 , . . . , p2 ql , . . . , pm q1 , . . . , pm ql ).

Quelle interprétation peut-on donner de cette distribution dans le langage des variables
aléatoires? Vérifier que
H(p ⊗ q) = H(p) + H(q).
Déduire que H(p(n) ) = nH(p) où p(n) est le produit tensoriel de p par lui-même, n fois.
24 CHAPTER 3. CODES PRÉFIXES

Exercice 33 Formulaire de Shannon (source : Shannon)

Commençons par rappeler un résultat que nous avons déjà utilisé:

Lemme 3.2 Soient p et q deux distributions de probabilité discrètes. Alors

X p(x)
p(x) log ≥ 0.
q(x)
L’égalité se produit si et seulement si p(x) = q(x) pour tout x.

Démonstration du Lemma 3.2. On utilise la concavité stricte du logarithme,

X p(x) X q(x) X q(x)
− p(x) log = p(x) log ≤ log( p(x) ) = log 1 = 0,
q(x) p(x) p(x)
p(x)
et cette inégalité est une égalité si et seulement si toutes les valeurs q(x) sont égales. Dans ce
dernier cas leur valeur commune est évidemment 1. ◦

Soient X et Y deux variables aléatoires discrètes

P de distribution conjointe p(x,P y) = P(X =
x, Y = y). Donc on a P(X = x) = p(x) = y∈X p(x, y) et P(Y = y) = p(y) = x∈X p(x, y)
L’entropie (ou incertitude) d’une variable discrète X à valeurs dans l’alphabet fini X , et
l’entropie d’une paire de variables aléatoires (X, Y ) à valeurs dans X × Y ont été définies par
X X
H(X) = − p(x) log p(x), H(X, Y ) = − p(x, y) log p(x, y).
x x,y

1
1) Vérifier que l’entropie de X est l’espérance de g(X), où g(X) = log p(X) = − log p(x).

2) Démontrer que H(X) ≤ log Card(X ), et que cette inégalité devient une égalité si et seule-
ment si X a une distribution uniforme sur X . (Utiliser le lemme 3.2 où p est la distribution
de X et q la distribution uniforme sur X ).
3) Exemple important : On choisit pour X la variable de Bernouilli, X = 1 avec probabilité
p, X = 0 avec probabilité 1 − p. Alors

H(X) = −p log p − (1 − p) log(1 − p),

fonction de p que nous appellerons H(p). Vérifier que H(X) = 1 bit quand p = 12 . Dessiner
le graphe de H(p) et démontrer que H vaut 0 en 0 et 1, et est maximal quand p = 21 .
Interprétation : l’incertitude sur X est maximale quand p = 12 et minimale quand X est
déterministe. L’entropie est une mesure de l’incertitude sur la valeur de X.
4) L’entropie conjointe de deux variables aléatoires est mas petite que la somme des entropies.
L’égalité se produit si et seulement si les deux variables aléatoires sont indépendantes.

H(X, Y ) ≤ H(X) + H(Y ). (3.5)

Il suffit d’appliquer le lemme 3.2 aux distributions p(x, y) et p(x)p(y).

5) Entropie conditionnelle de Y sachant X : c’est “la moyenne de l’entropie de Y pour
chaque valeur de X, pondérée par la probabilité d’observer cette valeur particulière de X”.
3.1. THÉORIE DES CODAGES PRÉFIXES 25

Traduire cette définition due à Shannon en une formule, et vérifier que la formule qui suit est
une formule équivalente: X
H(Y |X) = − p(x, y) log p(y|x).
x,y

“This quantity measures how uncertain we are of Y on the average when we know X.”
Utilisons la définition de la probabilité conditionnelle :

p(x, y)
p(y|x) = P ,
y p(x, y)

X X X
H(Y |X) = − p(x, y) log p(x, y) + p(x, y) log p(x, y) = H(X, Y ) − H(X).
x,y x,y y

Donc
H(X, Y ) = H(X) + H(Y |X).
”The uncertainty (or entropy) of the joint event X, Y is the uncertainty of X plus the uncer-
tainty of Y when X is known”. Mais nous savons que

H(X) + H(Y ) ≥ H(X, Y ) = H(X) + H(Y |X).

Alors
H(Y ) ≥ H(Y |X).
“The uncertainty of Y is never increased by knowledge of X. It will be decreased unless X
and Y are independent events, in which case it is not changed”.

Exercice 34 Entropie relative et information mutuelle

1) Considérons deux distributions de probabilité p(x) et q(x). Nous appellerons distance de
Kullback Leibler, ou entropie relative des deux distributions p(x) et q(x) la quantité
X p(x) p(X)
D(p||q) := p(x) log = Ep log .
q(x) q(X)
x∈X

Vérifier que D(p||q) ≥ 0 et que D(p||q) = 0 ⇔ p = q. L’entropie relative est une mesure
de la distance entre deux distributions. On appelle information mutuelle I(X, Y ) l’entropie
relative entre la distribution conjointe p(x, y) et la distribution produit p(x)p(y),
XX p(x, y) p(X, Y )
I(X, Y ) = p(x, y) log = D(p(x, y)||p(x)p(y)) = Ep(x,y) log .
p(x)p(y) p(X)p(Y )
x∈X y∈X

2) Démontrer que

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

I(X, Y ) = I(Y, X) = H(X) + H(Y ) − H(X, Y ), I(X, X) = H(X).

On observera que I(X, Y ) = 0 si X et Y sont indépendantes et que I(X, Y ) = 0.
26 CHAPTER 3. CODES PRÉFIXES

3) Soient X1 ,, X2 , ..., Xn variables aléatoires discrètes de distribution conjointe p(x1 , x2 , . . . xn ).

Démontrer que
n
X
H(X1 , X2 , . . . Xn ) = H(Xi |Xi−1 , . . . , X1 ). (3.6)
i=1

4) Démontrer, en utilisant les définitions de D et de la probabilité conditionnelle que

X
D(p(x, y)||q(x, y)) = D(p(x)||q(x)) + p(x)D(p(y|x)||q(y|x)).
x

5) déduire finalement que

n
X
H(X1 , X2 , . . . Xn ) ≤ H(Xi ),
i=1

et que l’égalité se produit si et seulement si Xi sont indépendantes. (Utiliser la question

précédente et (3.6)).
Chapter 4

Le codage de Huffman

En 1952 Huffman découvrit un codage particulièrement simple. Nous allons le décrire et

démontrer su optimalité. L’algorithme s’explique de nouveau très bien avec une figure et un
exemple. Soient

p = (p1 , . . . , pk ) = (0.01; 0.02; 0.04; 0.13; 0.13; 0.14; 0.15; 0.15; 0.23),

ordonnées en croissant. A partir de cette suite on construit un arbre binaire dont les feuilles
seront les probabilités. A chaque pas de la construction de l’arbre on groupe les deux prob-
abilités qui ont la somme la plus petite et on les remplace par leur somme. On passe donc
à la suite obtenue en réunissant (p1 + p2 , . . . , pk ). Le noeud parent immédiat de p1 et p2 est
alors p1 + p2 . Itérant le procédé n − 1 fois, on construit un arbre comme celui de la figure
4.1. Avec la convention graphique que la probabilité la plus grande est toujours à droite et
la probabilité la plus petite à gauche, l’arbre se réarrange comme indiqué dans la figure 4.2.
Alors nous pouvons associer par la convention habituelle un code binaire à chaque noeud dans
l’arbre, ce qui fixe en particulier un code pour chaque feuille de l’arbre, c’est-à-dire chaque
pi . Comme nous allons voir, ce procédé nous donne un codage optimal au sens adopté au
chapitre précédent.

Exercice 35 Calculer la longueur moyenne du code qui a été construit!

Exercice 36 Etant donnée une distribution de probabilités discrète p = (p1 , . . . , pk ), démontrer

qu’il existe bien au moins un codage optimal, à savoir un codage dont l’espérance de longueur
est minimale parmi les espérances de longueur de tous les codages possibles.

Le lemme qui suit explique pourquoi un code de Huffman est optimal.

Lemme 4.1 Soit n ≥ 3 et considérons une distribution décroissante de probabilités p =

(p1 , p2 , . . . , pk ), avec p1 ≥ p2 ≥ · · · ≥ pk > 0. Alors il existe un code optimal h pour p tel que

h(k) = w0, h(k − 1) = w1,

pour au moins une suite w faite de zéros et de uns, et tel que le code h0 défini par

h0 (i) = h(i), 1 ≤ i ≤ k − 1, h0 (k − 1) = w

soit optimal pour la distribution p0 = (p1 , p2 , . . . , pk−2 , pk−1 + pk ).

27
28 CHAPTER 4. LE CODAGE DE HUFFMAN

Figure 4.1: Soit p = (p1 , . . . , pn ) = (0.01; 0.02; 0.04; 0.13; 0.13; 0.14; 0.15; 0.15; 0.23) une dis-
tribution ordonnée. A partir de cette suite on construit un arbre binaire. A chaque pas de la
construction de l’arbre on groupe les deux probabilités qui ont la somme la plus petite et leur
somme est placée au noeud qui est créé comme parent immédiat de ces deux probabilités.
En itérant le procédé n − 1 fois, on construit un arbre binaire dont la racine est 1, la somme
de toutes les probabilités, et dont les feuilles sont les probabilités de départ.

Figure 4.2: Avec la convention graphique que la probabilité la plus grande est toujours à
droite et la probabilité la plus petite à gauche, l’arbre de la figure 4.1 se réarrange. Alors
nous pouvons associer par la convention habituelle un code binaire à chaque noeud dans
l’arbre, ce qui fixe en particulier un code pour chaque feuille de l’arbre, c’est-à-dire chaque
pi .
 29

Il s’agit dans tous les cas de codage préfixe. Voyons d’abord pourquoi le lemme justifie la
construction du code de Huffman. Le lemme nous garantit que pour construire un codage
optimal d’une distribution de k éléments, il suffit de trouver un code optimal pour la dis-
tribution de n − 1 éléments obtenue en groupant les deux probabilités les plus petites. Et
que le code de ces probabilités pk−1 et pk s’obtient en ajoutant un zéro et un 1 au code de
pk + pk−1 . Au dernier pas, quand n est réduit à 2, le codage optimal est forcé, 0 et 1. Donc
on déduit que tous les codes successifs sont optimaux.

Preuve du lemme 4.1. Soit h un code optimal pour p. Nous pouvons imposer, comme
une propriété générale des codes préfixes, que les longueurs vérifient l1 ≤ l2 ≤ · · · ≤ lk . En
effet si par exemple l1 > l2 , il y a deux cas : si p1 = p2 nous pouvons échanger p1 et p2 . Par
contre p1 > p2 est impossible, puisque celà impliquerait que nous pouvons obtenir un code
de longueur moyenne strictement inférieure en interchangeant les codes de p1 et p2 . En effet
cet échange donnerait p2 l1 + p1 l2 < p1 l1 + p2 l2 .
Observons aussi comme une propriété générale d’un codage préfixe optimal que lk−1 = lk .
Sinon, nous pourrions maintenir la propriété du préfixe et faire diminuer sa longueur moyenne
en supprimant les lk − lk−1 derniers bits de h(k).
Le code h(k − 1) peut s’écrire w0 ou bien w1. Supposons par exemple que ce soit w0.
Alors nous pouvons choisir h(k) = w1. En effet, si ce code est déjà utilisé par un pi , on peut
échanger le code h(i) de pi et celui de pk−1 . Si le code w1 n’est pas utilisé, il est clair que
nous pouvons l’utiliser pour h(k) tout en maintenant la propriété du préfixe. En effet si un
autre h(j) était préfixe de w1, comme il serait de longueur strictement inférieure puisqu’il
est différent de w1, h(j) serait préfixe de w0 = h(k − 1). Après ces échanges éventuels, la
longueur moyenne n’a pas changé et reste optimale.
Considérons maintenant le code h̃ induit par h sur p0 := (p1 , . . . , pk−2 , pk−1 + pk ):

h̃(i) = h(i), (1 ≤ i ≤ k − 2) et h̃(k − 1) = w.

Pour conclure la preuve du lemme, il reste à démontrer que h̃ est de longueur moyenne
optimale. La longueur moyenne de ce codage, L̃, est reliée à celle de h, L, par la relation

L = L̃ + pk−1 + pk .

Soit L0 la longueur moyenne d’un code optimal h0 sur p0 . Partant de h0 on peut définir un
code ĥ sur p par

ĥ(i) = h0 (i), (1 ≤ i ≤ k − 2), ĥ(k − 1) = h0 (k − 1)0, ĥ(k) = h0 (k − 1)1.

Donc la longueur moyenne de ĥ est

L̂ = L0 + pk−1 + pk .

Mais nous savons que L0 est la longueur optimale de p0 et que L est la longueur optimale de
p. Donc L̂ ≥ L0 , L̃ ≥ L0 et nous obtenons:

L̃ + pk−1 + pk = L ≤ L̂ = L0 + pk−1 + pk ≤ L̃ + pk−1 + pk ,

ce qui nous donne L0 = L̃. Donc h̃ est optimal. ◦

30 CHAPTER 4. LE CODAGE DE HUFFMAN

4.1 Exercices et implémentations Matlab

Exercice 37 Expériences. Implémenter en Matlab un algorithme qui:

1. étant donné un texte de N caractères extrait les fréquences (probabilités empiriques) de

tous les caractères, y compris les espaces et chiffres. Ainsi, on déduit une distribution
empirique de ces caractères p = (p1 , . . . , pk );

2. de la même manière, un entier n étant fixé (en pratique n = 2, 3, 4 ou 5), calcule les
fréquences de chaque suite de n symboles (bien sûr on ne stocke les fréquences que
pour les suites qui apparaissent au moins une fois.) Cette distribution de probabilité
s’appelle pn ;

3. calcule l’entropie binaire de H n := H(pn ), qui indique combien de bits il faut dépenser
par caractère;

4. déduit quelle est la longueur théorique prévue pour le texte en bits (produit de l’entropie
H(pn ) par le nombre de caractères divisé par n);

5. calcule les codes de Shannon associés à pn ;

6. génère le code binaire du texte, calcule sa longueur Ln et la compare avec la longueur

théorique prévue;
N n N
7. vérifie que nH ≤ Ln ≤ n (H
n + 1);
n
8. vérifie que n → Hn est une fonction décroissante et donne le facteur optimal de com-
pression obtenu.

Exercice 38 La définition de l’entropie, axiomatique de Shannon, opus cit. p. 49

Considérons un ensemble fini d’évènements dont les probabilités sont p1 , . . . , pn . L’entropie
H(p1 , . . . , pn ) va se définir comme une mesure de l’incertitude sur celui des évènements i =
1, . . . , n qui se produira. Pour comprendre les axiomes qui nous conduisent à la définition de
l’entropie, il faut prendre en compte qu’une partition d’évènements disjoints peut être l’objet
de regroupements partiels. Par exemple nous pouvons grouper les k premiers évènements
en un évènement
Pk unique de probabilité p01 . On obtient ainsi une distribution de probabilité,
0
(p1 = i=1 pi , pk+1 , . . . , pn ) telle qu’à son tour le premier évènement se décompose en
pi
(π1 , . . . , πk ) avec πi = p1 +···+p k
. Dans la distribution initiale nous avions un tirage entre n
évènements. Dans le second cas nous avons d’abord un tirage entre n − k + 1 évènements
disjoints, suivi d’un second tirage entre k évènements quand le premier tirage a donné 1. En
résumé, nous avons des présentations du même tirage final sous deux formes:
(p1 , . . . pn ), ou bien
((p01 , π1 ), . . . (p01 , πk ), pk+1 , . . . pn )
Nous formalisons alors l’entropie ou incertitude par les axiomes intuitifs suivants

1. H est continue
1
2. Supposons que les pi soient égaux, pi = n. Alors H doit être une fonction croissante
de n
4.1. EXERCICES ET IMPLÉMENTATIONS MATLAB 31

3. Si on recompose les n évènements par regroupement suivi de tirage conditionnel, comme

expliqué plus haut, l’incertitude finale doit être la même. Cela nous conduit à exiger

H(p1 , . . . , pn ) = H(p01 , pk+1 , . . . pn ) + p01 H(π1 , . . . πk ).

Notre but est de démontrer qu’avec ces axiomes 1, 2 et 3 il existe une constante positive K
telle que
n
X
H(p1 , . . . , pn ) = −K pi log pi .
i=1

1) Ecrivons H( n1 , . . . n1 ) = A(n). Utilisant l’axiome 3, démontrer que A(sm ) = mA(s). Si t

est un autre entier, on peut trouver, pour n arbitrairement grand, un m tel que sn ≤ tn <
A(t)
sm+1 . Utilisant la monotonie (axiome 2) déduire que m m 1
n ≤ A(s) ≤ n + n et finalement que
A(t) = K log t.
2) Supposons que pi = Pnni soient des probabilités rationnelles. Démontrer grâce à l’axiome
1 ni
3 que X X
K log ni = H(p1 , . . . , pn ) + K pi log ni .

3) Traiter le cas général en approchant les pi par des rationnels et en utilisant l’axiome 2 de
continuité.

Exercice 39 Messages typiques Considérons une suite Xn de v.a.i.i.d. avec valeurs dans
un ensemble fini de symboles X = {x1 , x2 , ..., xk } et telles que P (Xn = xi ) = pi , i = 1, ..., k.
Soit X n l’ensemble des suites de longueur n, que nous appelons messages. Il y a k n tels
messages. Considérons aussi l’entropie de la répartition (pi )1≤i≤k ,
i=k
H2 (p1 , ..., pk ) = −Σi=1 pi log2 pi .

Cette quantité va être reliée à la probabilité d’un message long. La remarque cruciale est que
les messages longs (n grand) ont tous plus ou moins la même probabilité d’être émis. Pour
s’en rendre compte, il suffit d’appliquer la loi faible des grands nombres à la variable aléatoire
définie comme le logarithme moyen de la probabilité d’une suite longue,
n
1 1X X
log P (X1 , . . . , Xn ) := log P (X) → E(log P (Xi )) = pi log pi = H2 (p1 , . . . , pk ).
n n
i=1 i

On déduit la formule fondamentale

P (X1 , . . . , Xn ) = 2n(HD (p1 ,..., pk )+²(n)) ,

avec ²(n) → 0 quand n → +∞.

Cette observation nous conduit à définir ce que nous appellerons l’ensemble des “messages
typiques”,

Cn = {(x1 , ..., xn ) ∈ X n , 2−n(H2 +ε) ≤ p(x1 )...p(xn ) ≤ 2−n(H2 −ε) }.

1) Démontrer que E(− log2 pXn ) = H2 .

32 CHAPTER 4. LE CODAGE DE HUFFMAN

2) déduire que

1 Var(− log2 pX1 )

P ((X1 , ..., Xn ) ∈ Cnc ) ≤ P ({| Σnl=1 (− log2 pXl ) − H2 | ≥ ε}) ≤ .
n nε2

3) Démontrer que
P ((X1 , ..., Xn ) ∈ Cn )) ≥ 2−n(H2 +ε) Card(Cn ).
déduire que Card(Cn ) ≤ 2(H2 +ε)n .
4) Réciproque. Supposons que nous ayons trouvé C̃n ⊂ X n tel que limn→+∞ P ((X1 , ..., Xn ) ∈
C̃n ) = 1 et Card(C̃n ) ≤ 2Kn . On va montrer que K ≥ H2 .
4a) Vérifier que limn→∞ P ((X1 , ..., Xn ) ∈ Cn ∩ C̃n ) = 1.
4b) Démontrer que P ((X1 , ..., Xn ) ∈ Cn ∩ C̃n ) ≤ 2−n(H2 −ε) 2Kn et conclure.
5) Soient X = {0, 1}, p1 = p, p2 = (1 − p). Si p1 = p2 = 21 , vérifier que H2 = 1 et que le
nombre des suites typiques est 2n . (En d’autres termes la compression est impossible).
Cas général : étudier la forme de H2 (p) = −p log p − (1 − p) log(1 − p) et en déduire le
comportement du nombre de suites typiques.
6) Application au codage. Nous allons interpréter H2 comme la longueur moyenne de mes-
sages codés dans l’alphabet {0, 1} de manière optimale. Commençons par la description d’un
codage qui réalise une telle longueur moyenne. Pour celà, fixons ε > 0 et choisissons n suff-
isamment grand, de sorte que P (Cnc ) ≤ ε. (Expliquer pourquoi c’est possible). Donc, on
attribue un code binaire à chacun des éléments de Cn . Celà implique que le nombre de codes
binaires est inférieur ou égal à 2n(H2 +ε) . Considérons alors les codes non typiques, qui sont
beaucoup plus nombreux! Leur nombre est de l’ordre de k n = 2n log k . Donc nous pouvons les
énumérer avec tout au plus k n codes binaires distincts des précédents c’est-à-dire les nombres
inférieurs à 2n log k + 2n(H2 +ε) ≤ 2n log k+1 . De cette manière un code est attribué à tous les
éléments de X n . Démontrer que la longueur moyenne d’un code binaire avec ce codage est
inférieure ou égale à n(H2 + ε(1 + log k)). H(p) peut en conséquence s’interpréter comme la
longueur moyenne du code utilisée pour chaque symbole quand n est grand.
7) Finalement on se demande si on pourrait trouver un codage encore plus efficace. Si c’était
possible, on aurait un sous-ensemble de messages C̃n de cardinal plus petit que 2nK avec
K < H2 et tel que P(C̃n ) → 1 quand n → ∞. Démontrer que ce n’est pas possible. Conclure
que nous venons de démontrer que:
La longueur minimale par symbole d’un codage transmettant des messages de longueur n dans
l’alphabet X avec la distribution p1 , . . . , pk est H2 (p1 , . . . , pk ).
Chapter 5

Langage et communication selon

Shannon

5.1 Introduction
Notre but est, suivant Shannon, d’expliquer comment nous pouvons réduire le problème
de mesurer la quantité d’information transmise dans un dispositif de communication à une
analyse aussi élémentaire que celle d’une distribution discrète de probabilité. Shannon réduit
la communication à la transmission d’une série de symboles émis par une source aléatoire.
La source émet les symboles. Chacun d’entre eux représente, par exemple, une phrase en
français. L’incertitude du récepteur est grande, mais pas non plus totale, puisqu’il y a
des phrases plus probables que d’autres. Par exemple dans une conversation la probabilité
qu’une réponse soit “oui” ou “non” est loin d’être négligeable. L’hypothèse fondamentale
est que le récepteur tout comme l’émetteur connaissent la probabilité de chaque phrase.
Cette hypothèse pourrait paraı̂tre fantastique si Shannon ne nous donnait pas les moyens de
calculer effectivement une bonne estimation de chaque unité significative du langage, partant
des lettres pour arriver aux phrases et même aux textes. Le modèle sous-jacent est un modèle
Markovien. On suppose par exemple que, étant donnée une suite de symboles m1 m2 . . . mn ,
la probabilité qu’apparaisse ensuite un symbole mn+1 dépend seulement de mn et pas des
précédents. Evidemment, cette hypothèse markovienne est fausse, mais devient de plus en
plus vraie quand la taille des symboles croı̂t.
Grâce à l’hypothèse markovienne, la probabilité d’une suite de symboles peut se calculer
par la formule

P(m1 m2 . . . mn ) = P(m1 )P(m2 |m1 )P(m3 | m2 ) . . . P(mn | mn−1 ),

où P(m2 | m1 ) = P(m 1 m2 )

P(m1 ) est la probabilité que m2 suive m1 dans un texte et P(m1 ) est
la probabilité que m1 apparaisse dans un texte. Toutes ces probabilités peuvent s’estimer
empiriquement en utilisant un texte ou un ensemble de textes, dans lesquels on calcule la
fréquence de chaque mot et ensuite la fréquence de chaque paire de mots successifs. Calculer
ces fréquences et les garder sous forme de dictionnaire est informatiquement possible et même
facile.
Shannon, avec son génie, et dans un temps où l’informatique balbutiait, démontre avec
un procédé très simple que la “chaı̂ne de Markov du langage” peut être simulée avec la plus
grande facilité si on dispose d’un livre. L’intérêt de cette simulation est de démontrer que

33
34 CHAPTER 5. LANGAGE ET COMMUNICATION SELON SHANNON

si on respecte les probabilités et les probabilités de transition apprises d’un texte en anglais,
alors les phrases synthétisées ressemblent à l’anglais!
Le procédé de Shannon consiste à :

– choisir au hasard un mot dans un livre (ouvrir au hasard, placer le doigt au hasard)

– ouvrir de nouveau le livre au hasard et chercher le même mot ; quand on l’a trouvé,
choisir le mot qui le suit

– itérer

Voici les exemples historiques simulés par Shannon avec ce procédé:

1. Approximation d’ordre zéro (symboles tirés indépendants, équiprobables):

XFOML RXKHRRJFFJUJ ZLPWCFWKCYJ FFJEYVKCQSGHYD QPAAMKBZAACI-
UBZLHJQD.

2. Approximation d’ordre 1 (symboles indépendants, mais avec les fréquences d’un texte
anglais).
OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI ALHENHTTPA OOBTTVA
NAH BRL.

3. Approximation d’ordre 2 (fréquences de paires de lettres correctes pour l’anglais).

ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIN D ILONASIVE
TUCOOWE AT TEATSONARE FUSO TIZIN ANDY TOBE SEACE CTISBE.

4. Approximation d’ordre 3 (fréquences des triplets de lettres correctes).

IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID PONDENOME OF
DEMONSTURES OF THE REPTAGIN IS REGOACTIONA OF CRE.

5. Approximation d’ordre 1 avec des mots : la fréquence des mots est correcte
REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFER-
ENT NATURAL HERE HE THE A CAME THE TO OF TO EXPERT GRAY COME
TO FURNISHES THE LINE MESSAGE HAD BE THESE;

6. Approximation d’ordre 2 avec des mots : les probabilités de transition entre mots sont
comme en anglais.
THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE
CHARACTER OF THIS POINT IS THEREFORE ANOTHER METHOD FOR THE
LETTERS THAT THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN
UNEXPECTED;

Shannon observe : “The resemblance to ordinary English text increases quite noticeably
at each of the above steps. Note that these samples have reasonably good structure out
to about twice the range that is taken into account in their construction. Thus in 3. the
statistical process insures reasonable text for two-letter sequences, but four-letter sequences
from the sample can usually be fitted into good sentences. In 6. sequences of four or more
words can easily be placed in sentences without unusual or strained constructions.”
5.2. EXERCICES D’IMPLÉMENTATION EN MATLAB 35

5.2 Exercices d’implémentation en Matlab

Exercice 40 Implémenter en Matlab un algorithme de synthèse markovienne de texte
probabilistiquement correct. Ce programme, pour chaque k:

P(y k xi )
– calcule la probabilité empirique P(xi | y k ) := P(y k )
qu’apparaisse un caractère xi
sachant qu’il est précédé par un k-gramme yk .(P(xi ) est la fréquence de xi et P(y k )
est la fréquence de y k calculées dans l’exercice précédent);

– tire au sort le k-gramme initial xi1 . . . xik du texte synthétisé suivant la distribution de
probabilité pk ;

– tire au sort le caractère suivant selon la distribution conditionnelle x → P(x | xi1 . . . xik );

– itère: étant donné un texte déjà synthétisé de n caractères, synthétise le n + 1-ème

caractère suivant la distribution conditionnelle x → P(x | xin−k+1 . . . xin );

– édite le texte synthétisé.

Exercice 41 Le but est d’apprendre un code avec un texte très long, et de coder un autre
texte avec le premier.
1) Algorithme qui calcule le code de Shannon associé à une distribution de probabilité
2) Algorithme qui calcule le code de Huffman associé à une distribution de probabilité
3) Appliquer ces algorithmes à des textes pour vérifier que la longueur du binaire obtenu
correspond bien à la longueur théorique optimale nH(p), où n est le nombre de symboles
(nombre de caractères, ou de digrammes, ou trigrammes, ou mots, ou paires de mots).
4) Pour placer le codage dans un cadre aplicatif réaliste, nous avons réalisé qu’il fallait
définir le code avec un premier texte d’apprentissage qui nous donnerait une distribution de
probabilité de référence. Ce texte doit être grand ou très grand, pour garantir que la grande
majorité des symboles codés apparaisse plusieurs fois et permette d’estimer sa probabilité.
5) Une fois établi un code de référence (par exemple un dictionnaire de mots, et un
dictionnaire de paires de mots pour le français, obtenu d’un livre), l’utiliser pour coder un
AUTRE texte, et voir quel degré de compression on obtient.

Détails techniques d’expérimentation pour les textes

– Il faut établir pour chaque code un dictionnaire symbole → code et le dictionnaire

inverse code → symbole

– les symboles peuvent être des monogrammes (lettres), digrammes, trigrammes, mots, ou
paires de mots. Il ne convient pas d’aller plus loin parce que les probabilités deviennent
trop petites et ne sont plus observables.)

– Quand on code un texte nouveau, est possible qu’apparaissent des symboles qui ne sont
pas dans le dictionnaire. Dans un tel cas, le symbole reste tel quel dans le code. Ainsi le
code est une suite de zéros, uns, et symboles non codés. La longueur de ce qui n’est pas
codé se compte comme (nombre de lettres)×8, vu que chaque lettre se code “bêtement”
avec huit bits.
36 CHAPTER 5. LANGAGE ET COMMUNICATION SELON SHANNON

– Quand on code par mots ou par paires de mots: les séparateurs (ponctuation, par-
enthèses, etc.) seront comptés comme mots. On néglige les majuscules puisqu’après un
point il est facile de reconnaı̂tre qu’il y a une majuscule. Chaque mot commence par
un espace.
Chapter 6

Messages répétés et entropie

Nous allons interpréter l’entropie H(p) comme la moyenne du logarithme du nombre de

messages “typiques” quand une source envoie une suite de n symboles successifs indépendants
qui suivent tous la distribution p. Ensuite, on va en déduire que l’entropie est la longueur
moyenne minimale, mesurée en bits/symbole, requise pour coder une source d’entropie H(p).
Toutes les suites x1 x2 . . . xn sont possibles, mais elles ne sont pas équiprobables. Cependant
par la loi des grands nombres, la fréquence d’apparition de chaque symbole x dans x1 . . . xn
tend vers p(x) quand n tend vers l’infini. C’est pourquoi il y a beaucoup moins de messages
typiques que de messages possibles. Nous allons voir que le nombre de messages typiques a
pour ordre de grandeur 2nH(p) tandis que le nombre de messages possibles est (CardX)n =
2n log Card(X) .

6.1 Messages typiques

Considérons une suite Xn de v.a.i.i.d. avec valeurs dans un ensemble fini de symboles X
et telles que P(Xn = x) = p(x). Soit X n l’ensemble des suites de longueur n, que nous
appelerons messages de longueur n, ou simplement messages. Il y a k n messages possibles.
Considérons aussi l’entropie de la distribution p = (p(x))x∈X ,
H(p) = −Σx∈X p(x) log p(x).
Cette quantité va être interprétée en relation avec la probabilité d’un message long. La
remarque cruciale est que les messages longs (n grand) ont tous plus ou moins la même
probabilité d’être émis. Pour s’en rendre compte, il suffit d’appliquer la loi forte des grands
nombres à la variable aléatoire définie comme le logarithme moyen de la probabilité d’une
suite longue,
n
1 1X X
log p(X1 , . . . , Xn ) := log p(Xi ) → E(log p(X)) = p(x) log p(x) = H(p).
n n
i=1 x∈X

On en déduit la formule fondamentale

p(X1 , . . . , Xn ) = 2n(H(p)+²(n)) ,
avec ²(n) → 0 quand n → +∞. (Ici les convergences sont des convergences presque sûres).
Cette observation, que nous n’allons pas utiliser (nous utiliserons seulement la loi faible
des grands nombres), nous conduit néanmoins à la définition suivante.

37
38 CHAPTER 6. MESSAGES RÉPÉTÉS ET ENTROPIE

Définition 6.1 Pour chaque ε > 0 nous appellerons ensemble des “messages typiques”,

Cn = {(x1 , ..., xn ) ∈ X n , 2−n(H(p)+ε) ≤ p(x1 . . . xn ) = p(x1 )...p(xn ) ≤ 2−n(H(p)−ε) }.

Lemme 6.1 L’ensemble Cn des messages typiques associé avec p, n et ε vérifie

1. P(Cn ) ≥ 1 − ε pour n suffisamment grand ;

2. Card(Cn ) ≤ 2(H(p)+ε)n
Pn
Démonstration Considérons la variable aléatoire Sn = i=1 log p(Xi ) et passons au log-
arithme dans les inégalités définissant Cn . On voit que
n
X
Cn = {(x1 , ..., xn ) | −n(H(p) + ε) ≤ log p(xi ) ≤ −n(H(p) − ε)}.
i=1

Donc
1
Cn = {| Σni=1 (− log p(Xi )) − H(p)| ≤ ε}.
n

Observons que E(− log p(X)) = H(p). Cela provient directement de la définition de l’espérance
d’une variable
P aléatoire f (X) quand X est une autre variable aléatoire à valeurs dans X ,
Ef (X) = x∈X f (x)P(X = x). Ici, on l’applique à f (x) = − log p(x).
Nous pouvons appliquer l’inégalité de Tchebychev

Sn σ 2 (− log p(X))
P(| − E(− log p(X))| ≥ ε) ≤ → 0 quand n → ∞,
n nε2
ce qui nous donne

1 σ 2 (− log p(X))
P((X1 , ..., Xn ) ∈ Cnc ) = P({| Σni=1 (− log p(Xi )) − H(p)| > ε}) ≤ .
n nε2
Fixant ε et choisissant n suffisamment grand nous obtenons P(Cn ) ≥ 1 − ε.
Dans Cn les suites ont toutes plus ou moins la probabilité 2−nH(p) et, plus précisément:
X
P(Cn )) ≥ p(x1 . . . xn ) ≥ 2−n(H(p)+ε) Card(Cn ).
(x1 ...xn )∈Cn

Comme P(Cn ) ≤ 1 on déduit que Card(Cn ) ≤ 2(H(p)+ε)n .

◦

Nous allons interpréter nH(p) comme la longueur moyenne de messages de n symboles codés
dans l’alphabet {0, 1} de manière optimale.

Lemme 6.2 Soit X un ensemble de messages élémentaires ou symboles et X une source

émettant des messages répétés avec la distribution p = (p(x))x∈X . Pour tout ε > 0 nous
pouvons, si n est suffisamment grand, coder les messages répétés de telle manière que la
longueur moyenne par symbole soit inférieure ou égale à H(p) + ε.
6.1. MESSAGES TYPIQUES 39

Démonstration Pour réaliser le codage annoncé, fixons 1 > ε > 0 et choisissons n suffisam-
ment grand pour assurer que P(Cnc ) ≤ ε et Card(Cn ) < 2n(H(p)+ε) . Donc nous pouvons coder
tous les éléments de Cn en utilisant les nombres binaires supérieurs ou égaux à 2[n(H(p)+ε)+1]
et strictement inférieurs à 2[n(H(p)+ε)+2] . Ce sont des nombres binaires qui ont tous la même
longueur [n(H(p) + ε) + 2]. Donc ils forment un code préfixe. De plus au moins un de ces
codes, m, n’est pas utilisé.
Considérons alors les codes non typiques, qui sont beaucoup plus nombreux! Leur nombre
est strictement inférieur à k n = 2n log k . Comme pour les éléments de Cn , nous pouvons les
énumérer avec des nombres binaires ayant tous la même longueur [n log k + 2]. Pour obtenir
un codage préfixe, il convient d’ajouter à tous ces nombres le préfixe m. Ainsi, nous obtenons
des codes de longueur [n log k + 2] + [nH(p) + 2].
Nous avons attribué un code à tous les éléments de X n . La longueur de chaque code
binaire de Cn est inférieure ou égale à n(H(p) + ε) + 2. La longueur des autres codes est
inférieure ou égale à n(log k + H(p)) + 4. Comme Pn (Cn ) ≤ 1 et Pn (Cnc ) ≤ ε), la longueur
moyenne Eln d’un message de n symboles avec ce codage vérifie

Eln ≤ ε(n(log k + H(p)) + 4) + (1 − ε)(n(H(p) + ε) + 2), ce qui nous donne:

Eln
lim sup ≤ (1 − ε)(H(p) + ε) + ε(log k + H(p)).
n→∞ n

Comme p et k sont fixes et ε arbitrairement petit, nous obtenons le résultat annoncé. ◦

Maintenant il faut démontrer l’inégalité inverse, c’est-à-dire que nous ne pouvons pas coder
les messages de n symboles avec strictement moins que H(p) bits par symbole.

Lemme 6.3 Pour tout ² > 0, si n est suffisamment grand, l’espérance Eln de la longueur de
tout codage binaire h de Cn vérifie

Eln ≥ n(H(p) − ε).

Démonstration Fixons ε > 0 et considérons l’ensemble des messages typiques Cn . La

probabilité πi de chacun de ces messages, énumérés de i = 1 à N , vérifie (par définition de
l’ensemble des messages typiques)

π(i) ≥ 2−n(H(p)+ε) . (6.1)

Le cardinal N de l’ensemble Cn vérifie 2n(H(p)−ε) ≤ N ≤ 2n(H(p)+ε) . De plus, nous savons que

N
X
πi = P(Cn ) ≥ 1 − ε (6.2)
i=1

pour n suffisamment grand. Soit h(i) un codage binaire de Cn . Pour éviter que certains des
codes commencent par des zéros, nous pouvons, pour que tous ces codes binaires distincts
deviennent des nombres binaires distincts, juxtaposer à tous les h(i) un 1 à gauche, ce qui
augmente leur longueur de 1. Supposons sans perte de généralité que les nouveaux codes
1h(i) sont ordonnés en ordre croissant. Donc 1 ≤ i ≤ N est le rang de 1h(i). Finalement
40 CHAPTER 6. MESSAGES RÉPÉTÉS ET ENTROPIE

remarquons que [log i] est la longueur de i écrit comme un nombre binaire. Comme 1h(i) ≥ i,
nous avons l(1h(i)) ≥ [log i], ce qui donne

N
X N
X N
X
πi l(h(i)) ≥ πi [log i] − 1 ≥ πi log i − 2, (6.3)
i=1 i=1 i=1

puisque [r] ≥ r − 1. On a

N
X N
X
πi log(i) ≥ (log N − k) πi . (6.4)
i=1 i=N 2−k

Mais des estimations sur πi et N , il vient

−k N
2X
πi ≤ 2−n(H(p)−ε) 2−k 2n(H(p)+ε) = 22nε−k . (6.5)
1

De (6.4), (6.5) et (6.2), on tire

N
X
πi log(i) ≥ (log N − k)(1 − 22nε−k − ε) ≥ (n(H(p) − ε) − k)(1 − 22nε−k − ε).
i=1

Choisissant k =: 4nε, on obtient de cette dernière minoration et de (6.3)

N
1X
lim inf πi l(h(i)) ≥ (H(p) − 5ε)(1 − ε).
n→∞ n
i=1

Cette inégalité étant vraie pour ε arbitrairement petit, on conclut.

◦

En combinant les deux lemmes précédents, nous pouvons démontrer le résultat fonda-
mental de Shannon :

Théorème 6.1 L’espérance minimale El de la longueur par symbole d’un message émis n
fois par une source d’entropie H(p) est égal à (H(p) + ε(n)) avec ε(n) → 0 quand n → ∞.

Démonstration Considérons par chaque n un codage h de longueur minimale de X n .

Comme X n ⊃ Cn , ce codage code Cn et nous pouvons appliquer le lemme 6.3. Donc sa
longueur par symbole est supérieure ou égale à H(p) − ε, pour n grand. Comme h est
un codage optimal, l’espérance de sa longueur est aussi pour n grand inférieure ou égale à
H(p) + ε par le lemme 6.2. Combinant les deux résultats nous voyons que pour tout ε > 0 et
pour n suffisamment grand, H(p) − ε ≤ El ≤ H(p) + ε.
◦
6.2. EXERCICES ET IMPLÉMENTATIONS MATLAB 41

6.2 Exercices et implémentations Matlab

Exercice 42 On va montrer que la longueur moyenne λ(N ) des nombres binaires inférieurs
à N vérifie λ(N ) ∼ log N, où ε(N ) → 0 quand N → ∞.
1) Soit m tel que 2m ≤ N < 2m+1 . Vérifier que les nombres binaires plus grands que 2j−1 et
strictement plus petits que 2j ont une longueur égale à j et que leur nombre est égal à 2j−1 .
Déduire que
m
1 X j−1
m + 1 ≥ log N ≥ λ(N ) = ( j2 + (m + 1)(N − 2m + 1)). (6.6)
N
j=1

2) Soit p ∈ IN tel que 2−p < ε. Ecrire

m
X
1
λ(N ) ≥ ( j2j−1 + (m + 1)(N − 2m + 1))
N
j=m−p+1

et déduire que λ(N ) ≥ (m − p + 1)(1 − 2−p ).

3) Déduire que
λ(N )
1 ≥ lim sup ≥ (1 − 2−p )
N →∞ log N
et conclure.

Exercice 43 Le codage de Lempel Ziv

Ziv et Lempel ont inventé un algorithme de codage universel qui est optimal, au sens
très général que pour n’importe quelle suite ergodique, son taux de compression tend vers
l’entropie de la source. La preuve qu’il en est ainsi est donnée dans Cover-Thomas, pp. 319
à 326. Cette preuve n’est pas difficile. De plus, il est immédiat de vérifier que cette preuve
s’applique directement à l’hypothèse plus simple qu’une source est markovienne d’ordre k.
Dans ce cas, la preuve mentionnée montre que si on considère le vecteur aléatoire (X1 , . . . , Xn )
fait des n valeurs produites par la source, et si on note l(X1 , X2 , . . . , Xn ) la longueur du code
de Lempel-Ziv de ce vecteur, alors
1
lim sup l(X1 , . . . , Xn ) ≤ H(X ),
n
où l’entropie de la source markovienne X d’ordre k est définie par H(X ) = H(Xk | Xk−1 , . . . , X0 ).
Cette définition de l’entropie d’une source markovienne est parfaitement transparente: elle
mesure l’incertitude laissée sur Xn quand on connaı̂t les k précédents, Xn−1 , . . . , Xn−k .
L’algorithme de Lempel-Ziv est facile à décrire. Etant donnée une suite de longueur n, elle
se décompose en chaı̂nes de 0 et 1 de longueur minimale et telles que chacune d’entre elles ap-
paraı̂t pour la première fois dans la suite. Ainsi la suite 101100101000111101011100011010101101
se décompose en

(1)(0)(11)(00)(10)(100)(01)(111)(010)(1110)(001)(101)(010)

1) Démontrer que chacune des chaı̂nes de la décomposition s’écrit w0 ou w1 où w est une
chaı̂ne apparue antérieurement. On appelle c(n) le nombre de chaı̂nes de la suite.
42 CHAPTER 6. MESSAGES RÉPÉTÉS ET ENTROPIE

2) Alors on code la suite en donnant comme code à chaque chaı̂ne s’écrivant w0 ou w1 le

numéro d’ordre dans la suite de la chaı̂ne antérieure w, suivi de son dernier bit (0 ou 1). Le
code de la suite que nous avons donnée comme exemple est donc

(0000, 1)(0000, 0)(0001, 1)(0010, 0)(0001, 0)(0101, 0)(0010, 1)(0011, 1)(0111, 0)(1000, 0)
(0010, 1)(0011, 1)(0101, .)

La dernière chaı̂ne, incomplète, est laissée telle quelle.

3) Démontrer que la longueur totale de la suite comprimée est c(n)(log c(n) + 1) bits.
4) Ecrire l’algoritme en Matlab, l’appliquer à un texte très grand et comparer la longueur en
bits résultante avec celle obtenue avec un code de Huffman.
Chapter 7

La communication sûre est possible

malgré le bruit

7.1 Transmission dans un canal bruité

Le problème principal que Shannon aborde et résoud est la transmission dans un canal avec
bruit, c’est-à-dire subissant des erreurs aléatoires durant la transmission. Le problème prin-
cipal est de décider si la transmission est possible et, surtout, à quel prix en termes de redon-
dance. Shannon part de ses expériences de jeunesse quand, enfant dans une ferme americaine
immense, il comuniquait avec ses copains par télégraphe grâce aux fils eléctriques des haies
de pâturages. Il réalisa qu’un message en anglais très incomplet, où presque la moitié des
lettres est incorrecte ou manquante, peut être reconstruit correctement par le récepteur. Celà
est dû à la redondance du langage. Le destin de Shannon était de faire très jeune cette ob-
servation empirique, et de la formaliser mathématiquement bien des années plus tard, quand
il réussit à calculer l’entropie de l’anglais de tous les jours. On vérifie en effet que le degré
de compression d’un texte anglais courant atteint cinquante pour cent. Une autre intuition
acquise par l’expérience est celle que Shannon traduira dans son fameux théorème: plus une
suite est longue, et plus elle est facile à reconstruire (et donc aussi à comprimer).
Le théorème de Shannon, bien qu’obtenu par des arguments d’existence mathématique
non constructifs, provoqua l’enthousiasme des ingénieurs par sa simplicité et par le défi tech-
nologique ainsi lancé. Shannon considère une source émettrice X, ou source d’entrée. Mais
s’il y a du bruit dans le canal la réception est représentée par une variable aléatoire Y dis-
tincte de X, que l’on appelle la sortie du canal. Pour mesurer l’incertitude sur X laissée
quand on observe la sortie Y , Shannon introduit la notion d’entropie relative, H(X|Y ). Elle
peut aussi être utilisée sous la forme H(Y |X), qui mesure l’incertitude qui sera laissée sur la
sortie Y connaissant l’entrée X. H(Y |X) mesure donc l’incertitude causée par le bruit.
Dans son théorème fondamental, Shannon démontre qu’il est possible de coder les mes-
sages émis par X de telle manière que la proportion d’erreurs dans la transmission soit
arbitrairement basse. En d’autres termes la communication sûre malgré le bruit est pos-
sible! Shannon propose de mesurer la capacité d’un canal de transmission bruité comme
maxX H(X) − H(X|Y ), le maximum étant pris parmi toutes les sources possibles prises
comme entrées. Cette capacité est donc obtenue en soustrayant de la quantité d’information
émise H(X) l’incertitude H(X|Y ) laissée sur X après l’observation de Y . Le grand théorème
de Shannon est quantitatif: toute source d’entropie inférieure à la capacité peut être transmise

43
44 CHAPTER 7. LA COMMUNICATION SÛRE EST POSSIBLE MALGRÉ LE BRUIT

intégralement dans le canal.

Messages et sorties typiques pour un canal avec bruit
Considérons une source X de loi p(x), x ∈ X . Un canal de transmission bruité transmet X
avec des erreurs. Le résultat observé est Y , de loi p(y), y ∈ Y. La loi conjointe de X et Y est
p(x, y) = P(X = x, Y = y), définie sur X × Y. Dans le cas d’un canal sans bruit nous aurions
p(x, x) = p(x) par tout x et p(x, y) = 0 si x 6= y. Las entropies de deux variables et de leur
couple s’écrivent H(X), H(Y ) et H(X, Y ). Dans la communication répétée, si la source émet
des messages composés de n symboles équidistribués et indépendants, le message résultant
vu comme une variable aléatoire s’écrit X n et la sortie Y n . La séquence Y n est également
composée de symboles indépendants. Plus précisément, les couples (X1 , Y1 ), (X2 , Y2 ), ...
(Xn , Yn ) sont supposés indépendants. X n et Y n sont à valeurs dans X n et Y n respectivement.
Les valeurs possibles de X n s’écriront xn ∈ X n et celles de Y n , y n ∈ Y n .

Définition 7.1 Nous appellerons ensemble de paires entrée-sortie typiques relativement à la

distribution p(x, y) l’ensemble Anε des suites {(xn , y n )} dont les probabilités sont typiques au
sens suivant: Anε = Bεn ∩ Cεn ∩ Dεn avec
1
Bεn = {(xn , y n ) ∈ X n × Y n : | − log p(xn , y n ) − H(X, Y )| < ε}; (7.1)
n
1
Cεn = {(xn , y n ) ∈ X n × Y n : | − log p(xn ) − H(X)| < ε}; (7.2)
n
1
Dεn = {(xn , y n ) ∈ X n × Y n : | − log p(y n ) − H(Y )| < ε}; (7.3)
n
où p(xn ) =: P1 ({xn }) = Πni=1 p(xi ), p(y n ) =: P2 ({y n }) = Πni=1 p(yi ), p(xn , y n ) = P({xn , y n }) =
Πni=1 p(xi , yi ) en utilisant l’indépendance des messages successifs, et P1 et P2 sont les marginales
de P.

Lemme 7.1 Soit (X n , Y n ) une suite de longueur n de v.a.i.i.d. suivant la loi P({x,n , y n }) =
p(xn , y n ) = Πni=1 p(xi , yi ). Alors
1. P((X n , Y n ) ∈ Anε ) → 1 quand n → ∞.
2. Card({y n , (xn , y n ) ∈ Anε }) ≤ 2n(H(Y |X)+2ε)
3. Card({xn , (xn , y n ) ∈ Anε }) ≤ 2n(H(X|Y )+2ε)

La relation 2. indique une borne cruciale sur le nombre de messages typiques y n que peut
causer un message typique xn . Dans la démonstration qui suit et dans le reste de ce chapitre
nous écrirons 2a±ε pour indiquer un nombre quelconque b tel que 2a−ε ≤ b ≤ 2a+ε . Avec
cette notation, on a la relation 2a±ε × 2b±ε = 2a+b±2ε .

Démonstration On va montrer la première relation. Considérons π1 : (xn , y n ) → xn et

π2 : (xn , y n ) → y n les aplications de projection de X n × Y n sur X n et Y n respectivement.
Le résultat du lemme 6.1 permet d’affirmer que quand n → ∞,

P(Bεn ) → 1 (7.4)
P(Cεn ) = P(π1 (Cεn ) × Y n ) = P1 (π1 (Cεn )) → 1 (7.5)
P(Dεn ) = P(X n × π2 (Dεn )) = P2 (π2 (Dεn )) → 1. (7.6)
7.1. TRANSMISSION DANS UN CANAL BRUITÉ 45

En effet, π1 (Cεn ) est tout bonnement l’ensemble des messages typiques pour P1 et de même
π2 (Dεn ) est l’ensemble des messages typiques pour P2 . La relation 1. se déduit alors de la
remarque générale que si des suites d’ensembles Bin , i = 1, . . . , k vérifient P(Bin ) → 1 quand
n → ∞, alors P(∩ki=1 Bin ) → 1 aussi. On applique cette remarque à l’intersection des trois
ensembles précédents,

Aεn = Bεn ∩ (π1 (Cε ) × Y n ) ∩ (X n × π2 (Dεn )).

Maintenant passons à la relation 2. Par les hypothèses de typicité, P(X n = xn ) = p(xn ) =

2−n(H(X)±ε) et P((X n , Y n ) = (xn , y n )) = p(xn , y n ) = 2−n(H(X,Y )±ε) . Donc
X X
p(xn ) = p(xn , y n ) ≥ p(xn , y n ) ≥ Card({y n , (xn , y n ) ∈ Anε }) inf p(xn , y n ).
(xn ,y n )∈An
ε
yn y n , (xn ,y n )∈An
ε

Mais p(xn ) = 2n(H(X)±ε) et p(xn , y n ) = 2n(H(X,Y )±ε) . Donc

Card({y n , (xn , y n ) ∈ Anε }) ≤ 2−n(−H(X,Y )+H(X)+2ε) = 2n(H(Y |X)+2ε) .

La démonstration de 3. est strictement analogue de celle de 2. ◦

Capacité d’un canal bruité

Considérons un canal discret, c’est-à-dire un système disposant d’un alphabet d’entrée X
et d’un alphabet de sortie Y ainsi que d’une matrice de probabilités de transition p(y|x)
donnant la probabilité d’observer un symbole y comme sortie quand le symbole x a été émis.
Nous dirons qu’un tel canal est “sans mémoire”, car la distribution de probabilité de la sortie
dépend uniquement de l’entrée et est indépendante des entrées et sorties précédentes. Nous
allons alors définir le transmission rate du canal, ou taux de transmission étant données la
source X et sa sortie correspondante Y par

I(X; Y ) = H(X) − H(X|Y ) = H(Y ) − H(Y |X) = H(X) + H(Y ) − H(X, Y ).

The first defining expression has already been defined as the amount of information sent less
the uncertainty of what was sent. The second measures the amount received less the part of
this which is due to noise. The third is the sum of the two amounts less the joint entropy
and therefore in a sense is the number of bits per second common to the two. Thus, all
three expressions have a certain intuitive significance. H(Y | X) est donc interprétée comme
une mesure de la quantité de bruit, sans que l’on ait pour cela besoin de modéliser le bruit
par lui-même. Rappelons que I(X; Y ) est une formule symétrique en X et Y , que l’on ap-
pelle aussi information mutuelle, et qui est nulle si et seulement si X et Y sont indépendantes.

Définition 7.2 Nous appellerons capacité d’un canal discret sans mémoire la quantité

C = max I(X; Y ),
p(x)

où le maximum se calcule sur toutes les distributions de probabilité possibles p(x), x ∈ X en
entrée.
46 CHAPTER 7. LA COMMUNICATION SÛRE EST POSSIBLE MALGRÉ LE BRUIT

La première chose qu’il faut remarquer est que ce problème est un problème d’optimisation
dans RCard(X ) , puisque nous connaissons les valeurs de p(y|x).
Exemple 1: transmission sans bruit
Si le canal transmet intégralement une entrée binaire sans erreur, la matrice de transition est
l’identité. Alors Y = X et donc I(X; X) = H(X) − H(X|X) = H(X). Alors la capacité est
maximale quand l’entropie de la source émettrice est maximale, ce qui implique ce que nous
attendons, à savoir p(0) = p(1) = 12 et C = H(p) = 1 bit.
Exemple 2 : canal binaire symétrique
Prenons X = Y = {0, 1} et

p(y = 1|x = 1) = p(y = 0|x = 0) = 1 − p, p(y = 1|x = 0) = p(y = 0|x = 1) = p.

Comme l’entropie d’une variable de Bernoulli B(p, 1−p) est H(p) = −p log p−(1−p) log(1−p),
nous obtenons
X X
H(Y )−H(Y |X) = H(Y )− p(x)H(Y |X = x) = H(Y )− p(x)H(p) = H(Y )−H(p) ≤ 1−H(p).

Il y aura égalité dans cette inégalité si et seulement si X est uniforme, puisqu’alors Y est
aussi uniforme et H(Y ) = 1. Donc C = 1 − H(p). Quand p = 12 , la capacité est nulle et le
canal ne transmet rien. Dans tous les autres cas, il y a transmission d’information.

7.2 Le théorème fondamental pour un canal discret bruité

Théorème 7.1 (Shannon pages 71, 72, 73) Considérons un canal discret de capacité C et
une source discrète d’entropie E.
(a) Si E ≤ C il existe un système de codage tel que la sortie de la source se transmette par
le canal avec une fréquence arbitrairement petite d’erreur.
(b) Si E > C il est encore possible de coder la source de telle sorte que l’incertitude sur les
messages H(X|Y ) soit inférieure à E − C + ε, où ε est arbitrairement petit.
(c) Il n’y a pas de méthode de codage permettant d’atteindre une incertitude sur les messages,
H(X|Y ), inférieure à E − C.

Démonstration (a) Considérons une source X0 de taux de transmission très proche de la

capacité maximale C et soit Y0 sa sortie. Nous allons utiliser X0 comme entrée dans le canal.
Considérons toutes les suites possibles transmises et reçues, de longueur n. Dans tout ce qui
suit, les ε, η, θ seront des réels positifs qui tendent vers zéro quand le taux de la source X0
se rapproche de la capacité maximale du canal ou quand la durée de transmission n → ∞.
Chaque fois que nous aurons Cε avec une constante C indépendante de n, nous écrirons ε
pour Cε afin d’alléger la notation, s.p.d.g..
Soit Anε l’ensemble des paires typiques (xn , y n ). (Definition 7.1).
1. Les suites transmises peuvent être dans deux groupes : les messages typiques dont le
nombre est 2n(H(X0 )±ε) et les autres, dont la probabilité totale est inférieur à η.

2. De la même manière, les suites reçues forment un ensemble de suites typiques de nombre
2n(H(Y0 )±ε) et de probabilité totale supérieur à 1 − η. Nous allons appeler M0 cet
ensemble de messages typiques.
7.2. LE THÉORÈME FONDAMENTAL POUR UN CANAL DISCRET BRUITÉ 47

3. Par le lemme 7.1, propriété 3, chaque sortie typique a pu être produite par tout au plus
2n(H(X0 |Y0 )+ε) entrées.

4. De la même manière, chaque entrée typique peut produire tout au plus 2n(H(Y0 |X0 )±ε)
sorties (mais nous n’allons pas utiliser cette dernière propriété.)

Considérons alors une source X d’entropie E < C. Ecrivons E = C − 2θ et choisissons X0

tel que son taux de transmission vérifie H(X0 ) − H(X0 |Y0 ) > C − θ. Donc

E − (H(X0 ) − H(X0 |Y0 )) < −θ. (7.7)

En un temps de transmission n, la source X peut produire 2n(E±ε) messages typiques. Nous

allons appeler M cet ensemble de messages typiques et nous allons les coder en les associant à
des messages typiques de longueur n de la source X0 , qui seront utilisés comme codes. Chaque
codage est une application C | : M → M0 obtenue en tirant au sort (avec une distribution
uniforme) pour chaque message dans M un élément de M0 qui est donc choisi aléatoirement
comme son code. Les autres messages, non typiques, ne sont tout bonnement pas codés, ce
qui nous donne de toutes façons une probabilité d’erreur inférieure à η.
Nous allons évaluer la probabilité d’erreur, c’est-à-dire la probabilité qu’un message donné
y1 ait été associé à un message de M. Pour tout message effectivement observé y1 , cette
probabilité s’interprète comme une probabilité d’erreur, à savoir comme la probabilité que y1
ait été associé à deux messages de M. Par la conclusion 3. du lemme 7.1, nous savons que
y1 n’a pu être produit par plus de 2n(H(X0 |Y0 )+ε) messages x0 dans M0 . Mais la probabilité
que chaque x0 ∈ M0 soit un code est 2n(E−H(X0 )±ε) . En effet, nous avons distribué 2n(E±ε)
messages uniformément sur 2n(H(X0 )±ε) codes. Cela implique que la probabilité que y1 soit
le code d’un autre message de X (en plus du message dont il est déjà le code) est inférieure à

P(erreur sur y1 ) ≤ 2n(E−H(X0 )±ε) 2n(H(X0 |Y0 )+2ε) .

Donc par (7.7),

P(erreur sur y1 ) ≤ 2n(E−H(X0 )+ε+H(X0 |Y0 )+2ε) = 2−n(θ−3ε)

Comme η a été fixé (arbitrairement petit) et, η une fois fixé, comme nous pouvons choisir
ε aussi petit que désiré pour n assez grand, nous déduisons que la probabilité d’erreur pour
chaque message est arbitrairement petite, ce qui démontre (a) pour E < C.

(b) Si E ≥ C, on peut toujours appliquer la construction précédente mais ne pouvons coder

plus de 2n(C−ε) messages des 2n(E±ε) typiques. Celà enlève pas mal d’intérêt au codage,
puisque la majorité des messages typiques ne sont pas transmis!

(c) Supposons que l’on puisse transmettre par un canal de capacité C les messages d’une
source X0 d’entropie E = C + a, avec a > 0 et que l’incertitude sur le message vérifie
H(Y0 |X0 ) = a − ε avec ε > 0. Alors H(X0 ) − H(X0 |Y0 ) = C + ε et cela contredit la définition
de C comme le maximum de H(X0 ) − H(X0 |Y0 ) pour toutes les sources en entrée.

Exercice 44 La question de la fin

1) Expliquer le raisonnement par lequel Shannon conclut sa démonstration:
48 CHAPTER 7. LA COMMUNICATION SÛRE EST POSSIBLE MALGRÉ LE BRUIT

Figure 7.1: Le schéma original de Shannon. T , le temps de transmission est ce que nous
avons appelé n. Hy (x) est dans nos notations H(X | Y ).

Actually more has been proved than was stated in the theorem. If the average of a set of
√
positive numbers is within ε of zero, a fraction of at most ε can have values greater than
√
ε. Since ε is arbitrarily small we can say that almost all the systems are arbitrarily close
to the ideal.
2) En d’autres termes presque tous les codes considérés, choisis au hasard, sont des codes qui
corrigent spontanément les erreurs! Alors, pourquoi est-il difficile en pratique de concevoir
un code correcteur d’erreurs?
Chapter 8

Séries de Fourier (Révision)

On considère l’espace de Hilbert hermitien L2 ([−π, π]) que l’on notera aussi L2 (−π, π). Ces
fonctions sont à valeurs réelles ou complexes. On va montrer que le système orthonormé
1
1 (eint )n∈Z
(2π) 2

est une base hilbertienne de L2 (−π, π). Cette base s’appelle la base de Fourier. On notera
Z π
1
cn (f ) = f (x)e−inx dx,
2π −π
en sorte que pour toute f dans L2 ([−π, π]) on puisse écrire
X
f (x) = cn (f )einx ,
n∈Z

la série précédente convergeant au sens L2 .

Les cn (f ) s’appellent les coefficients de Fourier
de f et sont proportionnels aux coordonnées de f dans la base de Fourier.
Pour montrer ce résultat, on va commencer par analyser le comportement des coefficients
de Fourier selon la régularité de f .
Lemme 8.1 Riemann-Lebesgue (Lemme de) (Lemme de Riemann-Lebesgue)
i) On pose pour f ∈ L1 (R), Z
ˆ
f (ξ) = f (x)e−iξx dx.
R
Si f ∈ Cc (R) est k fois continûment différentiable et telle que f (k) ∈ L1 (R), alors
||f (k) ||L1
|fˆ(ξ)| ≤ .
|ξ|k
R
ii) Si f ∈ L1 (R) alors R f (x)eiax dx → 0 quand |a| → ∞.
iii) Application aux coefficients de Fourier : si f ∈ L1 (−π, π),
lim cn (f ) = 0.
|n|→∞

Remarque 8.1 Si f ∈ L2 , on sait immédiatement que cn (f ) → 0 car cn (f ) s’interprètent

comme les coordonnées de f sur un système orthonormé.

49
50 CHAPTER 8. SÉRIES DE FOURIER (RÉVISION)

Démonstration i) En intégrant par parties k fois l’intégrale définissant fˆ, on obtient pour
ξ 6= 0,
Z
ˆ 1 (k) −ixξ ||f (k) ||L1
|f (ξ)| = | f (x)e dx| ≤ .
(iξ)k |ξ|k

ii) Soit fn une suite de fonctions C ∞ et à support compact qui tendent vers f dans L1
(proposition ??). On a, pour n fixé assez grand : ||fn − f ||1 ≤ ε, ce qui implique |fˆn (ξ) −
fˆ(ξ)| ≤ ε pour tout ξ. En utilisant (i), on voit que |fˆn (ξ)| → 0 quand n est fixé et |ξ| → ∞.
Donc |fˆn (ξ)| ≤ ε pour ξ assez grand. Finalement,
|fˆ(ξ)| ≤ |fˆ(ξ) − fˆn (ξ)| + |fˆn (ξ)| ≤ 2ε
pour ξ assez grand. ◦

La proposition suivante nous dit que la série de Fourier de f converge vers f (x) en tout point
x où f est suffisamment régulière.

Proposition 8.1 principe de localisation (Principe de localisation)

Si f ∈ L1 (−π, π) et si la fonction y → f (y)−f
y−x
(x)
est intégrable sur un voisinage de x, alors
P
limN →∞ sN f (x) = f (x), où on a noté : sN f (x) =: |n|≤N cn (f )einx .

Expliquons pourquoi le résultat précédent s’appelle principe de localisation. Alors que sN (f )

est le résultat d’un calcul intégral sur tout l’intervalle [−π, π], et donc d’un calcul global, le
comportement de sN f (x) dépend du comportement local de f au voisinage de x. Il y a donc
“localisation”.

Démonstration Etape 1 On se ramène au cas f (x) = 0, x = 0.

Supposons la proposition démontrée pour x = 0, f (x) = 0. Soit maintenant g ∈ L1 (−π, π)
telle que g(y)−g(x)
y−x soit intégrable au voisinage de x. Alors on pose f (y) = g(x + y) − g(x). On
a bien f (0) = 0 et f (y)
y =
g(x+y)−g(x)
y est intégrable au voisinage de 0. Donc, par hypothèse,
sN f (0) → f (0) = 0. Mais
X X 1 Z π
sN f (0) = cn (g(x + y) − g(x)) = (g(x + y) − g(x))e−iny dy
2π −π
|n|≤N |n|≤N

X 1 Z π X 1 Z π
−in(z−x) inx
=( g(z)e dz) − g(x) = ( e g(z)e−inz dz) − g(x)
2π −π 2π −π
|n|≤N |n|≤N

= sN g(x) − g(x).
Donc sN g(x) → g(x). En fait, l’argument précédent montre que sN commute avec les trans-
lations :
sN [g(. + x)] = (sN g)(. + x).

Etape 2 On a
Z
1 π sin(N + 21 )y
sN f (0) = f (y) dy. (8.1)
2π −π sin y2
 51

PN iky = sin(N + 12 )y
En effet, −N e sin y2 , ce qui se prouve aisément en sommant la suite géométrique.
f (y)
Etape 3 Par l’étape 1 il suffit de montrer que si f ∈ L1 (−π, π) et si y est intégrable
|y|
autour de 0, alors sN f (0) → 0. Comme sur [−π, π], |sin y2 | ≥ π , on a

f (y) π|f (y)|

| |≤ ∈ L1 (−π, π).
sin y2 |y|

f (y)
Donc on peut appliquer le lemme de Riemann-Lebesgue à la fonction sin y . On conclut que
2
l’intégrale de (8.1) définissant sN f (0) tend vers 0 quand N tend vers l’infini. ◦

Exercice 45 Une preuve rapide et une généralisation du principe de localisation.

Soit f ∈ L1 (0, 2π), 2π-périodique. On note sN,M f la série partielle de Fourier de f , définie
par
sN,M f (x) = Σk=M
k=−N ck (f )e
ikx
,
1
R 2π −ikx dx. On rappelle que par le Lemme de Riemann-Lebesgue, c (f ) →
où ck (f ) = 2π 0 f (x)e k
0 quand k → ±∞. Nous allons montrer le théorème suivant, qui est une version du ”principe
de localisation”.

Théorème 8.1 principe de localisation!généralisation (i) Soit f (x) une fonction 2π-périodique
telle que
f (x)
ix
= g(x) ∈ L1 (0, 2π).
e −1
Alors sN,M f (0) → 0 quand N, M → +∞.
(ii) Plus généralement, si x → f (x)−c 1
x−y ∈ L (0, 2π), alors sN,M f (y) → c.

Remarque : si f est continue en 0, la première hypothèse entraı̂ne f (0) = 0. Si f est

continue en y, la deuxième hypothèse entraı̂ne f (y) = c.

On appelle l’énoncé précédent le principe de localisation car il dit, en termes informels,

que ”si f est régulière en x, alors la série de Fourier de f tend vers f (x) au point x”. Bien
que sN,M f soit définie par une formule globale (une intégrale sur l’intervalle [0, 2π]), la série
de Fourier reconnaı̂t les points réguliers et son comportement dépend du comportement local
de f . La démonstration qui suit est un exercice vraiment élémentaire grâce à l’astucieuse
démonstration due à Ronald Coifman, de l’Université de Yale (démonstration communiquée
par Yves Meyer).

1) Déduire (ii) de (i).

2) Sous l’hypothèse de (i), onPappelle γk les coefficients de Fourier de g. Montrer que

ck = γk−1 − γk . En déduire que M
N ck → 0 et conclure en appliquant le Lemme de Riemann-
Lebesgue.
52 CHAPTER 8. SÉRIES DE FOURIER (RÉVISION)

Corollary 1 base!de Fourier Le système

1
1 (eikt )k∈Z
(2π) 2

1
Rπ
est une base hilbertienne de L2 (−π, π). Notant cn (f ) = 2π −π e−inx f (x)dx, on a donc pour
toute f dans L2 ([−π, π]), X
f (x) = cn (f )einx ,
n∈Z

la série précédente convergeant au sens L2 .

Démonstration
PN On appelle polynôme trigonométrique toute expression de la forme P (t) =
a e ikt , où les a sont des nombres complexes. Pour montrer que le système de Fourier
k=−N k k
est une base hilbertienne, il nous suffit de montrer que c’est un système total, c’est-à-dire que
les polynômes trigonométriques forment un sous-espace vectoriel dense de L2 (−π, π). Mais
le lemme 8.1 (Principe de localisation) nous assure que si f est (e.g.) C 2 et 2π-périodique
sur R, alors sN (f )(x) → f (x) en tout point (On peut aussi utiliser directement le théorème
de Stone-Weierstrass). Comme de plus les coefficients de la série de Fourier de f vérifient
|ck (f )| ≤ kC2 , la série de Fourier est en fait uniformément convergente et donc converge aussi
dans L2 ([−π, π]) vers f . Or, les fonctions C 2 et 2π-périodiques forment un sous-espace dense
de L2 ([−π, π]). En effet, par la proposition ??, les fonctions C ∞ à support compact dans
[−π, π] sont denses dans L2 (−π, π). On conclut que le système de Fourier est total, et donc
une base hilbertienne. ◦

Corollary 2 principe de localisation!(pour une fonction Hölderienne) si f ∈ L1 ([−π, π]) est

Höldérienne d’exposant 0 < α ≤ 1 en x ( c’est-à-dire |f (x) − f (y)| ≤ C|x − y|α ), alors
sN f (x) → f (x). Cette conclusion s’applique si f est une primitive sur [−π, π] d’une fonction
de L2 (−π, π).

Démonstration L’application du principe de localisation est immédiate :

| f (y)−f
y−x
(x)
| ≤ |x − y|α−1 qui est bien intégrable au voisinage de x. Soit maintenant f une
fonction qui est la primitive sur [−π, π] d’une fonction de L2 (−π, π). En appliquant l’inégalité
de Cauchy-Schwarz,
Z x Z π
1 1
|f (x) − f (y)| = | f 0 (t)dt| ≤ |y − x| 2 ( |f 0 (t)|2 dt) 2 .
y −π

1
La fonction f est donc Hölderienne d’exposant 2 et le principe de localisation s’applique. ◦

8.1 Convolution des fonctions périodiques et séries de Fourier

La décomposition en série de Fourier d’une fonction f ∈ L2 ([−π, π]) implique qu’on la con-
sidère comme une fonction 2π−périodique, puisque la série de Fourier l’est. On note L2per (R)
8.1. CONVOLUTION DES FONCTIONS PÉRIODIQUES ET SÉRIES DE FOURIER 53

l’ensemble des fonctions f ∈ L2loc (R) qui sont 2π-périodiques. Toute fonction f ∈ L2 ([−π, π])
définit un élément unique de L2 ([−π, π]).

Définition 8.1 convolution!périodique et proposition Si f ∈ L1 ([−π, π]) et g R∈ L1 ([−π, π]),

π
on prolonge f et g en des fonctions 2π-périodiques sur R et on pose f ∗ g(x) = −π f (y)g(x −
y)dy. La fonction f ∗ g ainsi définie appartient à L1 (−π, π) et est 2π-périodique.

Exercice 46 En reprenant l’argument du théorème ??, montrer que si T : L2per ([−π, π]) →
0 ([−π, π]) est linéaire, continu et commute avec les translations, alors il existe une fonction
Cper
g ∈ L2 ([−π, π]) telle que T f = g ∗ f , où ”∗” désigne la convolution périodique.‘

Théorème 8.2 continuité!de la convolée de deux fonctions L2 Si f, g ∈ L2 (−π, π), alors

f ∗ g est continue et cn (f ∗ g) = 2πcn (f )cn (g). De plus, la série de Fourier de f ∗ g converge
uniformément vers f ∗ g.

Remarquons que la relation précédente montre l’effet régularisant de la convolution : les

hautes fréquences de f ∗ g sont plus faibles que celles de f , puisque cn (g) tend vers zéro.

Démonstration i) On a par l’inégalité de Cauchy-Schwarz

Z
|(f ∗ g)(x)| ≤ |f (x − y)||g(y)|dy ≤ ||f ||L2 ||g||L2 .

Donc f ∗ g est majorée et appartient aussi à L2 (−π, π). On a, en appliquant plusieurs fois le
théorème de Fubini (les intégrales se font sur [−π, π] ou, indifféremment, sur n’importe quel
intervalle de longueur 2π) :
Z Z Z Z
1 −int 1
cn (f ∗ g) = f (x − y)g(y)e dydx = f (x − y)e−in(x−y) g(y)e−iny dydx
2π 2π
Z Z
1
= ( g(y)e−iny dy)( f (u)e−inu du) = 2πcn (f )cn (g).
2π

Le terme général de la série de Fourier de f ∗ g vérifie

|cn (f ∗ g)einx | = |cn (f )||cn (g)| ≤ |cn (f )|2 + |cn (f )|2 .

P
Cette dernière série est convergente. La série de Fourier de f ∗ g, FN (x) = Nn=1 cn (f ∗ g)e
inx ,

est donc uniformément convergente. Sa F limite est donc continue. Donc d’une part FN tend
vers f ∗ g dans L2 et donc par la réciproque du théorème de Lebesgue une sous-suite tend
vers cette fonction presque partout. De l’autre FN tend vers F . On en déduit que f ∗ g = F
presque partout et on en déduit que f ∗ g est égale presque partout à une fonction continue
(et donc peut être appelée continue). ◦

Exercice 47 Transformée de Fourier discrète et transformée inverse.

La transformée de Fourier discrète est l’application de L2 ([−π, π]) → l2 (Z) qui associe à une
54 CHAPTER 8. SÉRIES DE FOURIER (RÉVISION)

fonction u la suite de ses coefficients de Fourier c(f ) = (ck (u))k∈Z . la transformée inverse est
la série de Fourier associée à c ∈ l2 (Z), notée
X
S(c)(x) = ck eikx .
k∈Z

On a donc S(c(f )) = f , ce qui constitue une formule d’inversion de Fourier. Si a, b ∈ l2 (Z),

on note ab le produit terme à terme, défini par (ab)k = ak bk .
1
1) Avec le formalisme précédent, vérifier que S(ab) = 2π S(a) ∗ S(b).
2) Cette formule nous permet de mieux comprendre. La démonstration que nous avons
donnée pour le principe de localisation. Considérons le “filtre passe-bas” bN ∈ l2 (Z) défini
par bN N N
k = 1 si |k| ≤ N , bk = 0 sinon. Calculer S(b ).

3) En déduire que la série de Fourier tronquée de f , sN f , est obtenue par convolution 2π-
périodique de f avec ce qu’on appelle le noyau de Féjer, sN f = hN ∗ f , où

sin(N + 21 )y
hN (x) = .
sin y2

8.1.1 Autres bases de Fourier

Corollary 3 base!de Fourier en sinus et cosinus Bases en sinus et en cosinus
i) On pose pour T > 0 ω = 2π T , c’est la fréquence de base associée à la période T . Les
fonctions
1
√ eikωt , k ∈ Z
T
forment une base hilbertienne de L2 (0, T ). Les fonctions
r r
1 2 2kπt 2 2kπt
√ , cos( ), sin( ), k = 1, 2, ...
T T T T T

forment également une base hilbertienne de L2 (0, T ).

ii) Il en est de même pour les fonctions base!en cosinus
r
1 2 kπt
√ , cos( ), k = 1, 2, ...
T T T

La transformée associée à la base en cosinus s’appelle

q la ”transformée en cosinus.”
Il y a également une ”base en sinus”,base!en sinus T2 sin( kπt
T ), k = 1, 2, ....

Démonstration i) La deuxième base résulte de l’application à la base de Fourier de la

remarque générale suivante. Si (ek )k∈Z est une base hilbertienne, alors le système f0 = e0 ,...,
e +e e −e
f2k = k √2−k , f2k+1 = k √2−k , ... aussi.
ii) Si f ∈ L2 (0, T ), on lui associe la fonction paire f˜ sur [−T, T ] qui coı̈ncide avec f sur [0, T ].
On décompose f˜ sur la base de Fourier de [−T, T ]. La base de Fourier sur [−T, T ] est formée
iπkt
des fonctions √1 e T . Donc on a
2T
8.2. BASES DE FOURIER EN DIMENSION 2 55

P RT −iπkt iπkx
f˜(x) =L2 n∈Z 1
2T ( −T f˜(t)e T dt)e T . Comme f˜ est paire, on voit en faisant le change-
iπkt −iπkt
ment de variables t → −t dans les intégrales que les coefficients de e T et e T sont égaux.
RT iπkt RT
On remarque aussi que −T f˜(t)e T dt = 2 0 f (t)cos( πkt T )dt. Aussi,
RT P RT −iπkt iπkx iπkx
˜ 1 ˜ 1 ˜
f (x) =L2 2T −T f (t)dt + n∈IN∗ 2T ( −T f (t)e T )(e T + e T ), et donc
R
1 T P 2
RT
f (x) =L2 f (t)dt + I
N ( 0 f (t)cos( πkt πkx
T ))cos( T ). Comme les fonctions
q T 0 n∈ T
√1 , 2 πkx 2
T T cos( T ) forment un système orthonormé de L (0, T ), l’égalité précédente exprime
qu’elles forment en fait une base hilbertienne.

(iii) Si on prolonge la fonction f en une fonction impaire sur [−T, T ] et que l’on reprend
le raisonnement précédent, on trouve la base en sinus. Cette base a la propriété, utile pour
modéliser les cordes vibrantes, que ses éléments valent 0 aux extrémités de l’intervalle.
◦

Exercice 48 Détailler la preuve de (iii) en vous inspirant de la preuve de (ii).

Remarque: Le résultat ii), relatif à la transformée en cosinus, s’obtient en considérant

la série de Fourier du signal pair f˜ obtenu par symmétrie par rapport à l’axe des y. Ceci est
très important en pratique, car l’introduction de cette symmétrie, qui se généralise sans mal
au cas des images, permet d’éviter la présence de discontinuités aux frontières du domaine
du signal ou de l’image (supposés périodique dans le cadre de la décomposition en séries de
Fourier), qui sont à l’origine d’effets de Gibbs (voir le paragraphe 8.4). Ce type de transformée
en cosinus est souvent utilisé en compression des images (comme dans le standard JPEG).
Un autre avantage de cette décomposition, pour la compression, est présenté ci-dessous.

8.2 Bases de Fourier en dimension 2

Les énoncés qui suivent se généralisent sans changement de démonstration à la dimension
N . Nous traitons le cas N = 2 pour éviter des indices de sommation inutiles. On pose
x = (x1 , x2 ) ∈ R2 , k = (k1 , k2 ) ∈ R2 et on note k.x = k1 x1 + k2 x2 leur produit scalaire.

Lemme 8.2 fonction!à variables séparées Les fonctions à variables séparées, c’est-à-dire de
la forme w(x) = u(x1 )v(x2 ) avec u, v ∈ L2 (0, 2π) forment un système total de L2 ([0, 2π]2 ).

Démonstration Les fonctions caractéristiques de rectangles sont à variables séparées et

elles forment un système total de L2 ([0, 2π]2 ). ◦

Lemme 8.3 Si uk (x) → u(x) et vl (x) → v(x) dans L2 (0, 2π), alors uk (x1 )vl (x2 ) →
u(x1 )v(x2 ) dans L2 ([0, 2π]2 ) quand k, l → +∞.
56 CHAPTER 8. SÉRIES DE FOURIER (RÉVISION)

Démonstration On remarque que par le théorème de Fubini,

||u(x1 )v(x2 )||L2 ([0, 2π]2 ) = ||u(x1 )||L2 ([0, 2π]) ||v(x2 )||L2 ([0, 2π]) .

Donc, par l’inégalité triangulaire,

||uk (x1 )v l (x2 ) − u(x1 )v(x2 )||L2 ([0, 2π]2 ) ≤ ||(uk − u)v l ||L2 ([0, 2π]2 ) + ||u(v l − v)||L2 ([0, 2π]2 ) =

||uk − u||L2 ([0, 2π]) ||v l ||L2 ([0, 2π]) + ||u||L2 ([0, 2π]) ||v l − v||L2 ([0, 2π]) .
Les deux termes de droite tendent vers zéro quand k, l → +∞. ◦

1 ik.x
Théorème 8.3 série de Fourier!sur le carré Les fonctions ek (x) = 2π e , k ∈ Z2 , forment
une base hilbertienne de L ([0, 2π]) et on a donc pour toute fonction u ∈ L2 ([0, 2π]2 ),
2

X Z
1
u= ck (u)eik.x , avec ck (u) = 2
u(x)e−ik.x dx, (8.2)
2
(2π) [0,2π]2
k∈Z

la convergence de la série se vérifiant au sens de L2 .

Démonstration On vérifie facilement que ek est un système orthonormé. Pour montrer

qu’il est total, il suffit de montrer, par le lemme 8.2, que les ek engendrent les fonctions
séparables. Mais si w(x) = u(x1 )v(x2 ) ∈ L2 ([0, 2π])2 est une telle fonction, par une applica-
tion directe du théorème de Fubini, u(x1 ) et v(x2 ) sont dans L2 (0, 2π). Les fonctions u et v
sont donc sommes au sens L2 de leurs séries de Fourier :
X Z
ik1 x1 1
u(x1 ) = ck1 e , ck1 = u(x1 )e−ik1 x1 ;
2π [0,2π]
k1 ∈Z

X Z
ik2 x2 1
v(x2 ) = ck2 e , ck2 = v(x1 )e−ik2 x2 .
2π [0,2π]
k2 ∈Z

En appliquant le lemme 8.3, on obtient une série double convergente dans L2 ([0, 2π]2 ), ce qui
donne (8.2) dans le cas d’une fonction séparable w(x) = u(x1 )v(x2 ) avec ck (w) = ck1 (u)ck2 (v).
Il en résulte que le système (ek )k∈Z2 est une base hilbertienne de L2 ([0, 2π]2 ) et (8.2) est donc
valide. ◦

8.3 Décroissance des coefficients de Fourier et problèmes de

compression du signal
On s’intéresse au comportement des coefficients de Fourier quand la 2π-périodisée de f est
C 1 , C 2 , etc... Si f est C p et 2π-périodique, en intégrant par parties p fois sur [0, 2π],
Z Z
−inx 1
cn (f ) = e f (x)dx = e−inx f (p) (x)dx.
(in)p
8.4. PHÉNOMÈNE DE GIBBS 57

Donc, les coefficients décroissent d’autant plus vite que f est plus régulière.
Si maintenant f présente un saut en 0, on montre que si f est C 1 sur [0, 2π] mais pas
2π-périodique, alors cn (f ) = O( n1 ). Plus précisément, si nous notons f (0+ ) la valeur en 0 par
la droite et f (2π − ) la valeur en 2π par la gauche
Z
1 2π −inx 0 f (0+ ) − f (2π − )
cn (f ) = e f (x)dx + .
in 0 in
Or on montre
P (par le lemme de Riemann-Lebesgue) que le premier terme est o( n1 ). On
sait que n≥N n12 = O( n1 ), et la décroissance des coefficients de Fourier de la fonction est
donc très lente (1000 termes pour une précision de 10−3 ), dès que la fonction présente une
discontinuité.
En ce qui concerne les coefficients de Fourier ck,l d’une “image”, c’est-à-dire une fonction
f (x, y) définie sur un carré [0, 2π] × [0, 2π], C 1 , mais pas 2π × 2π-périodique, le résultat est
1
identique. On montre que cn,m = O( nm ) et le reste (pour la norme L2 ) de la série double est
1
donc en O( nm ). Donc, pour une précision de 10−3 , il faut encore 1000 termes.
Une bonne alternative lorsque la fonction présente Rune discontinuité du type précédent
2π
consiste à utiliser la tranformée en cosinus: cn (f ) = π1 0 cosnxf (x)dx. On a, en intégrant
par parties et en remarquant que sinnx s’annule en 0 et 2π,
Z 2π
1
cn (f ) = sinnxf 0 (x)dx.
iπn 0
Puis on montre que cn (f ) = o( n1 ) par le lemme de Riemann-Lebesgue. Les coefficients de
Fourier “en cosinus” décroissent donc plus vite qu’avec la transformée de Fourier classique
et on peut donc en transmettre moins pour une qualité d’image égale. Pour transmettre une
image, on la découpe en petits carrés et on transmet une partie des coefficients de Fourier de
chaque imagette (principe utilisée par le standard JPEG). On augmente ainsi la probabilité
qu’une imagette présente une couleur homogène et soit donc régulière. L’utilisation de la
tranformée en cosinus permet donc de comprimer l’information dans les sous-carrés de l’image
où celle-ci est régulière. Par contre, les calculs précédents prouvent qu’on ne gagne rien
quand un “bord” est présent dans l’imagette. En effet, (on pourra expliciter le calcul pour
une image blanche au dessus de la diagonale et noire en dessous), un calcul du même type
1
que ci-dessus implique que les coefficients décroissent en O( nm ). C’est ce qui explique les
phénomènes de “halo” autour des objets sur un fond contrasté : le petit nombre de coefficients
transmis ne suffit pas à approcher bien l’imagette. Nous verrons au chapitre 8.4 qu’il y a une
autre raison à ceci: le phénomène de Gibbs (voir la figure 8.2). Le long des discontinuités
de l’image, apparaissent toujours des oscillations résiduelles, quel que soit le nombre de
coefficients transmis.
En conclusion, la transformée en cosinus, s’affranchissant des discontinuités aux frontières
du domaine de l’image, présente un double avantage sur la transformée de Fourier. En termes
d’économie de la représentation, elle tire mieux partie de l’eventuelle régularité de la fonction
à l’intérieur de son domaine (régularité souvent élevée dans le cas d’imagettes). De plus, elle
évite l’apparition d’oscillations résiduelles le long de ces frontières.

8.4 Phénomène de Gibbs

phénomène de Gibbs La représentation d’un signal par sa série de Fourier conduit à l’apparition
d’oscillations résiduelles, dont l’amplitude ne dépend pas du nombre de coefficients utilisés
58 CHAPTER 8. SÉRIES DE FOURIER (RÉVISION)

pour représenter la fonction. Ce résultat mathématique sur l’approximation d’un signal

par les sommes partielles de sa série de Fourier porte le nom de phénomène de Gibbs. Ce
phénomène est observé à la sortie de tout système physique ou numérique mesurant ou calcu-
lant une fonction f . Si la fonction f (t) (t désignant par exemple le temps) “saute” brusque-
ment d’une valeur à une autre, alors l’expérimentateur observe une série d’oscillations avant
et après le saut. Il se gardera bien de les interpréter comme faisant partie du signal. En
effet, le phénomène est dû au fait que les appareils de mesure (et les programmes numériques
sur ordinateur) “tronquent” nécessairement les hautes fréquences. Cela veut aussi dire que
l’on n’observe jamais les fonctions elles mêmes, mais des sommes partielles de leur série de
Fourier. Et on observe donc aussi les “parasites” dûs à cette troncature en fréquence ; en
particulier, le phénomène de Gibbs. Du point de vue mathématique, on peut énoncer le
phénomène comme suit :
“ Si une fonction f , par ailleurs régu’lière, présente un saut en un point, alors les sommes
partielles sN f de sa série de Fourier accentuent ce saut en le multipliant par un facteur qui
ne dépend pas de N .”
On commence par donner le résultat précis dans un cas simple: on considère la fonction
“en dents de scie” s(x), 2π-périodique et telle que s(x) = π−x 2 sur [0, 2π[. Le calcul des
P
coefficients de Fourier de s et le corollaire 1 montrent que s(x)”=” ∞ sin(kx) au sens de
k=1 k
la convergence L2 , ainsi qu’en tout point de l’intervalle ouvert ]0, 2π[, d’après la proposition
P
8.1. On considère les sommes partielles de cette série de Fourier, sn (x) =: nk=1 sink(kx) .
Proposition 8.2 (Phénomène de Gibbs): phénomène de Gibbs
lim sup sn (x) = (1 + c)s(0+ ); lim inf sn (x) = (1 − c0 )s(0+ ). (8.3)
n→∞,x→0+ n→∞,x→0+

Démonstration On va étudier la suite sn ( πn ) quand n → ∞. On commence par étudier les

Ra
variations de G(a) =: 0 sint (t) dt pour en déduire que G(π) > G(+∞). La fonction G(a) est
croissante sur les intervalles pairs [2kπ, (2k + 1)π] et décroissante sur les intervalles impairs.
On voit aisément que |G((n + 1)π) − G(nπ)| est une suite décroissante. Il en résulte que la
suite G(2nπ) est une suite croissante strictement, la suite G((2n + 1)π) une suite strictement
décroissante, et les deux convergent vers une valeur commune notée G(+∞). On a donc
G(π) > G(+∞). On sait par ailleurs que G(+∞) = π2 . Revenons à la suite sn ( πn ). On a
Xn n Z π
π sin( kπ
n ) π X sin( kπn ) sinu
sn ( ) = = kπ
→n→+∞ du.
n k n n 0 u
k=1 k=1
La dernière limite vient du fait que l’on reconnaı̂t la somme de Riemann associée à
l’intégrale. Mais
π π
sn ( ) → G(π) > G(+∞) = = s(0+ ),
n 2
π
R +∞ sin u
car s(0+ ) = 2 = 0 u du. Donc pour tout n, il y a une valeur très proche de 0, en
l’occurrence πn , telle que la somme partielle de la série de Fourier dépasse d’un facteur con-
G(π)
stant G(+∞) la valeur de la limite s(0+ ). Pour raisons de symétrie, la même chose se produit
en 0− avec la suite sn (− πn ). Nous avons donc montré l’existence des lim sup et lim inf de
l’équation (8.3). ◦
8.4. PHÉNOMÈNE DE GIBBS 59

Exercice 49 On peut préciser un peu plus le résultat précédent en donnant le comportement

asymptotique de sn (x) au voisinage de 0, ce qui permet de tracer les oscillations de sn au
voisinage de la discontinuité. Montrer que pour |x| ≤ 1 et uniformément en x,
Z x
sin(nt) x 1
sn (x) = dt − + O(x, ).
0 t 2 n

Numériquement, les constantes positives c et c0 sont de l’ordre de 0, 18. Plus précisément,

la somme partielle sn de la série de Fourier de f présente des oscillations, maximales aux points
kπ
n . Les oscillations de cette approximation ont donc une fréquence de plus en plus élevée
avec l’ordre d’approximation n, mais l’erreur reste proportionnelle au saut de la fonction f .
Ce résultat se généralise au cas d’une fonction C 1 sur [0, 2π], mais pas 2π périodique. Pour
ce faire, on soustrait à la fonction f une fonction en “dents de scie” λs + µ = s̃, où λ et µ
ont été choisis de manière à la rendre Lipschitzienne et on applique à la différence f − s̃ le
principe de localisation. Il y a donc convergence uniforme de la série de Fourier de f − s̃ vers
f − s̃, alors que la série de Fourier de s̃ présente le phénomène de Gibbs. Le développement
de Fourier de f présente donc aussi le phénomène de Gibbs.
Nous illustrons, à la figure 8.1, le phénomène dans le cas de la fonction 2π-périodique,
impaire, et valant 1 sur l’intervalle ]0, π]. Nous montrons les sommes partielles de sa série de
Fourier. Remarquons en particulier le fait que l’erreur maximum ne varie pas avec le nombre
de coefficients de l’approximation. En revanche, la fréquence de ces oscillations augmente avec
l’ordre d’approximation. Nous présentons ensuite une illustration du phénomène de Gibbs
dans le cas des images numériques: partant d’une image, nous calculons sa série de Fourier (en
fait une approximation finie de cette série présentée au paragraphe suivant: la transformée
de Fourier discrète), mettons les hautes fréquences à zéro, puis calculons l’image dont la série
de Fourier est celle ainsi obtenue (anticipant sur les définitions et notations du paragraphe
suivant sur la transformée de Fourier discrète, nous multiplions l’image ũmn par la fonction
indicatrice d’un carré centré sur ũ0,0 , puis appliquons la TFD inverse). Nous montrons le
résultat figure 8.2, où l’image originale est placée à gauche. Le résultat, image obtenue après
troncature des hautes fréquences, à droite, présente de très nombreuses oscillations.
Ce phénomène apparaı̂t également lorsque le spectre est utilisé à des fins de manipulation
d’image, comme nous le verrons au chapitre suivant.
60 CHAPTER 8. SÉRIES DE FOURIER (RÉVISION)

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
0 20 40 60 80 100 120 140 160

0.8

0.6

0.4

0.2

0
0 20

50 15

100 10

150 5

200 0

Figure 8.1: Sommes partielles de la série de Fourier de la fonction 2π-périodique, impaire,

valant 1 sur ]0, π]. Haut: les approximations sont représentées sur le même graphe, sur
l’intervalle ]0, π]. Bas: les différentes approximations sont traçées selon un troisième axe
(nombre de termes entre 1 et 20). On remarque que l’erreur maximale d’approximation ne
varie pas avec le nombre de termes, tandis que la fréquence des oscillations augmente.
8.4. PHÉNOMÈNE DE GIBBS 61

Figure 8.2: Illustration de l’effet de Gibbs. Gauche: l’image originale; droite: l’image après
que l’on ait tronqué ses hautes fréquences, et sur laquelle sont visibles de nombreuses oscilla-
tions. L’image de droite est obtenue en ne conservant que les fréquences dont le module est
inférieur au quart de la fréquence maximale. Le phénomène est particulièrement visible le
long des frontières du domaine de l’image (voir en particulier le côté droit) et le long des dis-
continuités de l’image. Remarquons que l’image est également devenue floue par suppression
des hautes fréquences.
62 CHAPTER 8. SÉRIES DE FOURIER (RÉVISION)
Chapter 9

Le cas discret (Révision)

9.1 Transformée de Fourier Discrète, applications

9.1.1 La dimension 1
La transformée de Fourier discrète est un moyen de calculer les coefficients de Fourier d’un
fonction a-périodique u, directement à partir de ses N échantillons u( ka
N ), k = 0, ...N−1. Cela
n’est possible exactement que si la fonction présente un nombre de fréquences inférieur à N .
Pour des raisons de simplicité des notations, nous supposerons dans ce paragraphe que N
est pair. Tous les résultats énoncés (sauf ceux du paragraphe 9.1.4 relatifs à la transformée
de Fourier rapide) s’adaptent sans difficulté au cas N impair. En pratique, N est en fait
toujours une puissance de 2.
Soit u(x) une fonction réelle ou complexe de période a, et N un entier pair. On cherche
un polynôme trigonométrique de la forme
N
−1
X
2 µ ¶
2iπnx
P (x) = ũn exp , (9.1)
a
n=− N
2

qui soit égal à u aux points ka

N pour k = 0, ..., N −1. On dira dans la suite que P est de degré
N ka
2 . Le but est donc d’interpoler les échantillons u( N ) = uk .

Pourquoi choisir un polynôme trigonométrique ? La raison est physique : tous les dispositifs d’acquisition
de signaux (sons) ou images ont une bande passante, c’est-à-dire un intervalle de fréquences captées
par le dispositif d’enregistrement ; les autres fréquences sont perdues ou tellement atténuées qu’on
les néglige : on suppose donc que la ”bande passante” est [− N2 , N2 − 1]. Il n’y a par contre aucune
raison de supposer que le signal ou image soit périodique et d’une période qui coı̈ncide avec la fenêtre
d’observation [0, a] comme c’est le cas pour P . Cette hypothèse est donc imposée à la donnée et
provoque une distorsion qu’on a évaluée : le phénomène de Gibbs. Si en fait la fonction u dont
on possède les N échantillons n’a pas une bande de fréquence dans − N2 , N2 − 1, son interpolation
par un polynôme trigonométrique de degré N2 provoque une autre distorsion que nous allons évaluer
précisément : l’aliasage.
On va commencer par calculer les coefficients de P .
¡ 2iπ ¢ PN−1 k
Exercice 50 On pose ωN = exp N , racine N -ième de l’unité. Montrer que k=0 ωN = 0,

63
64 CHAPTER 9. LE CAS DISCRET (RÉVISION)

PN−1 kl = 0 pour l 6= 0 et finalement que pour tout k ,

Pk0 +N−1 kl = 0 pour tout
puis que k=0 ωN 0 k=k0 ωN
l 6= 0.

Définition 9.1 transformée de Fourier!discrète On pose uk = u( ka N N

N ) et, pour n = − 2 , ... 2 −
1,
N−1
1 X −nl
ũn = ul ωN . (9.2)
N
l=0

Les N coefficients ũn sont appelés transformée de Fourier discrète (TFD) des N échantillons
uk . On appelle transformée de Fourier discrète inverse l’application de C | N dans lui même

définie par
N
−1
2X
kn
uk = ũn ωN , k = 0, ..., N −1. (9.3)
n=− N
2

Proposition 9.1 transformée de Fourier!discrète Les coefficients (ũn ) définis

¡ kapar
¢ (9.2) sont
les uniques coefficients tels que le polynôme trigonométrique (9.1) vérifie P N = uk , pour
tout k = 0, ..., N −1. En d’autres termes, la transformée de Fourier discrète composée avec
son inverse donne bien l’identité.

Démonstration Pour k = 0, ..., N −1,

N
−1
ka 2X
nk
P( ) = ũn ωN
N
n=− N
2
N
−1 N−1
1 X
2 X
−nl nk
= ( ul ωN )ωN
N N
n=− l=0
2
N
N−1 −1
1 X X
2
nk−nl
= ul ( ωN )
N
l=0 N
n=− 2
N−1
X
1
= N δ(k − l)ul = uk ,
N
l=0

où on a noté δ la fonction définie sur les entiers, valant 1 en 0, et 0 ailleurs. L’unicité provient
du fait que toute application linéaire surjective de CN dans lui-même est aussi injective. ¤

P N2 −1 ¡ 2iπnx ¢
Corollary 4 polynôme trigonométrique Si u est un polynôme trigonométrique u(x) = n=− N
ũn exp a ,
2
les coefficients ũn sont obtenus par la formule (9.2). Ce sont les coefficients de Fourier de u.

Exercice 51√On note u un vecteur de C | N et T F D(u) = ũ sa transformée de Fourier discrète.

Vérifier que N T F D est unitaire et que l’on a T F D−1 = N.T F D.

9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 65
PSfrag replacements b

u
uk echantillonage
TFD

ûk
TFD
Série de Fourier a c

échantillonnage Serie de Fourier

Figure 9.1: La TFD après échantillonage calcule bien les coefficients de Fourier si la fonction
u est un polynôme trigonométrique (corollaire 4)

On rappelle d’autre part que si u ∈ L2 (0, a), les coefficients de la série de Fourier de u
sont définis, pour n ∈ Z, par
Z µ ¶
1 a −2iπnx
cn (u) = u(x) exp . (9.4)
a 0 a

Les coefficients ũn de la transformée de Fourier discrète sont approchés par les termes de
la TFD de (uk ) au sens suivant:

Proposition 9.2 Soit u continue et a-périodique. Alors les ũn sont des approximations des
cn (u) par la formule des trapèzes, pour n = −N N
2 , ..., 2 − 1.

Démonstration Il suffit d’écrire l’approximation de l’intégrale (9.4) par la méthode des

trapèzes en tenant compte du fait que u(a) = u(0) pour une fonction a-périodique. ¤

Proposition 9.3 On suppose que les échantillons uk sont réels. Alors ũ0 et ũ− N sont réels,
2
et pour k = 1... N2 − 1, ũk = ũ−k .

1 P 1 P
Démonstration ũ0 = N k uk , et ũ− N = N (−1)k uk ; ces deux coefficients sont donc
2
réels. D’autre part
N−1 N−1
1 X kn 1 X −nk
ũ−n = uk ωN = uk ωN = ũn .
N N
k=0 k=0

¤
Remarquons le rôle particulier joué par le terme ũ− N , qui n’a pas de terme conjugué lui
2
correspondant.

Proposition 9.4 si u est un polynôme trigonométrique réel dont les fréquences sont parmi
− N2 , ..., N2 − 1, le terme ũ− N est nul.
2

Démonstration En effet, en regroupant les termes conjugués, on a, pour le polynôme

trigonométrique P dont les coefficients sont les ũn :
N
−1
X 2
2inπx −2inπx −iN πx
P (x) = ũ0 + (ũn e a + ũ−n e a ) + ũ− N e a .
2
n=1
66 CHAPTER 9. LE CAS DISCRET (RÉVISION)

0.5

−0.5

−1
0 2000 4000 6000 8000 10000 12000

300

250

200

150

100

50

0
−6000 −4000 −2000 0 2000 4000 6000

Figure 9.2: Haut: un signal correspondant à la voyelle ”Ah” (le signal représente la pres-
sion de l’air en fonction du temps); bas: module de la TFD (coefficients |ũ|, voir le texte).
On remarque que le module du spectre est symétrique, et qu’il existe trois pics importants
correspondant aux fréquences dominantes.

Tous les termes de la somme sont réels sauf le dernier, qui ne l’est que si ũ− N = 0. ◦
2

La Figure 9.2 montre un exemple de signal (représentant le son A) et le module de sa TFD.

9.1.2 La dimension 2
On considère un réel a, une fonction u de R2 dans ¡ kaR, latelle
¢ que u(x + a, y + a) = u(x, y). On
fixe à nouveau un entier N , et l’on pose uk,l = u N , N . On définit la TFD des uk,l comme
la suite des coefficients, pour m, n ∈ {− N2 , ..., N2 − 1},
N−1 N−1
1 XX −mk −nl
ũm,n = uk,l ωN ωN . (9.5)
N2
k=0 l=0

Exercice 52 Montrer que la transformation ainsi définie est séparable, et que le passage des
uk,l aux ũm,n s’effectue par deux TFDs à une dimension successives.

De même qu’en dimension 1, nous avons la propriété d’interpolation suivante:

Proposition 9.5 Soient les coefficients ũm,n définis, pour m, n = − N2 , ..., N

2 − 1, par (9.5).
Considérons le polynôme trigonométrique
N
−1
X
2
2iπmx 2iπny
P (x, y) = ũm,n exp( ) exp( ).
a a
m,n=− N
2
9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 67

Les¡ coefficients
¢ ¡ũkam,nlasont
¢ les seuls nombres complexes tels que, pour tout k, l ∈ {0, ..., N −1},
ka la
P N , N = u N , N . Par conséquent, la transformée discrète inverse de uk,l → ũm,n est
donnée par le calcul du polynôme aux échantillons ( ka la
N , N ), 0 ≤ k, l ≤ N −1 :

N N
−1 2 −1
ka la X
2 X
km+ln
u(k, l) = P ( , ) = ũm,n ωN .
N N N N
− 2
− 2

Exercice 53 Montrer la proposition précédente. Le calcul est exactement le même qu’en

dimension 1. De même qu’en dimension 1, nous pouvons identifier un certain nombre de
symétries des ũm,n si l’image est à valeurs réelles. On suppose à nouveau que N est pair.
Montrer également la proposition suivante.

Proposition 9.6 Supposons que les échantillons uk,l soient réels. Alors les coefficients ũ0,0 ,
ũ0,− N , ũ− N ,0 , et ũ− N ,− N sont réels; de plus
2 2 2 2

N N
∀m, n ∈ {− + 1, ... − 1} ũm,n = ũ−m,−n
2 2
Exercice 54 A nouveau, comme en dimension 1, les coefficients (ũm,n ) correspondent aux
fréquences de l’image u, ordonnées des négatives aux positives. Plus précisément, si u ∈ L1
et que l’on définit les coefficients de la série de Fourier de u par
Z µ ¶ µ ¶
1 −2iπmx −2iπny
cm,n = 2 u(x, y) exp exp ,
4π [0, 2π]2 a a

alors, pour m, n = − N2 , ..., N

2 − 1 les ũm,n sont des approximations des cm,n par la méthode
des trapèzes.

La figure 9.3 présente une image et le logarithme du module de sa transformée de Fourier

discrète (le logarithme est utilisé car le module des TFD des images usuelles décroit très vite
lorsque l’on s’éloigne des basses fréquences).

9.1.3 Le phénomène du repliement de spectre ou aliasage

repliement de spectre
Le but de ce paragraphe est de calculer les perturbations auxquelles est exposée la trans-
formée de Fourier discrète d’un signal lorsque celui-ci est sous-échantillonné. On vient de
voir que la transformée de Fourier discrète calculait exactement les coefficients de Fourier
P N2 −1 ¡ 2iπnx ¢
d’un polynôme trigonométrique de degré N2 , P (x) = n=− N ũn exp a , dont on con-
2
naissait N échantillons u( kaN ), N = 0, ..., N −1. Dans cette section, on considère une fonction
u ∈ L2 (0, a) et sa série de Fourier
X 2inπx
u(x) = cn (u)e a .
n∈Z
P
Dans toute la suite, on supposera que n∈Z |cn (u)| < +∞, ce qui implique que u est continue
et a-périodique. Cette hypothèse n’est pas irréaliste. En effet, étant donné un signal v
68 CHAPTER 9. LE CAS DISCRET (RÉVISION)

Figure 9.3: Gauche: une image numérique de taille 256 × 256; droite: le logarithme du
module de sa TFD. Le spectre décroı̂t rapidement aux hautes fréquences (rappelons que
l’image étant bornée, son spectre est dans L2 ). En pratique, la grande vitesse de décroissance
du spectre rend nécessaire l’utilisation du logarithme pour la visualisation. La symétrie
centrale du module de la TFD est visible. Les lignes horizontales et verticales correspondent
aux bords verticaux et horizontaux respectivement. Remarquer également les lignes obliques
qui correspondent aux bords obliques de l’image (voir en particulier les dalles sur le sol). Les
droites horizontales et verticales sont également dues aux fortes discontinuités présentes aux
frontières du domaine de l’image (rappelons que celle-ci est périodisée pour le calcul de son
spectre).
9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 69

régulier (C 2 par exemple) sur [0, a/2], on peut le rendre pair en posant u(−x) = ṽ(x) pour
x ∈ [−a/2, 0], u(x) = v(x) sur [0, a]. On voit que la a-périodisée de cette extension u reste
Lipschitz et C 2 par morceaux et on peut en déduire (exercice !) que la série des coefficients
de Fourier de u est convergente. On suppose également, ce qui est réaliste, qu’un signal u
n’est en fin de compte connu que par ses échantillons sur [0, a], u(0), ..., u( N−1
N a).
P
Théorème 9.1 Soit u définie sur [0, a], vérifiant n |cn (u)| < +∞. Shannon !théorème
discret de Alors la transformée de Fourier discrète de u est la N -périodisée de la suite des
coefficients de Fourier de u :
+∞
X N N
ũn = cn+qN (u), n = − , ..., − 1. (9.6)
q=−∞
2 2

2iπ
Démonstration On rappelle la notation ωN = e N et (ωN )N = 1. Comme
X 2imπx
u(x) = cm (u)e a ,
m∈Z

on a
ka X
mk
u( )= cm (u)ωN .
N
m∈Z

On pose pour m ∈ Z, m = qN + n, − N2 ≤ n ≤ N
2 − 1. En regroupant les termes de la série
de Fourier on obtient
−1N Ã +∞
!
ka X
2 X
nk
u( ) = cn+qN (u) ωN , k = 0, ..., N −1.
N N q=−∞
n=− 2

Mais on a aussi (formule d’inversion de la transformée de Fourier discrète):

N
−1
ka X
2
nk
u( ) = ũn ωN , k = 0, ..., N −1.
N N
n=− 2

Ces deux dernières formules définissent toutes deux la transformée de Fourier discrète et par
identification on obtient la formule de ”repliement de spectre” (9.6).
◦

Ce théorème va nous permettre d’interpréter les effets de moiré visibles dans beaucoup
d’images digitales ou de films digitalisés (DVD). Ces effets de moiré sont dûs à un ”repliement
de spectre”, ou ”aliasage”. Le repliement de spectre provient d’un sous-échantillonnage
abusif. Le terme aliasage se réfère à la présence des coefficients parasites cn+qN , pour q 6= 0
dans le calcul du coefficient de la fréquence n, ũn . Quand la transformée de Fourier discrète
fait correctement son travail, qui est de retrouver le coefficient cn de la fréquence n de u,
on doit avoir ũn = cn . Les coefficients cn+qN qui s’y ajoutent dans (9.6) sont des répliques,
ou ”alias” de coefficients correspondant aux fréquences plus grandes n + qN , q 6= 0. D’où le
terme d’aliasage.
70 CHAPTER 9. LE CAS DISCRET (RÉVISION)

Définition 9.2 sous-échantillonnage d’un signal Soit un signal échantillonné (uk ), k =

0, ..., N − 1, et soit p un entier divisant N . On définit l’opérateur “sous-échantillonnage
d’ordre p” comme suit:
Sp : RN −→ RN/p

(uk )k=0, ..., N−1 −→ (vk ) = (ukp )k=0,...,N/p .

Le signal (vk ) est dit sous-échantillonné d’un facteur p.

Nous commençons par le cas, technologiquement classique, où p = 2.

Corollary 5 Soit (vk ) = S2 ((uk )) (on suppose que N2 est pair). Alors (ṽn ), la transformée
de Fourier Discrète de (vk ), s’écrit, pour n = − N4 , ..., N4 − 1,

ṽn = ũn + ũn− N + ũn+ N , (9.7)

2 2

le deuxième terme étant par ailleurs nul si n < 0 et le troisième étant nul si n ≥ 0.

Démonstration Appliquons le théorème 9.1 à l’unique polynôme trigonométrique P à N

coefficients qui a pour échantillons les uk . Alors par définition de la transformée de Fourier
discrète, ũn = cn (P ). On a donc pour N4 ≤ n ≤ N4 − 1,
X
ṽn = cn+q N (P ) = ũn + ũn− N + ũn+ N .
2 2 2
q∈Z

Remarquons que si n ≥ 0 cela donne ṽn = ũn + ũn− N , l’autre coefficient étant nul. De même,
2
si n < 0, on obtient ṽn = ũn + ũn+ N .
2
◦

Cette proposition indique que le spectre du signal sous-échantillonné d’un facteur deux
s’obtient en superposant à lui-même le spectre du signal original avec un décalage de N2 .
On dit qu’il y a repliement de spectre. Ainsi, le spectre du signal sous-échantillonné con-
tient généralement des informations non présentes dans le spectre du signal de départ, ce qui
se traduit sur le signal sous-échantillonné par l’apparition de structures périodiques n’ayant
pas de lien direct avec le contenu du signal. Ceci est particulièrement frappant dans le cas
des signaux bi-dimensionnels, pour lesquels on a un résultat identique à celui de la proposi-
tion 5. Nous montrons deux exemples d’images sous-échantillonnées aux figures 9.1.3 (image
synthétique) et 9.1.3, exemple où l’apparition de structures périodiques est dûe à la super-
position, lors du sous-échantillonnage, des hautes fréquences de l’image. La manipulation
numérique à faire pour créer des effets de moiré dans une image est aussi simple que son in-
terprétation est subtile : il suffit de prendre ”un point sur deux” de l’image. L’interprétation
de l’opération se fait en Fourier : on a créé de basses fréquences parasites en cn qui corre-
spondent au ”repliement” de hautes fréquences cn+ N . D’où l’apparition de sinusoı̈des qui
2
n’ont rien à voir avec le signal original et qui créent des effets de moiré.
Le résultat de la proposition 5 se généralise dans le cas d’un sous-échantillonnage d’ordre
plus élevé, comme le montre la proposition suivante:
9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 71

Figure 9.4: Exemple de repliement avec une image synthétique. En haut à gauche: image
originale, à droite son spectre. En bas à gauche: l’image sous-échantillonnée d’un facteur
deux dans chaque direction, à droite le spectre correspondant. Le spectre de l’image sous-
échantillonnée est obtenu en périodisant le spectre de l’image originale avec pour période le
carré visible en surimpression.

Proposition 9.7 Soit (vk ) = Sp ((uk )) (on suppose que N = pM , pour un certain entier
M ). Alors (ṽk ), la transformée de Fourier discrète de (vk ), s’écrit, pour k = 1...M − 1,
p−1
X
ṽk = ũk+ aN . (9.8)
p
a=−p+1

Démonstration Appliquer de nouveau le théorème 9.1 à l’unique polynôme trigonométrique

à N coefficients qui a pour échantillons les uk . Ce polynôme vérifie cn (P ) = ũn . ◦

On peut comparer les propositions 5 et 9.7 au théorème 9.1. Le théorème 9.1 nous
donne notamment les conditions générales de Shannon et Whittaker pour qu’un signal soit
correctement échantillonné : ces conditions sont que le spectre soit borné (nombre fini N de
coefficients de Fourier) et que l’on dispose d’au moins N échantillons. Les propositions 5 et 9.7
sont plus pratiques : elles ne donnent aucune hypothèse sur le signal qui a été échantillonné
et ont l’avantage de s’appliquer à un signal discret, quelconque, qu’il soit ou non issu d’un
bon échantillonnage.

9.1.4 La transformée de Fourier rapide

transformée de Fourier!rapide
Comme nous l’avons vu plus haut, le calcul des coefficients de Fourier ũn revient à
l’évaluation d’un certain polynôme aux racines N -ièmes de l’unité. Dans le cas général,
l’évaluation classique (ex. méthode de Hörner) d’un polynôme de degré N −1 en un point
prend O(N ) opérations. Donc si l’on répète cela pour les N racines de l’unité on devra ef-
fectuer O(N 2 ) opérations. L’algorithme de la Transformée de Fourier Rapide (TFR) permet
72 CHAPTER 9. LE CAS DISCRET (RÉVISION)

(a) Image originale (b) Sa TFD, non nulle en dehors du

carré visible en surimpression

(c) Image sous-échantillonnée d’un (d) La TFD correspondante, sur

facteur 2 laquelle il y a repliement

Figure 9.5: Sous-échantillonnage et repliement: le cas d’une image mal échantillonnée. Pour
les images (a), (b), (c), (d), le principe est le même que dans la figure 9.1.3, mais le détail de
la transformation du spectre est plus difficile à suivre ! les effets du repliement (aliasing en
anglais) sont particulièrement visibles sur les yeux de la mouche, image (c), qui présentent
des oscillations à basse fréquence. Les structures quasi-périodiques de l’image originale sont
visibles sous formes de taches et de filaments sur le spectre (b). Le repliement est dû à la
présence de ces structures aux hautes fréquences: la TFD de l’image originale n’est pas nulle
en dehors du carré visible en surimpression figure (b). Ce type d’effet de moiré est visible
dans de nombreux DVD commerciaux.
9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 73

(a) Image obtenue par TFD inverse (b) Image obtenue en mettant à zéro
de b les hautes fréquences de 9.1.3-a

(c) Sous-échantillonnage: le (d) TFD de c

repliement a disparu

Figure 9.6: Une solution possible pour éviter les effets de repliement illustrés sur la figure
9.1.3. L’image (a) est l’image dont le spectre est le même que celui de l’image 9.1.3-(a)
à l’intérieur du carré, et est nul à l’extérieur (filtrage passe-bas). L’image (c) est l’image
sous-échantillonnée correspondante. On observe que l’effet de repliement a disparu.
74 CHAPTER 9. LE CAS DISCRET (RÉVISION)

de résoudre le problème en O(N log N ) opérations. Appelons “calcul d’ordre N ” l’évaluation

d’un polynôme de degré N − 1 aux racines N -ièmes de l’unité. Et soit T (N ) le nombre
d’opérations (additions et multiplications) demandées par ce calcul.
On se place dans le cas N = 2n et soit un polynôme
N−1
X
P (X) = ak X k .
k=0
On pose
N
−1
2 X
Q(X) = a2k X k ,
k=0
N
−1
X
2

R(X) = a2k+1 X k .
k=0
Alors µ³ ´2 ¶ µ³ ´ ¶
2
k k k k
P (ωN ) =Q ωN + ωN R ωN . (9.9)
¡ k ¢2
Or, si N est pair les ωN sont exactement les racines d’ordre N2 de l’unité. Il suffit donc
d’évaluer les deux polynômes Q et R aux racines d’ordre N2 de l’unité ce qui est un problème
d’ordre N2 . On a donc, en tenant compte des additions et multiplications demandées par
(9.9), µ ¶
N
T (N ) = 2T + 2N.
2
On en tire aisément T (N ) = O(N log(N )).
Remarque 9.1 Les programmes usuels de calcul numérique ne calculent pas les coefficients
ũn , mais les coefficients ûn , définis par la formule suivante, pour n = 0, ..., N −1:
½
ũn si n = 0... N2 − 1
ûn = . (9.10)
ũn−N si n = N2 , ..., N

9.1.5 L’utilisation de la transformée de Fourier discrète pour définir zoom,

translations et rotations des images
Le zoom Nous présentons une méthode d’interpolation reposant sur une extension de
la TFD d’un signal ou d’une image. Nous détaillons la méthode, dite du “prolongement
par des 0” (“0-padding”), en une dimension, le principe se généralisant sans mal pour une
image. Comme précédement, considèrons des échantillons uk , k variant de 1 à N − 1, et
P N2 −1 −kn
ũn = N1 n=− N un ωN . On suppose que N est pair et que l’on veut zoomer d’un facteur
2
2, c’est à dire que l’on veut construire un signal de taille deux fois plus grande que le signal
de départ. On définit un nouveau signal v, de taille 2N comme étant la TFD inverse de ṽ,
donné par

N N N N
ṽn = ũn si − ≤n≤ − 1, ṽn = 0 si n ∈ [−N, − − 1] ∪ [ , N − 1]. (9.11)
2 2 2 2
Proposition 9.8 zoom discret par Fourier Le signal v dont la TFD est donnée par la formule
(9.11) vérifie v2k = uk , pour k = 0, ..., N −1.
9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 75

Démonstration On a
N
N−1 −1
X X
2
2nk nk
v2k = ṽn ω2N = ũn ωN = uk .
−N −N
2

2nk = ω nk .
En effet, ω2N ¤
N

Remarque 9.2 Ce résultat est évident sans démonstration : en effet, on peut considérer
l’unique polynôme trigonométrique de degré N2 passant par les échantillons uk . Les échantillons
vk s’interprètent immédiatement comme des échantillons de ce même polynôme.

Remarque 9.3 On remarquera que les signaux obtenus par cette méthode peuvent être com-
plexes, même lorsque le signal original est réel (ceci étant dû au terme d’aliasage u− N ).
2

La méthode se généralise aux cas des images. Nous considérons une image numérique
(uk,l ), et nous définissons une image zoomée (vi,j )i,j=0, ..., 2N−1 comme étant la transformée
de Fourier discrète inverse de ṽi,j définie pour i, j = −N, ..., N −1 par

N N
ṽm,n = ũm,n si − ≤ m, n ≤ − 1, ṽm,n = 0 sinon. (9.12)
2 2
La figure 9.7 montre la partie réelle d’une partie de l’image 9.3 zoomée par TFD, ainsi que
par réplication des pixels (chaque pixel est remplacé par quatre pixels de la même valeur). On
remarque que le zoom par TFD produit une image bien plus régulière, et évite l’effet “marche
d’escalier” visible sur l’image zoomée par réplication. La figure 9.8 illustre ce point sur un
détail. Une autre remarque concerne l’effet de Gibbs (cf. paragraphe 8.4). Ce phénomène
produit des rebonds le long de la frontière du domaine de l’image. En effet, et comme nous
l’avons déjà mentionné, le calcul des coefficients de Fourier de l’image (dont les coefficients
de la TFD sont une approximation) suppose l’image périodique, ce qui fait apparaı̂tre des
discontinuités le long des frontières de son domaine de définition. Le phénomène de Gibbs
est également visible le long des discontinuités dans l’image, les contours. Le phénomène
est mis en évidence sur la figure 9.7. Expliquons pourquoi le phénomène apparaı̂t dans le
cas du zoom: une nouvelle image vk,l de taille 2N × 2N est obtenue en utilisant les valeurs
prises par le polynôme P (x) entre les points dont on dispose au départ. Cette utilisation
de P fait apparaı̂tre les oscillations qui étaient invisibles dans le cas de l’image de départ
puisqu’il y avait interpolation des (uk ). Comme nous l’avons déjà évoqué, les oscillations aux
frontières du domaine de l’image peuvent être supprimées par utilisation de la transformée en
cosinus. En revanche, le problème subsistera le long des discontinuités présentes à l’intérieur
de l’image.

La translation La méthode présentée au paragraphe précédent permet de définir une trans-

lation d’une quantité 1/2 (ou a/(2N ) pour revenir à notre définition première du signal u),
en ne gardant que les points d’indice impair du signal zoomé v. Plus généralement, nous
pouvons définir une translation d’un signal d’une quantité 0 < α < 1. Comme d’habitude,
l’opération de translation sur la fonction u dont nous connaissons les échantillons uk se
fait sous l’hypothèse que celle-ci est un polynôme trigonométrique. En d’autres termes, on
 76 CHAPTER 9. LE CAS DISCRET (RÉVISION)

PSfrag replacements
a
b

PSfrag replacements
a
b

Figure 9.7: Zoom sur une partie de l’image 9.3. Haut: zoom par TFD, bas: zoom par
réplication des pixels. Le zoom par TFD est obtenu en prolongeant par des zéros le spectre de
l’image initiale. Celui par réplication des pixels en remplaçant chaque pixel par quatre pixels
de la même valeur. Remarquons tout d’abord la plus grande régularité du zoom par TFD,
qui supprime les effets de “blocs” très visibles sur le zoom par réplication. En contrepartie,
le phénomène de Gibbs (voir paragraphe 8.4) est très visible sur le zoom par TFD, puisque
l’on a mis à zéro brutalement des coefficients de la TFD. Ce phénomène est particulièrement
visible le long des frontières de l’image, qui correspondent à des discontinuités puisque l’image
est périodisée (par exemple zone a), et des contours des objets (par exemple zone b).
9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 77

Figure 9.8: détails après zoom, à gauche par TFD, à droite par réplication des pixels.

translate le polynôme d’interpolation, la ”vraie” fonction u étant inconnue en dehors des

échantillons. Le polynôme d’interpolation est
N
−1
X
2
2iπnx
P (x) = ũn e a .
−N
2

En translatant de α, on obtient
N
−1
X
2
2iπnα 2iπnx
τα P (x) = P (x − α) = ũn e− a e a .
−N
2

On a donc :

Proposition 9.9 translatée!discrète par Fourier La TFD (ṽn ) de P (x − α) s’obtient à partir

de la TFD de P (x), ũn , par
2iπnα
ṽn = ũn e− a .

Cette méthode de translation se généralise sans mal au cas des images, en remarquant
qu’une translation à deux dimensions peut se décomposer en deux translations, une selon les
lignes et une selon les colonnes.

La rotation Décrivons maintenant une méthode pour implémenter une rotation discrète,
due à L. Yaroslavsky. En bref, cette méthode réduit une rotation à des translations en ligne
ou en colonne de l’image. Commençons par remarquer que
µ ¶ µ ¶µ ¶µ ¶
cos(θ) sin(θ) 1 tan( θ2 ) 1 0 1 tan( θ2 )
R(−θ) := = := T (θ)S(θ)T (θ)
−sin(θ) cos(θ) 0 1 −sin(θ) 1 0 1
(9.13)
78 CHAPTER 9. LE CAS DISCRET (RÉVISION)

Figure 9.9: Rotation de π/4 par TFD. La rotation est implémentée en remarquant qu’elle
peut se décomposer en trois transformations consistant en des translations selon les lignes ou
les colonnes de l’image (formule 9.13). Chacune de ces transformations est ensuite effectuée
grâce à une TFD sur la ligne ou colonne considérée, en utilisant la méthode présentée au
paragraphe précédent.

(sauf si θ = π auquel cas il suffit de retourner l’image).

Une rotation d’angle θ de l’image discrète u(i, j) consiste à calculer u(R(−θ)(i, j)) que
l’on notera (R(−θ)u)(i, j). Mais on a R(−θ)u = T (θ)S(θ)T (θ)u. Donc il suffit d’expliquer
comment calculer T (θ)u et S(θ)u. Or ces deux opérations ont la même structure, à savoir
une translation ligne par ligne ou une translation colonne par colonne. Traitons par exemple
le cas de T (θ). On a (T (θ)u)(i, j) = u(i + j tan( 2θ ), j). Donc partant de la matrice ui,j , on
translate sa première ligne de tan( 2θ ), la deuxième de 2 tan( 2θ ), etc.. Appliquer S(θ) revient
à faire une opération similaire sur les colonnes. Enfin on réapplique T (θ) et on fait donc à
nouveau une translation sur les lignes. Or comme on vient de le voir ces translations ligne à
ligne ou colonne à colonne se font en temps N log N en utilisant la TFD à une dimension.
La figure 9.9 montre une image après une rotation de π/4 par la méthode décrite ci-
dessus. Puis, pour illustrer la stabilité de la méthode, nous montrons figure 9.10 le résultat
de l’application successive de douze rotations de π/4, et, à titre de comparaison, le résultat
de ces douze rotations successives implémentés par interpolation bilinéaire (les valeurs aux
nouveaux points sont des combinaisons linéaires des quatre points à coordonnées entières les
plus proches). Cette figure illustre clairement la supériorité de la méthode par FFT dans le
cas de rotations multiples.

Remarque 9.4 Cette méthode présente un défaut. En effet, du fait que l’on manipule des
fonctions périodiques, une translation conduit à faire sortir une partie de l’image par un bord
pour la faire entrer par l’autre. Ce qui conduit à l’apparition, sur les bords de l’image d’un
certain nombre de détails qui sont en fait mal placés. On se débarrasse facilement de ce
9.1. TRANSFORMÉE DE FOURIER DISCRÈTE, APPLICATIONS 79

Figure 9.10: Bas: après douze rotations successives de π/4 par TFD; haut: même expérience
en utilisant une interpolation bilinéaire (la valeur en un nouveau point (x, y) est obtenue
par combinaisons linéaires des valeurs aux quatre points à coordonnées entières de l’image
originale les plus proches de (x, y)).
80 CHAPTER 9. LE CAS DISCRET (RÉVISION)

problème en insérant l’image dans un cadre deux fois plus grand. . .

Remarque 9.5 La méthode de rotation n’est pas parfaite. En effet, l’image u continue
associée à u(i, j) est dans l’interpolation shannonienne supposée implicitement N -périodique,
ce qui revient à dire qu’elle est de la forme (pour une image carrée)
N−1
X π
u(x, y) = ci,j e2i N (kx+ly) .
k,l=0

Mais, si on lui applique une ”translation” suivant l’axe des x de valeur λy, la formule devient
N−1
X π
u1 (x, y) = ci,j e2i N (kx+(l−λk)y) .
k,l=0

La fonction u1 n’est pas (pour λ ∈ / Z) N -périodique en y. Or, après la première translation

on ne dispose plus que des échantillons du signal u1 sur une grille carrée N × N . D’après la
théorie de Shannon un tel ensemble de données ne permet pas de capturer toute l’information
sur u1 (à la seconde étape on effectue des translations suivant y qui est justement l’axe qui
pose problème). On rencontre encore ce problème à la troisième translation. Le seul moyen
d’avoir une rotation exacte serait d’évaluer u aux points de l’image de [0, N −1] × [0, N −1]
par une rotation d’angle −θ, mais cette méthode est en N 4 ce qui la rend inopérante. . .

9.1.6 Importances relatives de la phase et du module de la TFD pour une

image
Nous nous intéressons à la pertinence visuelle des caractéristiques de la transformée de Fourier
discrète dans le cas des images, et plus particulièrement à la phase et au module de la TFD,
au moyen de deux exemples. Tout d’abord nous montrons, figure 9.11, deux images A et B,
ainsi que les images obtenues en échangeant les phases de leurs TFD. Nous remarquons grâce
à cette expérience qu’une part très importante de l’information géométrique d’une image
est contenue dans la phase de sa TFD. Rappelons que si l’on translate une fonction, les
coefficients de sa série de Fourier sont multipliés par des exponentielles complexes de module
1, et que par conséquent la phase de la TFD contient en en sens des informations sur le
placement des constituants de l’image.
Dans la figure 9.12, nous montrons deux images de textures, qui visuellement semblent
invariantes par translation, ainsi que les deux images obtenues à partir de ces textures en
ne conservant que le module de leur TFD, et en tirant au hasard les phases (selon une loi
uniforme). On voit cette fois que le module de la TFD contient l’information. Cette propriété
est caractéristique des textures homogènes du type présenté figure 9.12, et l’on peut même
donner une définition des “microtextures” comme images caractérisées uniquement par le
module de leur transformée de Fourier.

9.2 Lien avec la théorie de Shannon

Théorème 9.2 Shannon!théorème pour les polynômes trigonométriques (de Shannon pour
les polynômes trigonométriques) Soit un signal trigonométrique
N
X
f (t) = cn e2iπλn t .
n=−N
9.2. LIEN AVEC LA THÉORIE DE SHANNON 81

(a) Image A (b) Image A

(c) Module de la TF de A et phase de (d) Module de la TF de B et phase de

B A

Figure 9.11: Haut: les deux images de départ; bas: les deux images après échange des
phases de leurs TFD. L’information géométrique est contenue dans la phase ! Les formes
sont principalement codées dans l’argument des coefficients de Fourier de l’image. Bien que
les images (a) et (c) d’une part, et (b) et (d) d’autre part, aient des modules complétement
différents, on y distingue les mêmes formes géométriques. Remarquons également que les
directions horizontales et verticales très présentes sur l’image (a) apparaissent sous forme de
texture dans l’image (c). Cette remarque est précisée par l’expérience de la figure 9.12.
82 CHAPTER 9. LE CAS DISCRET (RÉVISION)

Figure 9.12: Haut: deux images de textures; bas: les deux images après remplacement des
phases de leurs TFD par des phases aléatoires. Une information essentielle sur la texture
est donc présente dans le module des coefficients de Fourier de l’image. Pour la texture de
gauche, il semble que la plupart de l’information soit contenue dans le module de la TFD.
A droite, quelques aspects de la texture sont perdus. Nous renvoyons le lecteur intéressé à
un article (en anglais) sur une méthode de synthèse de texture par modification de la phase:
[Van Wijk]
9.2. LIEN AVEC LA THÉORIE DE SHANNON 83

On a encore la formule de Shannon

¸ · +∞
X
1 sin π (t − na)
∀a ∈ 0, , ∀t ∈ R, f (t) = f (na) π a ,
2λc n=−∞ a (t − na)

avec λc = max {|λn |}. La convergence est ponctuelle.

Remarque 9.6 Ce théorème complète le théorème de Shannon pour un signal qui est ni
périodique ni dans L2 .

Démonstration
il suffit de démontrer le résultat dans le cas d’une seule onde. Soit donc

f (t) = e2iπλt , λ ∈ R.
1
¡ 1 1¢
Soit g périodique de période a et égale à f sur − 2a , 2a . les coefficients de Fourier de f sont

asin πa (λ − na)
cn = .
π(λ − na)

Donc
+∞
X sin π (λ − na)
g(t) = π
a
e2iπnat .
−∞ a (λ − na)
¤ 1 1
£ ¤ 1 1£
Comme f est C1 sur − 2a , 2a , Cette égalité est ponctuelle pour t ∈ − 2a , 2a (principe
de localisation). D’où
+∞
X sin πa (λ − na) 1
∀λ ∈ R, e2iπλt = e2iπnat π , |t| < .
n=−∞ a (λ − na) 2a

En intervertissant λ et t, on obtient
+∞
X sin πa (t − na) 1
∀t ∈ R, e2iπλt = e2iπnaλ π , |λ| < .
n=−∞ a (t − na) 2a
84 CHAPTER 9. LE CAS DISCRET (RÉVISION)
Chapter 10

La compression des images et la

norme JPEG

Figure 10.1: Une photo de fleur compressée en JPEG, avec des compressions de plus en plus
fortes, de gauche à droite.

Dans ce chapitre, la norme JPEG est décrite en détail sous ses aspects DCT, quantification,
codage, compression avec ou sans perte. Ce chapitre reprend, avec quelques précisions, l’article de
Wikipedia

[Link] JPEG.

10.1 Introduction
La norme JPEG est une norme qui définit le format d’enregistrement et l’algorithme de décodage
pour une réprésentation numérique compressée d’une image fixe. JPEG est l’acronyme de Joint
Photographic Experts Group. C’est un comité d’experts qui édite des normes de compression pour
l’image fixe. La norme communément appelée JPEG est le résultat de l’évolution des travaux qui ont
débuté dans les années 1978 à 1980 avec les premiers essais en laboratoire de compression d’images.
Le groupe JPEG qui a réuni une trentaine d’experts internationaux, a spécifié la norme en 1991.
Mais la norme officielle et définitive n’a été adoptée qu’en 1992. La norme dont nous allons parler est

85
86 CHAPTER 10. LA COMPRESSION DES IMAGES ET LA NORME JPEG

Figure 10.2: Organigramme de compression. Cette figure ne représente pas un cycle !

basée sur la DCT. Une norme plus récente, JPEG 2000, est basée sur la transformée en ondelettes,
qui généralise la transformée de Fourier. JPEG normalise uniquement l’algorithme et le format de
décodage. Le processus d’encodage est laissé libre à la compétition des industriels et universitaires,
du moment que l’image produite est décodable par un décodeur standard. La norme propose un jeu
de fichiers de tests appelés fichiers de conformance qui permettent de vérifier qu’un décodeur respecte
bien la norme. Un décodeur est alors dit conforme s’il est capable de décoder tous les fichiers de
conformance. JPEG définit deux classes de processus de compression : avec pertes ou compression
irréversible. C’est le JPEG “classique”. Il permet des taux de compression de 3 à 100. Le second est
le processus sans pertes ou compression réversible. Il n’y a pas de perte d’information et il est donc
possible de revenir aux valeurs originales de l’image. Les gains en terme de compression sont alors
plus modestes, avec un taux de compression de l’ordre de 2. Cette partie fait l’objet d’une norme
spécifique: JPEG-LS.

10.2 L’algorithme avec pertes

On peut diviser la compression et la décompression JPEG en six étapes données dans l’organigramme
de la figure 10.2.
Les étapes sont:

Découpage en blocs
Le format JPEG, comme le font généralement les algorithmes de compression à perte, commence
par découper l’image en blocs ou carreaux généralement carrés de 64 (8 x 8) ou 256 (16 x 16) pix-
els. L’utilité de ces petits blocs est que les chances augmentent que le bloc soit homogène, et donc
facilement résumable en quelques coefficients de Fourier.

Transformation des couleurs

(Référence: [Link] JPEG est capable de coder les couleurs sous n’importe
quel format, toutefois les meilleurs taux de compression sont obtenus avec des codages de couleur de
type luminance/chrominance tels que Y U V , car l’oeil est assez sensible à la luminance mais peu à la
chrominance. Les coordonnées Y U V , où Y désigne la luminance et U et V désignent les composantes
de chrominance peuvent en gros s’interpréter comme suit : Y est le niveau de gris, U est en gros la
différence entre le bleu et le vert et V est à peu près la différence entre le rouge et le vert. Dans le cas
10.2. L’ALGORITHME AVEC PERTES 87

d’une image grise (image noir et blanc), comme R = G = B, on a U = V = 0, ce qui veut dire que
l’image n’a pas de chrominance, mais seulement une luminance. Plus précisément,
    
Y 0, 299 0, 587 0, 114 R
 U  =  −0, 147 −0, 289 0, 436   G  .
V 0, 615 −0, 515 0, 100 B

Remarquer que la somme des coefficients des deux dernières lignes est nulle. La compression va
traiter sommairement les composantes U, V et va être plus fidèle pour la composante Y , qui contient
l’information géométrique de l’image.

Sous-échantillonnage
La façon la plus simple d’exploiter la faible sensibilité de l’oeil à la chrominance est simplement de
sous-échantillonner les signaux de chrominance. Généralement on utilise un sous-échantillonnage de
type 2h1v ou 2h2v. Dans le premier cas (le plus utilisé) on a un sous-échantillonnage 2:1 horizontale-
ment et 1:1 verticalement, dans le deuxième cas on a un sous-échantillonnage 2:1 horizontalement et
verticalement. Ces sous-échantillonnages sont utilisés pour les chrominances, pour la luminance on
n’utilise jamais de sous-échantillonnage.

Transformée en cosinus discrète

La transformée DCT (Discrete Cosine Transform) est une transformation numérique qui est appliquée
à chaque bloc et pour chaque ” couleur ”. Cette transformée est une variante de la transformée de
Fourier. Cette méthode permet de décrire chaque bloc en une carte de fréquences et amplitudes plutôt
qu’en pixels et couleurs. La valeur d’une fréquence reflète l’importance et la rapidité d’un changement,
tandis que la valeur d’une amplitude correspond à l’écart associé à chaque changement de couleur. À
chaque bloc de pixels sont ainsi associées 64 fréquences. La transformée DCT directe est
N
X −1 N
X −1
2 (2k + 1)mπ (2l + 1)nπ
c(m, n) =: C(m)C(n) u(k, l)cos cos ,
N 2N 2N
k=0 l=0

et la transformée DCT inverse s’exprime par

N
X −1 N
X −1
2 (2m + 1)kπ (2n + 1)lπ
u(k, l) =: C(k)C(l) u(m, n)cos cos .
N m=0 n=0
2N 2N

Dans les deux cas, la constante vaut C(m) = √12 pour m = 0 et m = 1 sinon. Pourquoi la DCT plutôt
que la DFT (discrete Fourier transform)? On rappelle que la DCT est en fait une DFT appliquée
à une image quatre fois plus grande obtenue en symétrisant l’image par rapport à ses cotés gauche
et bas et par rapport à son coin bas et gauche. Cette nouvelle image reste continue quand on la
périodise. Ainsi, l’analyse de Fourier s’applique à une image vraiment périodique, ce qui évite les forts
coefficients de Fourier associés aux discontinuités produites par une périodisation directe.
Pour illustrer la compression, a été repris un exemple complet provenant de “Digital Images
Compression Techniques” de Majid Rabbani et Paul W. Jones. Matrice (bloc de pixels) de base :
 
139 144 149 153 155 155 155 155
 144 151 153 156 159 156 156 156 
 
 150 155 160 163 158 156 156 156 
 
 159 161 162 160 160 159 159 159 
f = 

 159 160 161 162 162 155 155 155 
 161 161 161 161 160 157 157 157 
 
 162 162 161 163 162 157 157 157 
162 162 161 161 163 158 158 158
88 CHAPTER 10. LA COMPRESSION DES IMAGES ET LA NORME JPEG

En effectuant la transformée DCT on obtient la matrice des fréquences suivante :

 
1260 −1 −12 −5 2 −2 −3 1
 −23 −17 −6 −3 −3 0 0 −1 
 
 −11 −9 −2 2 0 −1 −1 0 
 
 −7 −2 0 1 1 0 0 0 
 
 −1 −1 1 2 0 −1 1 1 
 
 2 0 2 0 −1 1 1 −1 
 
 −1 0 0 −1 0 2 1 −1 
−3 2 −4 −2 2 1 −1 0

Le calcul d’une DCT est l’étape qui coûte le plus de temps et de ressources dans la compression et
la décompression JPEG, mais c’est peut-être la plus importante car elle permet de séparer les basses
fréquences et les hautes fréquences présentes dans l’image. Remarquer que les coefficients grands se
concentrent dans les fréquences basses.

Quantification
La quantification est l’étape dans laquelle on perd réellement des informations (et donc de la qualité
visuelle), mais c’est celle qui fait gagner beaucoup de place (contrairement à la DCT, qui ne compresse
pas). La DCT a retourné, pour chaque bloc, une matrice de 8×8 nombres (dans l’hypothèse que les
blocs de l’image font 8×8 pixels). La quantification consiste à diviser cette matrice par une autre,
appelée matrice de quantification, et qui contient 8×8 coefficients savamment choisis par le codeur.
Le but est ici d’atténuer les hautes fréquences, c’est-à-dire celles auxquelles l’oeil humain est très
peu sensible. Ces fréquences ont des amplitudes faibles, et elles sont encore plus atténuées par la
quantification (les coefficients sont même ramenés à 0). Voici le calcul permettant la quantification :
µ ¶
F (u, v) + b Q(u,v) c F (u, v)
F ? (u, v) =: b 2
c ' entier le plus proche de ,
Q(u, v) Q(u, v)
avec bxc désignant l’entier directement inférieur à x. Et pour la quantification inverse :

F̂ (u, v) = F ? (u, v)Q(u, v).

Comme le montre l’image ci-dessous la quantification ramène beaucoup de coefficients à 0 (surtout

en bas à droite dans la matrice, là où sont les hautes fréquences). Seules quelques informations
essentielles (coin en haut à gauche) sont gardées pour représenter le bloc. L’intérêt est qu’au moment
de coder le résultat dans le fichier, la longue suite de zéros nécessitera très peu de place. Mais si la
quantification est trop forte (= taux de compression trop élevé), il y aura trop peu de coefficients
non nuls pour représenter fidèlement le bloc ; dès lors, à l’écran la division en blocs devient visible,
et l’image apparaı̂t ” pixellisée ”. Dans notre exemple nous avons pris la matrice de quantification
suivante :
 
16 11 10 16 24 40 51 61
 12 12 14 19 26 58 60 55 
 
 14 13 16 24 40 57 69 56 
 
 14 17 22 29 51 87 80 62 
Q =: 



 18 22 37 56 68 109 103 77 
 24 35 55 64 81 104 113 92 
 
 49 64 78 87 103 121 120 101 
72 92 95 98 112 100 103 99

Ce qui donne comme matrice des fréquences quantifiée :

10.2. L’ALGORITHME AVEC PERTES 89

 
79 0 −1 0 0 0 0 0
 −2 −1 0 0 0 0 0 0 
 
 −1 −1 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 
F =: 
?



 0 0 0 0 0 0 0 0 
 0 0 0 0 0 0 0 0 
 
 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0

Codage RLE
(Voir [Link] L’étape suivante demande un run-length
encoding, en français codage par plages. C’est un algorithme élémentaire de compression de données
en informatique que nous allons expliquer maintenant.
Le RLE s’applique essentiellement à des documents scannés en noir et blanc : au lieu de coder un
bit par point, on dispose d’un compteur en général sur un octet indiquant combien de points blancs
ou noirs se suivent. Comme il est rare de ne pas avoir au moins 8 pixels noirs ou 8 pixels blancs qui
se suivent, et que 256 ne sont pas rares sur les endroits vierges ou les à-plats noirs, le système a bien
pour effet une compression. S’il y a plus de 256 bits de la même couleur, on peut placer ensuite un
octet spécifiant 0 bit de la couleur opposée, puis coder le nombre de bits qui restent...
Par exemple, considérons un écran de texte noir sur fond blanc. Il sera constitué de longues
séquences de pixels blancs pour le fond, et de courtes séquences de pixels noirs pour le texte. Représentons
une ligne d’un tel écran, avec B pour les pixels noirs et W pour les pixels blancs :

vvvvvvvvvvvvbvvvvvvvvvvvvvvbbbvvvvvvvvvvvvvvvvvvvvvvvbvvvvvvvvvvv

Un encodage RLE consiste alors à indiquer pour chaque suite de pixels d’une même couleur, le
nombre de pixels de cette séquence. Le résultat comporte en général moins de caractères, bien que ce
ne soit pas une obligation. On obtient par exemple pour la ligne précédente :

12v1b14v3b23v1b11v,

tandis que :

vbvbvbvbvb

donnerait

1v1b1v1b1v1b1v1b1v1b,

qui est passablement plus longue.

Les formats d’images utilisent cette compression en considérant que toutes les lignes de pixels sont
jointes pour former une unique séquence de couleur.
Le format BMP de Windows et OS/2 permet d’utiliser la compression RLE pour les images en
1, 4 et 8 bits/pixel (respectivement noir et blanc, 16 couleurs et 256 couleurs). Ce n’est pas une très
bonne compression, dès que la gamme de couleurs est riche, mais elle est excellente pour les images
en noir et blanc. Le format PCX utilise également le principe de la compression RLE pour les images
en 8 et 24 bits/pixel. Dans le cas des images en 24 bits/pixel, l’image est en fait découpée en trois
plans de couleur (rouge, vert et bleu) où chaque plan est encodé comme une image en 8 bits/pixel.
RLE est aussi utilisé pour les faxs, ce qui est son usage le plus fréquent hors informatique.
90 CHAPTER 10. LA COMPRESSION DES IMAGES ET LA NORME JPEG

Figure 10.3: Ordre de codage défini par la norme JPEG.

Codage JPEG: compression RLE et Huffman

Revenons à JPEG. Le codage RLE des coefficients de la DCT quantifiés s’effectue en zigzag comme
le montre la figure 10.3 et se termine par un caractère de fin :
Par exemple le codage de notre exemple est :

79, 0, −1, −1, −1, 0, 0, −1, EOB.

Ce résultat est ensuite compressé avec un RLE basé sur la valeur 0 (le codage RLE intervient unique-
ment sur cette dernière), puis un codage entropique de type Huffman ou arithmétique qui utilise le
fait que la distribution des valeurs de la DCT est concentrée autour de quelques valeurs autour de 0,
donc une distribution discrète à entropie faible. Avec le schéma de codage très simplifié suivant on
remarque que le codage nous délivre deux tables (quatre pour une image couleur). Ces tables étant
enregistrées dans le fichier final peuvent être choisies par le compresseur.

Figure 10.4: Schéma de codage simplifié.

La décompression JPEG
Les étapes de la décompression s’effectuent dans l’ordre inverse de la compression suivant les méthodes
définies précédemment (en même temps que la compression). Voici dans notre exemple le résultat de
la décompression :
10.3. JPEG, CODAGE SANS PERTES 91

 
144 146 149 152 154 156 156 156
 148 150 152 154 156 156 156 156 
 
 155 156 157 158 158 157 156 155 
 
 160 161 161 162 161 159 157 155 
 
 163 163 164 164 162 160 158 156 
 
 163 163 164 164 162 160 158 157 
 
 160 161 162 162 162 161 159 158 
158 159 161 161 162 161 159 158
Ainsi que la matrice d’erreur :
 
−5 −2 0 1 1 −1 −1 −1
 −4 1 1 2 3 0 0 0 
 
 −5 −1 3 5 0 −1 0 1 
 
 −1 0 1 −2 −1 0 2 4 
 
 −1 0 1 −2 −1 0 2 4 
 
 −2 −2 −3 −3 −2 −3 −1 0 
 
 2 1 −1 1 0 −4 −2 −1 
4 3 0 0 1 −3 −1 0
Les erreurs sont au maximum de 5 et en moyenne 1,6 sur environ 150 ce qui nous donne une erreur
moyenne d’environ 1, et tout cela pour un passage de 64 à 10 valeurs (avec le caractère de fin) ; à cela
il faut rajouter la matrice de quantification, mais comme généralement on compresse de gros fichiers,
elle n’influence que peu.

10.3 JPEG, codage sans pertes

À la place de la DCT, le codage sans pertes utilise un prédicteur qui permet de coder une différence
entre valeur prédite et valeur observée, au lieu de la valeur elle-même. Pour se faire une première idée
de comment marche un tel codage prédictif, on examinera un compresseur utilisant la prédiction la plus
banale. Il consiste à lire l’image ligne à ligne et de gauche à droite. La première valeur u(i, 1) de chaque
ligne est gardée telle quelle, et les valeurs suivantes sont remplacées par u(i + 1, j) − u(i, j). L’image
étant régulière, ces valeurs sont statistiquement petites: leur distribution est concentrée autour de
zéro. Il en résulte que l’entropie de l’ensemble des valeurs u(i + 1, j) − u(i, j) a un nombre de bits
nettement plus petit que huit (en pratique, proche de 4). On peut donc pratiquer une compression sans
perte en utilisant un codage de Hufman de ces valeurs. Ce codage prédictif s’améliore facilement avec
un prédicteur un peu plus sophistiqué: utilisant toujours la régularité locale de l’image, on ”prédit”
la valeur u(i + 1, j + 1) à partir des trois valeurs u(i, j), u(i + 1, j), u(i, j + 1), la prédiction est tout
bonnement linéaire. La valeur prédite est

ũ(i + 1, j + 1) =: u(i + 1, j) + u(i, j + 1) − u(i, j).

Ensuite on fait un codage de Huffman de la séquence des différences ũ(i, j) − u(i, j). Pour démarrer
la prédiction, les valeurs u(1, 1), u(1, 2) et les premières valeurs de chaque ligne u(k, 1) sont gardées
telles quelles.

10.4 Exercices et implémentation Matlab

Exercice 55 1) Récupérer sur le web un code public JPEG, de préférence en Matlab, et commenter
en détail chaque partie, en particulier, discuter la partie ”lossless” (compression sans perte) dans son
lien avec la théorie du codage de Shannon, et la partie compression avec perte, dans son lien avec
l’analyse de Fourier et le filtrage.
92 CHAPTER 10. LA COMPRESSION DES IMAGES ET LA NORME JPEG

Figure 10.5: Schéma de compression JPEG sans pertes.

2) Appliquer JPEG à plusieurs images avec des taux de compression allant de faible à très fort et
discuter la qualité visuelle des images.

Exercice 56 Compression sans perte

1) Implémenter une compression sans perte avec le premier prédicteur banal décrit plus haut.
2) Implémenter le prédicteur linéaire à trois valeurs indiqué plus haut
3) Essayer d’inventer un prédicteur plus sophistiqué (le premier se base sur l’idée que l’image est
localement constante, le second sur l’idée qu’elle est localement linéaire, donc il faut passer à une
prédiction quadratique...)
Chapter 11

Ondelettes de Malvar-Wilson et
segmentation de la voix

Exercice 57 La DCT (discrete cosine transform, transformée de Fourier discrète.) On veut

analyser un signal discret (u0 , ..., uN −1 ) de l2 (0, 1, ..., N − 1) en évitant de créer un saut en 0 par
périodisation. Pour cela, on procède comme pour les bases en cosinus : on étend le signal en un
signal de l2 (0, ..., 2N − 1) en faisant une symétrie par rapport à N − 12 . On a créé ainsi une suite
à 2N coefficients, que l’on analyse par transformée de Fourier discrète. Sa 2N -périodisée n’a plus de
discontinuité artificielle.
1) Calculer la transformée de Fourier discrète (ṽn )n=−N, ...N −1 du nouveau signal discret

(v0 , . . . , v2N −1 ) = (u0 , ..., uN −1 , uN −1 , uN −2 , ..., u0 ).

Montrer que
N −1
1 n2 X 1 π
ṽn = ω2N ul cos(n(l + ) ), n = −N, ..., N − 1.
N 2 N
l=0

n
2) Vérifier que ṽn = ṽ−n ω2N et ṽ−N = 0.
ṽ0
3) En déduire que la transformation u = (u0 , . . . , uN −1 ) → ( √ 2
, ṽ1 , . . . , ṽN −1 ) est une isométrie, à
un facteur près que l’on précisera. On pourra commencer par vérifier que la transformée de Fourier
discrète est une isométrie à un facteur multiplicatif. Pour cela: vérifier que sa matrice est propor-
tionnelle à une matrice unitaire. On rappelle qu’une matrice unitaire U est une matrice telle que
U t U = Id.
PN −1
4) Dans la suite, on pose, pour 1 ≤ n ≤ N − 1, w̃n = √1N l=0 (ul cosn(l + 21 ) N π
) and w̃0 =
P N −1
√1
2N l=0 ul . Déduire de la question précédente que l’application u → w est aussi une isométrie. On
l’appelle ”transformée en cosinus discrète” (DCT).
5) Montrer sans calcul que la transformation inverse de la DCT est donnée par
N −1
1 X 1 π 1
ul = √ w̃n cos(n(l + ) ) + w̃0 √ .
N n=1 2 N 2N
q
2
Exercice 58 Montrer que la suite uk (t) = π cos(k + 12 )t, k ∈ IN , est une base orthonormée de
L2 (0, π). Indication : considérer l’espace E des fonctions 4π-périodiques, paires, et vérifiant f (2π−t) =
−f (t) et écrire le développement de Fourier de ces fonctions. Remarquer ensuite que ces fonctions
sont entièrement déterminées par leur restriction à [0, π].

93
94CHAPTER 11. ONDELETTES DE MALVAR-WILSON ET SEGMENTATION DE LA VOIX

Exercice 59 Les ondelettes de Malvar discrètes (Yves Meyer, Ondelettes et Algorithmes

Concurrents, Hermann, pp.19-23).
Soit un signal de parole déja échantillonné. On le prend de longueur arbitraire et il appartient
donc à l2 (Z). Par ailleurs, on va supposer qu’il est déja segmenté, ce qui veut dire qu’on sait le
couper en tranches temporelles pertinentes [aj , aj+1 ] avec aj → ±∞ quand j → ±∞. On suppose
que aj + 12 ∈ Z et que les aj forment une suite strictement croissante (les aj sont placés à mi-chemin
entre deux échantillons pour couper proprement). On pose lj = aj+1 − aj et on considère une suite
ηj ∈ IN ∗ telle que ηj + ηj+1 ≤ lj . Les tranches temporelles [aj , aj+1 ] correspondent à des notes, ou
des voyelles, ou des consonnes, ayant une certaine cohérence fréquentielle. L’analyse de Fourier est
justifiée et on peut utiliser la DCT dans chaque tranche. On a ainsi une décomposition orthogonale
de l2 (Z) en espaces Ej = l2 (Z ∩ [aj , aj+1 ])), par exemple, et chacun de ces espaces dispose à son tour
d’une base orthogonale par DCT.
1) Formaliser le raisonnement précédent et montrer qu’il amène à conclure que le système

1 π 1
uj,k (x) = p cos(k(x − aj ) )11[aj ,aj−1 ] , 1 ≤ k ≤ lj − 1 et uj,0 (x) = p 11[aj ,aj−1 ] , j ∈ Z (11.1)
lj lj 2lj

est une base orthonormée de l2 (Z).

Saucissonnage mou pour les sons: pourquoi? On obtient donc à peu de frais une base orthono-
male de l2 (Z). Il est toutefois plus habile d’utiliser un découpage ”mou” de la droite temporelle, afin
d’éviter les effets de bord dûs au saucissonnage du signal. Ces effets de bord sont essentiellement
liés au fait que la transformée de Fourier sur un intervalle de longueur T traite le signal comme T -
périodique, et donc crée une discontinuité artificielle au bord. Une première réponse est d’utiliser la
transformée en cosinus, qui revient à symétriser le signal par rapport à une des bornes de l’intervalle,
puis à 2T -périodiser le signal obtenu, qui reste alors continu. Ce procédé, qui donne des résultats
satisfaisants pour les images, n’est encore pas suffisant pour les sons. Par la DCT, la dérivée du signal
aux bornes de l’intervalle reste discontinue, et l’application de la DCT à des intervalles du son par
saucissonnage dur provoque des “clics” désagréables à l’audition. Il faut donc faire un découpage mou,
où chaque portion du son naı̂t très doucement au début de l’intervalle et meurt très doucement à la
fin. Cela ne peut se faire qu’avec des intervalles recouvrants.
Le problème est alors de maintenir l’orthogonalité, puisque les intervalles d’un découpage mou (une
partition de l’unité) se recouvrent partiellement. C’est ce problème qu’ont résolu indépendamment
il n’y a pas si longtemps (1990) un prix Nobel de physique, Kenneth Wilson, et un spécialiste de
traitement du signal, Enrique Malvar. La présentation simple que nous donnons suit une construction
de Ronald Coifman et Yves Meyer (1997). La partition de l’unité est donnée par des fenêtres wj (x),
x ∈ Z, vérifiant

0 ≤ wj ≤ 1 et wj (x) = 1 si aj + ηj ≤ x ≤ aj+1 − ηj+1 , (11.2)

wj (x) = 0 si x ≤ aj − ηj ou si x ≥ aj+1 + ηj+1 , (11.3)

2
si x = aj + t et |t| ≤ ηj , alors wj−1 (aj − t) = wj (aj + t) et wj−1 + wj2 (x) = 1. (11.4)
P
2) Remarquer que les wj2 forment une partition de l’unité, c’est-à-dire j wj2 = 1.
3) Définir et dessiner des exemples de fonctions wj vérifiant les conditions (11.2-11.3-11.4).
Le but des deux questions qui suivent est de comprendre la difficulté du problème posé, à savoir
: trouver une base de Fourier qui soit à la fois localisée sur les intervalles [aj − ηj , aj+1 +P
ηj+1 ] et
orthonormale. La tentative la plus naturelle est d’écrire pour toute suite u de l2 (Z) : u = j wj2 u.
Ensuite, les tranches molles wj u peuvent subir une analyse de Fourier locale sur les intervalles [aj −
ηj , aj+1 + ηj ]. Voyons que ça marche, mais que ce n’est pas parfait.
 95

4) Montrer en utilisant la partition de l’unité précédente et la DCT que tout signal de l2 (Z) peut
s’écrire sous la forme
X X kπ
u= cj,k wj (x)cos 0 (x − a0j ),
0
lj
j∈Z 0≤k≤lj −1

où on a posé l0 j = aj+1 + ηj+1 − aj − ηj et a0 j = aj − ηj . On précisera les coefficients cj,k .

5) Montrer que les fonctions wj (x)cos kπ 0
l0 (x − aj ), j ∈ Z, 0 ≤ k ≤ lj − 1 ne forment pas une base
j

orthogonale de l2 (Z).
Pour restaurer l’orthogonalité, on a besoin d’une construction du type précédent, mais un peu
plus sophistiquée. On appelle ondelettes de Malvar les fonctions uj,k (x), j ∈ Z, 0 ≤ k ≤ lj − 1 définies
par
s µ ¶
2 1 x − aj
uj,k (x) = wj (x)cos π(k + )( ) . (11.5)
lj 2 lj

Théorème 11.1 La suite uj,k est une base orthonormée de l2 (Z).

6) Comparer la forme des ondelettes de Malvar à la base orthonormale de l2 (Z) donnée par (11.1).
La démonstration du théorème va se faire en deux étapes que ce problème va détailler :
(I) Décomposer l2 (Z) en une somme d’espaces orthogonaux Ej de dimension lj .
(II) Vérifier que pour chaque j les fonctions uj,k , 0 ≤ k ≤ lj − 1, forment une base orthonormée de
Ej .
Définissons Ej . Soit Fj l’espace des fonctions g ∈ l2 (Z) nulles hors [aj − ηj , aj+1 + ηj+1 ] et
vérifiant
g(aj + t) = g(aj − t) si |t| ≤ ηj (11.6)
g(aj+1 + t) = −g(aj+1 − t) si |t| ≤ ηj+1 (11.7)

7) Montrer que dim Fj = lj . On dira que f ∈ Ej si et seulement si f = wj g où g ∈ Fj .

8) Dessiner sur un même graphe : wj , wj+1 , et une fonction g ∈ Fj . On peut résumer la situation
ainsi : On part d’un signal u ∈ l2 (Z), on considère sa restriction uj à l’intervalle [aj , aj+1 ]. Cette
restriction définit une unique fonction g ∈ Fj , en étendant uj à gauche de l’intervalle par parité et à
droite par imparité. La fonction g ∈ Fj obtenue est ensuite ramenée vers zéro aux bords de l’intervalle
[a − j − ηj , aj+1 + ηj+1 ] : il suffit de la multiplier par la fonction fenêtre wj . Cette construction va
permettre d’obtenir l’orthogonalité des Ej , grâce à l’alternance de prolongements pairs et impairs.
9) Vérifier que les Ej sont orthogonaux entre eux : commencer par remarquer qu’il suffit de considérer
Ej et Ej−1 . Si fj ∈ Ej et fj−1 ∈ Ej−1 , on peut écrire fj = wj gj , fj−1 = wj−1 gj−1 . L’orthogonalité se
déduit des propriétés de parité ou d’imparité des fonctions considérées sur l’intervalle [aj −ηj , aj +ηj ].
10) Vérifier que les fonctions uj,k sont dans Ej .
12) Montrer en utilisant (11.2-11.4) que si f1 et f2 appartiennent à Ej ,
X X
f1 (x)f2 (x) = g1 (x)g2 (x). (11.8)
z∈Z aj <x<aj+1

13) En déduire que l’application Uj : Ej → l2 (aj + 12 , . . . , aj+1 − 12 ) est un isomorphisme isométrique.

q ¡π ¢
14) Montrer que les fonctions N2 cos N (k + 21 )(x + 12 ) , 0 ≤ k < N −1 forment une base orthonormée
de l2 (0, 1, . . . , N − 1). Remarque : leur nombre est égal à la dimension N de l’espace et il suffit
96CHAPTER 11. ONDELETTES DE MALVAR-WILSON ET SEGMENTATION DE LA VOIX

donc de vérifier leur orthonormalité. Pour montrer l’orthogonalité, utiliser les identités 2cosa cosb =
cos(a − b) − cos(a + b), puis
X · ¸
π 1
cos m(x + ) = 0 si 1 ≤ m ≤ 2N − 1.
N 2
0≤x<N

P π 1
Cette dernière identité s’obtient en calculant 0≤x<N ei N m(x+ 2 ) .
15) Déduire des questions précédentes que le résultat (II) est juste.
Il nous faut maintenant montrer que si f ∈ l2 (Z) est orthogonale à tous les Ej , alors elle est nulle.
16) Commencer par vérifier que si x0 ∈ [aj + ηj , aj+1 − ηj+1 ], alors la fonction égale à 1 en x0 et à 0
ailleurs appartient à Ej . En déduire que f est nulle sur ces intervalles.
17) En utilisant des fonctions adéquates dans Ej et Ej+1 , montrer que si on pose x = aj + t et
x0 = aj − t, où |t| ≤ ηj , t − 12 ∈ Z, alors on a

f (x)wj (x) + f (x0 )wj (x0 ) = 0 et f (x)wj−1 (x) − f (x0 )wj−1 (x0 ) = 0.

En déduire que f (x) = f (x0 ) = 0 et conclure.

Exercice 60 Commentaire dirigé de l’article Entropy-based Algorithms for Best Basis Selection, de
Ronald R. Coifman et Mladen V. Wickerhauser
1) Lire l’article.
2) Etablir le lien entre les fonctions Si,k introduites dans la page 2 de l’article et les ondelettes de
Malvar-Wilson telles qu’elles sont décrites dans le problème précédent.
3) Démontrer la relation additive donnée page 4 de l’article que les auteurs commentent en disant
This Shannon’s equation for entropy ....
4) Démontrer la première proposition de la page 4 concernant la dimension d’un vecteur.
5) Démontrer la deuxième proposition de la page 4, concernant la relation entre dimension d’un vecteur
et concentration de ses coefficients.
6) Développer la preuve de la dernière proposition, qui justifie l’algorithme de meilleure base. La
preuve donnée est-elle correcte? Avez-vous une opinion sur l’algorithme proposé: trouve-t-il vraiment
la meilleure base de Malvar-Wilson?
 97

Conseils de lecture :
Claude E. Shannon et Warren Weaver The mathematical theory of communication University of Illi-
nois Press 1998.
Thomas M. Cover et Joy A. Thomas Elements of Information Theory, Wiley Series Telecommunica-
tions, (chapitres 2, 5 et 8), 1991.
Pierre Brémaud Introduction aux probabilités, Springer.
J.M. Bony, Cours d’Analyse de l’Ecole Polytechnique, Ecole Polytechnique, 1994 (polycopié).
J.M. Bony, Cours de Méthodes Mathématiques pour les Sciences Physiques, Ecole Polytechnique,
(1997). (polycopié).
C. Gasquet et P. Witomski, Analyse de Fourier et applications, Masson (1995).
S. Mallat, A Wavelet Tour of Signal Processing, Academic Press, (1997).
S. Mallat, Une exploration des signaux en ondelettes, Editions de l’Ecole Polytechnique, 2000.
S. Mallat Traitement du Signal, polycopié de la Majeure de Mathématiques Appliquées, Ecole Poly-
technique, 1998.
Y. Meyer, Wavelets, Algorithms and Applications, SIAM (1993), translated and revised by Robert
Ryan.
Y. Meyer, Ondelettes et Algorithmes concurrents. Hermann, Paris (1992).
Y. Meyer, cours de DEA ondelettes (1994-1997 (manuscrits).
L. Yaroslavsky, M. Eden, Fundamentals of Digital Optics, Birkhäuser, (1996). Sources: Claude E.
Shannon A mathematical source of communication.
Pierre Brémaud Introduction aux probabilités, Chapitre 5, Springer.
Thomas M. Cover, Joy A. Thomas, Elements of information theory (pages 194-197), Wiley, 1991.
Thomas M. Cover et Joy A. Thomas Elements of Information Theory, Wiley Series Telecommunica-
tions.
Eva Wesfreid, Travaux pratiques sur l’analyse du son, DEA MVA, ENS Cachan, 2002.
Agnès Desolneux, Travaux pratiques sur l’entropie et la théorie de l’information, préparation à
l’agrégation, ENS Cachan, 2002.
Sylvie Fabre, Jean-Michel Morel, Yann Gousseau, Notes du cours d’analyse, ENS Cachan 1ère année,
2007.