Main
Main
𝑏 𝑘
𝑀 =0
∑𝑘 1
+ 1 1 )
𝑘 1 1 1
−
𝑛 0 0 0
𝑦 0 1
𝑎𝑘 0 1 1 1 0
1 0 0
𝑁=
𝑘
∑ 𝐻 =
(
1 0 1
− 2 i 𝜋 𝜈 𝑡 d
𝑠( 𝑡 ) e
∶ = ⌠
(̂ 𝜈 ) ⌡
Introduction R
au
Traitement
du
Signal
Ce document est mis à disposition selon les termes de la licence Creative
Commons : « Attribution - Partage dans les mêmes conditions 4.0
International ».
Pour accéder à une copie de cette licence, merci de vous rendre à l’adresse
suivante :
[Link]
Table des matières
Introduction 1
0.1 Objectifs du cours . . . . . . . . . . . . . . . . . . . . . . . . 2
0.2 Chaîne de transmission numérique . . . . . . . . . . . . . . . 2
0.3 Les sons et les images . . . . . . . . . . . . . . . . . . . . . 4
0.3.1 Le son . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.3.2 Les images . . . . . . . . . . . . . . . . . . . . . . . 5
0.4 Plan du cours . . . . . . . . . . . . . . . . . . . . . . . . . . 6
i
TABLE DES MATIÈRES
5 Filtres numériques 89
5.1 Filtres linéaires . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . 90
5.1.2 Propriétés des filtres . . . . . . . . . . . . . . . . . . 92
5.2 Stabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.3 Filtres linéaires récursifs causaux . . . . . . . . . . . . . . . 96
5.3.1 Réponse impulsionnelle finie (RIF) et infinie (RII) . . 97
5.3.2 Transformée en 𝑧 . . . . . . . . . . . . . . . . . . . . 97
5.3.3 Fonction de transfert . . . . . . . . . . . . . . . . . . 100
5.3.4 Stabilité . . . . . . . . . . . . . . . . . . . . . . . . . 101
Sommaire du chapitre
0.1 Objectifs du cours . . . . . . . . . . . . . . . 2
0.2 Chaîne de transmission numérique . . . . . . 2
0.3 Les sons et les images . . . . . . . . . . . . 4
0.3.1 Le son . . . . . . . . . . . . . . . . . 4
0.3.2 Les images . . . . . . . . . . . . . . 5
0.4 Plan du cours . . . . . . . . . . . . . . . . . 6
1
TABLE DES MATIÈRES
Conversion analogique-numérique
Lorsque l’on parle dans le microphone d’un téléphone, les vibrations acous-
tiques sont transformées en une tension oscillante par l’intermédiaire d’une
membrane et d’un électro-aimant qui convertit ainsi le signal mécanique en
signal électrique. C’est à ce moment qu’intervient la conversion analogique-
numérique, c’est-à-dire le passage du continu au discret, de l’analogique au
numérique, de R → R à Z → Z en quelque sorte. Le temps et les valeurs prises
par la tension sont des valeurs continues, à valeur dans R. Pour obtenir un
signal complètement numérique, la tension est donc discrétisée en temps et en
valeur. Concrètement, cela revient à prendre une série de photos instantanées
des valeurs de la tension, puis de projeter les valeurs obtenues sur une grille
fixe. Dans le vocabulaire du traitement numérique du signal, ces deux étapes
sont respectivement appelées échantillonnage et quantification. L’ensemble
de ces deux étapes constitue la conversion analogique-numérique, souvent
notée C.A.N.
Codage et compression
pendant Δ𝑡 seconde. Toute cette étape est généralement désignée sous le terme
de modulation. Dans le canal, le signal codé subit des altérations de nature
très variées, que le codage canal va pouvoir corriger.
Réception et décodage
À la réception en sortie de canal, interviennent séquentiellement les opé-
rations inverses de celles présentées ci-dessus. On effectue donc une démodu-
lation, un décodage canal, un décodage source et finalement une conversion
numérique-analogique.
L’ensemble de cette chaîne de transmission est reproduite dans la figure 1.
Conversion analogique-numérique
Chapitre 1 Chapitre 2 Chapitre 3 & 5-7 Chapitre 3
0.3.1 Le son
Un son est un ébranlement élastique de l’air, d’un fluide ou d’un solide qui
se manifeste par des variations de pression autour de la pression moyenne du
milieu. Lorsque le milieu est homogène, l’onde sonore se propage à vitesse
constante 𝑐 appelée célérité, célérité qui va dépendre du milieu.
Ces variations de pression sont modélisées par une fonction, et cette fonc-
tion peut-être décomposée, sous certaines hypothèses, en somme de cosinus
et de sinus (série de Fourier). Pour les sons simples, il suffit d’ailleurs de peu
de fonctions sinus et cosinus pour décrire correctement le son.
En reliant un microphone à un oscilloscope, on peut observer l’évolution
1. Le chapitre 2 ne fait pas partie du contenu du cours, il est là, à titre d’information pour
répondre à la curiosité des plus investi·e·s.
Chapitre
Formule de Shannon-Nyquist et échan-
tillonnage
Sommaire du chapitre
1.1 Transformées de Fourier des fonctions 𝐿1 . . 8
1.1.1 Définitions et notations . . . . . . . . 8
1.1.2 Convolution . . . . . . . . . . . . . . 11
1.1.3 Le lemme de Riemann-Lebesgue . . . 12
1.1.4 La formule d’inversion . . . . . . . . 13
1.1.5 Dérivation et transformée de Fourier 16
1.1.6 Transformée de Fourier à deux dimen-
sions . . . . . . . . . . . . . . . . . . 18
1.2 Séries de Fourier des signaux 𝐿1loc . . . . . . 19
1.2.1 Définitions, coefficients de Fourier . . 19
1.2.2 Convolution . . . . . . . . . . . . . . 21
1.2.3 Formule d’inversion et formule de
Poisson faible . . . . . . . . . . . . . 23
1.3 Reconstruction des signaux périodiques . . . 27
1.3.1 Le théorème de Shannon-Nyquist . . 28
1.3.2 Phénomène de recouvrement de spectre 32
1.3.3 Sur-échantillonnage . . . . . . . . . 35
1.4 Note bibliographique . . . . . . . . . . . . . 35
7
CHAPITRE 1. FORMULE DE SHANNON-NYQUIST ET
ÉCHANTILLONNAGE
que nous allons détailler. Ce théorème est connu sous le nom du théorème
d’échantillonnage, du théorème de Shannon ou bien encore du théorème de
Nyquist-Shannon. 1
La démonstration du théorème, ainsi que bon nombre de résultat de trai-
tement du signal reposent sur la théorie de la Transformation de Fourier 2 ,
théorie au cœur du traitement du signal. Ainsi ce chapitre débute par quelques
rappels de résultats bien connus.
̂ ≝ ⌠ 𝑠(𝑡)e−2i𝜋𝜈𝑡 d𝑡.
𝑠(𝜈)
⌡R
La transformée de Fourier se note aussi ℱ(𝑠) = 𝑠.̂
1. (Wikipédia) À partir des années 1960, le théorème d’échantillonnage est souvent appelé
théorème de Shannon, du nom de l’ingénieur qui en a publié la démonstration en posant les
bases de la théorie de l’information chez Bell Laboratories en 1949. Quelques années plus
tard, on joint à ce nom celui de Nyquist, de la même entreprise, qui avait ouvert la voie dès
1928.
2. Joseph Fourier (21 mars 1768, Auxerre - 16 mai 1830, Paris) est un mathématicien
et physicien français, connu pour ses travaux sur la décomposition de fonctions périodiques
en séries trigonométriques convergentes appelées séries de Fourier.
Remarque 1.2 :
— Le cadre fonctionnel 𝐿1 (R) est un cadre naturel pour la transfor-
mée de Fourier. En effet, avec ce cadre là, la transformée 𝑠 ̂ est bien
définie pour tout 𝜈 dans R puis que (𝑥 ↦ 𝑠(𝑥)e−2i𝜋𝜈𝑥 ) ∈ 𝐿1 . Nous
verrons que dans ce cadre fonctionnel, la transformée de Fourier
n’est pas toujours inversible.
— La transformée de Fourier peut être étendue aux fonctions 𝐿2 par
un passage à la limite, cadre dans lequel elle est un isomorphisme
et une isométrie (théorème de Plancherel). On adoptera ce cadre
fonctionnel au chapitre 6.
— La transformée de Fourier peut être considéré dans l’espace des
distributions tempérées de Laurent Schwartz qui contient tous
les 𝐿𝑝 et dans lequel elle est encore inversible. Beaucoup de réfé-
rences de traitement du signal se placent dans ce cadre là. Nous
ne l’aborderons presque pas ici.
Exercice 1.1 :
Montrer que pour 𝑇 > 0, la transformée de Fourier d’une fonction fenêtre,
encore appelée signal rectangulaire,définie par
1 𝑇
−3 −2 −1 0 1 2 3
−𝑇 /2 0 𝑇 /2 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇 𝑇
Exercice 1.2 :
Soit 𝑓 une fonction de 𝐿1 (R) paire. Montrez que :
+∞
∀𝜈 ∈ R, ℱ(𝑓)(𝜈) = 2 ⌠ 𝑓(𝑡) cos(2𝜋𝜈𝑡)d𝑡.
⌡0
Exercice 1.3 :
Soit 𝑎 > 0 et
𝑓 ∶ 𝑡 ∈ R ↦ e−𝑎|𝑡| .
Montrez que
2𝑎
∀𝜈 ∈ R, ℱ(𝑓)(𝜈) = .
𝑎2 + 4𝜋2 𝜈 2
Transformations 𝑓 𝑓̂
Délais 𝑓 ∶ 𝑡 ↦ 𝑠(𝑡 − 𝑡0 ) 𝑓 ̂ ∶ 𝜈 ↦ e−2i𝜋𝜈𝑡0 𝑠(𝜈)
̂
𝑓 ∶ 𝑡 ↦ 𝜆𝑠(𝑡) 𝑓 ̂ ∶ 𝜈 ↦ 𝜆𝑠(𝜈)
̂
𝑓 ∶ 𝑡 ↦ 𝑠∗ (𝑡) 𝑓 ̂ ∶ 𝜈 ↦ 𝑠(−𝜈)
̂ ∗
Exercice 1.5 :
Montrer que la transformée de Fourier est linéaire et continue dans 𝐿1 (R).
1.1.2 Convolution
Une loi de composition est généralement associée à la transformée de
Fourier, c’est le produit de convolution 3 . Nous verrons que cette loi de com-
position donne les clés pour comprendre et analyser les problèmes soulevés
par la conversion d’un signal analogique en signal digital (CAN : conversion
analogique-numérique) et aussi pour la conversion inverse, d’un signal digital
en un signal analogique (CNA : convertion numérique-analogique).
Exercice 1.6 :
Soit 𝑎 de classe 𝒞1 , stable de dérivée 𝑎′ stable, et soit 𝑏 un signal stable.
Montrer que
d
∀𝑡 ∈ R, (𝑎 ⋆ 𝑏)(𝑡) = 𝑎′ ⋆ 𝑏(𝑡).
d𝑡
lim |𝑠(𝜈)|
̂ = 0.
|𝜈|→+∞
𝐾𝑛
|̂
𝑠𝑛 (𝜈)| ≤ .
|𝜈|
̂
|𝑠(𝜈)| 𝑠𝑛 (𝜈)| + ⌠ |𝑠(𝑡) − 𝑠𝑛 (𝑡)|d𝑡
≤ |̂
⌡R
𝐾𝑛
≤ + ⌠ |𝑠(𝑡) − 𝑠𝑛 (𝑡)|d𝑡,
|𝜈| ⌡R
qui peut être rendu arbitrairement petit, sous réserve que |𝜈| soit suffisamment
grand.
𝑠(𝑡) = ⌠ 𝑠(𝜈)e
̂ 2i𝜋𝜈𝑡
d𝜈.
⌡R
2 +𝛽𝑡
∀𝑡 ∈ R, 𝑓𝛼,𝛽 (𝑡) = e−𝛼𝑡 .
1 − 𝑡
2
ℎ𝜎 (𝑡) = e 2𝜎2 ,
𝜎√2𝜋
̂(𝜈) = e−2𝜋2 𝜎2 𝜈 2 .
ℎ𝜎
̂ ℎ
𝑠(𝜈) ̂(𝜈) = ⌠ ⌠ 𝑠(𝑢)ℎ (𝑢)𝑓 1 𝑢 (𝑡)e−2𝜋𝑖𝜈𝑡 d𝑡d𝑢
𝜎 𝜎 ,
⌡R ⌡R 𝜎√2 𝜎2
— donc :
⌠ 𝑠(𝜈)
̂ ℎ ̂(𝜈)e2i𝜋𝜈𝑡 d𝜈 = ⌠ ⌠ 𝑠(𝑢)ℎ (𝑢)𝑓 ̂ 1 𝑢 (𝜈)e2i𝜋𝜈𝑡 d𝑢d𝜈
𝜎 𝜎 ,
⌡R ⌡R ⌡R 𝜎√2 𝜎2
=𝑠 ⋆ ℎ𝜎 (𝑡),
ce qui constitue la conclusion recherchée.
3. Enfin, nous avons :
2 2 2
lim ℎ̂ 𝜎 (𝜈) = lim e2𝜋 𝜎 𝜈 = 1.
𝜎→0 𝜎→0
lim ⌠ 𝑠(𝜈)
̂ ℎ ̂(𝜈)e2i𝜋𝜈𝑡 d𝜈 = ⌠ 𝑠(𝜈)e
̂ 2i𝜋𝜈𝑡
d𝜈.
𝜎
𝜎→0 ⌡R ⌡R
Il reste donc à montrer :
lim 𝑠 ⋆ ℎ𝜎 = 𝑠,
𝜎→0
dans 𝐿1 . Pour ce faire, en utilisant le fait que ∫R ℎ𝜎 (𝑢)d𝑢 = 1, notons que :
Exercice 1.8 :
En utilisant le résultat de l’exercice 1.3, et la transformée de Fourier
inverse, montrer que la transformée de Fourier de la fonction, pour 𝑏 ∈ R,
définie par
1
𝑓 ∶𝑡∈R↦ 2
𝑏 + 𝑡2
est
𝜋
ℱ(𝑓) ∶ 𝜈 ↦ e−2𝜋𝑏𝑡 .
𝑏
∀𝜈 ∈ R, 𝑠(𝑘)
̂ (𝜈) = ⌠ (−2i𝜋𝑡)𝑘 𝑠(𝑡)e−2i𝜋𝜈𝑡 d𝑡.
⌡R
Exercice 1.9 :
Montrer que la transformée de Fourier d’une gaussienne est une gaus-
sienne :
2 2 √𝜋 − 𝜋22 𝜈 2
ℱ(𝑓 ∶ 𝑡 ↦ e−𝑏 𝑡 ) = (𝜈 ↦ e 𝑏 ).
|𝑏|
On pourra partir de l’équation différentielle que satisfait 𝑓, et d’en faire la
transformée de Fourier. On rappellera que
2 𝑡2 √𝜋
⌠ e−𝑏 d𝑡 = .
⌡R |𝑏|
Exercice 1.10 :
Résoudre par transformée de Fourier l’équation de la chaleur suivante
𝜕𝜃 𝜕2𝜃
=𝜅 2 ,
𝜕𝑡 𝜕 𝑥
où
— pour tout 𝑥 ∈ R et 𝑡 ∈ R, 𝜃(𝑥, 𝑡) est la température au temps 𝑡 au
point 𝑥 d’une barre unidimensionnelle de conductance 𝜅 ∈ R ;
— à 𝑡 = 0, on a pour tout 𝑥 ∈ R, 𝜃(𝑥, 0) = 𝑓(𝑥) avec 𝑓 ∈ 𝐿1 (R) et
𝑓 ̂ ∈ 𝐿1 (R).
On supposera l’application partielle 𝑡 ↦ 𝜃(𝑥, 𝑡) suffisamment régulière et
Remarque 1.3 :
On peut remarquer que 𝑥1 𝜈1 + 𝑥2 𝜈2 = 𝑥 ⋅ 𝜈, et qu’avec la notation avec le
produit scalaire, il est assez immédiat d’étendre la transformée de Fourier
à R𝑛 .
Un signal périodique n’est ni stable (𝐿1 (R)), ni d’énergie finie (𝐿2 (R)).
Pour ce type de signal, nous allons considérer leurs séries de Fourier. Celles-ci
peuvent être vues comme des transformées de Fourier particulières : il s’agit
en effet de transformées de Fourier de fonctions périodiques. Dans la suite,
𝐿1loc désigne l’espace des signaux localement stable, i.e. :
la somme partielle.
Bien entendu d’autres résultats de convergence pour les séries de Fourier
existent et nous renvoyons à [6, 4] pour plus de détails.
Illustration graphique
Le vidéaste 3Blue1Brown 4 , mathématicien et vulgarisateur mathématique
sur YouTube, a réalisé une vidéo où il illustre la décomposition de Fourier
d’un chemin fermé par des animations de mécanismes d’engrenages de cercles
mis bout à bout. Le résultat est magnifique et envoûtant (voir figure 1.2).
Figure 1.2 – Vidéo Mais qu’est-ce qu’une série de Fourier ? Du transfert ther-
mique à des dessins avec des cercles du vidéaste 3Blue1Brown sur YouTube.
1.2.2 Convolution
Puisque le produit de convolution est une opération essentiellement algé-
brique, elle s’applique au cadre précédemment défini. On peut même convoler
des fonctions périodiques et des fonctions 𝐿1 , comme l’explique le résultat
suivant.
𝑇
⌠ ℎ(𝑡 − 𝑢)𝑠(𝑢)d𝑢 = ⌠ ℎ̃ 𝑇 (𝑡 − 𝑢)𝑠(𝑢)d𝑢,
⌡R ⌡0
où l’on a noté ℎ̃ 𝑇 (𝑢) = ∑𝑛∈Z ℎ(𝑢 + 𝑛𝑇 ). De plus, on peut montrer que 𝑔 est périodique
de période 𝑇 partout où elle est définie. En effet, en utilisant le fait que ℎ ⋆ 𝑠 = 𝑠 ⋆ ℎ,
on a
Comme :
𝑇
⌠ |ℎ̃ 𝑇 (𝑢)|d𝑢 ≤ ⌠ |ℎ(𝑢)|d𝑢 < +∞,
⌡0 ⌡R
𝑇 𝑇 𝑇
⌠ |𝑔(𝑡)| d𝑡 ⩽ ⌠ ⌠ |ℎ̃ 𝑇 (𝑡 − 𝑢)||𝑠(𝑢)|d𝑢d𝑡
⌡0 ⌡0 ⌡0
𝑇
⩽ ‖ℎ‖𝐿1 ⌠ |𝑠(𝑢)| d𝑢
⌡0
< +∞
Ainsi pour presque tout 𝑡 ∈ [0, 𝑇 ], 𝑡 ↦ ∫R ℎ(𝑡 − 𝑢)𝑠(𝑢)d𝑢 est définie, et par 𝑇-
La formule que nous venons d’obtenir sur les coefficients peut sembler
sophistiquée, mais elle nous sera utile par la suite.
Noyau de Poisson **
On introduit tout d’abord le noyau de Poisson et quelques-unes de ses
propriétés.
7. Claude Elwood Shannon (30 avril 1916 Gaylord, Michigan - 24 février 2001) est un
ingénieur électricien et mathématicien américain. Il est l’un des pères, si ce n’est le père
fondateur, de la théorie de l’information.
8. Harry Nyquist (7 février 1889 Nilsby, Suède- 4 avril 1976, Harlingen, Texas) a été un
important contributeur à la théorie de l’information et à l’automatique. Ses travaux théoriques
sur la détermination de la bande passante nécessaire à la transmission d’information, publiés
dans l’article Certain factors affecting telegraph speed posent les bases des recherches de
Claude Shannon.
Formule d’inversion
Les propriétés 2, 3, 4 correspondent à ce que l’on appelle une identité
approchée. On a déjà rencontré cette notion, sans le signaler, avec la fonction
ℎ𝜎 de la preuve du théorème 1.1. Les identités approchées permettent de
régulariser les fonctions par convolution et d’utiliser ensuite des formules du
type :
𝑇
1
lim ⌠ 𝜑(𝑡)𝑃𝑟 (𝑡)d𝑡 = 𝜑(0), (1.2)
𝑟→1 𝑇 ⌡0
Remarque 1.4 :
Si on suppose en outre que 𝑠 est continue, alors la formule d’inversion
devient vraie pour tout 𝑡 ∈ R.
𝑇
1 𝑛
⌠ 𝑠(𝑢)𝑃𝑟 (𝑡 − 𝑢)d𝑢 = ∑ 𝑠𝑛̂ 𝑟|𝑛| e2i𝜋 𝑇 𝑡 ,
𝑇 ⌡0 𝑛∈Z
𝑇 𝑇
1
lim ⌠ ∣ ⌠ 𝑠(𝑢)𝑃𝑟 (𝑡 − 𝑢)d𝑢 − 𝑠(𝑡)∣ d𝑡 = 0,
𝑟→1 ⌡0 𝑇 ⌡0
(indexée par 𝑟) converge dans 𝐿1loc vers 𝑠. D’autre part, puisque ∑𝑛∈Z |𝑠𝑛̂ | < +∞,
la fonction 𝜑𝑟 (𝑡) tend vers ∑𝑛∈Z 𝑠𝑛̂ exp(2i𝜋 𝑇𝑛 𝑡) ponctuellement. On utilise alors le
résultat du cours d’intégration suivant :
« Si une suite de fonction 𝑓𝑛 converge vers 𝑓 dans 𝐿𝑝 et vers 𝑔 presque partout, alors
𝑓 = 𝑔 presque partout »
Corollaire 1.1 : Deux signaux 𝑇-périodiques stable ayant les mêmes coeffi-
cients de Fourier sont égaux presque partout.
∀𝑡 ∈ R, 𝜙(𝑡) = ∑ 𝑠(𝑡 + 𝑛𝑇 ).
𝑛∈Z
1 𝑛 𝜋
𝑆𝑓 (𝑡) = ∑ 𝑠 ̂ ( ) e2i 𝑇 𝑡 .
𝑇 𝑛∈Z 𝑇
On utilise ici le mot formelle car nous ne disons rien sur la convergence de
cette série de Fourier.
Remarque 1.5 :
Si on arrive à montrer 𝜙(0) = 𝑆𝑓 (0), alors on aura la formule de Poisson
forte : pour tout 𝑠 ∈ 𝐿1 ,
𝑛
𝑇 ∑ 𝑠(𝑛𝑇 ) = ∑ 𝑠 ̂ ( ) .
𝑛∈Z 𝑛∈Z
𝑇
Pour aller un peu plus loin vers la version forte, on peut énoncer le résultat
suivant.
Proposition 1.4 : Soit 𝑠 un signal stable tel que ∑𝑛∈Z ∣𝑠 ̂ ( 𝑇𝑛 )∣ < +∞. Alors :
1 𝑛 𝑛
∑ 𝑠(𝑡 + 𝑛𝑇 ) = ∑ 𝑠 ̂ ( ) e2i𝜋 𝑇 𝑡 .
𝑛∈Z
𝑇 𝑛∈Z 𝑇
Alors :
1 𝑛 𝑛
∑ 𝑠(𝜈
̂ + 2𝑗𝐵) = ∑ 𝑠 ( ) e−2i𝜋𝜈 2𝐵 ,
𝑗∈Z
2𝐵 𝑛∈Z 2𝐵
pour presque tout 𝜈 ∈ R.
1 𝑛𝜈
𝜙𝑛̂ = ⌠ 𝑠(𝜈)e
̂ −2i𝜋 2𝐵
d𝜈.
2𝐵 ⌡R
Mais puisque 𝑠 ̂ est stable, on peut appliquer la formule d’inversion du théorème 1.1.
Dans notre cas, celle-ci s’écrit :
𝑛𝜈 𝑛
⌠ 𝑠 ̂ (𝜈) e−2i𝜋 2𝐵 d𝜈 = 𝑠 (− ) .
⌡R 2𝐵
1 𝑛 𝑛𝜈
𝜙(𝜈) = ∑ 𝑠 ( ) e−2i𝜋 2𝐵 .
2𝐵 𝑛∈Z 2𝐵
1 𝑛 𝑛
̃ =
𝑠(𝑡) ∑ 𝑠 ( ) ℎ (𝑡 − ) (1.6)
2𝐵 𝑛∈Z 2𝐵 2𝐵
admet la représentation :
Preuve : Notons tout d’abord que 𝑠 ̃ est borné et continu, en tant que somme d’une
série normalement convergente (en plus des hypothèses sur 𝑠, ℎ est bornée, et unifor-
mément continue).
En remplaçant ℎ par sa valeur dans (1.6), on obtient :
1 𝑛 𝑛
̃ =
𝑠(𝑡) ∑ 𝑠 ( ) ⌠ 𝜒(𝜈)e2i𝜋𝜈(𝑡− 2𝐵 ) d𝜈
2𝐵 𝑛∈Z 2𝐵 ⌡R
1 𝑛 2i𝜋𝜈𝑛
=⌠ ∑ 𝑠 ( ) e− 2𝐵 𝜒(𝜈)e2i𝜋𝜈𝑡 d𝜈,
⌡R 𝑛∈Z 2𝐵 2𝐵
𝑛 𝑛
⌠ ∑ ∣𝑠 ( )∣ ⋅ ∣𝜒(𝜈)∣ d𝜈 = (∑ ∣𝑠 ( )∣) ⋅ (⌠ ∣𝜒(𝜈)∣ d𝜈) < +∞.
⌡R 𝑛∈Z 2𝐵 𝑛∈Z
2𝐵 ⌡R
Donc :
̃ = ⌠ 𝑔(𝜈)𝜒(𝜈)e2i𝜋𝜈𝑡 d𝜈,
𝑠(𝑡)
⌡R
avec :
1 𝑛 2i𝜋𝜈𝑛
𝑔(𝜈) = ∑ 𝑠 ( ) e− 2𝐵 ,
𝑛∈Z
2𝐵 2𝐵
ou encore, d’après le lemme 1.4 :
𝑔(𝜈) = ∑ 𝑠(𝜈
̂ + 2𝑗 𝐵),
𝑗∈Z
Dans le cadre temporel, ce théorème nous dit que si un signal n’a pas de
fréquence plus haute que 𝐵 hertz, alors il est complètement déterminé par les
valeurs discrètes séparées de 1/2𝐵 seconde.
Ainsi le théorème de Shannon-Nyquist nous indique comment choisir une
fréquence d’échantillonnage lorsqu’on a des informations sur le support de la
transformée de Fourier du signal 9 considérée et comment le reconstruire.
Démontrons ce théorème.
Preuve : Définissons 𝜒 par la formule :
𝜒 = 1[−𝐵,𝐵] ,
2i𝜋𝜈𝑡 1 𝑛 𝑛
̃ = ⌠ 𝑠(𝜈)e
𝑠(𝑡) ̂ d𝜈 = ∑ 𝑠 ( ) ℎ (𝑡 − ),
⌡R 2𝐵 𝑛∈N 2𝐵 2𝐵
2i𝜋𝜈𝑡
⌠ 𝑠(𝜈)e
̂ d𝜈 = 𝑠(𝑡),
⌡R
ce qui achève la démonstration.
Lorsqu’on utilise le cadre des distributions tempérées (voir [2, 13]), alors
l’échantillonnage d’un signal 𝑠 revient à multiplier ce signal par un peigne de
Dirac.
Par abus de langage, cette distribution est souvent expliquée comme étant
une « fonction » qui vaut zéro partout, sauf en 0 où sa valeur infinie correspond
à une « masse » de 1.
À partir de cette distribution, on peut définir un outil important de traite-
ment du signal.
𝒟(R) → R
𝛿𝑎 ∶ .
𝜙 ↦ ⟨𝛿𝑎 , 𝜙⟩ ≝ 𝜙(𝑎)
+∞
𝑠𝑇 (𝑡) = ∑ 𝑠(𝑛𝑇 )𝛿𝑛𝑇 (𝑡),
𝑛=−∞
1 1
𝑂 𝑡 𝑂 𝑡
𝑂 𝑡
𝑇
Figure 1.5 – Phénomène de sous-échantillonnage.
Proposition 1.5 : Soit 𝑠 un signal stable et continu tel que la condition (1.4)
soit satisfaite. Alors le signal :
𝑛
̃ = ∑𝑠(
𝑠(𝑡) ) sinc ((2𝐵𝑇 − 𝑛)𝜋),
𝑛∈N
2𝐵
admet la représentation :
̂̃
̃ = ⌠ 𝑠(𝜈)e
𝑠(𝑡) 2i𝜋𝜈𝑡
d𝜈,
⌡R
avec :
̂̃ = (∑ 𝑠(𝜈
𝑠(𝜈) ̂ + 2𝑗𝐵)) 1[−𝐵,𝐵] (𝜈). (1.8)
𝑗∈Z
−𝑊−𝐵 𝐵 𝑊
̂ − 4𝐵) 𝑠(𝜈
𝑠(𝜈 ̂ − 2𝐵) ̂
𝑠(𝜈0𝐵) ̂ + 2𝐵) 𝑠(𝜈
𝑠(𝜈 ̂ + 4𝐵)
−4𝐵 −2𝐵 0𝐵 2𝐵 4𝐵
̂̃
𝑠(𝜈)
−𝑊−𝐵 𝐵 𝑊
10. En utilisant un vocabulaire plus proche de celui des ingénieurs, on dirait « numériser ».
∀𝜈 ∈ [−𝑊 , 𝑊 ], 𝜒(𝜈) = 1,
et
∀𝜈 ∈ R − [−𝐵, 𝐵], 𝜒(𝜈) = 0,
où nous ne disons rien entre sur ] − 𝐵, −𝑊 [ et sur ]𝑊 , 𝐵[.
Alors, le théorème de Shannon-Nyquist s’applique et en en reproduisant
la preuve, on obtient :
1 𝑛 𝑛
𝑠(𝑡) = ∑ 𝑠 ( ) ℎ (𝑡 − ),
2𝐵 𝑛∈Z 2𝐵 2𝐵
Chapitre
Quantification scalaire des signaux
discrets
Sommaire du chapitre
2.1 Introduction . . . . . . . . . . . . . . . . . . 38
2.2 Formulation mathématique . . . . . . . . . . 39
2.2.1 Cadre . . . . . . . . . . . . . . . . . 39
2.2.2 Erreur de distorsion de quantification 40
2.2.3 Taux de quantification . . . . . . . . 40
2.3 Quantification uniforme . . . . . . . . . . . . 41
2.3.1 Quantification uniforme des sources
uniformes . . . . . . . . . . . . . . . 42
2.3.2 Quantification uniforme des sources
non-uniformes . . . . . . . . . . . . . 43
2.4 Quantification adaptative . . . . . . . . . . . 44
2.4.1 Approches online et offline . . . . . . 45
2.4.2 Quantification adaptative directe – of-
fline . . . . . . . . . . . . . . . . . . 45
2.4.3 Quantification adaptative rétrograde
– online . . . . . . . . . . . . . . . . 46
2.5 Quantification non-uniforme . . . . . . . . . 47
2.6 Note bibliographique . . . . . . . . . . . . . 48
Remarque 2.1 :
Ce chapitre n’est pas au programme du cours, il est là à titre d’information
pour satisfaire la curiosité des plus curieux et curieuses.
37
CHAPITRE 2. QUANTIFICATION SCALAIRE DES SIGNAUX
DISCRETS
2.1 Introduction
Après avoir échantillonné un signal analogique, on dispose d’un signal
discret, c’est-à-dire une suite de nombres réels. À ce stade, la conversion
analogique-numérique (souvent désignée par CAN ) n’est pas encore achevée.
Il nous faut encore transformer une suite de nombres réels en une suite de 0
et de 1. C’est l’objet de ce chapitre.
On considère donc une source 1 émettant un signal discret en temps. La
transformation des nombres émis en suite de nombres binaires consiste en
fait en deux opérations : le codage et le décodage.
Coder, ou encoder un signal, c’est appliquer à chacun des termes de la
suite qu’il constitue une fonction de la forme :
où :
— l’ensemble {𝐼𝑛 }0≤𝑛≤𝑁 est une famille d’intervalles disjoints formant
une partition de l’intervalle [−𝑀 , 𝑀 ] (𝑁 est un entier naturel),
— 𝑠(𝑡) est un réel, représentant la valeur du signal 𝑠 à l’instant 𝑡, sup-
posé appartenir à l’intervalle [−𝑀 , 𝑀 ] (𝑀 est un réel, qui peut être
inconnu).
L’encodage est donc une opération irréversible car faisant intervenir une
fonction non-injective, qui entraîne une perte d’information.
Un exemple courant est la quantification sur 3 bits. Dans ce cas, l’intervalle
[−𝑀 , 𝑀 ] est partitionné en 𝑁 = 23 = 8 intervalles.
Décoder un signal, c’est réaliser l’opération inverse, c’est-à-dire appliquer
à chacun des termes d’une suite d’intervalles une fonction de la forme :
𝐼𝑛 → 𝑦𝑛 ,
Remarque 2.2 :
Les valeurs 𝑦𝑛 sont ensuite elles-même codées par des entiers binaires.
1s
2.2.1 Cadre
On considère donc une source émettant un signal aléatoire 𝑆 de densité de
probabilité 𝑓𝑆 ∈ 𝐿1 (R). Pour construire une quantification, il faut donc définir
une famille d’intervalles (i.e. la famille {𝐼𝑛 }0≤𝑛≤𝑁 de l’introduction), donc de
frontières, et de valeurs d’assignation (i.e. les valeurs 𝑦𝑛 de l’introduction).
Pour fixer les idées conservons les notations de l’introduction et désignons
par 𝑁 le nombre d’intervalles constituant la partition et donc également le
nombre de valeurs d’assignations. Le nombre de valeurs frontières, aussi
appelées valeurs de décision, que l’on note 𝑏𝑖 est alors 𝑁 + 1. On pose a priori
𝑏0 = −∞ et 𝑏𝑁 = +∞ et on signalera dans la suite les cas où l’on adopte
une autre convention. La fonction de quantification s’écrit :
𝑄(𝑥) = 𝑦𝑛 ,
Problème 1
Si l’on se donne une contrainte de distorsion de quantification
𝜎𝑞 ≤ 𝜎⋆ , (2.4)
Problème 2
Si l’on se donne une contrainte sur le taux
𝑅 ≤ 𝑅⋆ , (2.5)
Remarque 2.3 :
L’une où l’autre de ces formulations constitue un problème plus général
que celui que nous allons considérer dans ce chapitre. On se restreint en
effet dans la suite à de codage de tailles fixes, si bien que 𝑅 est constant
par rapport à 𝐵 et 𝑌. Le problème du codage en taille variable sera quant
à lui traité au chapitre 3.
𝜎𝑥2
𝑆𝑁 𝑅 = 10 log10 ( ),
𝜎𝑞2
𝜎𝑥2
𝑆𝑁 𝑅 = 10 log10 ( )
𝜎𝑞2
(2𝑆max )2 12
= 10 log10 ( × )
12 2𝑆
( 𝑁max )
2
(2.6)
= 10 log10 (𝑁 2 )
= 20 log10 (2𝑘 )
= 6.02𝑘 dB,
Remarque 2.4 :
Dans ce cas, on peut en fait distinguer deux types d’erreurs de quantifica-
tion :
1. L’erreur de surcharge, qui correspond aux erreurs se produisant
dans les deux intervalles extrêmes. On parle également de bruit
de saturation.
2. L’erreur granulaire, qui correspond à l’erreur de quantification
dans les autres intervalles. On parle alors de bruit granulaire.
1 𝑀 −1 2
𝜎𝑥2̂ = ∑ 𝑥 ,
𝑀 𝑖=0 𝑖+𝑛
où on a supposé que notre signal d’entrée avait une valeur moyenne nulle.
Pour quantifier le bloc considéré, une stratégie possible est alors de consi-
dérer une densité de probabilité 𝑓𝑆 pour le bloc considéré du signal qui par
exemple peut être une gaussienne avec pour variance la variance empirique
précédemment calculée et utiliser la stratégie uniforme indiquée à la sec-
tion 2.3.2.
Évidemment d’autres raffinements sont possible mais dépasse le cadre de
cette introduction à la quantification.
𝑀𝑘 = 𝑀𝑘+𝑁 /2 ,
Chapitre
Codage sans perte de l’informa-
tion
Sommaire du chapitre
3.1 Codage source et compression sans perte . . 50
3.1.1 Définitions . . . . . . . . . . . . . . . 50
3.1.2 Entropie et mesure de la quantité d’in-
formation . . . . . . . . . . . . . . . 51
3.1.3 Propriétés d’un codage source . . . . 54
3.1.4 Algorithme de Huffman . . . . . . . . 60
3.2 Codage canal et correction d’erreur . . . . . 64
3.2.1 Une approche naïve . . . . . . . . . . 65
3.2.2 Codes linéaires par blocs . . . . . . . 66
3.2.3 Détection et correction d’erreur . . . 70
3.2.4 Syndrôme et matrice de vérification . 73
3.2.5 Codes de Hamming . . . . . . . . . . 76
3.3 Notes bibliographiques . . . . . . . . . . . . 79
49
CHAPITRE 3. CODAGE SANS PERTE DE L’INFORMATION
code de Hamming qui permet de détecter deux erreurs par mot transmis et
d’en corriger une.
3.1.1 Définitions
On commence par poser deux définitions.
1. David Albert Huffman (9 août 1925 — 7 octobre 1999, Ohio), chercheur américain
pionnier dans le domaine de l’informatique.
2. L’alphabet français lui comporte l’alphabet latin morderne de 26 lettres auxquelles il
faut ajouter les lettres accentuées au nombre de 13, le c cédille et deux ligutares, e-dans-l’a
et e-dans-l’o, pour un total de 42 !
Remarque 3.1 :
Notons que le débit de la source 𝑆𝑘 est 𝑘 fois moins élevé que celui de
la source initiale 𝑆. De plus, si 𝑆 est une source de symboles 𝑚-aire,
l’alphabet de la source 𝑆𝑘 sera de taille 𝑚𝑘 .
Exemple
Soit 𝐴 = {𝑠1 , … , 𝑠𝑚 } un alphabet et 𝑆 une source emettant dans cet alphabet,
c’est-à-dire un enchaînement de 𝑠𝑖 de l’alphabet, par exemple :
𝑆 = 𝑠2 𝑠4 𝑠8 𝑠5 𝑠1 𝑠9 𝑠2 𝑠2 𝑠3 …
source, par exemple si l’on sait que la source émet des mots dans une certaine
langue écrite.
Notons ℎ la quantité d’information — que nous n’avons pas encore définie
— apportée par un symbole 𝑥 ∈ 𝐴. Faisons une liste des propriétés de ℎ
attendues.
1. Tout d’abord, on souhaite que la quantité d’information apportée par
l’émission d’un symbole 𝑥 augmente lorsque la probabilité d’émission
de 𝑥, notée 𝑝(𝑥) dans la suite, diminue, ce qui peut se modéliser par
1
ℎ(𝑥) = 𝑓 ( ),
𝑝(𝑥)
où 𝑓 est un fonction croissante.
2. Si la probabilité d’émission d’un symbole est 1, alors celui-ci n’apporte
aucune information, on peut alors imposer
𝑓(1) = 0.
3. On souhaite enfin que la quantité d’information apportée par deux
messages indépendants soit la somme des quantités d’information
apportées par chacun des messages. On peut alors demander à 𝑓 de
vérifier
1 1 1 1
𝑓( ) = 𝑓( ) = 𝑓( ) + 𝑓( ).
𝑝(𝑥 et 𝑦) 𝑝(𝑥) ⋅ 𝑝(𝑦) 𝑝(𝑥) 𝑝(𝑦)
Ces différentes propriétés impliquent que la fonction ℎ doit être choisie de la
forme :
ℎ(𝑥) = − log𝑞 (𝑝(𝑥)).
La base 𝑞 n’est pas fixée a priori. Nous verrons plus tard que on la choisira
en fonction de la « dimension » de codage que on va utiliser.
et 𝑛 𝑛
∑ 𝑝𝑖 = 1, ∑ 𝑞𝑖 ≤ 1.
𝑖=1 𝑖=1
Alors : 𝑛
𝑞
∑ 𝑝𝑖 log𝑞 ( 𝑖 ) ≤ 0,
𝑖=1
𝑝𝑖
avec égalité si et seulement si
∀𝑖, 0 ≤ 𝑖 ≤ 𝑛, 𝑝𝑖 = 𝑞 𝑖 .
Exercice 3.1 :
Montrer ce lemme pour le logarithme népérien.
avec égalité dans le cas où tous les symboles de 𝑆 sont équiprobables, c’est-à-
dire que pour tout 𝑖 ∈ {1, … , 𝑚}, 𝑝𝑖 = 1/𝑚.
5. Johan Ludwig William Valdemar Jensen, surtout connu comme Johan Jensen, (8 mai
1859, Nakskov, Danemark - 5 mars 1925, Copenhague, Danemark) était un mathématicien
et ingénieur danois. Il est surtout connu pour sa fameuse inégalité de Jensen. En 1915, il
démontra également la formule de Jensen en analyse complexe.
Exercice 3.2 :
Montrer cette proposition.
Arbre 𝑞−aire
6. Cette inégalité fut publiée pas Leon Kraft en 1949. Dans l’article correspondant Kraft
ne considère que les codes auto-ponctués et attribue l’analyse qu’il présente pour obtenir son
résultat à Raymond M. Redheffer. Cette inégalité est aussi parfois appelée « Théorème de
Kraft-McMillan » après que Brockway McMillan l’a découverte indépendamment en 1956.
McMillan prouve le résultat pour une classe plus large de codes et attribue quant à lui la
version correspondant aux codes auto-ponctués de Kraft à des observations de Joseph Leo
Doob en 1955.
Preuve : Soit 𝒜 un arbre 𝑞-aire. On note ℒ(𝒜) l’ensemble de ses feuilles et 𝑑(ℓ) la
profondeur de la feuille ℓ ∈ ℒ(𝒜).
𝒜 est un arbre 𝑞-aire, ainsi, on peut considérer 𝑞 sous arbres 𝒜1 , … , 𝒜𝑞 de 𝒜,
chacun d’eux étant lui-même un arbre 𝑞-aire. On note alors 𝒜 = 𝒩(𝒜1 , … , 𝒜𝑞 ) le
l’assemblage des sous-arbres avec la racine de 𝒜. On va procéder par récurrence.
Si 𝒜 n’a qu’une seule feuille, la profondeur de cette est 𝑑(ℓ) = 0 et ℒ(𝒜) = 1 7 .
L’inégalité de Kraft est alors vérifiée.
Supposons maintenant que 𝒜 = 𝒩(𝒜1 , … , 𝒜𝑞 ) où chaque 𝒜𝑖 vérifie l’ιnégalité
de Kraft. On a alors :
𝑞 𝑞
′ (ℓ)−1
∑ 𝑞 −𝑑(ℓ) = ∑ ∑ 𝑞 −𝑑(ℓ) = ∑ ∑ 𝑞 −𝑑 ,
ℓ∈ℒ(𝒜) 𝑖=1 ℓ∈ℒ(𝒜𝑖 ) 𝑖=1 ℓ∈ℒ(𝒜𝑖 )
où on a noté 𝑑′ (ℓ) la profondeur de la feuille ℓ dans les sous arbres. Puisque les sous
arbres vérifient l’inégalité de Kraft, on a :
′ (ℓ)
∑ 𝑞 −𝑑 ≤ 1,
ℓ∈ℒ(𝒜𝑖 )
et donc : 𝑞
−𝑑(ℓ) −1 ′ (ℓ)
∑ 𝑞 ≤𝑞 ∑ ∑ 𝑞 −𝑑 ≤ 𝑞 −1 𝑞 = 1.
ℓ∈ℒ(𝒜) 𝑖=1 ℓ∈ℒ(𝒜𝑖 )
Cet algorithme permet de construire un arbre 𝑞-aire dont les feuilles sont situées à
des profondeurs (𝑛𝑖 )1≤𝑖≤𝑚 . En voici les justifications :
— On ne supprime jamais un noeud marqué dans la procédure puisque lors-
qu’on fabrique la feuille de profondeur 𝑛𝑖 , on ne supprime que des nœuds de
profondeur strictement supérieure à 𝑛𝑖 car on a ordonné les 𝑛𝑖 .
— À l’étape 𝑖, il existe bien un nœud non marqué de profondeur 𝑛𝑖 . En effet, pour
une étape 𝑗, l’algorithme supprime ou marque (si on a une feuille) 𝑞 𝑛𝑚 −𝑛𝑗 .
Ainsi, à l’étape 𝑖, on a supprimé ou marqué :
𝑖 𝑖
∑ 𝑞 𝑛𝑚 −𝑛𝑗 = 𝑞 𝑛𝑚 ∑ 𝑞 −𝑛𝑗 .
𝑗=1 𝑗=1
et donc
𝑖
∑ 𝑞 𝑛𝑚 −𝑛𝑗 < 𝑞 𝑛𝑚 .
𝑗=1
Or :
— 𝐻(𝑆) = − ∑𝑚 𝑖=1 𝑝𝑖 log𝑞 𝑝𝑖 ,
— ∑𝑚 𝑝
𝑖=1 𝑖 = 1,
— ∑𝑚 ̄
𝑖=1 𝑝𝑖 𝑛𝑖 = ℓ, la longueur moyenne d’un mot du nouveau code.
Finalement, on trouve :
𝐻(𝑆) ≤ ℓ.̄
Nous avons donc obtenu la borne théorique de compression annoncée dans l’introduc-
tion de cette section.
Montrons maintenant qu’on peut s’approcher aussi près que l’on veut de cette
borne. On cherche à minimiser ℓ.̄ Pour ce faire, on peut essayer d’approcher le cas
d’égalité dans les inégalités de Kraft et de Gibbs utilisées, c’est-à-dire à avoir :
𝑄 = 1, 𝑞 −𝑛𝑖 = 𝑝𝑖 ,
𝐻(𝑆) ≤ ℓ ̄ ≤ 𝐻(𝑆) + 1.
𝑆𝑘 . Si on considère les symboles comme des variables aléatoires prenant des valeurs
dans 𝐴 = {𝑠1 , … , 𝑠𝑚 }, alors
ℓ𝑘̄ = ∑ 𝑝(𝑥1 , … , 𝑥𝑘 )𝑛(𝑥1 , … , 𝑥𝑘 )
𝑥1 ,…,𝑥𝑘
où la somme est sur toutes les combinaisons possibles, et 𝑝 est la probabilité d’avoir la
combinaison et 𝑛 la longueur de codage de cette suite de symboles. Pour cette source
là, on applique le théorème que l’on vient d’obtenir, et on obtient :
𝐻(𝑆𝑘 ) ≤ ℓ𝑘̄ ≤ 𝐻(𝑆𝑘 ) + 1,
où ℓ𝑘̄ représente la longueur moyenne des mots du nouveau codage de 𝑆𝑘 . On divise
alors ces inégalités par 𝑘 :
𝐻(𝑆𝑘 ) ℓ̄ 𝐻(𝑆𝑘 ) 1
≤ 𝑘 ≤ + .
𝑘 𝑘 𝑘 𝑘
ℓ𝑘̄ 𝐻(𝑆𝑘 )
La quantité 𝑘 est alors notre longueur moyenne pour la source 𝑆 et notons ℋ = 𝑘 .
On a alors
1 1
ℋ= ∑ 𝑝(𝑥1 , … , 𝑥𝑘 ) log𝑞 ( )
𝑘 𝑥 ,…,𝑥 𝑝(𝑥1 , … , 𝑥𝑘 )
1 𝑘
1 1
= E [log𝑞 ( )]
𝑘 𝑝(𝑋1 , … , 𝑋𝑘 )
où on a noté 𝑋𝑘 les variables aléatoires du processus et E(𝑋) = ∑𝑖 𝑥𝑖 𝑝𝑖 . Dans ce
cours, on ne considère que des sources sans mémoire, et donc les symboles sont
indépendants, ainsi 𝑝(𝑥1 , … , 𝑥𝑘 ) = 𝑝(𝑥1 )𝑝(𝑥2 ) ⋯ 𝑝(𝑥𝑘 ) et donc
𝑘
1 1
ℋ= E ⎡log𝑞 ( ∏ )⎤
𝑘 ⎣ 𝑖=1
𝑝(𝑋𝑖 ) ⎦
1 𝑘 1
= ∑ E [log𝑞 ( )]
𝑘 𝑖=1 𝑝(𝑋𝑖 )
1 𝑘
= ∑𝐻
𝑘 𝑖=1
= 𝐻.
Remarque 3.2 :
Nous avons démontrer ce résultat dans le cas d’une source sans mémoire,
mais on peut aussi montrer que ℋ ≤ 𝐻 dans le cas d’une source avec
mémoire.
Remarque 3.3 :
Évidemment, approcher cette limite a un certain coût ! En effet, la tech-
nique de codage considérée implique à un moment ou à un autre la trans-
mission d’un dictionnaire permettant le décodage pour retrouver les sym-
boles émis initialement. Si l’on code les extensions de 𝑆 au lieu de 𝑆
elle-même, la taille du dictionnaire va augmenter et ce exponentiellement
par rapport à l’extension considérée.
sur l’ensemble des longueurs {𝑛𝑖 }𝑖∈{1,…,𝑚} et sous la contrainte donnée par
l’inégalité de Kraft :
𝑚
∑ 𝑞 −𝑛𝑖 ≤ 1.
𝑖=1
que l’on différentie par rapport aux 𝑛𝑖 . Un rapide calcul donne les longueurs
optimales 𝑛∗𝑖 = − log2 (𝑝𝑖 ), c’est-à-dire une longueur moyenne égale à l’en-
tropie. Bien évidemment, ces longueurs optimales ne sont pas des longueurs
entières. Le but de cette section est de présenter un algorithme qui permet
d’approcher cette limite.
L’algorithme
Il nous reste à donner une méthode permettant la mise en pratique du
résultat théorème 3.1 (qui n’est pas constructif). C’est l’algorithme 2, dit de
Huffman, qui fournit ce résultat à partir d’une source de 𝑚 symboles, dont
on connaît les probabilités (𝑝𝑖 )1≤𝑖≤𝑚 d’émission. En pratique cet algorithme
explique comment construire un arbre de codage.
Soit 𝑇 un arbre binaire de 𝑛 feuilles dont les poids respectifs sont notés
𝑝𝑖 et les profondeurs ℓ𝑖 . Montrons que l’algorithme de Huffman minimise la
longueur moyenne ∑𝑖 ℓ𝑖 𝑝𝑖 dans le cas d’un arbre binaire.
Lemme 3.3 Soit 𝑇 un arbre optimal, alors l’arbre 𝑇 n’a aucun nœud qui
n’a qu’un seul descendant.
(non vide), alors on obtient un arbre 𝑇 ’ dont la longueur est strictement inférieur.
Impossible puisque l’arbre 𝑇 est optimal.
𝐵(𝑇 ’) = 𝐵(𝑇 ) − 𝑝𝑥 ℓ𝑥 − 𝑝𝑏 ℓ𝑏 + 𝑝𝑥 ℓ𝑏 + 𝑝𝑏 ℓ𝑥
= 𝐵(𝑇 ) − (𝑝𝑏 − 𝑝𝑥 )(ℓ𝑏 − ℓ𝑥 )
⩽ 𝐵(𝑇 ).
Comme l’arbre 𝑇 est optimal, 𝐵(𝑇 ’) = 𝐵(𝑇 ), ainsi 𝑇 ’ est aussi optimal. On fait de
même en échangeant 𝑐 et 𝑦 et on obtiont un nouvel arbre 𝑇 ’’, toujours optimal, qui
vérifie la condition voulue.
Exercice 3.3 :
On considère une source 𝑆 composée des états {𝑠1 , 𝑠2 , … , 𝑠8 } avec la
distribution de fréquence suivante que l’on veut coder en binaire :
𝑠1 𝑠2 𝑠3 𝑠4 𝑠5 𝑠6 𝑠7 𝑠8
0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.04
Remarque 3.4 :
En ayant calculé l’entropie de la source 𝑆, on peut établir une prescription
d’un objectif pour la taille moyen du code ℓ.̄ Si l’objectif de longueur
moyenne n’est pas atteint, alors il suffit de reprendre l’algorithme avec
une extension d’ordre plus élevée du code.
ℓ ̄ = 1 × 1/4 + 1 × 3/4 = 1.
0 1
0.44 𝑠𝑠 0.56
0 1
𝑠𝑐 0.19 0.25
0 1
𝑐𝑐 0.06 𝑐𝑠 0.19
𝑐𝑐 → 010, 𝑐𝑠 → 011, 𝑠𝑐 → 00 et 𝑠𝑠 → 1.
ce qui donne
ℓ∗̄ = 0.5 × ℓ2̄ < ℓ.̄
0 → 00,
1 → 11,
on pourra facilement détecter une erreur (si les symboles reçus ne coïncident
pas deux à deux). Par contre, on ne pourra corriger l’erreur correctement
qu’une fois sur deux en moyenne, en choisissant arbitrairement de remplacer
la séquence erronée détectée par un 0, par exemple.
Dans cette démarche, on a ajouté un bit de correction par bit transmis. Si on
choisit maintenant d’en ajouter deux, en adoptant une stratégie de triplement,
on constate que la correction sera plus efficace : on remplacera une séquence
erronée, par exemple 001, par le signe apparaissant majoritairement 8 dans
le triplet, 0 dans notre exemple. Cette méthode permet de détecter deux
erreurs par bloc de trois bits et d’en corriger une : en effet, si deux erreurs
affectent, lors de la transmission la séquence de trois bits, alors la stratégie
8. On parle parfois de stratégie du vote majoritaire.
choisie donnera lieu, lors du décodage, à une erreur. Pour aller plus loin, on
peut regarder l’exemple d’un canal introduisant 5% d’erreurs, avec lequel
on applique la stratégie du triplement. Puisqu’une erreur est corrigée, la
probabilité qu’une séquence de trois bits soit transmise correctement ou avec
une seule erreur est de :
𝑝 = 0, 953 + 3 × 0, 952 × 0, 005 = 0, 99275.
Ainsi le taux de succès est passé de 95% à un taux supérieur 99%. Évidem-
ment, ceci a un coût ! Il a en effet fallu tripler la taille du signal à transmettre.
On va voir dans la suite comment « optimiser » l’usage des bits de correc-
tion.
Remarque 3.5 :
— Le plus petit corps fini est noté F2 . Il est composé de deux éléments
distincts, 0 qui est l’élément neutre pour l’addition, et 1 qui est
élément neutre pour la multiplication. Ceci détermine les tables de
ces deux opérations en dehors de 1 + 1 qui ne peut alors être que
0, car 1 doit avoir un opposé. On vérifie alors qu’elles définissent
bien un corps commutatif.
+ 0 1 × 0 1
0 0 1 0 0 0
1 1 0 1 0 1
Le corps F2 peut s’interpréter diversement. C’est l’anneau Z/2Z,
les entiers pris modulo 2, c’est-à-dire que 0 représente les entiers
pairs, 1 les entiers impairs (c’est le reste de leur division par 2),
et les opérations se déduisent de celles sur Z.
C’est aussi l’ensemble des valeurs de vérité classiques, 0 pour le
faux, et 1 pour le vrai. L’addition est le « ou exclusif » (xor), la
multiplication le « et ».
Définition 3.7 — (Poids d’un mot) On définit le poids d’un mot 𝑚 de F𝑘2
comme le nombre de composantes non nulles du mot. On le notera 𝑤(𝑚).
On peut montrer, mais nous ne le ferons pas ici, que cette distance de
Hamming 10 est bien une distance au sens mathématique du terme.
On a par exemple :
𝑑(111, 101) = 1.
Une propriété intéressante de cette distance est qu’elle vérifie :
où :
0F𝑛 = (0,
⏟ … , 0).
2
𝑛 fois
Autrement dit, pour connaître la distance entre deux mots, il suffit de les
additionner et de compter le nombre de composantes égales à 1 dans le résultat.
Derrière cette notion de distance, se cache une stratégie de correction : étant
donné que les mots du code ne forment qu’une sous-partie de F𝑛2 , lorsqu’on
reçoit en sortie de canal un mot ne figurant pas dans l’ensemble des mots
possible, on le remplace par le mot du code le plus proche.
Code
Dans le cadre que l’on vient d’introduire, l’ajout de 𝑟 bits de correction
peut être vu comme l’application d’une certaine fonction injective :
𝑔 ∶ F𝑘2 → F𝑛2 ,
𝑚′ = 𝑚𝐺,
Exemple
Un exemple particulièrement simple est le bit de parité : on ajoute à la fin
du message un bit correspondant à la parité de la somme des éléments du
message. Si la somme est paire, alors le bit vaut 0 et 1 sinon. Pour un mot
de longueur 𝑘, le code associé a donc pour paramètres (𝑘, 𝑘 + 1).
𝑑𝐶 = min {𝑑(𝑚1 , 𝑚2 ); 𝑚1 ∈ 𝐶, 𝑚2 ∈ 𝐶, 𝑚1 ≠ 𝑚2 } .
𝑑𝐶 = min {𝑤(𝑚); 𝑚 ∈ 𝐶, 𝑚 ≠ 0} .
Exercice 3.4 :
Écrire la preuve.
𝑑𝐶 ≤ 𝑛 − 𝑘 + 1.
Exercice 3.5 :
Écrire la preuve (indication : faire un raisonnement sur les dimensions
des espaces).
Le lemme suivant donne une méthode simple pour calculer la distance d’un
code.
Lemme 3.5 La distance d’un code est égale au nombre de 1 contenus dans
le mot non nul du code qui en contient le moins.
Preuve : Ce lemme est une conséquence directe de la formule (3.1). En effet, puisque
𝐶(𝑘, 𝑛) est un espace vectoriel, on a :
𝑚∗ = 𝑚′ + 𝑒,
𝑑(𝑚1 , 𝑚2 ) ⩽ 𝑡 + 𝑡 ⩽ 2𝑡 + 𝑠,
et donc 𝑑𝐶 qui est inférieur ou égale à 𝑑(𝑚1 , 𝑚2 ) est aussi inférieure ou égale à 2𝑡 + 𝑠.
Ensuite, si le code peut corriger tous les schémas de moins de 𝑡 erreurs mais
ne peut pas détecter tous les schémas à 𝑡 + 1, … , 𝑡 + 𝑠 il existe au moins un mot
de code 𝑚1 et schéma d’erreur 𝑒 de poids entre 𝑡 + 1 et 𝑡 + 𝑠 qui ne sont pas
détectés mais décodé en un autre mot du code 𝑚2 = 𝒟(𝑚1 + 𝑒). En introduisant
l’erreur 𝑒′ = 𝑚2 + (𝑚1 + 𝑒), nous avons aussi 𝒟(𝑚2 + 𝑒′ ) = 𝑚2 , c’est-à-dire que
𝑒′ est une erreur qui est corrigée lorsqu’elle est appliquée à 𝑚2 . Comme 𝑤(𝑒′ ) =
𝑑(𝑚2 + 𝑒′ , 𝑚2 ) = 𝑑(𝑚1 + 𝑒, 𝑚2 ) ⩽ 𝑑(𝑚1 + 𝑒, 𝑚1 ) = 𝑤(𝑒) (puisque le décodage est
à distance minimale), nous avons 𝑤(𝑒′ ) ⩽ 𝑡 + 𝑠. Comme 𝑒′ est une erreur qui est
corrigée, alors 𝑤(𝑒′ ) ⩽ 𝑡. On conclut alors
et donc 𝑑𝐶 ⩽ 2𝑡 + 𝑠.
Réciproquement, supposons que 𝑑𝐶 ⩽ 2𝑡 + 𝑠. Il existe donc deux mots du code
𝑚1 et 𝑚2 tels que 𝑑(𝑚1 , 𝑚2 ) ⩽ 2𝑡 + 𝑠. Ceci signifie aussi que le poids du vecteur
Pour illustrer ce résultat, considérons un code par bloc ayant une distance
minimale de 8. Un tel code peut être utilisé pour l’un ou l’autre des points
suivants :
— corriger tous les schémas d’erreur de moins que 3 (inclus) erreurs et
détecter tous les schémas à 4 erreurs (𝑡 = 3, 𝑠 = 1) ;
— corriger tous les schémas d’erreur de moins que 2 erreurs et détecter
tous les schémas de 3 à 5 erreurs (𝑡 = 2, 𝑠 = 3) ;
— corriger tous les schémas d’erreur de 1 erreur et détecter tous les
schémas de 2 à 6 erreurs (𝑡 = 1, 𝑠 = 5) ;
— détecter tous les schémas de moins que 7 (inclus) erreurs (𝑡 = 0,
𝑠 = 7).
Un code par bloc ayant une distance minimale de 7 peut (l’un ou l’autre) :
— corriger tous les schémas d’erreur de moins que 3 (inclus) erreurs
(𝑡 = 3, 𝑠 = 0) ;
— corriger tous les schémas d’erreur de moins que 2 erreurs et détecter
tous les schémas de 3 à 4 erreurs (𝑡 = 2, 𝑠 = 2) ;
— corriger tous les schémas d’erreur de 1 erreur et détecter tous les
schémas de 2 à 5 erreurs (𝑡 = 1, 𝑠 = 4) ;
— détecter tous les schémas de moins que 6 (inclus) erreurs (𝑡 = 0,
𝑠 = 6).
Du théorème précédent, on obtient les deux résultats suivants.
Remarque 3.6 :
La théorie de l’algèbre linéaire montre qu’une telle application existe,
il suffit par exemple de considérer un projecteur a sur un sous-espace
supplémentaire de 𝐶(𝑘, 𝑛) parallèlement à 𝐶(𝑘, 𝑛). Notons qu’un code
linéaire donné pourrait avoir plusieurs matrices de vérification différentes :
toute matrice dont les lignes sont une base de l’espace vectoriel orthogonal
au code linéaire est une matrice de vérification pour ce code.
puisque 𝑚 ∈ Ker(𝐻).
Remarque 3.7 :
— Si seul une erreur s’est produite sur la composante 𝑖 de 𝑚′ , alors
le syndrome sera égal à la 𝑖-ème colonne de 𝐻.
— On note ici 𝐻𝑚 au lieu de 𝑚𝐻 𝑇 car cela facilitera l’écriture du
prochain théorème.
— Les définitions précédentes ne disent pas comment trouver en
pratique les matrices de vérifications ce qui sera l’objet de ce qui
suit.
𝐺 = [𝐼𝑘 𝑃 ]
la matrice
𝐻 = [−𝑃 ⊤ 𝐼𝑛−𝑘 ]
est une matrice de vérification.
Preuve : Pour tout message 𝑚 ∈ F𝑘2 , le mot de code 𝑧 ∈ F𝑛2 correspondant est
𝑧 = 𝑚 ⋅ 𝐺 = 𝑚 ⋅ [𝐼𝑘 𝑃 ],
c’est-à-dire
(𝑧1 , … , 𝑧𝑘 ) = 𝑚,
{
(𝑧𝑘+1 , … , 𝑧𝑛 ) = 𝑚 ⋅ 𝑃 .
Ainsi
(𝑧𝑘+1 , … , 𝑧𝑛 ) = (𝑧1 , … , 𝑧𝑘 ) ⋅ 𝑃 ,
𝑧 = (𝑧1 , … , 𝑧𝑘 ) ⋅ 𝐺
Remarque 3.8 :
On notera qu’il est fait mention de la matrice −𝑃 𝑇 . Le signe − est là
car, même s’il n’a pas été défini sur l’espace F2 , il provient de la preuve,
et le résultat s’étend à des espaces vectoriels autre que F2 . Pour notre
cas, c’est-à-dire le cas binaire, le signe − est comme le signe +, en effet
1 − 1 = 0 = 1 + 1 en binaire, et 0 − 1 = 0 + 1 = 1.
Exercice 3.6 :
Soit le code 𝐶 dont la matrice génératrice est
1 0 1 0 1
𝐺=( ).
0 1 1 1 1
Preuve : Pour tout vecteur 𝑧 ∈ F𝑛2 , 𝐻 ⋅𝑧 est une combinaison linéaire de 𝑤(𝑧) colonnes
de 𝐻. Par définition, 𝑧 ∈ 𝐶(𝑘, 𝑛) si et seulement si 𝐻 ⋅ 𝑧 = 0. Ainsi, si 𝑧 ∈ 𝐶(𝑘, 𝑛), il
existe 𝑤(𝑧) colonnes de 𝐻 qui sont linéairement dépendantes. Réciproquement, si 𝑞
colonnes de 𝐻 sont linéairement dépendantes, il existe un mot du code de poids 𝑞.
Donc 𝑑𝐶 est le nombre minimal de colonnes de 𝐻 qui sont linéairement dépendantes
en vertu de la proposition 3.3.
On se place dans le cadre simple où au plus une erreur peut affecter les
mots (de longueur 𝑛) du code. Il y a donc 𝑛 + 1 scenari possibles : soit il n’y a
pas eu d’erreur pendant la transmission, soit une erreur s’est produite sur l’un
des 𝑛 bits. Or, d’après les dimensions des espaces considérés, 2𝑟 syndromes
possibles, puisque 𝐻𝑒 ∈ F𝑟2 . Si l’on veut pouvoir faire correspondre de manière
sûre, c’est-à-dire par le biais d’une injection, les vecteurs syndromes observés
et le scénario dont il est la conséquence, il faut nécessairement :
2𝑟 ⩾ 𝑛 + 1.
2𝑟 = 𝑛 + 1. (3.2)
D’autre part, on a :
𝑛 = 𝑘 + 𝑟. (3.3)
Enfin, on prend 𝑘 ⩾ 1, car on travaille sur des blocs de longueur non
nulle ! En cherchant quels sont les 𝑘 pour lesquels (3.2) et (3.3) ont des
solutions (𝑘, 𝑛) entières, on trouve par exemple :
𝑛 𝑘 𝑟
3 1 2
7 4 3
15 11 4
31 26 5
63 57 6
Par construction, ces matrices donnent bien un code linéaire et sont bien
de rang plein puisqu’il est aisé de construire la matrice indentité 𝐼𝑛−𝑘 à partir
des colonnes. La dimension du noyau est alors 𝑘.
Exemple
Soit la matrice de syndrôme du code de Hamming 𝐶(4, 7) :
0 0 0 1 1 1 1
𝐻 = ( 0 1 1 0 0 1 1 ).
1 0 1 0 1 0 1
𝑧1 = 1110000
𝑧2 = 1101001
𝑧3 = 1000011
𝑧4 = 1111111
ce qui donne
1 1 1 0 0 0 0
⎡1 1 0 1 0 0 1⎤
𝐺=⎢ ⎥
⎢1 0 0 0 0 1 1⎥
⎣1 1 1 1 1 1 1⎦
Supposons maintenant devoir envoyer le message 𝑚 = 1001. Il est codé
𝑧 = 𝑧 ̂ − 0010000.
Remarque 3.9 :
On peut montrer que pour un canal ayant une probabilité d’erreur de 5%,
la probabilité de transmettre correctement 4 bits est .954 ≈ 81%.
L’utilisation de 𝐶(4, 7) permet de faire passer cette valeur à (1 − 𝑝)7 +
7𝑝(1 − 𝑝)6 ≈ 95%. Ce résultat, comparable à la stratégie par triplement,
est en fait bien meilleur, car la taille des mots du code n’a même pas
doublé. Notons enfin qu’on peut rendre la probabilité d’erreur aussi faible
que l’on veut en appliquant un code correcteur plusieurs fois de suite.
Chapitre
Transformation de Fourier discrète
Sommaire du chapitre
4.1 La transformée de Fourier discrète (TFD) . 82
4.1.1 Cadre et problèmes . . . . . . . . . . 82
4.1.2 Propriétés de la TFD et signaux pé-
riodiques discrets . . . . . . . . . . . 83
4.2 L’algorithme FFT . . . . . . . . . . . . . . . 84
4.2.1 Nombres d’opérations pour le calcul
de la TFD . . . . . . . . . . . . . . . 84
4.2.2 L’algorithme de Tuckey et Cooley . . 85
4.3 Analyse numérique . . . . . . . . . . . . . . 88
4.4 Notes bibliographiques . . . . . . . . . . . . 88
1. John Wilder Tukey (16 juin 1915, New Bedford, Massachusetts - 26 juillet 2000,
New Brunswick, New Jersey. ) était un statisticien américain.
2. James Cooley (1926-2016) était un mathématicien americain.
81
CHAPITRE 4. TRANSFORMATION DE FOURIER DISCRÈTE
𝑠 = {𝑠0 , 𝑠1 , … , 𝑠𝑁 −2 , 𝑠𝑁 −1 },
obtenu à partir d’un signal analogique. également noté 𝑠, par une formule du
type :
𝑠𝑛 = 𝑠(𝑛Δ𝑡),
où Δ𝑡 est le pas de l’échantillonnage, relié à la fréquence d’échantillonnage
2𝐵 du chapitre 1 par l’équation :
1
Δ𝑡 = .
2𝐵
On ne tient pas compte ici du fait que le signal peut avoir été quantifié, c’est-
à-dire que les 𝑠𝑛 sont considérés a priori comme réels.
Comme toute transformée de Fourier, on voit que la TFD est une applica-
tion linéaire. Sa matrice est une matrice pleine, c’est-à-dire ne comportant pas
de 0, de type matrice de Vandermonde. On voit de plus que le pas de temps
utilisé n’apparaît pas dans la formule. On peut en quelque sorte considérer
que celui-ci est égal à 1. Ceci est en fait naturel : un signal discret est une
suite de nombres et seules des informations supplémentaires sur ce qu’elle
représente permettent de connaître la fréquence qui a été utilisée pour obtenir
l’échantillon.
1 𝑁 −1
𝑎𝑛 = ∑ 𝐴 𝜔−𝑛𝑚 .
𝑁 𝑚=0 𝑚 𝑁
Exercice 4.1 :
Prouver ce résultat.
Remarque 4.1 :
Cette formule reste valable si on considère les extensions périodiques de
𝑎 et 𝐴, définies par les formules :
𝑎𝑛+𝑘𝑁 = 𝑎𝑛 , 𝐴𝑚+𝑘𝑁 = 𝐴𝑚 .
C’est maintenant comme cela que l’on envisagera les choses. Tous les
signaux considérés seront vus dorénavant comme des signaux discrets
périodiques.
Pour simplifier encore, on notera dans la suite ces relations en abrégé par :
ℱ𝑁
(𝑎𝑛 ) ⟷ (𝐴𝑚 ).
ℱ𝑁 ℱ𝑁
Théorème 4.2 Si (𝑎𝑛 ) ⟷ (𝐴𝑚 ) et (𝑏𝑛 ) ⟷ (𝐵𝑚 ), alors :
𝑁 −1
ℱ𝑁
( ∑ 𝑎𝑘 𝑏𝑛−𝑘 ) ⟷ (𝐴𝑚 𝐵𝑚 ).
𝑘=0
Exercice 4.2 :
Montrer ce résultat.
Ce théorème est une variante de ceux que nous avions déjà vus au chapitre
1 sur le lien entre séries de Fourier et convolution.
Première itération
On se place dans le cas où la taille des suites considérées est paire et on
considère
ℱ2𝑁
(𝑎𝑛 ) ⟷ (𝐴𝑚 ).
On introduit alors deux suites (𝑏𝑛 )𝑛=0,…,𝑁 −1 et (𝑐𝑛 )𝑛=0,…,𝑁 −1 définies par
𝑏𝑛 = 𝑎2𝑛 et 𝑐𝑛 = 𝑎2𝑛+1 et on note :
ℱ𝑁 ℱ𝑁
(𝑏𝑛 ) ⟷ (𝐵𝑚 ), (𝑐𝑛 ) ⟷ (𝐶𝑚 ).
Exercice 4.3 :
Le prouver.
On en déduit :
𝑚
𝐴𝑚 = 𝐵𝑚 + 𝜔2𝑁 𝐶𝑚 𝑚 = 0, … , 𝑁 − 1 (4.2)
𝑚
𝐴𝑚+𝑁 = 𝐵𝑚 − 𝜔2𝑁 𝐶𝑚 𝑚 = 0, … , 𝑁 − 1. (4.3)
suite (𝐵𝑚 ) ou (𝐶𝑚 ) (qui ont la même taille) plus 𝑁 multiplications (les calculs
de 𝜔2𝑁
𝑚
𝐶𝑚 ).
De même, le nombre nécessaire d’additions pour calculer la suite (𝐴𝑚 )
est égal à deux fois le nombre d’additions pour calculer la suite (𝐵𝑚 ) ou (𝐶𝑚 )
(qui ont la même taille) plus 2𝑁 additions (les additions et soustrations de
𝑚
𝜔2𝑁 𝐶𝑚 ).
Cas général
On peut aller encore plus loin ! Il suffit pour cela d’appliquer récursivement
le raisonnement précédent. Supposons pour ce faire que 𝑁 = 2𝑀 . Comme 𝑁
est de cette forme on pourra reproduire la division en deux sous suites pour
les suite (𝐵𝑚 ) et (𝐶𝑚 ) et ainsi de suite, 𝑀 fois.
Notons ℳ(𝑗) et 𝒜(𝑗) respectivement le nombre de multiplications et d’ad-
ditions à l’étape 𝑗, 𝑗 allant de 1 à 𝑀.
Regardons tout d’abord ce qu’il se passe quand on a une suite de deux
éléments. Calculons la suite (𝐴0 , 𝐴1 ) à partir de la suite (𝑎0 , 𝑎1 ). On a
𝐴0 = 𝑎0 + 𝑎1
{
𝐴1 = 𝑎0 − 𝑎1
1
ℳ(𝑀 ) = (𝑀 − 1)2𝑀 −1 = (𝑁 log2 𝑁 − 𝑁 )
2
𝒜(𝑀 ) = 𝑀 2𝑀 = 𝑁 log2 𝑁
𝑎0 + + + 𝐴0
𝑎4 𝜔20 − + + 𝐴1
𝑎2 + 𝜔40 − + 𝐴2
𝑎6 𝜔20 − 𝜔41 − + 𝐴3
𝑎1 + + 𝜔80 − 𝐴4
𝑎5 𝜔20 − + 𝜔81 − 𝐴5
𝑎3 + 𝜔40 − 𝜔82 − 𝐴6
À ÉCRIRE
Chapitre
Filtres numériques
Sommaire du chapitre
5.1 Filtres linéaires . . . . . . . . . . . . . . . . 90
5.1.1 Définitions . . . . . . . . . . . . . . . 90
5.1.2 Propriétés des filtres . . . . . . . . . 92
5.2 Stabilité . . . . . . . . . . . . . . . . . . . . 95
5.3 Filtres linéaires récursifs causaux . . . . . . 96
5.3.1 Réponse impulsionnelle finie (RIF) et
infinie (RII) . . . . . . . . . . . . . . 97
5.3.2 Transformée en 𝑧 . . . . . . . . . . . 97
5.3.3 Fonction de transfert . . . . . . . . . 100
5.3.4 Stabilité . . . . . . . . . . . . . . . . 101
5.3.5 Représentation en schéma-bloc . . . 102
5.4 Réponse fréquentielle . . . . . . . . . . . . . 103
5.4.1 Définition . . . . . . . . . . . . . . . 103
5.4.2 Modification spectrale du signal d’en-
trée . . . . . . . . . . . . . . . . . . 104
5.4.3 Réponse à phase linéaire . . . . . . . 106
5.4.4 Diagramme de Bode . . . . . . . . . 106
5.5 Synthèse de filtre . . . . . . . . . . . . . . . 107
5.5.1 Filtres idéaux et gabarits . . . . . . . 108
5.5.2 Conception de filtres à RIF . . . . . . 109
5.5.3 Synthèse par transformation de
Fourier discrète . . . . . . . . . . . . 110
5.6 Notes bibliographiques . . . . . . . . . . . . 110
89
CHAPITRE 5. FILTRES NUMÉRIQUES
5.1.1 Définitions
On donne donc une définition mathématique d’un filtre numérique.
2
ℓ2 (Z) = {(𝑥𝑛 )𝑛∈Z ; ∑ ∣𝑥𝑛 ∣ < +∞} .
𝑛∈Z
Cet espace est un espace vectoriel muni de la norme définie pour tout
𝑥 = (𝑥𝑛 ) ∈ ℓ2 ,
1/2
2
‖𝑥‖2 = (∑ ∣𝑥𝑛 ∣ ) .
𝑛∈Z
Un filtre numérique est donc un système qui produit un signal discret, que
l’on notera dans la suite 𝑦 = (𝑦𝑛 )𝑛∈Z à partir d’un signal reçu en entrée
𝑥 = (𝑥𝑛 )𝑛∈Z . On appelle parfois excitation ou entrée du filtre la suite 𝑥 et
1. Il existe aussi des filtres analogiques, qui agissent sur des fonctions 𝐿1 , par exemple,
et dont les outils sont proches de ceux introduit au chapitre 1. On en trouve dans la nature,
par exemple l’oreille humaine, ou plus généralement tout système physique répondant à une
excitation. Du point de vue de l’activité humaine, l’essor massif des technologies numériques
les place plutôt sur la liste des espèces en voie de disparition.
Dans la pratique, les signaux rencontrés sont finis, si bien que le fait
de travailler dans ℓ2 (Z) plutôt que dans un autre ℓ𝑝 (Z) n’a pas beaucoup
d’importance. Le fait de choisir cet espace plutôt qu’un autre vient du fait
que la norme 2 d’un signal (discret ou pas) est souvent égale à son énergie et
que d’un point de vue physique, il est raisonnable de ne considérer que des
signaux d’énergie finie.
Remarque 5.1 :
Dans toute la suite, on ne considère –− sauf mention contraire −– que
des filtres qui élaborent la réponse en un temps fixé 𝑛 en fonction d’un
nombre fini de termes de 𝑥 ou de 𝑦.
𝑦𝑛 = 𝑥𝑛−1 .
1 1 1
𝑦𝑛 = 𝑦𝑛−1 + 𝑥𝑛 + 𝑥𝑛−1 . (5.1)
4 2 2
91 Version du 2 avril 2025, 11 h 21 CEST. M. Chupin
CHAPITRE 5. FILTRES NUMÉRIQUES
On parle alors de filtre récursif 2 . Attention, un même filtre peut avoir une
définition récursive et une définition non récursive. Par exemple :
1
𝑦𝑛 = 𝑦 + 𝑥𝑛
2 𝑛−1
produit le même filtre que :
1 𝑘
𝑦𝑛 = ∑ ( ) 𝑥𝑛−𝑘 .
𝑘∈N
2
Par contre, cette dernière formule n’entre pas dans le cadre des filtres non-
récursifs que l’on considère dans la suite de ce cours, puisqu’on s’est placé
dans le champs de la remarque 5.1.
Réponse impulsionelle
Dans la suite, on considérera souvent l’image par les filtres de l’entrée
impulsion, c’est-à-dire le signal spécifique :
1 si 𝑛 = 0,
𝛿𝑛0 = {
0 sinon.
Exercice 5.1 :
Montrer que le filtre défini par la relation :
𝑦𝑛 = 𝑛𝑥𝑛 ,
Remarque 5.2 :
Tous les filtres que nous considérerons à partir de maintenant seront
invariants en temps.
Autrement dit, un filtre est dit linéaire si la fonction 𝔽 est une application
linéaire.
Un premier théorème permet de caractériser simplement les filtres linéaires
invariants en temps.
∀𝑛 ∈ Z, 𝑦𝑛 = ∑ 𝑥𝑘 ℎ𝑛−𝑘 . (5.2)
𝑘∈Z
Remarque 5.3 :
Nous ne considérerons à partir de maintenant que les systèmes linéaires
invariants.
Remarque 5.4 :
La propriété du théorème 5.1, à savoir d’être entièrement déterminé par
la donnée de sa réponse impulsionnelle peut avoir une grande utilité. Ima-
ginons que l’on dispose d’un filtre devant nous dont nous ne connaissons
pas les propriétés, mais auquel nous pouvons soumettre une entrée et
récupérer la sortie correspondante. Supposons alors que c’est un SLI. Il
suffit alors d’envoyer une entrée le signal impulsion et de récupérer la
réponse impulsionnelle (sortie) pour, si notre hypothèse SLI est valide,
pouvoir prédire la réponse à n’importe quel signal d’entrée.
Preuve : Notons ℎ = (ℎ𝑛 )𝑛∈Z la réponse impulsionnelle d’un filtre défini par une
fonction 𝔽.
On a :
(𝑦𝑛 )𝑛∈Z = 𝔽 ((𝑥𝑛 )𝑛∈Z )
0
= 𝔽 ((∑ 𝑥𝑘 𝛿𝑛−𝑘 ) )
𝑘∈Z 𝑛∈Z
0
= ∑ 𝑥𝑘 𝔽((𝛿𝑛−𝑘 )𝑛∈Z ) (𝔽 linéaire)
𝑘∈Z
= ∑ 𝑥𝑘 𝔽(𝜏 −𝑘 (𝛿𝑛0 )𝑛∈Z ) (Déf. de 𝜏 )
𝑘∈Z
= ∑ 𝑥𝑘 𝜏 −𝑘 𝔽((𝛿𝑛0 )𝑛∈Z ) (𝔽 invariante en temps)
𝑘∈Z
= ∑ 𝑥𝑘 𝜏 −𝑘 (ℎ𝑛 )𝑛∈Z (Déf. de (ℎ𝑛 )𝑛∈Z )
𝑘∈Z
= ∑ 𝑥𝑘 (ℎ𝑛−𝑘 )𝑛∈Z (Déf. de 𝜏 )
𝑘∈Z
= (∑ 𝑥𝑘 ℎ𝑛−𝑘 )
𝑘∈Z 𝑛∈Z
La formule (5.2) est une formule de convolution. On voit ainsi une relation
algébrique très simple entre l’entrée et la sortie d’un filtre linéaire, invariant
en temps :
𝑦 = ℎ ⋆ 𝑥,
qui montre que de tels filtres ne font, in fine, que réaliser des produits de
convolution.
Causalité
Dans les exemples que nous avons traités jusqu’à présent, l’indice 𝑛 des
signaux numériques représente le temps. Dans ce cadre, il est impossible
qu’un filtre élabore une réponse en fonction de données du futur. C’est ce qui
motive l’introduction de la définition suivante.
𝑦𝑛 = ∑ ℎ𝑛−𝑘 𝑥𝑘 = ∑ ℎ𝑘 𝑥𝑛−𝑘 ,
𝑘≤𝑛 𝑘∈N
Remarque 5.5 :
Il existe cependant des cas où il est nécessaire de considérer des filtres
non causaux. En traitement d’image par exemple, où les signaux – les
images donc – sont de dimension 2, les filtres appliquent à chaque pixel
de l’image une fonction de l’ensemble des pixels de l’image considérée.
La notion de causalité dans ce cas n’a pas vraiment de sens.
5.2 Stabilité
On introduit maintenant une notion importante pour la conception des
filtres.
De manière imagée, on parle de filtre stable si le filtre n’explose pas pour
certaines entrées. La plupart des filtres que l’on considère sont évidemment
stables. Les filtres instables donnent cependant parfois lieu à des phénomènes
de saturation, qui peuvent être mis à profit dans certaines applications 3 .
Remarque 5.6 :
Cette définition est valable pour tout filtre, même non-linéaire.
On en déduit le résultat.
Ce lemme n’est qu’une reformulation du fait que le dual de ℓ1 (Z) est ℓ∞ (Z).
L’intérêt de tels filtres est qu’ils sont très faciles à implémenter en pratique.
On dit que ces systèmes sont définis par une équation aux différences.
5.3.2 Transformée en 𝑧
La réponse impulsionnelle d’un filtre n’est pas forcément très parlante.
Nous avons donc besoin d’outils pour caractériser les filtres et savoir construire
la réponse impulsionnelle d’un filtre en fonction des caractéristiques que l’on
désire pour lui. Un de ces outil est ce qu’on appelle la transformée en 𝑧.
𝑋(𝑧) = ∑ 𝑥𝑛 𝑧 −𝑛 ,
𝑛∈Z
Remarque 5.7 :
1. La transformée en 𝑧 est une série entière dite série de Laurent.
2. Le domaine de convergence de ces séries est un sujet en soit,
faisant appel à l’analyse complexe. Nous ne l’aborderons pas ici.
3. Il y a un lien entre la transformée en 𝑧 et la transformée de Fourier
discrète : la TFD est la transformée en 𝑧 restreinte au cercle
unité (𝑧 = e2i𝜋/𝑁 ) à condition qu’il appartienne à la couronne de
convergence.
4. La transformée en 𝑧 est à la TFD ce que la transformée de Laplace
est à la transformée de Fourier.
Exercice 5.2 :
Calculer la transformée en 𝑧 de (𝑥𝑛 ) définie par
∀𝑛 ∈ N, 𝑥𝑛 = 𝑎𝑛
où 𝑎 ∈ R, 𝑥𝑛 = 0 pour 𝑛 < 0.
Exercice 5.3 :
Démontrer la propriété de retard de la proposition 5.2.
c’est-à-dire que les seuls 𝑎/(𝑥–𝑧)𝑘 avec 𝑎 non nul qui risquent d’apparaître
sont pour 𝑧 égal à un pôle de F et 𝑘 inférieur ou égal à son ordre. 𝑇 est
appelé la partie entière de 𝐹.
Exercice 5.4 :
Déterminer la transformée inverse de :
1
𝑋(𝑧) = .
1 − 32 𝑧 −1 + 12 𝑧 −2
𝐻(𝑧) = ∑ ℎ𝑖 𝑧 −𝑖 .
𝑖 ∈Z
𝑌 (𝑧) ∑𝑀
𝑘=0 𝑏𝑘 𝑧
−𝑘
𝐻(𝑧) = = .
𝑋(𝑧) 1 − ∑𝑁
𝑘=1 𝑎𝑘 𝑧
−𝑘
𝑌 (𝑧) = ∑ 𝑦𝑛 𝑧−𝑛
𝑛∈Z
𝑁 𝑀
= ∑ ( ∑ 𝑎𝑘 𝑦𝑛−𝑘 ) 𝑧−𝑛 + ∑ ( ∑ 𝑏𝑘 𝑥𝑛−𝑘 ) 𝑧−𝑛
𝑛∈Z 𝑘=1 𝑛∈Z 𝑘=0
𝑁 𝑀
= ∑ 𝑎𝑘 𝑧 −𝑘 (∑ 𝑦𝑛−𝑘 𝑧−(𝑛−𝑘) ) + ∑ 𝑏𝑘 𝑧 −𝑘 (∑ 𝑥𝑛−𝑘 𝑧−(𝑛−𝑘) )
𝑘=1 𝑛∈Z 𝑘=0 𝑛∈Z
𝑁 𝑀
= ∑ 𝑎𝑘 𝑧 −𝑘 𝑌 (𝑧) + ∑ 𝑏𝑘 𝑧−𝑘 𝑋(𝑧),
𝑘=1 𝑘=0
d’où le résultat.
On voit facilement que la fonction de transfert d’un filtre récursif causal est
une fraction rationnelle. La réciproque n’est pas vraie. On peut par exemple
voir que le filtre défini par la formule :
𝑦𝑛 = 𝑥𝑛+1
Exercice 5.5 :
Calculer la fonction transfert des filtres définis par :
— 𝑦𝑛 = 𝑥𝑛−1 ;
— 𝑦𝑛 = 14 𝑦𝑛−1 + 12 𝑥𝑛 + 12 𝑥𝑛−1 .
5.3.4 Stabilité
La fonction de transfert introduite à la section précédente permet de
formuler un nouveau critère de stabilité des filtres linéaires récursifs, causaux.
Preuve : (partielle) Puisque l’on considère un filtre causal, on sait que le domaine de
convergence de sa fonction de transfert est l’extérieur d’un cercle,
Par hypothèse de rationalité de la fonction de transfert, on peut la réduire en
éléments simples, c’est-à-dire la mettre sous la forme, où on a supposé pour simplifier
que les pôle étaient simples
𝛼𝑖
𝐻(𝑧) = ∑ −1
=∶ ∑ 𝐻𝑖 (𝑧).
𝑖∈{1,…,𝑁}
1 − 𝑝 𝑖 𝑧 𝑖
1
𝑥𝑛 2 𝑥𝑛 𝑦𝑛
1/2 + +
𝑧 −1 𝑧 −1
𝑥𝑛−1 1/2 1 1
1/4 𝑦𝑛−1
2 𝑥𝑛−1 4 𝑦𝑛−1
5.4.1 Définition
La réponse fréquentielle d’un filtre (linéaire, récursif ou non, causal ou
non) donne des informations sur la manière dont le filtre réagit aux excitations
périodiques.
[−𝜋, 𝜋] → C
𝜔 ↦ 𝐻(ei𝜔 ).
Cette fonction est souvent, par abus de notations, simplement notée 𝐻(𝜔).
On remarque que 𝐻(e𝑖𝜔 ) est la série de Fourier dont les coefficients sont
ceux de la réponse impulsionnelle. La réponse en fréquence est donc la trans-
formée de Fourier de la suite (ℎ𝑛 )𝑛∈Z .
On se place dans le cadre d’application du théorème d’échantillonnage de
Shannon, et on suppose que le contenu fréquentiel du signal d’entrée est inclus
dans [−𝑓𝑒 /2, 𝑓𝑒 /2] où 𝑓𝑒 est la fréquence d’échantillonnage.
De plus, comme on se place après la phase d’échantillonnage, bien
qu’il n’apparaisse plus, le temps entre 𝑥𝑛 et 𝑥𝑛+1 est 1/𝑓𝑒 (et doit être
transmis).
On a alors la correspondance suivante :
𝑓
𝜔 = 2𝜋
𝑓𝑒
qui appartient à [−𝜋, 𝜋] quand 𝑓 ∈ [−𝑓𝑒 /2, 𝑓𝑒 /2]. Le passage par 𝜔 permet
de normaliser la réponse fréquentiel. Le retour à la réponse fréquentielle non
normalisée se fait par une simple multiplication pour la fréquence d’échan-
tillonnage 𝑓𝑒 .
Remarque 5.8 :
— On note que 𝜔 ↦ 𝐻(ei𝜔 ) est 2𝜋-périodique.
— Sans rentrer dans le détail mathématique, dans le cas où l’anneau
de convergence inclut le cercle unité, l’intégrale d’inversion de la
transformée en 𝑧 peut se faire sur le cercle unité. On a alors
2𝜋
1
𝑥𝑘 = ⌠ 𝑋(ei𝜔 )ei𝑘𝜔 d𝜔.
2𝜋 ⌡0
Exercice 5.6 :
Soit le filtre numérique défini par
𝑦𝑛 = ∑ 𝑎𝑘 𝑥𝑛−𝑘 , (5.4)
𝑘∈N
Dans le cas où le filtre n’est pas à phase linéaire, la déformation qu’il engendre
sur le signal d’entrée est appelée distorsion de phase. Ce défaut ne doit pas
être confondu avec la distorsion harmonique qui intervient lorsque le filtre
n’est pas linéaire.
Exercice 5.7 :
Étudier la réponse fréquentielle du filtre défini par la réponse impulsion-
nelle suivante :
ℎ = {0, 5; 0; 0; 0; 0; 0; 0; 0; 0, 5}.
1
𝐻(𝑧) = 3 −1
(5.5)
1− 2𝑧 + 12 𝑧 −2
10
0
−10
0 0.5 1 1.5 2 2.5 3
𝜔
arg (𝐻(ei𝜔 ))
−0.5
En figure 5.4, un exemple gabarit type d’un filtre passe-bas est présenté.
On a en rouge le filtre idéal que l’on souhaite réaliser avec des paramètres de
tolérance :
— Δ𝑓 est la zone de coupure autour de la fréquence de coupure souhaité,
notée 𝑓𝑐 , pendant laquelle la transition doit être effectuée ;
— Δ𝑒1 et Δ𝑒2 sont les tolérances autour de respectivement les valeurs 1
et 0.
|𝐻(𝜔)|
Δ𝑒1
Filtre réel
Δ𝑓
Filtre idéal
Δ𝑒2
𝑓𝑐 𝜔
Figure 5.4 – Illustration d’un gabarit d’un filtre et ses paramètres de tolé-
rance.
Méthode de la fenêtre
La méthode de la fenêtre est la suivante. On choisit une réponse fréquen-
tielle idéale notée 𝐻 ∗ (𝜔). Ce choix peut-être fait par exemple par le graphe
de la fonction dans le domaine fréquentiel.
Par ailleurs, on a
𝐻 ∗ (𝜔) = ∑ ℎ∗𝑛 ei𝜔𝑛
𝑛∈Z
avec, grâce à la formule de transformée inverse :
𝜋
1
ℎ∗𝑛 = ⌠ 𝐻 ∗ (𝜔)ei𝜔𝑛 d𝜔.
2𝜋 ⌡−𝜋
Malheureusement, rien ne garantit que la suite (ℎ∗𝑛 ) correspondante soit
à support fini. On va donc tronquer la suite de coefficients (ℎ∗𝑛 ) à un certain
rang 𝑀 − 1, c’est-à-dire multiplier (ℎ∗𝑛 ) par une suite fenêtre (𝑔𝑘 ) défini par :
1 si 𝑘 = 0, … , 𝑀 − 1
𝑔𝑘 = { .
0sinon.
Ce procédé revient à définir un nouveau filtre (ℎ𝑘 ) par l’opération :
ℎ𝑘 = ℎ∗𝑘 𝑔𝑘 .
Pour avoir la réponse fréquentielle du filtre réel obtenue, on prend la
transformée de Fourier du produit :
𝐻(𝜔) = 𝐻 ∗ ⋆ 𝐺(𝜔),
c’est-à-dire 𝜋
1
𝐻(𝜔) = ⌠ 𝐻 ∗ (𝜔)𝐺(𝜔 − 𝜈)d𝜈,
2𝜋 ⌡−𝜋
et
𝑀 −1
𝐺(𝜔) = ∑ e−i𝑘𝜔 .
𝑘=0
Malheureusement, si cette méthode est assez simple à comprendre et à
mettre en place, elle souffre du phénomène de Gibbs (voir figure 5.5).
𝑦
signal
1 𝑠0
𝑠1
𝑠8
0.5
𝜋 2𝜋 𝑥
Remarque 5.9 :
Pour améliorer cette méthode, il est possible d’utiliser des fonctions
fenêtre plus régulières comme les fenêtre de Hamming, Barlett, etc.
Chapitre
L’analyse temps/fréquences
Sommaire du chapitre
6.1 Transformées de Fourier des fonctions 𝐿2 . . 112
6.1.1 Définition et propriétés de 𝐿2 . . . . 112
6.1.2 Transformation de Fourier . . . . . . 113
6.2 La transformée de Fourier à fenêtre . . . . . 115
6.2.1 Fonction fenêtre . . . . . . . . . . . . 115
6.2.2 Formule d’inversion . . . . . . . . . . 116
6.2.3 Le principe d’incertitude . . . . . . . 117
6.2.4 Spectrogramme . . . . . . . . . . . . 121
6.3 La transformation en ondelettes . . . . . . . 123
6.3.1 L’idée de base . . . . . . . . . . . . . 123
6.3.2 Localisation temps-fréquence . . . . 126
6.4 Aspects numériques et compression . . . . . 127
6.5 Notes bibliographiques . . . . . . . . . . . . 127
111
CHAPITRE 6. L’ANALYSE TEMPS/FRÉQUENCES
donnée (une note), elle est reliée à l’énergie totale de toutes les occurrences de
cette note dans tout le morceau.
Après avoir donner rapidement des résultats sur la transformée de Fourier
dans l’espace fonctionnel 𝐿2 , on introduira la transformée de Fourier à fenêtre,
puis nous introduirons la transformée en ondelettes.
1/2 1/2
⌠ |𝑢(𝑥)𝑣(𝑥)| d𝑥 ⩽ (⌠ |𝑢(𝑥)|2 d𝑥) (⌠ |𝑣(𝑥)|2 d𝑥) .
⌡Ω ⌡Ω ⌡Ω
3. L’application
Théorème 6.1 Soit (𝑓𝑛 ) une suite de Cauchy dans 𝐿2 (Ω). Alors il existe
𝑓 ∈ 2 (Ω) tel que
Remarque 6.1 :
Dans la construction de la transformée de Fourier dans 𝐿2 on passe par
l’ensemble 𝐿1 ∩ 𝐿2 . En pratique, pour calculer la transformée de Fourier
d’une fonction de 𝐿2 qui n’est pas dans 𝐿1 , on utilisera le résultat qui dit
que pour 𝑓 ∈ 𝐿2 , on a 𝑓 ̂ comme limite dans 𝐿2 lorsque 𝑛 → +∞ de
⌠ 𝑓(𝑡)e−2i𝜋𝜈𝑡 d𝑡.
⌡|𝑡|⩽𝑛
où 𝑤 est une fonction fenêtre temporelle paire qui est nulle, ou suffisamment
proche de zéro, en dehors d’un petit intervalle autour de zéro. Donnons deux
exemples classiques pour se fixer les idées.
La fenêtre rectangulaire : 𝑤 ∶ 𝑡 ↦ 𝑤(𝑡) = 1[−𝛼,𝛼] (𝑡) où 𝛼 > 0 ;
2
La fenêtre gaussienne : 𝑤 ∶ 𝑡 ↦ 𝑤(𝑡) = e−𝛼𝑡 où 𝛼 > 0.
𝑓(𝑡)𝑤(𝑡 − 𝑏)
𝑓(𝑡)
𝑤(𝑡 − 𝑏)
𝑏 𝑡
Figure 6.1 – Illustration de l’action d’une fenêtre rectangulaire sur une
fonction.
1. Dennis Gabor (5 juin 1900 à Budapest, Hongrie - 8 février 1979 à Londres) est un
ingénieur et physicien hongrois. Il est notamment connu pour l’invention de l’holographie
pour laquelle il a reçu le prix Nobel de physique de 1971.
2
⌠ ⌠ ∣𝑊𝑓 (𝜈, 𝑏)∣ d𝜈d𝑏 = ⌠ |𝑓(𝑡)|2 d𝑡.
⌡R ⌡R ⌡R
De plus, on a la formule de reconstruction (ou formule d’inversion) :
2
lim ⌠ ∣𝑓(𝑡) − ⌠ ⌠ 𝑊𝑓 (𝜈, 𝑏)𝑤(𝑡 − 𝑏)e 2i𝜋𝜈𝑡
d𝜈d𝑏∣ d𝑡.
𝐴→+∞ ⌡R ⌡|𝜈|⩽𝐴 ⌡R
Remarque 6.2 :
— En notant
𝑤𝜈,𝑏 (𝑡) = 𝑤(𝑡 − 𝑏)e2i𝜋𝜈𝑡 ,
on a alors 𝑊𝑓 (𝜈, 𝑏) = ⟨𝑓, 𝑤𝜈,𝑏 ⟩𝐿2 .
— D’après le théorème de Plancherel, on a alors
Localisation temps-fréquence
Commençons par définir le centre d’une fonction.
1
𝑚𝑤 = ⌠ 𝑡 |𝑤(𝑡)|2 d𝑡.
‖𝑤‖2𝐿2 ⌡R
Remarque 6.3 :
Quand la fenêtre 𝑤 est paire, et donc 𝑚𝑤 = 0, 𝑤𝜈,𝑏 (𝑡) = 𝑤(𝑡 − 𝑏)e2i𝜋𝜈𝑡
est centré sur 𝑏. Le produit 𝑓 𝑤𝜈,𝑏 isole donc les composantes de 𝑓 au
voisinage de 𝑏.
Exemple
2
Pour la gaussienne 𝑤 ∶ 𝑡 ↦ e−4𝑡 , on a ‖𝑤‖2𝐿2 = 14 √2𝜋, et 𝜎𝑤 = 14 .
0.5
0
−3 −2 −1 0 1 2 3
Il est assez aisé de vérifier que dans le cas d’une fenêtre centrée en 0, on
a:
1/2
1 2
∀𝑏 ∈ R, 𝜎𝑤 = ( 2
⌠ (𝑡 − 𝑏)2 ∣𝑤𝜈,𝑏 (𝑡)∣ d𝑡) .
‖𝑤‖𝐿2 ⌡R
Exercice 6.1 :
Montrer que
̂ + 𝜈).
̂𝜈,𝑏 (𝜔) = e−2i𝜋𝑏(𝜔+𝜈) 𝑤(𝜔
𝑤
Là encore, il est assez aisé de vérifier que, dans le cas où 𝑚𝑤̂ = 0 et que
1/2
1 2
∀𝑏 ∈ R, 𝜎𝑤̂ = ( 2
𝑤𝜈,𝑏 (𝜈)∣ d𝜈)
⌠ (𝜈 − 𝜔)2 ∣̂ .
𝑤‖𝐿2 ⌡R
‖̂
𝜎𝑤
∣̂
𝑤𝜈1 ,𝑏1 (𝜔)∣
𝜈1 𝜎𝑤̂
𝑡
𝑏1 𝑏2
Figure 6.2 – Illustration du concept de boîte de Heisenberg pour la trans-
fourmée de Fourier à fenêtre.
Incertitude de Heisenberg
Pour mesurer les composantes de la fonction 𝑓 à étudier dans les petits
voisinages de 𝑏 et 𝜈, il faut construire une fenêtre 𝑤 qui est bien localisée dans
le temps, et dont l’énergie de la transformée de Fourier est concentrée dans
un petit domaine fréquentiel. Nous avons vu avec l’exemple de la transformée
de Fourier du créneau (exercice 1.1), un phénomène général : moins une
fonction temporelle est étalée en temps, plus sa transformée de Fourier l’est
en fréquence. Ce phénomène peut aussi être illustré par le fait d’opérer un
changement d’échelle de temps d’un facteur 𝑎 > 1, c’est-à-dire considérer
la fonction 𝑤𝑎 ∶ 𝑡 ↦ 𝑤(𝑎𝑡) dont la transformée de Fourier est, d’après la
𝑤(𝜈)|2 d𝜈 = 0.
⌠ 𝑡 |𝑤(𝑡)|2 d𝑡 = ⌠ 𝜈 |̂
⌡R ⌡R
Alors on a l’inégalité de Heisenberg suivante :
1
𝜎𝑤 𝜎𝑤̂ ⩾ . (6.3)
4𝜋
Preuve : Nous ne démontrerons ici le résultat que pour les fonctions fenêtre 𝑤 𝒞∞ à
support compact, le résultat s’obtenant dans le cas général par des outils de densité,
qui dépasse le cadre de ce cours.
On doit montrer que
1
𝑤‖𝐿2 ⩾
‖𝑡𝑤‖𝐿2 ‖𝜈̂ ‖𝑤‖2𝐿2 .
4𝜋
∀𝜈 ∈ R, ̂′ (𝜈) = 2i𝜋𝜈̂
𝑤 𝑤(𝜈),
1 ̂′ 2 1
𝑤‖2𝐿2 =
‖𝜈̂ 2
∥𝑤 ∥ 2 = ‖𝑤′ ‖2𝐿2 .
4𝜋 𝐿 4𝜋2
Il reste alors à montrer que
1
‖𝑡𝑤‖𝐿2 × ‖𝑤′ ‖𝐿2 ⩾ ‖𝑤‖2𝐿2 . (6.4)
2
Par l’inégalité de Cauchy-Schwarz, on a :
On a alors :
Preuve : Pour qu’il y ait égalité dans la preuve du théorème 6.7, il faut et il suffit
qu’il y ait égalité dans l’inégalité de Cauchy-Schwarz, c’est-à-dire que 𝑡𝑤(𝑡) et 𝑤′ (𝑡)
soient proportionnelles :
∃𝑐 ∈ R, 𝑤′ (𝑡) = −𝑐𝑡𝑤(𝑡),
ce qui donne
2
𝑤(𝑡) = 𝐴e−𝑐𝑡
où 𝑐 > 0 car 𝑤 ∈ 𝐿2 . Le reste de la preuve se poursuit sans difficulté.
6.2.4 Spectrogramme
import librosa
import matplotlib . pyplot as plt
import librosa . display
from scipy .io import wavfile
20000
17500
15000
12500
Hz
10000
7500
5000
2500
0
0:00 0:50 1:40 2:30 3:20 4:10
Time
Remarque 6.4 :
Nous venons de présenter rapidement la transformée de Fourier à fenêtre
sur le plan théorique et analytique. Il faudrait, mais cela ferait trop pour
ce cours introductif, rentrer dans le détails de la version discrète et des
aspects numériques de cette transformée de Fourier à fenêtre.
1 𝑡−𝑏
𝜓𝑎,𝑏 (𝑡) = 𝜓( ), 𝑎, 𝑏 ∈ R, 𝑎 ≠ 0. (6.5)
√|𝑎| 𝑎
et
2
̂
∣𝜓(𝜈)∣
⌠ d𝜈 = 𝐾 < ∞.
⌡R |𝜈|
La transformée en ondelettes d’une fonction 𝑓 ∈ 𝐿2 est la fonction 𝐶𝑓 ∶
(R − {0}) × R → C définie par :
Ondelette de Haar. Une ondelette mère simple qui permet de bien visualiser
les effets de translation et de dilatation est l’ondelettede Haar 4 , ondelette
considérée comme la première ondelette connue.
La fonction-mère des ondelettes de Haar est une fonction constante par
morceaux :
−1 pour − 12 ≤ 𝑡 < 0,
𝜓(𝑡) = {1 pour 0 ≤ 𝑡 < 12 ,
0 sinon.
En figure 6.4, sont représenter l’ondelette mère de Haar ainsi que deux
ondelettes construites à partir d’elle.
La transformée de Fourier de l’ondelette de Haar est imaginaire pure, et
vaut
̂ = i cos(𝜋𝜈) − 1 .
𝜓(𝜈)
𝜋𝜈
Nous la représentons en figure 6.5.
0.5
Ondelette mère 𝜓 𝑡
𝜓1/2,2 0
𝜓2,4 0 2 4
−0.5
−1
Figure 6.4 – Représentation de l’ondelette mère de Haar ainsi que deux on-
delettes filles qui permettent d’observer les phénomènes de décalage temporel
et de dilatation.
2 /2
𝜓(𝑡) = e−𝑡 cos(5𝑡),
1 2 d𝑎 d𝑏
⌠ |𝑓(𝑡)|2 d𝑡 = ⌠ ⌠ ∣𝐶𝑓 (𝑎, 𝑏)∣ ,
⌡R 𝐾 ⌡R−{0} ⌡R 𝑎2
et
1 d𝑎 d𝑏
𝑓(𝑡) = ⌠ ⌠ 𝐶𝑓 (𝑎, 𝑏)𝜓𝑎,𝑏 (𝑡) 2 .
𝐾 ⌡R−{0} ⌡R 𝑎
0.5
𝜈
−4 −2 2 4
−0.5
̂
𝜓
1
𝜓
0.5
𝑡 0.5
−2 2
𝜈
−0.5
−2 −1 1 2
Exercice 6.2 :
Montrer les égalités (6.6) et (6.7).
Exercice 6.3 :
Montrer les égalités (6.8) et (6.9).
À ÉCRIRE
129
ANNEXE A. RAPPELS D’INTÉGRATION
⌠ ∣𝑓𝑛 − 𝑓∣ d𝜇 → 0 et ⌠ 𝑓𝑛 d𝜇 → ⌠ 𝑓 d𝜇.
⌡ 𝑛→∞ ⌡ 𝑛→∞ ⌡
𝜕𝑓
𝐹 ′ (𝑡) = ⌠ (𝑡, 𝑥)d𝜇(𝑥).
⌡ 𝜕𝑡
Soient (Ω, 𝐵, 𝜇) et (Ω′ , 𝐵′ , 𝜈) des espaces mesurés 𝜎-fini (on pourra penser
à des ouverts de R𝑛 par exemple).
133
BIBLIOGRAPHIE
135
INDEX
récursif, 92 uniforme, 41
stable, 95
à phase linéaire, 106 recouvrement du spectre, 34
FIR, 97 réponse fréquentielle, 103
fonction de transfert, 100 RIF, 97
fonction fenêtre, 115 réponse, 91
fonction à support borné, 8 réponse impulsionnelle, 92
forme normalisée d’une fonction de
schéma fonctionnel, 102
transfert, 101
schéma-bloc, 102
forme systématique, 74
signal
fréquence
rectangulaire, 9
de Nyquist, 32
stable, 8
fréquence de coupure, 108
SLI, 93
identité approchée, 24 sortie, 91
impulsion, 92 source, 38
incertitude de Heisenberg, 119 source sans mémoire, 50
spectre, 81
La disparition, 51 spectrogramme, 121
localement stable, 19 stratégie
matrice du vote majoritaire, 65
de contrôle, 73 syndrome, 74
de vérification, 73 système linéaire invariant, 93
pleine, 82 Série de Laurent, 98
modulation, 4
transformée de Fourier rapide, 6
mots, 50
transformée de Fourier rapide, 87
mp3, 3
transformée de Fourier rapide, 81,
méthode de la fenêtre, 109
84, 90
noyau de Poisson, 23 transformée de Fourier à fenêtre,
116
offline, 51 transformée en ondelettes, 123
ondelette-mère, 123 transformée en 𝑧, 97
online, 51
valeurs de décision, 39
phase, 106
produit de convolution, 11, 21, 94, wavelet transform, 123
103
zip, 3, 49
quantification, 2, 38, 39, 41, 43
adaptative., 44 échantillonage, 82
stable
signal
définie
résultat
forme
longueur
distance
suite fenêtre
matrice
avril
fonctions
source
exemple
code
arbre
nombre
temps
échantillonnage
signaux
aussi
filtres
théorème
codage
Fourier
cours
erreur
algorithme
taille
transformée
entre
linéaire
Exercice
erreurs
fonction filtreréponse
alphabet
Remarque
Définition
formule
quantification information
fréquence
cadre
espace
Théorème
numérique