Analyse du signal

Thierry Audibertthierry.audibert@maths2b.fr

20 decembre 2013

Disponible sur http://www.univenligne.fr sous le nom AnalyseSignal.pdf

Table des matieres

1 Objectifs et mode d’emploi 2

2 Transformee de Fourier 32.1 Transformee de Fourier : point de vue elementaire . . . . . . . . . . . . . . . . . 32.2 Produit de convolution (fonctions integrables) . . . . . . . . . . . . . . . . . . . 42.3 Transformee de Fourier et convolution : formulaire . . . . . . . . . . . . . . . . 72.4 Les corriges et demonstrations des sous-sections (2.1) et (2.2) . . . . . . . . . . 8

3 Etude du signal 123.1 Premiere approche du spectre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2 Echantillonnage, theoreme de Shannon et Nyquist . . . . . . . . . . . . . . . . . 163.3 Corriges des exercices des sections (3.1) et (3.2) . . . . . . . . . . . . . . . . . 22

4 Transformations de Fourier discretes 304.1 Transformation de Fourier discrete . . . . . . . . . . . . . . . . . . . . . . . . . 304.2 Les transformations de Fourier rapides . . . . . . . . . . . . . . . . . . . . . . . 314.3 Transformees en cosinus discretes . . . . . . . . . . . . . . . . . . . . . . . . . 354.4 Transformee en cosinus discrete en dimension 2 . . . . . . . . . . . . . . . . . . 374.5 Corriges des exercices de la section (4) . . . . . . . . . . . . . . . . . . . . . . 38

5 L’analyse du son 425.1 Enregistrement aux formats .wav et .text avec goldwave . . . . . . . . . . . . . . 42

1

1 Objectifs et mode d’emploi

Le cours sur les series de Fourier nous apprend que l’on peut representer une fonction ou un signalT−periodique (et continu par morceaux) comme somme d’une serie trigonometrique

∞∑−∞

cne

2iπnt

T

dans laquelle les fonctions trigonometriques ont des periodes qui divisent T.

La plupart des signaux n’admettent pourtant pas une representation aussi simple. Ainsi, les sonsles plus courants, qu’ils soient produits par un instrument, par la voix, par le fonctionnement d’unmoteur, ne sont pas des signaux periodiques. Nous verrons pourtant que l’on peut, en faisant varierla duree d’observation, faire apparaıtre la plupart des sons comme une superposition de signauxsinusoıdaux. Les memes outils mathematiques et numeriques nous permettront d’etudier des si-gnaux qui necessitent une observation sur de grandes durees comme les variations des hauteurs demaree. On concoit avec ces deux exemples que la definition du signal va devenir assez generale :pour nous ce sera une fonction du temps, suffisamment reguliere pour se preter a nos calculs.

On propose ici une approche quasi-experimentale qui va nous permettre de debroussailler leprobleme. C’est pourquoi il n’est pas indispensable de connaıtre tous les resultats de la section2 sur la transformation de Fourier avant d’aborder la section 3 et le cœur de l’analyse du signal.Chaque section est suivie d’un resume (sous forme de formulaire ou de bilan provisoire) ce quidevrait faciliter une lecture avec aller-retours.

• Plan de lecture possible1. Commencer par la definition de la transformee de Fourier page 3 et l’exercice 1.

2. On pourra decouvrir ensuite la notion de spectre d’un signal avec l’exercice 9 page 13,

3. et poursuivre par l’etude de la problematique de d’echantillonnage avec le theoreme deNyquist et Shannon (forme simplifiee) en section 3.2.

4. La transformation de Fourier discrete et l’algorithme de transformation rapide sont presenteesen section 4.

5. Des applications concretes sont proposees dans la section ??. C’est a mon avis la que leschoses s’eclairent.

2

2 Transformee de Fourier

2.1 Transformee de Fourier : point de vue elementaire

Definition 1 On definit la transformee de Fourier d’une fonction integrable sur R en posant

F(f)(ω) = f(ω) =

∫Re−iωx f(x) dx (2.1)

La definition varie dans la litterature d’un facteur multiplicatif autour de la pulsation et on peutaussi poser

F(f)(ω) = f(ω) =

∫Re−2πiωxf(x) dx.

Exercice 1 existence, premieres proprietesSoit f une fonction integrable sur R.

1. Montrer que sa transformee de Fourier est definie pour tout reel ω.

2. Montrer que f est continue et bornee sur R, donner une majoration de ||f ||∞R.

3. Calculer la transformee de Fourier de la fonction caracteristique de l’intervalle [a, b] :χ(t) = 1 si a ≤ t ≤ bχ(t) = 0 sinon

Est-elle integrable ?

corrige en 2.4.1

Exercice 2 lemme de Riemann LebesgueSoit f une fonction continue par morceaux sur R. On veut montrer que

limω→+∞

f(ω) = 0;

1. On suppose que f est une fonction en escalier sur [a, b]. Montrer que

limα→+∞

∫ b

aeiαt f(t) dt

a pour limite 0 (α designe un reel).

2. Montrer que le meme resultat est vrai pour toute fonction f, continue par morceaux surl’intervalle [a, b].

3. On considere maintenant f integrable sur R. Montrer que

(a) pour tout ε > 0, il existe un intervalle compact [a, b] tel que∫]−∞,a]

|f | ≤ ε,∫

[b,+∞[|f | ≤ ε,

(b) En deduire que

limα→∞

∫ ∞−∞

eiαt f(t) dt = 0.

3

corrige en 2.4.2

Exercice 3 derivation

1. Donner une CS pour que la transformee de Fourier de f soit derivable. Donner alors uneexpression de sa derivee.

2. Donner une CS pour que la transformee de Fourier de f ′ soit definie. La calculer dans cecas.

corrige en 2.4.3

Exercice 4 transformee de Fourier d’une GaussienneSoit f definie par f(t) = e−at

2, avec a > 0.

1. Montrer que sa transformee de Fourier est de classe C∞.

2. Montrer que f verifie une equation differentielle lineaire et la calculer.

corrige en 2.4.4

2.2 Produit de convolution (fonctions integrables)

1

Definition 2 produit de convolutionSoient f et g deux fonctions continue par morceaux sur R. Lorsque la fonction t→ f(x− t)g(t)est integrable, on pose

f ∗ g(x) =

∫Rf(x− t)g(t) dt (2.2)

On appelle produit de convolution de f et g cette fonction f ∗ g

Exercice 5 existence et proprietes du produit de convolutionSoient f et g continues par morceaux sur R. On suppose f integrable et g bornee.

1. Montrer que f ∗ g et g ∗ f sont definies sur R et que f ∗ g = g ∗ f2. Montrer que si f ou g est continue, le produit de convolution f ∗ g est aussi continu.

3. En admettant au besoin la validite d’une formule du type∫R

(∫Rf(x, t)dt

)dx =

∫R

(∫Rf(x, t)dx

)dt

exprimer une relation entre f ∗ g, f et g.

corrige en 2.4.5

1

4

Exercice 6 convolution par une gaussienneOn note g la fonction definie sur R par g(x) = e−x

2et, pour s > 0, on pose

θs(x) =1

s√πg(xs

).

1. Tracer les fonctions θ1/n, pour n = 1, 2, ..5, et etudier la limite de la suite de fonctions(θ1/n)n.

2. Calculer l’integrale de θs sur R. On rappelle que∫Re−t

2dt =

√π.

3. Pour f continue par morceaux et integrable sur R, on pose

f ? θs(x) =

∫Rf(t)θs(x− t) dt =

∫Rf(x− t)θs(t) dt.

(a) Justifier l’existence et l’egalite de ces expressions.

(b) On suppose que f est, de plus, continue en x0 et bornee sur R. Montrer que

lims→0

f ? θs(x0)− f(x0) = 0.

On pourra observer que

f ? θs(x0)− f(x0) =

∫Rf(x0 − t)θs(t) dt−

∫Rf(x0)θs(t) dt.

(c) Etudier la convergence uniforme.

corrige en 2.4.6

Theoreme 1 formule de Fubini pour les fonctions integrables 1

On suppose f continue et integrable sur I × J. Si– pour tout x, la fonction y → f(x, y) est integrable sur J,– g : x→

∫J f(x, y) dy est continue par morceaux et integrable sur I,

alors, ∫∫I×J

f =

∫Ig.

Remarque : avec les hypotheses symetriques :– pour tout y, la fonction x→ f(x, y) est integrable sur I,– h : y →

∫I f(x, y) dx est continue par morceaux et integrable sur J,

on obtient ∫∫I×J

f =

∫Ig =

∫Jh.

1. On comparera au theoreme de Fubini pour les series numeriques...

5

Exercice 7 transformation de Fourier, formule d’echangeA toute fonction numerique f, continue par morceaux et integrable sur R, on associe sa trans-

formee de Fourier definie par

f(ω) =

∫Rf(t)e−iωt dt.

1. Justifier que f est continue et bornee.

2. Montrer que si f et g sont integrables sur R, il en va de meme pour les fonctions f × g etg × f .

3. On suppose f et g integrables et continues sur R. Montrer que la fonction de deux variables

φ(x, y) = f(x)g(y)e−ixy

est continue et integrable sur R2.

4. Sous ces hypotheses, montrer que ∫Rf × g =

∫Rg × f .

Exercice 8 transformee de Fourier et convolutionOn considere ici deux fonctions numeriques fet g, continues et integrables sur R.

1. On suppose que, de plus, l’une des deux fonctions f ou g est bornee sur R. Montrer que,pour tout x ∈ R, la fonction t→ f(x− t)g(t) est integrable sur R et que la fonction

h : x→∫Rf(x− t)g(t) dt

est continue sur R. On commencera par le cas le plus simple.

2. Montrer que la fonction de deux variables

(x, t)→ f(x− t)g(t)

est integrable sur R2.

3. On definit l’integrale de Fourier d’une fonction integrable θ, en posant

θω) =

∫Re−iωsθ(s) ds.

Montrer que

f(ω)× g(ω) =

∫ ∫R2

φ avec φ(x, t) = f(x− t)e−iω(x−t)g(t)e−iωt.

Peut on etablir la formule h(ω) = f(ω) × g(ω), lorsque h est la fonction definie en 1, enapportant eventuellement des hypotheses supplementaires ?

6

2.3 Transformee de Fourier et convolution : formulaire

• Si f est une fonction integrable sur R, sa transformee de Fourier est definie sur R, continue etbornee sur R sa limite est nulle en ±∞ : limω→+∞ f(ω) = 0 et on a les formules suivantes :

• lorsque la transformee est definie par F(f)(ω) = f(ω) =

∫Re−iωx f(x) dx,

Si f et x→ xf(x) sont integrables,df(ω)

dω= −i

∫Re−iωxx f(x) dx

Si f et f ′ sont integrables, f ′(ω) = i ωf(ω)

Si ga(t) = e−at2, ga(ω) =

√π

ae

−ω2

4a =

√π

ag1/4a(ω)

Si f, g, f ∗ g sont (definies) et integrables, f ∗ g = f × g.

• lorsque la transformee est definie par F(f)(ω) = f(ω) =

∫Re−2πiωxf(x) dx,

Si f et x→ xf(x) sont integrables,df(ω)

dω= −2 i π

∫Re−2 i π ωxx f(x) dx

Si f et f ′ sont integrables, f ′(ω) = 2,i π ωf(ω)

Si ga(t) = e−at2, ga(ω) =

√π

ae

−π2 ω2

a =

√π

agπ2/a(ω)

Si f, g, f ∗ g sont (definies) et integrables, f ∗ g = f × g.

1

7

2.4 Les corriges et demonstrations des sous-sections (2.1) et (2.2)

Corrige n˚ 2.4.1 de l’exercice 1 (integrale de Fourier)

1. Si f est integrable sur R, t→ f(t)e−iωt l’est aussi : elles ont le meme module.

2. Pour tout ω ∈ R,

|f(ω)| =∣∣∣∣∫

Rf(t)e−iωt dt

∣∣∣∣ ≤ ∫R|f(t)| dt

on a donc ||f ||∞ ≤ ||f ||1.3.

χ(ω) =

∫Re−iωtχ(t) dt =

∫ b

ae−iωt dt

=

(b− a) si ω = 0i

ω

[e−iωt

]ba

si ω 6= 0

=

(b− a) si ω = 02

ωsin(b−a

2 ω)e−i

b−a2ω si ω 6= 0

Cette fonction a pour module 2

∣∣∣∣∣sin(b−a

2 w)

w

∣∣∣∣∣ dont on sait qu’elle n’est pas integrable sur R

(mais elle admet une integrale impropre).

Corrige n˚ 2.4.2 corrige 2 (lemme de Riemann Lebesgue)

1. Les fonctions en escalier : si φ est une fonction en escalier attachee a la subdivision (tj)j dusegment [a, b], on a ∣∣∣∣∫ b

aφ(t)eint dt

∣∣∣∣ =

∣∣∣∣∣n−1∑k=0

∫ tk+1

tk

αk eint dt

∣∣∣∣∣≤

n−1∑k=0

∫ tk+1

tk

|αk|∣∣∣∣eintk+1 − eintk

in

∣∣∣∣ dt ≤ 2

nsup |αk||b− a|.

La limite est bien 0 lorsque n→ +∞.2. Considerons maintenant f continue par morceaux sur [a, b] et ε > 0. Il existe une fonction

en escalier qui verifie ||f − φ|| ∞[a,b]≤ ε/|b− a|. Nous avons par ailleurs

∣∣∣∣∫ b

af(t)eint dt

∣∣∣∣ ≤ ∣∣∣∣∫ b

a(f(t)− φ(t))eint dt

∣∣∣∣+

∣∣∣∣∫ b

aφ(t)eint dt

∣∣∣∣ .– Le premier terme du membre de droite est majore par ε;– Pour le second, on sait qu’il existe un rang Nε a partir duquel∣∣∣∣∫ b

aφ(t)eint dt

∣∣∣∣ ≤ ε.8

En consequence, pour tout ε > 0 il existe Nε tel que

n ≥ ε⇒∣∣∣∣∫ b

af(t)eint dt

∣∣∣∣ ≤ 2ε.

3. Considerons maintenant une fonction f integrable sur R ou sur un intervalle quelconqueI ⊂ R, et ε > 0. Il existe un segment [a, b] ⊂ I tel que∣∣∣∣∣

∫I|f | −

∫[a,b]|f |

∣∣∣∣∣ ≤ ε.On a : ∣∣∣∣∫

If(t)eint dt

∣∣∣∣ =

∣∣∣∣∣∫

[a,b]f(t)eint dt

∣∣∣∣∣+

∣∣∣∣∣∫I\[a,b]

f(t)eint dt

∣∣∣∣∣≤

∣∣∣∣∣∫

[a,b]f(t)eint dt

∣∣∣∣∣+ ε.

Comme dans la demonstration precedente, il existe un rang Nε a partir duquel∣∣∣∣∫ b

af(t)eint dt

∣∣∣∣ ≤ ε,et on conclut de la meme facon.

Corrige n˚ 2.4.3 de l’exercice 3 (derivation et transformation de Fourier)

1. On considere une fonction f integrable sur R de transformee de Fourier definie par f(ω) =∫R f(t)e−iωt dt. La fonction (ω, t) → f(t)e−iωt satisfait clairement au theoreme de conti-

nuite d’une integrale a parametre– g := t→ f(t)e−iωt est integrable sur R;– ω → f(t)e−iωt est continue ;– il existe une majoration uniforme |f(t)e−iωt| ≤ |f(t)| par une fonction integrable sur R.Par contre, pour la derivation sous le signe somme, rien n’assure que

∂

∂ωg(ω) = −iωf(t)e−iωt

verifie les memes hypotheses. On supposera donc pour aller plus loin dans les calculs quede plus, t→ tf(t) est integrable sur R. Alors

– g := t→ ∂

∂ωg(ω) = −i t f(t)e−iωt est integrable sur R;

– ω → ∂

∂ωg(ω)f(t)e−iωt est continue ;

– il existe une majoration uniforme∣∣∣∣ ∂∂ωg(ω)

∣∣∣∣ ≤ |t f(t)| par une fonction integrable sur R.

Donc, si f(t) et tf(t) sont integrables sur R, f est de classe C1 et

df(ω)

dω= −i

∫R

e−iωx x f(x) dx

9

2. On suppose maintenant que f est integrable et derivable sur R et que f ′ est integrable elleaussi. On peut donc definir la transformee de Fourier de f ′ qui est

F(f ′)(ω) = f ′(ω) =

∫Re−iωxf ′(x) dx.

On est alors tente d’integrer par parties. Cela donnerait

F(f ′)(ω) =[e−iωxf(x)

]+∞−∞ + iω

∫Re−iωxf(x) dx.

Dans cette formule les deux integrales sont definies. En consequence la partie toute integreea elle meme un sens lorsque f et f ′ sont toutes deux integrables. Pour se convaincre quecette limite est nulle on integre les memes fonctions sur l’intervalle [0,+∞[ par exemple.Cela montre que∫ +∞

0e−iωxf ′(x) dx =

[e−iωxf(x)

]+∞0

+ iω

∫ ∞0

e−iωxf(x) dx

et la on voit clairement que si la partie toute integree a une limite, lim+∞ f = 0.

3. Le formulaire est en page 7

Corrige n˚ 2.4.4 de l’exercice 4 (transformee d’une gaussienne)

1. f(ω) =∫R e−iωte−at

2dt =

∫R h(ω, t) dt.

La fonction h admet des derivees partielles par rapport a ω a tous les ordres qui sont

∂k

∂ωkh(ω, t) = (−i t)k e−iωte−at2 = hk(ω, t).

Pour tout k ≥ 0, on a– t→ hk(ω, t) integrable sur R;– t→ hk(ω, t) continue sur [−A,A];– il existe φk, integrable sur R telle que pour (ω, t) ∈ [−A,A]×R, |hk(ω, t)| = |t|ke−at

2 ≤Ake−at

2= φk(t).

Ainsi, f est de classe C∞ sur tout [−A,A] et donc sur R et f ′(ω) =∫R h1(ω, t) dt.

2. En derivant, nous avons

f ′(ω) =

∫Rh1(ω, t) dt = −i

∫R

(te−at

2)e−iωt dt

= −i

[e−at

2

−2ae−iω t

]∞−∞

+ i

∫R

e−at2

−2a(−iω)e−iωt dt

ce qui nous donne l’equation differentielle y′(ω) = − ω

−2ay(ω) assortie de la condition

initiale y(0) = f(0) =∫R e−at2 dt, d’ou, apres calcul de l’integrale de Gauss

f(ω) =

√π

ae−

ω2

4a (2.3)

10

Corrige n˚ 2.4.5 de l’exercice 5 (convolution)

1.

2.

Corrige n˚ 2.4.6 de l’exercice 6 (convolution par une gaussienne)

1.

2.

1

11

3 Etude du signal

1Pour l’etude du signal on preferera la definition

F(f)(ν) = f(ν) =

∫Re−2πiνxf(x) dx

et on se referera donc au deuxieme formulaire de la page 7.

3.1 Premiere approche du spectre

On propose ici une premiere exploration de la notion de spectre d’un signal. On aborde la ques-tion avec le calcul et l’observation graphique des transformees de Fourier de fonctions a supportcompact et sommes de sinusoıdes. La notion de spectre est alors simple et intuitive.

12

Exercice 9 2 ce que la transformee de Fourier nous apprend des frequences...

1. On considere λ > 0, a > 0 et la fonction a support compact

fa,λ(t) =

cos(2πλt), si t ∈ [−a, a]0 sinon .

(a) Calculer sa transformee de Fourier ; on choisira la definition

F(f)(ω) = f(ω) =

∫Re−2πiωxf(x) dx.

(b) Calculer puis representer graphiquement dans une feuille Maple ou Scilab les trans-formees de Fourier de fa,λ pour λ = 0.7 et a = 10, 20, 50, par exemple. Qu’observe-t-on ? Justifier les observations.

(c) La fonction fa,λ est elle integrable sur R? La fonction

ω → fa,λ(ω) e2iπωx

admet elle une integrale impropre sur R? Le cas echeant, calculez la transformee deFourier inverse de fa,λ.

2. (a) On definit

g := (a, t)→ (2 cos (2π λ1t) + 5 cos (2π λ2t) + cos (2π λ3t)) H (a− t) H (a+ t)

ou H designe la fonction echelon (H(a − t)H(a + 1) est egale a 1 sur [−a, a] nulleen dehors). Representer graphiquement la transformee de Fourier de t → g(a, t) sousMAPLE ou Scilab. Qu’observe-t-on ? Que se passerait il avec l’autre definition usuellede la transformee de Fourier ?

(b) On pose φN (t) = fN,λ(t).

Soit ε > 0. Montrer que la suite des transformees de Fourier(φN

)N, est uni-

formement bornee sur le complementaire de ]λ− ε, λ+ ε[∪]− λ− ε,−λ+ ε[.

Evaluez φN (±λ). Que dire du comportement asymptotique de (φN (±λ))N?

Meme question pour la transformee d’une combinaison lineaire∑i

Ai cos (2π λi t) .

corrige en 3.3.1

Exercice 10 Le spectre permet il de reconstituer le signal ?

On considere une fonction g continue par morceaux definie sur l’intervalle [0, T ], T > 0.

1. Montrer que les coefficients de Fourier cn(g) n ∈ Z, de son prolongement T−periodiques’expriment simplement en fonction de la transformee de Fourier de g.

2. fichier : AnTransFourierAnSignal.mws

13

2. Montrer que l’on peut exprimer g sous la forme d’une serie de fonctions dont les termesdependent des seules ( !) valeurs de son spectre, echantillonnees en les points

n

T, n ∈ Z.

Preciser le type de convergence de cette serie.

3. Exemple calculatoire et graphique : choisir un signal triangulaire sur [0, T ] arbitraire, calcu-ler formellement sa transformee de Fourier, ecrire un bref programme donnant les sommespartielles de la serie de la question precedente et comparer au signal d’origine.

corrige en 3.3.2

14

Bilan provisoire• La transformee de Fourier d’un signal sinusoıdal de duree finie 2a et de frequence

1

λest un sinus

cardinal dont les maxima (en valeur absolue) sont atteints en ±λ et verifient :

fλ,a(±λ) ∼a→+∞

a.

0

10

20

30

40

–3 –2 –1 1 2 3

w

Transformee de Fourier d’un signal sinusoıdal de duree de vie finie

• La transformee de Fourier d’une combinaison lineaire de signaux sinusoıdaux de duree finiepermet donc de reperer les differentes frequences qui interviennent dans ce signal.

–15

–10

–5

0

5

10

15

–8 –6 –4 –2 2 4 6 8

w

Transformee de Fourier d’un signal composite de duree de vie finie

• La transformee de Fourier d’un signal composite, continu par morceaux , de duree finie, permetde reconstituer le signal d’origine comme somme d’une serie de Fourier dont les coefficients sontobtenus par echantillonnage du spectre et qui converge en moyenne quadratique (et convergenormalement si g est de plus de classe C1 par morceaux et continue) :

g(t) =1

T

∞∑n=−∞

g(nT

)e

2iπnt

T (3.1)

La serie converge simplement si g est de classe C1 par morceaux et alors :

g(t+) + g(t−)

2=

1

T

∞∑n=−∞

g(nT

)e

2iπnt

T (3.2)

15

3.2 Echantillonnage, theoreme de Shannon et Nyquist

• VocabulaireNous dirons qu’un signal est analogique lorsqu’il est modelise par une grandeur susceptible deprendre des valeurs appartenant a un intervalle de R (on parle d’ensemble continu). C’est le caslorsque le signal est produit par des composants electroniques, des instruments de mesure...Nous dirons qu’un signal est numerique lorsque l’ensemble des valeurs qu’il est susceptible deprendre est discret (chaque element de l’ensemble est isole des autres 3) . C’est le cas d’un signalobtenu par echantillonnage ou produit par un algorithme...• En pratique, lorsqu’on veut traiter un signal, par exemple determiner son spectre, on est le plussouvent amene a le discretiser, a l’echantillonner. C’est a dire que l’on mesure des valeurs endes instants le plus souvent regulierement espaces t0 + kT. On parle alors d’echantillonnage de

frequence fe =1

T.Ce que nous proposons ici, c’est d’etudier les problemes que pose l’echantillon-

nage et de presenter quelques solutions.

Exercice 11 repliement de spectre

1. On considere ici deux signaux sinusoıdaux f(t) = cos(ω1 t) et g(t) = cos(ω2 t) avec|ω1| 6= |ω1|. On mesure ces signaux a des instants k T, k ∈ N.Pour quelles valeurs de T ou de fe =

1

Tles valeurs f (k T ) et g (k T ) seront elles confon-

dues pour tout k ∈ Z?

Verifier que si fe > |f1|+ |f2|, avec fi =ωi2π, ce phenomene ne se produit pas.

Construire une figure comme celle-ci ou deux signaux de frequences f1 et f2 sont indiscer-nables par un echantillonnage de frequence fe.

2. De telles valeurs existent elles lorsque f(t) = cos(ω1 t+ φ1) et g(t) = cos(ω2 t+ φ2)?

corrige en 3.3.3

3. a est isole dans D ssi ∃r > 0, ]a− r, a+ r[∩D = a.

16

Exercice 12 un premier pas vers le theoreme de Shannon (echantillonnage)

On veut montrer que pour tout signal signal g de la forme g(t) =∑N

k=0 akeiωkt, un echantillonnage

de frequence fe =1

T> 2 sup |fk| (avec fk =

ωk2π

) permet de reconstituer le signal g comme

somme d’une serie de fonctions.

On notera s le prolongement a R de la fonction x→ sinx

x.

1. Soient λ ∈ R,, T > 0 et fλ la fonction 2π−periodique qui coıncide avec x → eiλx sur[−π, π[.

(a) Donner une representation graphique de Im(fλ) sur [−5π, 5π] pour λ = 1/2, λ =9/10...

(b) Calculer la serie de Fourier de fλ et etudier avec soin sa convergence. On precisera enparticulier la somme en les points x = 0, π.

En deduire une expression de1

sinxpuis de de cotan x comme somme d’une serie.

2. Soient (a0, a1, ..., aN ) une suite de complexes et (ω0, ω1, ..., ωN ) une suite de reels.

(a) Montrer que la fonction g definie par

g(t) =

N∑k=0

akeiωkt

verifie la formule d’interpolation :

g(t) =∑n∈Z

s

(πt

T− nπ

)g(nT )

des que T est inferieur a la frequence de Nyquist : T ≤ π

|ωk|=

1

2|fk|.

On commencera par etablir le resultat pour un terme eiωkt...

corrige en 3.3.4

17

Bilan provisoire

• Frequence de Nyquist : on appelle frequence de Nyquist d’un signal g(t) =∑N

k=0 akeiωkt,

la frequence f0 =1

T0= 2 sup |fk| (avec fk =

ωk2π

). C’est la frequence d’echantillonnage au

dessus de laquelle il est theoriquement possible de reconstituer un signal comme somme d’uneserie (exercice 12), en dessous de laquelle ce n’est en general pas possible (exercice 11).

Nous generaliserons cette definition en section ??.

• Theoreme de Shannon, version elementaire

Theoreme 2Soit g un signal de la forme g(t) =

∑Nk=0 ake

iωkt. Pour toute frequence superieure a la frequence

de Nyquist, fe =1

T> 2 sup |fk|, g verifie la formule d’interpolation de Shannon :

g(t) =∑n∈Z

s

(πt

T− nπ

)g(nT ) (3.3)

Demonstration avec l’exercice 12.Nous generaliserons ce theoreme en section ??.

• Pourquoi parle-t-on de temps et de frequence ?

Rapprochons la formule 3.2 de la formule de Shannon 3.3

g(t) =1

T

∞∑n=−∞

g(nT

)e

2iπnt

Tg(t) =

∑n∈Z

s

(πt

T− nπ

)g(nT )

Celle de gauche reconstitue le signal a partir d’un echantillonnage des frequences, celle de droite,a partir d’un echantillonnage des temps.

• Que faire en pratique ?

Bien evidemment dans des conditions experimentales ou numeriques, il n’est ni possible d’echantillonnersur une infinite de termes, ni de sommer sur une infinite de termes dans la somme.En pratique, on filtre le signal pour eliminer les frequences depassant un certain seuil. Connaissantce seuil (par exemple 22000Hz) on dispose d’une frequence de Nyquist (44000 Hz, dans l’exempleprecedent).On choisit alors une frequence d’echantillonnage superieure a la frequence de Nyquist et onpreleve un nombre d’echantillons aux instants 0,T,2T,...,nT, suffisant pour couvrir l’intervalle. Oncalcule alors la somme partielle construite sur ces echantillons. La feuille de travail Maple qui suitillustre cela.

18

> >

(2.3)(2.3)

(2.1)(2.1)

> >

> >

(2.2)(2.2)

> >

La formule de Shannon

On se propose de reconstituer un signal à partir d'un échantillonnage. On construit une fonction g pour tester la convergence de la formule de Shannon.

fny est la fréquence de Nyquist de la fonction g.ech(g,f,n) permet d'échantillonner 2n+1 valeurs de la fonction g aux instants 0, T, 2T, ..., 2nT, àla fréquence f=1/T.sha(e,f,t) calcule la somme partielle de la série de Shannon construite sur l'échantillon e (comportant un nombre impair de termes), de fréquence f en t;

On teste avec la fréquence de Nyquist et en faisant varier la taille de l'échantillon

19

> >

> >

> >

On teste à une fréquence supérieure à la fréquence de Nyquist et en faisant varier la taille de l'échantillon. Plus la fréquence est grande, plus l'échantillon doit être de grande taille pour couvrir un intervalle de temps donné

20

> >

> >

21

3.3 Corriges des exercices des sections (3.1) et (3.2)

Corrige n˚ 3.3.1 de l’exercice 91. (a) Le calcul donne (penser a ecrire la fonction cos comme somme d’exponentielles) :

pour ω 6= ±λ :∫ a

−acos (2π λx) e−2 iπ ω xdx =

[e2iπ(λ−ω)x

4iπ(λ− ω)− e−2iπ(λ+ω)x

4iπ(ω + λ)

]aa

=sin (2π(λ− ω)a)

2π(λ− ω)+

sin (2π(λ+ ω)a)

2π(λ+ ω)

et pour ω = ±λ, par parite et passage a la limite, une transformee de Fourier etanttoujours continue, ∫ a

−acos (2π λx) e−2 iπ λ xdx =a+

sin (4πλa)

4πλ

(b) Comme la fonction signal est paire, sa transformee de Fourier est reelle. La questionavait donc un sens et voila ce que l’on trouve en superposant les transformees deFourier pour λ = 0.7 et a = 10, 20, 40 :

Il apparait que– les oscillations sont tres amorties en dehors d’un voisinage de±λ = ±0.7 qui est la

frequence du signal ;

22

– plus la plage d’observation du signal est large (2a), plus l’amplitude maximale at-teinte en±λ est grande avec comme on peut l’observer graphiquement ou le deduiredu calcul precedent,

f(±λ) ∼a→+∞

a

(c)

2. (a) Le calcul est sans mystere, simple superposition qui donne avec a = 100 et

g : x 7→ 1 + 2 cos (1.0π x)− 3 cos (3.0π x) + 4 cos (6π x) ,

On retrouve ici les frequences et des amplitudes maximales aux points ω = ±λi quisont proportionnelles aux coefficients des signaux de periode λi.

(b) Notons s la fonction x→ sinx

x. Nous avons donc en dehors de ±λ,

fλ,a(ω) =sin (2π(λ− ω)a)

2π(λ− ω)+

sin (2π(λ+ ω)a)

2π(λ+ ω)= a (s(2π(λ− ω)a) + s(2π(λ+ ω)a))

23

• Comme pour |x| 6= 0, |s(x)| ≤ 1

|x|, nous avons

∣∣∣fλ,a(ω)∣∣∣ ≤ 1

4π|λ− ω|+

1

4π|λ+ ω|

et si ω /∈]λ− ε, λ+ ε[∪]− λ− ε,−λ+ ε[, ie : |λ− ω| ≥ ε et |λ+ ω| ≥ ε cela donne∣∣∣fλ,a(ω)∣∣∣ ≤ 1

2πε.

• Nous avons deja note que pour un signal sinusoıdal

f(±λ) ∼a→+∞

a

il vient doncfλ,N (±λ) ∼

N→+∞N.

• Cela explique l’observation faite avec le signal composite : les valeurs en les points ±λisont equivalentes a Ai × a ou Ai est l’amplitude de la composante Ai cos(λit)

Corrige n˚ 3.3.2 de l’exercice 101. Les coefficients de Fourier de g sont donnes par la formule :

cn(g) =1

T

∫ T

0e−2inπ/T g(t) dt =

1

T

∫Re−2inπ/T g(t) dt =

1

Tg

(1

T

).

2. Comme g est continue par morceaux , sa serie de Fourier converge en moyenne quadratiquevers g sur R. On ecrit donc

g(t) =∞∑

n=−∞cn(g)e

2iπnt

T =1

T

∞∑n=−∞

g(nT

)e

2iπnt

T

– Lorsque g est continue par morceaux , la serie converge en moyenne quadratique vers gsur [0, T ];

– lorsque g est de classe C1 par morceaux, elle converge simplement vers la regularisee de

g (en 0 et T la limite est doncg(0+) + g(T−)

2;

– lorsque g est continue et de classe C1 par morceaux, elle converge normalement vers g.

3. Exploration numerique et graphique :

(a) On considere par exemple un signal triangulaire sur l’intervalle de temps [0, T ].Connais-sant son spectre (ou transformee de Fourier) le signal est reconstitue avec la formule

g(t) =1

T

∞∑n=−∞

g(nT

)e

2iπntT

ˆg(0) =T 2

4, ˆg(ω) =

1

4

−1 + 2 e−iπ wT − e−2 iTπ w

π2w2=

1

2πω2(1− cosπωT )e−iπωT

24

restart;with(plots);g :=(T, x)-> Heaviside(x)*Heaviside((1/2)*T-x)*x

+ Heaviside(T-x)*Heaviside(x-(1/2)*T)*(T-x);G := plot(g(2, x), x = -2 .. 4, color = red, thickness = 3);

Fg := (T, w)-> Int(exp(-(2*I)*Pi*w*t)*t, t = 0 .. (1/2)*T)+ Int(exp(-(2*I)*Pi*w*t)*(T-t), t = (1/2)*T .. T);

c0 := simplify(value(Fg(T, 0));simplify(value(Fg(T, w)));

1/4T 2

1/4−1 + 2 e−iπ wT − e−2 iTπ w

π2w2

Tg :=(N, T, t) -> simplify(((1/4)*Tˆ2+sum(value(Fg(T, k/T))*exp((2*I)*Pi*k*t/T), k = 1.. N)+sum(value(Fg(T, -k/T))*exp(-(2*I)*Pi*k*t/T), k = 1.. N))/T);Tg(5, T, t);

1

900T

(−1800 cos

(2π t

T

)− 200 cos

(6π t

T

)− 72 cos

(10π t

T

)+ 225π2

)π−2

25

plot(Im(simplify(value(Fg(2, w)))), Re(simplify(value(Fg(2, w)))),w = -3 .. 3, thickness = 2)

plot(evalc(Tg(7, 2, t)), t = -2 .. 4, color = black, thickness = 2);

display(%, G);

26

Corrige n˚ 3.3.3 de l’exercice 111. Dire que pour tout k ∈ Z, f(kT ) = g(kT ) c’est dire que

∀k ∈ Z,

∃nk ∈ Z, ω1k T = ω2k T + 2nkπ

ou

∃nk ∈ Z, ω1k T = −ω2k T + 2nkπ

∀k ∈ Z,

∃nk ∈ Z, k T =

2nk π

ω1 − ω2=

nkf1 − f2

ou

∃nk ∈ Z, k T =2nk π

ω1 + ω2=

nkf1 + f2

En faisant k = 1, il vient T =1

fe=

n1

f1 ± f2et on verifie sans peine que de telles valeurs

de T ou de la frequence d’echantillonnage conduiront a des valeurs identiques de f(kT ) =g(kT ) (on aura alors des solutions avec nk = kn1).

Pour etre certain que ce phenomene ne se produira pas on choisira

T <1

|f1|+ |f2|≤ 1

|f1 ± f2|soit fe > |f1|+ |f2|

Pour la figure on a choisi f1 := 1.1; f2 := 3.06;T =1

fe=

2

f1 + f2;

2. Dans ce cas , dire que pour tout k ∈ Z, f(kT ) = g(kT ) c’est dire que

∀k ∈ Z,

∃nk ∈ Z, (ω1 − ω2)k T + (φ1 − φ2) = 2nkπ

ou

∃nk ∈ Z, (ω1 + ω2)k T + (φ1 + φ2) = 2nkπ

En faisant k = 0 on voit qu’il est necessaire que φ1 − φ2 = 2n0π ou φ1 + φ2 = 2n0πChacune de ces conditions est suffisante et conduit a une condition sur T qui s’exprime

T =n1 − n0

f1 ± f2.

27

Corrige n˚ 3.3.4 correction de l’exercice 121. (a) Figure avec

Rf :=(L,x) − > sin(L*x) :plot(Rf(0.9,x-2*Pi*floor(x/(2*Pi)+1/2) ),x=-5*Pi..5*Pi, discont=true) ;

FIGURE 1 – Im(f0.9)

(b) si λ ∈ Z, c’est clair : tous les coefficients cn(f) sont nuls sauf cλ et la fonction est sapropre somme de Fourier des que n ≥ |λ|.Sinon

cn(f) =1

2π

∫ 2π

0eiλxe−inx dx =

1

2π

[ei(λ−n)

i(λ− n)

]π−π

= s((λ− n)π).

La fonction fλ est de periode 2π et de classe C1 par morceaux. Sa serie de Fourierconverge simplement vers sa regularisee. Cela donne

fλ(x) =∞∑

n=−∞s((λ− n)π)einx, x ∈ R/π(2Z + 1),

fλ(x+) + fλ(x−)

2= cos(λπ) =

∞∑n=−∞

sin(λπ)

(λ− n)π, si x = (2k + 1)π.

De cela on deduit avec y = λπ :

cot(y) =1

y+ 2

∑n≥1

y

y2 − n2π2.

2. Considerons la fonction de periode 2π dont la restriction a ] − π, π], est f(t) = eiλx. Saserie de Fourier en un point de continuite x ∈]− π, π[ est :

eiλx =∑n∈Z

s((λ− n)π)einx (3.4)

On en deduit la formule de Shannon en posant x = ωkT et λ = t/T :

28

eiλx = eiωkt =∑n∈Z

s((t/T − n)π)einωkT .

Ou encoreg(t) =

∑n∈Z

s((t/T − n)π)g(nT ).

On prendra garde au fait que |x| = |ωk|T impose T ≤ π

|ωk|=

1

2|fk|.

Enfin, lorsque g est comme dans l’enonce combinaison lineaire de fonctions de ce type, ilvient encore, pour tout T tel que 0 < T <

π

sup |ωk|, et pour t ∈ R, la formule de Shannon

(convergence simple)g(t) =

∑n∈Z

s((t/T − n)π)g(nT ).

29

4 Transformations de Fourier discretes

Se pose maintenant la question du calcul effectif de la transformee de Fourier d’un signal temporel(ou fonction) f a partir d’un echantillonnage. Nous allons voir comment une approximation parla methode des rectangles fait apparaıtre naturellement la transformee de Fourier discrete. Cetterelation entre integrale de Fourier et transformee de Fourier serait de peu d’interet si nous nedisposions pas d’algorithmes de calculs rapides pour cette derniere. Nous donnons un apercu deces methodes en indiquant leur utilisation sous Maple et Scilab.

4.1 Transformation de Fourier discrete

Se pose maintenant la question du calcul effectif de la transformee de Fourier d’un signal temporelrepresente par une fonction f. Quelques observations prealables s’imposent.– Le signal f est observe sur une periode restreinte, [T0, T1].– On ne dispose en pratique que d’un echantillonnage de la fonction f entre des instants T0 et T1.

C’est a dire que l’on connaıt seulement des valeurs f(tk) pour t0 = T0, ..., tN = T1.– On veut calculer

f(ν) =

∫ ∞−∞

f(t) e−2 i π νt dt ≈∫ T1

T0

f(t) e−2 i π ν t dt.

– On obtient une valeur approchee de cette derniere integrale avec une somme de Riemann :∫ T1

T0

f(t)e−2 i π ν t dt ≈N−1∑k=0

(tk+1 − tk)f(tk)e−2 i π tkν

– Comme on aura choisi une subdivision reguliere pour echantillonner, tk+1 − tk =T1 − T0

N, il

vient : ∫ T1

T0

f(t) e−2 i π ν t dt ≈ ∆T

Ne−2 i π ν T0

N−1∑k=0

f(tk) e−2 i π ν k∆T

N (4.1)

– Il va de soi que l’on ne peut pas calculer toutes les valeurs f(ν). Il va falloir choisir. On encalculera N. On va vite voir lesquelles, pourquoi et comment apres avoir defini la notion detransformation de Fourier discrete.

Definition 3 Soit (αk)0≤k≤N−1 une suite de N nombres. On appelle transformee de Fourierdiscrete de cette suite, la suite finie de N nombres egalement, definie par

TFD(α)(n) =N−1∑k=0

αke−2iπ

kn

N , n = 0, 1, ..., N − 1. (4.2)

Exercice 13

1. Expliciter la matrice ΩN de la transformation de Fourier discrete a l’aide de ωN = e

−2iπ

N .

et montrer que l’inverse de ΩN est1

NΩN .

30

2. Calculer la transformee de Fourier discrete de α = (f(tk))0≤k≤N−1, la subdivision etantdefinie comme ci-dessus et etablir une relation asymptotique entre TFD(α)(n) et f(ν)pour ν bien choisi.

voir corrige en 4.5.1

4.2 Les transformations de Fourier rapides

Le calcul de la TFD pourrait s’averer laborieux pour de grandes valeurs de N : le produit matrice-vecteur brutalement programme demandeO(N2) operations. En 1965, redecouvrant une methodedeja mise en œuvre par Gauss, Cooley et Tuckey, ont remarque que l’on pouvait reduire ce calcula O(Nln(N)) operations... Depuis, de nombreuses variantes de cet algorithme, connues sous lenom de transformees de Fourier rapides (TFR ou FFT), ont vu le jour, les plus recentes visant as’adapter a l’architecture des processeurs pour reduire encore les temps de calculs 4 et limiter leserreurs lors des calculs en flottants.

• Sans algorithme rapide, le calcul des N sommes

Y [n] =N−1∑k=0

X[k]ωnkN

demande O(N2) operations comme nous l’avons deja remarque ; il y a bien sur plusieurs faconsde l’envisager et nous n’insisterons pas sur cette question autrement que par l’exercice 14 qui suit :

Exercice 14 TFD sans algorithme rapide

1. Dans l’exemple qui suit, ou le meme algorithme est propose en Maple et en Scilab, denombrerles additions et les multiplications (on prendra garde au decalage des indices, ici Y =[Y [1], ..., Y [N ]] est indexe de 1 a N et non pas de 0 a N-1 et non pas [Y [0], ..., Y [N − 1]]comme dans nos formules).

2. Justifier que l’on calcule bien la transformee de Fourier discrete du vecteur X.

3. Y aurait il inconvenient a construire la matrice ΩN pour ensuite effectuer le calcul Y =ΩNX? Comparer les operations.

4. a distinguer du nombre d’operations

31

Avec Maple

N := 8;X := Array(1 .. N, i-->x[i-1]);w := z;# au lieu de exp(-(2*I)*Pi/N) pour verification rapide

wn := 1;Y := Array(1 .. N);for n to N doY[n] := 0;wnk := 1;for k to N do

Y[n] := Y[n]+wnk*X[k];wnk := wnk*wn

end do;wn := wn*w

end do;Y(7);

x0 + z6x1 + z12x2 + z18x3 + z24x4 + z30x5 + z36x6 + z42x7

Avec N :=5 et w :=exp(-(2*I)*Pi/N) en place de w :=z, nous obtenons pour Y(4),

x0 +(

e−2/5 iπ)3x1 +

(e−2/5 iπ

)6x2 +

(e−2/5 iπ

)9x3 +

(e−2/5 iπ

)12x4

Comme toujours, la verification est immediate avec un logiciel de calcul formel ; on voit ce que l’ona programme : c’est l’avenir !

voir corrige en (4.5.2)

32

• Diviser pour regnerSupposons que N soit un entier de la forme N = N1N2 et reprenons le calcul de

Y [n] =N−1∑k=0

X[k]ωnkN

en posant pour n, k tels que 0 ≤ n, k ≤ N − 1 :n = n1 + n2N2, 0 ≤ n1 ≤ N2 − 1

k = k1 + k2N1, 0 ≤ k1 ≤ N1 − 1

ce qui nous donnek n

N=k1 n1

N+k1 n2

N1+k2 n1

N2+ k2 n2

wnkN = wk1 n1N × wk1 n2

N1× wk2 n1

N2× 1

Y [n1 + n2N2] =

N1−1∑k1=0

N2−1∑k2=0

X[k1 + k2N1]wk2 n1N2

wk1 n1N

ωn2k1N1

(4.3)

Ainsi, pour chaque valeur de n (ou chaque couple (n1, n2), nous avons a calculerN1 TFD de tailleN1 : N2−1∑

k2=0

X[k1 + k2N1]wk2 n1N2

a multiplier ce resultat par wk1 n1

N et a calculer la TFD de taille N2 du vecteur obtenu. Cela conduita une procedure recursive qui s’ecrit plus facilement lorsqueN1 est invariablement egal a 2, ce quisuppose que N est de la forme N = 2p.

Exercice 15 l’algorithme de Cooley et Tuckey pour N = 2p.

On se propose ici d’expliciter l’algorithme de calcul rapide lorsque N1 = 2 et N2 =N

2.

1. Reecrire dans un tel cas la formule (4.3) en observant que k1 et n1 ne prennent que deuxvaleurs.

2. Ecrire un algorithme recursif du calcul de Y lorsque Y est une puissance de 2. Preciser lacondition d’arret ou l’initialisation.

3. Determinez la complexite de votre algorithme en nombre de multiplications par exemples.S’il n’est pas en O(N lnN) reecrivez le !

4. Reecrire cet algorithme dans une procedure iterative avec une boucle while.

voir corrige en (4.5.3)

33

Bilan• Soit N un entier naturel non nul. La transformee de Fourier discrete (TFD ou DFT) d’ordre Ndefinie par

(Xk)k ∈ CN → (Yn)n =

(N−1∑k=0

XkωnkN

)n

∈ CN ,

est bijective et son inverse (transformee de Fourier discrete inverse) est :

(Yn)n ∈ CN → (Xk)k =

(1

N

N−1∑n=0

Ynω−nkN

)k

∈ CN ,

La matrice de la TFD (ou DFT) :

ΩN =

1 1 1 1 . . . 1

1 ωN ωN2 ωN

3 . . . ωN(N−1)

1 ωN2 ωN

4 ωN6 . . . ωN

2(N−1)

1 ωN3 ωN

6 ωN9 . . . ωN

3(N−1)

......

......

. . ....

1 ωN(N−1) ωN

2(N−1) ωN3(N−1) . . . ωN

(N−1)2

,

d’inverse Ω−1N =

1

NΩN .

Attention cette representation matricielle, utile pour les demonstrations, n’intervient pas dans lescalculs effectifs (comme dans la plupart des cas).

• Lorsqu’on dispose d’un echantillonnage de tailleN de f sur [T0, T1], pour toute valeur ν =n

∆T,

∫ T1

T0

f(t) e−2 i π ν t dt =∆T

Ne−2 i π ν T0TFD(α)(ν∆T ) +O

(1

N

)(4.4)

• L’interet de cette formule c’est qu’on dispose pour le calcul d’algorithmes de complexite O(N lnN)

lorsque N est une puissance de 2. On se ramene a ce cas en completant (par interpolation le plussouvent) les donnees dont on dispose pour se ramener a 2N points. On dispose par ailleurs d’algo-rithmes rapides plus sophistiques qui permettent de traiter les releves en N points sans que N nesoit une puissance de 2 (voir l’article [2], disponible sur la toile, qui decrit ce type d’algorithme eten detaille un qui est par ailleurs implemente sous Scilab - voir l’aide de Scilab version 5.4.0).

34

4.3 Transformees en cosinus discretes

A voir ; utile pour les images...La ressemblance avec la section precedente, ou de la transformee de Fourier discrete il s’agissait,n’a rien de fortuit.On rappelle que l’espace C2π muni du produit scalaire

ψ(f, g) =1

2π

∫ 2π

0f(t) ¯g(t) dt

est un espace prehilbertien.

Exercice 16 Verifier que les trois familles de fonctions

t→ eint/n ∈ Z

t→ cos(nt)/n ∈ N ∪ t→ sin(nt)/n ∈ N∗,

t→ cos(nt

2/n ∈ N,

sont orthogonales. Preciser les normes de chacune de ces foncions.

Exercice 17 On considere une fonction de classe C1 sur l’intervalle [0, T ].

1. coefficients de Fourier– On considere la fonction g, T−periodique egale a f sur [0, T [. Donner une expression

des coefficients de Fourier de g en fonction de ceux de g′.– Donner une condition suffisante sur f pour que la convergence de cette serie de Fourier

soit une convergence normale.

2. coefficients en cosinus...– Montrer que la fonction h de periode 2T, paire, egale a f sur [0, T [, est limite uniforme

de polynomes de la forme

a0/2 +∑k

ak cos(kπt/T ).

– Donner une expression des coefficients de Fourier de h en fonction de ceux de h′. Com-parer avec les coefficients de Fourier de g.

3. Peut on en dire autant pour des polynomes 5∑k

bk sin(kπt/T )?

• Transformee en cosinus discrete en dimension 1On definit la transformee en cosinus discrete (TCD, en francais et DCT, en anglais) comme etantl’application lineaire de CN dans lui-meme definie par :

TCD = p ∈ CN → G ∈ CN ,

5. penser a la facon dont nous avons etudie l’equation de la chaleur

35

Gj = αcj

n−1∑k=0

pk cos

((2k + 1)

πj

2N

)(4.5)

ou les coefficients cj sont cj =1√2

sij = 0,

cj = 1 sinon.

Le choix de α sera fixe par la suite. L’exercice qui suit a pour but de determiner la bijectionreciproque et son expression :

TCDI(G)k0 = pk0 = β

N−1∑j=0

cjGj cos

((2k0 + 1)

πj

2N

)(4.6)

Exercice 18 Calcul de la transformation inverseOn se propose montrer que TCD est un automorphisme de CNet d’en calculer la bijection reciproque.La demarche est celle mise en œuvre pour le calcul de l’inverse de la TFD et les resultats fortsressemblants.

1. Donner une expression de la matrice DN associe a l’automorphisme TCD. 6

2. Soit k0, un entier fixe, tel que 0 ≤ k0 ≤ N − 1. On se propose de calculer

N−1∑j=0

cjGj cos

((2k0 + 1)

πj

2N

).

(a) Exprimer l’expression ci-dessus en fonctions des deux sommes

σ1 =N−1∑j=0

c2j cos

((k + k0 + 1)

πj

N

)

σ2 =

N−1∑j=0

c2j cos

((2k0 + 1)

πj

N

).

(b) Calculer chacune d’elles avec soin (en distinguant suivant que k = k0 ou pas, quek + k0 est pair ou impair.

(c) En deduire que la TCD et sa matrice DN sont inversibles, donner une expression dechacune d’elles. Que dire des colonnes de DN?

3. Choisir α pour que les coefficients α et β de la formule (4.6), soient egaux.

4. Calculer

2 (cos(1/16π))2 + 2 (cos(3/16π))2 + 2

(cos(

5

16π)

)2

+ 2

(cos(

7

16π)

)2

,

par exemple et montrer que la matrice DN est orthogonale.

6. fichier MAPLE : TCD.mws

36

4.4 Transformee en cosinus discrete en dimension 2

On introduit ici la TCD et son inverse en dimension 2 et on essaiera de montrer comment elleintervient pour la compression du signal audio ou video.

On definit de facon analogue la transformee en cosinus discrete pour un signal p(x, y) dependantde deux parametres discrets. Penser pour fixer les idees que la matrice carree

P = [p(x− 1, y − 1)]1≤x≤N,1≤y≤N ,

formee des coefficients des (p(x, y))0≤x<N,1≤y<N represente une image deN2 points (ou pixels),x et y representant les abscisse et ordonnee de ces points, p(x, y) un decrivant une intensite decouleur par exemple...

TCD2(i, j) =1√2N

cicj

N−1∑x=0

N−1∑y=0

p(x, y) cos

((2x+ 1)

πi

2N

)cos

((2y + 1)

πj

2N

)(4.7)

TCDI2(x, y) =1√2N

N−1∑i=0

N−1∑j=0

cicjTCD2(i, j) cos

((2x+ 1)

πi

2N

)cos

((2y + 1)

πj

2N

)(4.8)

avec toujours, cj =1√2

sij = 0,

cj = 1 sinon.

Exercice 19 On note toujours DN la matrice de la TCD en dimension 1, qui est donc une appli-cation de Cn dans lui-meme.

1. Soit P la matrice carree de taille N definie par

P = [p(x− 1, y − 1)]1≤x≤N,1≤y≤N .

Exprimer TCD2(P ) en fonction de P, de DN et de sa transposee.

2. En deduire que TCD2 est inversible et verifier que son inverse est bien donnee par la for-mule (4.8).

3. Calculer, lorsque, P est une matrice 1024× 512, le nombre d’additions, de multiplicationsnecessaires pour calculer sa TCD.

4. On partage la matrice en blocs 8 × 8. Combien faut il d’additions, de multiplications pourcalculer le TCD de chaque bloc ? Quel est le cout total ?

37

4.5 Corriges des exercices de la section (4)

Corrige n˚ 4.5.1 de l’exercice 131. Pour n = 0, 1, ..., N − 1 :

TFD(α)(n) =N−1∑k=0

αke−2iπ

kn

N =N−1∑k=0

αkωk nN ,

la matrice de cette application lineaire est donc definie par ΩN,n, k = ω(n−1)(k−1)N , soit

ΩN =

1 1 1 1 . . . 1

1 ωN ωN2 ωN

3 . . . ωN(N−1)

1 ωN2 ωN

4 ωN6 . . . ωN

2(N−1)

1 ωN3 ωN

6 ωN9 . . . ωN

3(N−1)

......

......

. . ....

1 ωN(N−1) ωN

2(N−1) ωN3(N−1) . . . ωN

(N−1)2

C’est la matrice de Vandermonde attachee aux racines N iemes de l’unite. Elle est doncinversible. Pour determiner son inverse, un calcul explicite pour N = 2, 3, 4 permet deconjecturer. Calculons ΩNΩN pour verifier

[ΩNΩN

]n,k

=N∑j=1

ΩN n jΩN j k =N∑j=1

ω(n−1)(j−1)N ω

(j−1)(k−1)N

Comme ωN est le conjugue de ωN , on a

[ΩNΩN

]n,k

=

N∑j=1

ω(j−1)(n−k)N =

N si ωn−kN = 1

0 sinon (somme des termes d′une s.g.).

La racine ωN etant primitive (ses puissances engendrent le groupe des racines de l’unite),seuls les termes diagonaux sont non nuls. On a donc

Ω−1N =

1

NΩN .

2. Rappelons que tk = t0 + (T1 − T0)k

Nsoit

k

N=

tk − t0T1 − T0

. Il vient donc, pour n =

0, 1, ..., N − 1 :

TFD(α)(n) =

N−1∑k=0

f(tk)ωk nN =

N−1∑k=0

f(tk)e−2iπ

kn

N

38

Si nous rapprochons cela de la formule (4.1)∫ T1

T0

f(t) e−2 i π ν t dt = limN→+∞

(∆T

Ne−2 i π ν T0

N−1∑k=0

f(tk) e−2 i π ν k∆T

N

),

nous avons pour chaque valeur ν =n

∆T,

TFD(α)(n) =

N−1∑k=0

f(tk)ωk nN =

N−1∑k=0

f(tk)e−2iπN

k n =

N−1∑k=0

f(tk)e−2 i π k ν ∆T

N

en d’autres termes et en se souvenant que la methode des rectangles converge en O(

1

N

):

∫ T1

T0

f(t) e−2 i π ν t dt =∆T

Ne−2 i π ν T0TFD(α)(ν∆T ) +O

(1

N

)Corrige n˚ 4.5.2 de l’exercice 14

1. Le programme MAPLE avec X1, X2, ..., Xn et w = ωN = e−2iπ/N donnes :

Le programme le total des operations

w := exp(-(2*I)*Pi/N);wn := 1;

Y := Array(1 .. N);for n to N doY[n] := 0;wnk := 1;for k to N do

Y[n] := Y[n]+wnk*X[k];wnk := wnk*wn

end do;wn := wn*w

end do

N2 additions et 2N2 multiplications dans la boucleinterne ;

N multiplications dans la boucle externe ;

2. Ce que l’on calcule : la preuve formelle est dans le cours d’informatique [1].

3. Cout de la construction de la matrice ΩN :

39

Corrige n˚ 4.5.3 de l’exercice 151. On suppose que N1 = 2. Comme

n = n1 + n2N2, 0 ≤ n1 ≤ N2 − 1

k = k1 + k2N1 = k1 + 2 k2, 0 ≤ k1 ≤ 1.

cela donnek n

N=k1 n1

N+k1 n2

2+k2 n1

N2+ k2 n2

wnkN = wk1 n1N × wk1 n2

N1× wk2 n1

N2× 1

La formule (4.3) se reecrit donc, avec ωN1 = ω2 = −1,

Y [n1 + n2N2] =

N1−1∑k1=0

N2−1∑k2=0

X[k1 + k2N1]wk2 n1N2

wk1 n1N

ωn2k1N1

(4.9)

=

1∑k1=0

N2−1∑k2=0

X[k1 + 2 k2]wk2 n1N2

wk1 n1N

(−1)n2k1 (4.10)

=

N2−1∑k2=0

X[2 k2]wk2 n1N2

+ (−1)n2

N2−1∑k2=0

X[2 k2 + 1]wk2 n1N2

wn1N

(4.11)

On calcule donc pour (n1, n2) fixe, (avec 0 ≤ n1 ≤ N2 − 1, et 0 ≤ n2 ≤ 1), deux TFD de

taille N2 =N

2, celles des composantes paires et impaires de X.

2. Voir l’algorithme pages suivantes. Le programme Scilab est detaille dans [1]

3. On notera Cp le nombre de multiplications lors d’un appel avec N = 2p du programmerecursif en MAPLE qui est presente dans le tableau.

On a, puisque N2 =N

2= 2p−1,

C0 = 0

Cp+1 = 2Cp + 3× 2p

Ce qui donne Cp = 3× p× 2p−1 que l’on exprime encore en fonction deN :3

2 ln 2× lnN ×N

40

Le programme avec MAPLE

TFDrapide := proc (X)local N, N2, r, Y, Y0, Y1, X0, X1, w, W, n1, n2, k2;N := Dimension(X);if N = 1then

Y := X;elseN2 := iquo(N, 2, r);if r <> 0 then error "2 doit diviser N" end if;X0 := Array([seq(X[2*k2-1], k2 = 1 .. N2)]);Y0 := TFDrapide(X0);X1 := Array([seq(X[2*k2], k2 = 1 .. N2)]);Y1 := TFDrapide(X1);

Y := Array(1 .. N);w := exp(-(2*I)*Pi/N);W := 1;

for n1 from 0 to N2-1 doY[n1+1] := Y0[n1+1]+Y1[n1+1]*W;Y[n1+1+N2] := Y0[n1+1]-Y1[n1+1]*W;W := W*w

end doend if;Yend proc

Il serait judicieux d’introduire un compteur pour verifier tout ce qui precede (a placer dans laboucle for et a declarer en variable globale sans oublier de l’initialiser avant chaque appel).

41

5 L’analyse du son

On se propose d’aborder l’etude des sons du point de vue de l’analyse du signal. Pour cela nousallons enregistrer quelques sons et montrer comment fonctionnent les outils que nous avons misen place.

• Quelques remarques preliminaires et desordonnees– Un son est detecte par l’intermediaire d’une membrane (situee dans un micro ou dans votre

oreille) qui enregistre des variations de pression de l’air ou du fluide dans lequel elle est im-mergee. Sur le plan physique enregistrer un son consiste donc a fournir des releves de pressionsous une forme analogique t→ P (t) ou numerique (P (k T ))k.

– Seules les variations rapides de pression semblent detectees par nos instruments (un plongeurn’entend pas de bruit lie directement a la variation de pression accompagnant sa descente, unmicro place dans un caisson hyperbare ne nous permettra pas non plus de reperer la pressionambiante contrairement a un manometre) ;

– un son est produit et a fortiori enregistre pendant un intervalle de temps fini [τ0, τ1]; on luiassociera donc au mieux des restrictions ou troncatures de signaux virtuels periodiques (cas dudiapason) ;

– en dehors de cas tres particuliers, mais dont la reconnaissance va se reveler fondamentale, unsignal sonore n’est en general pas periodique.

– On distingue pourtant des sons graves et aigus ce qui conduit aussi a penser aussi le son entermes de frequences.

– Nous nous proposons d’etudier un enregistrement sonore. Cela nous conduira a numeriser (ouechantillonner) notre enregistrement ; cela signifie que l’intervalle d’etude [τ0, τ1] est discretiseet que la pression est relevee avec une frequence proportionnelle au nombre de termes de la sub-division, ce qui induit une perte d’information. Ce phenomene a deja ete etudie dans l’abstrait(frequence de Nyquist, theoreme de Shannon page18).

• Les outilsOn pourra proceder a un enregistrement sonore avec le logiciel livre avec la carte son de l’ordina-teur, utiliser un logiciel comme goldwave, telecharger un fichier son quelconque... Pour l’analysedu son nous allons proposer de visualiser et analyser avec goldwave, Maple et Scilab.

5.1 Enregistrement aux formats .wav et .text avec goldwave

Commencons par enregistrer un son quelconque sous goldwave. On peut enregistrer le son sous leformat .wav dans un fichier .wav ou .txt. La premiere ligne du fichier .txt est

[48000Hz, Channels: 2, Samples: 343680, Flags: 0]

ce qui signifie que la frequence d’echantillonnage est de 48000Hz, que le son a deux canaux(stereo) et que l’on a preleve 343680 echantillons, ce qui couvre environ 7 secondes. On presenteici, la premiere figure, un releve des variations de pression enregistrees sur une duree d’environ4.5 secondes (le texte, remarquable, est pouet, pouet, pouet, pouet, I stop it). On reconnaitra laprononciation du I : a-i. Comme on l’a deja observe, a part la repetition de pouet pouet, ce n’estpas vraiment periodique...

42

On reprend donc le meme fichier et on observe le deuxieme pouet pendant 0.4 s puis pendant0.045s et la, on commence a y voir plus clair.

43

44

References

[1] THIERRY AUDIBERT, AMAR OUSSALAH

Informatique, Programmation et Calcul ScientifiqueEllipses, 2013

[2] MATTEO FRIGO AND STEVEN G. JOHNSON

The Design and Implementation of FFTW3 rapideProc. IEEE, vol. 93, no. 2, pp. 216-231 (2005).disponible en pdf sur le site de la revue IEEE :http ://ieeexplore.ieee.org/search/http ://www.fftw.org/

[3] C. GASQUET, P. WITOMSKI .Analyse de Fourier et ApplicationsMasson, 1990

[4] H. REINHARD .Elements de mathematiques du signaltome 1 - Signaux deterministesDunod, 1995

[5] W. RUDIN .Analyse reelle et complexeMasson, 1980

[6] BERNARD SIMON .La maree 1. La Maree oceanique cotiereInstitut oceanographique Collection : SYNTHESES (2007)

[7] L. SCHWARTZ .Methodes mathematiques pour les sciences PhysiquesHermann, 1993

[8] L. SCHWARTZ .Analyse III - Calcul IntegralHermann, 1993

[9] L. SCHWARTZ .Analyse IV - Applications de la Theorie de la MesureHermann, 1993

[10] WIKIPEDIA .Transformee de Fourier rapidehttp ://fr.wikipedia.org/wiki/Transformee de Fourier rapideconsultee novembre 2012

45

Indexalgorithme

Cooley et Tuckey, 34

convolution, 4, 6

derivationtransformee de Fourier, 3

Fouriertransformee de, 3transformee discrete, 30

frequencede Nyquist, 18

Fubinila formule de, 5

Lebesguelemme de Riemann-Lebesgue, 3

lemmede Riemann-Lebesgue, 3

Nyquistfrequence de, 18

produitde convolution, 4

Riemannlemme de Riemann-Lebesgue, 3

Shannonformule de, 17, 18theoreme, 18

TFD, 30theoreme

de Fubini, 5de Shannon, 17, 18

transformeede Fourier, 3de Fourier Discrete, 30

46