Bogdan Dumitrescu Facultatea de Automatica s¸i …Bogdan Dumitrescu Facultatea de Automatica s¸i...

Prelucrarea semnalelor

Capitolul 5: Analiza în frecventa a semnalelor

Bogdan Dumitrescu

Facultatea de Automatica si Calculatoare

Universitatea Politehnica Bucuresti

PS cap. 5: Analiza ın frecventa a semnalelor – p. 1/57

Cuprins

• Semnale periodice si seria Fourier discreta• Semnale cu suport finit si transformata Fourier discreta• Transformata Fourier rapida (FFT)

◦ FFT cu decimare în timp◦ FFT cu decimare în frecventa

• Alte transformate discrete• Aplicatii simple


Tipuri de semnale (discrete) studiate

• Semnale periodice: continutul în frecventa poate fi calculatdintr-o singura perioada a semnalului

• Semnale cu suport finit. Justificare: în timp real, seanalizeaza portiuni (cadre) succesive ale semnalului (care eneperiodic, eventual nestationar)

• Daca x[n] este un semnal N -periodic, notam x[n] semnalulcu suport 0 : N − 1 care reprezinta o perioada a lui x[n]

x[n] =

{

x[n], daca x ∈ 0 : N − 1

0, altfel

• Invers, daca x[n] este un semnal cu suport 0 : N − 1, notamx[n] prelungirea lui prin periodicitate, data de

x[n] = x[n mod N ]


Seria Fourier

• Un semnal analogic x(t) cu perioada T se poate scrie ca oserie Fourier

x(t) =

∞∑

k=−∞

akej(2πkt/T )

• Semnalul este descompus într-o suma infinita de sinusoidea caror frecventa este multiplu al frecventei fundamentale2π/T


Seria Fourier discreta (SFD)

• Fie x[n] un semnal discret N -periodic, i.e. x[n + kN ] = x[n],∀k ∈ Z

• Ca si în cazul continuu, semnalul se poate descompune cao suma de sinusoide de frecventa multiplu al frecventeifundamentale 2π/N

• Acum sunt însa doar N sinusoide distincte !• Reamintire:

◦ ejωn are perioada N doar daca exista k ∈ Z a.î.2kπ/ω = N , adica ω = 2kπ/N

◦ sinusoidele discrete cu frecventele ω si ω + 2ℓπ, ℓ ∈ Z,sunt identice


SFD—definitie

• Orice semnal N -periodic x[n] se poate reprezenta prin seriaFourier discreta (SFD)

x[n] =1

N

N−1∑

k=0

X[k]ej 2π

Nkn (1)

• Valorile X[k], k = 0 : N − 1, se numesc coeficientii serieiFourier discrete

• Factorul 1/N a fost introdus doar din considerente formale

• Notam wN = e−j 2π

N

• Relatia (1) se scrie x[n] =1

N

N−1∑

k=0

X[k]w−knN


SFD—demonstratie (1)

• Matricea TFD (explicatia denumirii—mai târziu):

FN =

w0N w0

N . . . w0N

w0N w1

N . . . w(N−1)N

w0N w2

N . . . w2(N−1)N

...... . . .

...

w0N w

(N−1)N . . . w

(N−1)2

N

• Matricea FN are structura Vandermonde

• Matricea FN este simetrica (dar nu hermitica: FN 6= FHN )



• Matricea FN are coloane ortogonale si

FHN FN = FNFH

N = N · I

• Într-adevar, elementul (i, ℓ) al matricei FHN FN este

(FHN FN )iℓ =

N−1∑

k=0

w−kiN wkℓ

N =

N−1∑

k=0

wk(ℓ−i)N =

{

N, daca i = ℓ

0, daca i 6= ℓ

• Am demonstrat anterior (vezi (3), pag.35, prezentare cap.3):

N−1∑

k=0

wkmN =

N−1∑

k=0

e−j2πkm/N =

{

N, daca m mod N = 0

0, altfel



• Notam (oarecum abuziv)

x =

x[0]

x[1]...

x[N − 1]

, X =

X[0]

X[1]...

X[N − 1]

• Relatia (1) se poate scrie în forma compacta

x =1

NFH

N X

• Înmultind la stânga cu FN , rezulta X = FN x, ceea ce aratacum se calculeaza coeficientii X[k] din (1)

• Relatia dintre x si X este biunivoca


Coeficientii SFD

• Coeficientii seriei Fourier (1) asociate semnalului periodicx[n] au forma

X[k] =

N−1∑

n=0

x[n]e−j 2π

Nkn =

N−1∑

n=0

x[n]wknN

• În forma vectorialaX = FN x

• Coeficientii X[k] ai seriei Fourier pot fi definiti pentru oricek ∈ Z, "semnalul" astfel obtinut fiind N -periodic (se observa

ca wknN = w

(k+N)nN )


SFD—analiza si sinteza

• Analiza

X[k] =

N−1∑

n=0

x[n]wknN

X = FN x

• Calculeaza coeficientiiSFD (vezi semnificatiemai jos)

• Sinteza

x[n] =1

N

N−1∑

k=0

X[k]w−knN

x =1

NFH

N X

• Reface semnalul X dincoeficientii SFD

• Relatia dintre semnalul x[n] si coeficientii SFD asociati estebiunivoca


SFD pentru sinusoide (1)

• Se considera urmatoarele sinusoide, cu m ∈ 0 : N − 1

x1[n] = ej 2πm

Nn x3[n] = sin

(

2πmN n

)

x2[n] = e−j 2πm

Nn x4[n] = cos

(

2πmN n

)

• Identificând pur si simplu în (1), obtinem, pentruk ∈ 0 : N − 1,

X1[k] = Nδ[k − m]

• Toata puterea semnalului este concentrata într-o singurafrecventa

• Observând ca x2[n] = ej 2π(N−m)

Nn, obtinem

X2[k] = Nδ[k − (N − m)]


SFD pentru sinusoide (2)

•• Pentru sinusoidele reale, observam ca

x3[n] =x1[n] − x2[n]

2j, x4[n] =

x1[n] + x2[n]

2

• Concluzie: seria Fourier asociata unei sinusoide complexede frecventa 2πm/N are un singur coeficient nenul, cel cuindice m sau N − m

• Daca sinusoida este reala, atunci ambii coeficienti suntnenuli (mai putin atunci când m = 0 sau m = N/2, daca N epar)

• Caz particular: pentru m = 0, rezulta x3[n] = 0 si x4[n] = 1.Deci X3[k] = 0 si X4[k] = Nδ[k]

• Daca N par si m = N/2, rezulta x3[n] = 0 si x4[n] = (−1)n.Deci X3[k] = 0 si X4[k] = Nδ[k − N/2]


SFD—semnificatie

• Coeficientii SFD X[k] arata ponderea sinusoidelor cufrecventele 2πk/N în semnalul N -periodic x[n]

• Puterea semnalului x[n] în frecventa 2πm/N este data dedoi coeficienti ai SFD, anume X[m] si X[N − m] (mai putinpentru m = 0, m = N/2 (daca N e par), adica pentrufrecventele ω = 0, respectiv ω = π)

• Mai precis, puterea în frecventa 2πm/N este|X[m]|2 + |X[N − m]|2 (vezi teorema lui Parseval)


SFD—ıntarziere (1)

• Întârziere. Daca n0 ∈ Z si y[n] = x[n − n0], atunci

Y [k] = wkn0

N X[k]

• Demonstratie:

Y [k] =

N−1∑

n=0

y[n]wknN =

N−1∑

n=0

x[n−n0]wk(n−n0)N wkn0

N = wkn0

N X[k]

Atât x[n] cât si v[n] = wknN sunt N -periodice, deci

N−1∑

n=0

x[n − n0]wk(n−n0)N =

N−1∑

n=0

x[n]wknN


SFD—ıntarziere (2)

• Întârzierea cu n0 a unui semnal N -periodic este echivalentacu deplasarea ciclica de n0 ori la dreapta a esantioanelor cusuportul 0 : N − 1

• Stânga: semnal periodic cu perioada N = 6. Dreapta:acelasi semnal, dupa întârzierea cu n0 = 2

n

... ...

n

... ...


SFD—proprietati (1)

• Liniaritate. Pentru orice α, β ∈ C avem

SFD(αx[n] + βy[n]) = α · SFD(x[n]) + β · SFD(y[n])

• Complex conjugare. Pentru y[n] = x∗[n] obtinem

Y [k] =

N−1∑

n=0

x∗[n]wknN =

(

N−1∑

n=0

x[n]w−knN

)∗

= X∗[−k] = X∗[N−k]

Ultima egalitate rezulta din periodicitatea coeficientilor SFD


SFD—proprietati (2)

• Daca semnalul x[n] este real, atunci x∗[n] = x[n] si

X[k] = X∗[−k]

ReX[k] = ReX[−k] ImX[k] = −ImX[−k]

|X[k]| = |X[−k]| argX[k] = −argX[−k]

• "Teorema" lui Parseval:

N−1∑

n=0

|x[n]|2 =1

N

N−1∑

k=0

|X[k]|2

• Demonstratie (ne amintim ca x = 1N FH

N X si FNFHN = N · I):

N−1∑

n=0

|x[n]|2 = xH x =1

N2XHFNFH

N X =1

NXHX =

1

N

N−1∑

k=0

|X[k]|2


Convolutie periodica (1)

• Convolutia periodica a semnalelor N -periodice x[n] si y[n]este semnalul

x[n] ⊛ y[n]def=

N−1∑

ℓ=0

x[ℓ]y[n − ℓ]

• E convolutia obisnuita, dar pe o singura perioada (si tinândseama de ciclicitatea data de periodicitate)

• SFD asociata convolutiei a doua semnale este produsul lanivel de element al SFD semnalelor

SFD(x[n] ⊛ y[n]) = X[k] · Y [k]


Convolutie periodica (2)

• Demonstratie: SFD asociata semnalului x[n] ⊛ y[n] este

N−1∑

n=0

N−1∑

ℓ=0

x[ℓ]y[n−ℓ]wknN =

(

N−1∑

ℓ=0

x[ℓ]wkℓN

)(

N−1∑

n=0

y[n − ℓ]wk(n−ℓ)N

)

adica X[k]Y [k]

• Expresia de mai sus pentru Y [k] este corecta deoarece

y[n − ℓ] si wk(n−ℓ)N sunt N -periodice

• Modulatie în timp:

SFD(x[n]y[n]) =1

NX[k] ⊛ Y [k]


Transformata Fourier discreta

•• Fie x[n] un semnal cu suport 0 : N − 1

• Dorim sa analizam spectrul semnalului• Transformata Fourier (TF) a semnalului este

X(ω) =

N−1∑

n=0

x[n]e−jωn

• Aceasta expresie poate fi utilizata pentru evaluareaspectrului în orice punct ω ∈ [0, 2π]

• Un mod de calcul mai eficient, prin care se obtine spectruldoar în N puncte echidistante, se bazeaza pe transformataFourier discreta (TFD)


TFD—definitie

• Transformata Fourier discreta (TFD) a semnalului x[n] cusuport 0 : N − 1 este secventa

X[k] =N−1∑

n=0

x[n]e−j 2π

Nkn =

N−1∑

n=0

x[n]wknN , k = 0 : N − 1

• Notam X[k] = TFDN (x[n]) (ignorând eventual indicele Natunci când lungimea suportului rezulta din context)

• TFD este TF pentru ω = 2πk/N , k ∈ 0 : N − 1


TFD–interpretare

•• Pentru semnale cu suport finit, TFD reprezinta oesantionare a TF, în N frecvente echidistante aflate înintervalul [0, 2π]

n

|x[n]|1

k

ωN/2

πN

2π

|X[k]|

0

1


TFD—relatia cu SFD

• TFD se defineste la fel ca seria Fourier discreta asociatasemnalului N -periodic x[n], care reprezinta prelungirea prinperiodicitate a semnalului x[n]

x[n] = x[n mod N ]

• Facem conventia ca TFD se defineste doar pe esantioanele0 : N − 1, în timp ce SFD se prelungeste prin periodicitatepentru orice k ∈ Z

• În acest fel, notatiile X[k] pentru TFD si X[k] pentrucoeficientii SFD sunt consistente

• Toate proprietatile SFD se pot aplica transformatei Fourierdiscrete, cu precautia de a evita iesirea din suportul finit0 : N − 1 în urma deplasarilor (care sunt interpretate ciclic)


Convolutia ciclica

• Fie x[n] un semnal cu suport 0 : N − 1. Semnalul deplasatcircular ("întârziat") cu n0 esantioane la dreapta estey[n] = x[(n − n0) mod N ]

• Convolutia ciclica a semnalelor x[n] si y[n], ambele cusuport finit 0 : N − 1, este semnalul

x[n] ⊛N y[n]def=

N−1∑

ℓ=0

x[ℓ]y[(n − ℓ) mod N ]

• TFD a convolutiei ciclice a doua semnale cu suport0 : N − 1 este

TFD(x[n] ⊛N y[n]) = X[k] · Y [k]


TFD inversa

•• Daca x[n] este un semnal cu suport 0 : N − 1 siX[k] = TFD(x[n]), atunci are loc egalitatea

x[n] =1

N

N−1∑

k=0

X[k]ej 2π

Nkn =

1

N

N−1∑

k=0

X[k]w−knN

care defineste transformata Fourier discreta inversa• (Forma este identica cu SFD)


TFD—forma matriceala

• Notând

x =

x[0]

x[1]...

x[N − 1]

, X =

X[0]

X[1]...

X[N − 1]

se poate scrie

x =1

NFH

N X, X = FNx,

unde FN este matricea TFD (vezi pag. 7)


Esantionarea spectrului

• Fie x[n] un semnal cu suport 0 : N − 1

• X[k] = TFDN (x[n]) este o esantionare în N puncte aspectrului X(ω) al semnalului

• Cum obtinem o esantionare în M > N puncte ?• Prelungim artificial suportul

y[n] =

{

x[n], daca 0 ≤ n ≤ N − 1

0, daca N ≤ n ≤ M − 1

• Avem evident X(ω) = Y (ω)

• Deci Y [k] = TFDM (y[n]) este o esantionare în M puncte aspectrului X(ω)

• Daca M = pN , atunci Y [pk] = X[k]


Transformata Fourier rapida (FFT)

• Transformata Fourier rapida (FFT – Fast Fourier Transform)este numele generic pentru o clasa de algoritmi rapizi decalcul al transformatei Fourier discrete (TFD), pentrusemnale cu suport finit

• Primul algoritm de acest tip a fost propus de Cooley siTukey în 1965, dar ideea e mult mai veche (Gauss !)

• Înmultirea matrice-vector X = FNx are o complexitate deO(N2) operatii

• Algoritmii FFT au complexitate O(N log2 N)

• Reducerea complexitatii este semnificativa pentru valoripractice ale marimii suportului

• Pentru N = 1024, avem N2 ≈ 106 si N log2 N ≈ 104

• Pentru N = 100 complexitatea scade de N/ log2 N > 10 ori


Ideea FFT

• Se presupune ca N este putere a lui 2• Algoritmi FFT

◦ cu decimare în timp◦ cu decimare în frecventa

• Ideea de baza este de tip divide et impera• Calculul TFDN (·) se reduce la calculul a doua transformari

TFDN/2(·)• Pentru calculul fiecarei TFD de lungime mai mica, se aplica

recursiv acelasi mod de calcul


Complexitatea FFT

• Reducerea calculului TFDN (·) la calculul a douatransformari TFDN/2(·) are complexitate αN , unde α este oconstanta

• Complexitatea algoritmului este

αN + 2αN

2+ 4α

N

4+ . . .

• Numarul de termeni în suma de mai sus este log2 N ,i.e. numarul de înjumatatiri necesare pentru a ajunge de laN la 1

• Concluzie: complexitatea este αN log2 N


Decimare ın timp—ideea de calcul (1)

• Definitia TFD pentru un semnal cu suport 0 : N − 1

X[k] =

N−1∑

n=0

x[n]wknN

• Separam doua sume, una pentru indici pari, alta pentruindici impari

X[k] =

N−1∑

n par

x[n]wknN +

N−1∑

n impar

x[n]wknN


Decimare ın timp—ideea de calcul (2)

• Substituim n = 2m, m = 0 : N/2 − 1, în prima suma, sin = 2m + 1, m = 0 : N/2 − 1, în a doua

X[k] =

N/2−1∑

m=0

x[2m]w2kmN +

N/2−1∑

m=0

x[2m + 1]wk(2m+1)N

• Tinem seama ca

w2kmN = e−j 2π

N2km = e

−j 2π

N/2km

= wkmN/2

si obtinem

X[k] =

N/2−1∑

m=0

x[2m]wkmN/2 + wk

N

N/2−1∑

m=0

x[2m + 1]wkmN/2


Decimare ın timp—primul pas

• Notam xp[m] = x[2m] semnalul cu suport 0 : N/2 − 1 formatdin esantioanele pare ale semnalului initial

• Notam xi[m] = x[2m + 1] pentru esantioanele impare

• Transformatele Fourier discrete ale acestora sunt

U [k] = TFDN/2(xp[m]), V [k] = TFDN/2(xi[m])

• Putem deci scrie

X[k] = U [k] + wkNV [k], k = 0 : N − 1

• În aceasta relatie avem k = 0 : N − 1, deci apar douaperioade ale transformatelor Fourier discrete U [k], V [k]


Decimare ın timp—primul pas, schema de calcul

-

-

-

-

-

-

-

-

��

��

��

��

��

��@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

U [1] = U [5] w0N

w1N

w4N

w5N

U [0] = U [4]

U [2] = U [6]

U [3] = U [7]

V [1] = V [5]

V [0] = V [4]

V [2] = V [6]

V [3] = V [7]

w6N

w7N

w2N

w3N

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]

TFDN/2(·)

TFDN/2(·)

-

-

-

-

-

-

-

-

x[0]

x[2]

x[4]

x[6]

x[1]

x[3]

x[5]

x[7]


Decimare ın timp—forma recursiva

• Folosind recursiv metoda de înjumatatire de mai sus,obtinem un prim algoritm FFT

• Daca N = 1, atunci TFD este identica cu semnalul• Pentru instructiunile 2.3 si 2.4 sunt necesare N adunari

complexe si N înmultiri complexe (constantele wkN sunt

tabelate)

functie X = FFT(x,N)1. daca N = 1 atunci

1. X = x2. altfel

1. Pune xp[m] = x[2m], xi[m] = x[2m + 1], pentru m = 0 : N/2 − 12. Calculeaza U = FFT(xp, N/2), V = FFT(xi, N/2) (apel recursiv)3. X[k] = U [k] + wk

NV [k], pentru k = 0 : N/2 − 14. X[k] = U [k − N/2] + wk

NV [k − N/2], pentru k = N/2 : N − 1


Decimare ın timp—diagrama fluture

• Implementarile practice ale algoritmului FFT nu folosescapelurile recursive, ci variante iterative echivalente, careconduc la programe mai eficiente

• Diagrama fluture (butterfly) din pagina urmatoare ilustreazatoate operatiile pentru cazul N = 8

• Liniile punctate verticale separa etapele de calcul (iteratiilesau nivelele de recursie, dupa cum interpretam algoritmul)

• Sunt log2 N etape si în fiecare dintre ele se efectueaza 2Noperatii, ceea ce conduce la un total de 2N log2 N


Decimare ın timp—diagrama fluture pentru N = 8

w08

w18

w48

w58

w68

w78

w28

w38

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]��

��

��

��

��

��

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

w04

w14

@@

@@

@@R

@@

@@

@@R

w24

w34

��

��

��

��

��

��

w04

w14

@@

@@

@@R

@@

@@

@@R

w24

w34

-

��*

-

HHHHHHjw0

2w12

-

-

-

-

-

-

��*HHHHHHjw0

2w12

��*HHHHHHjw0

2w12

��*HHHHHHjw0

2w12

x[0]

x[4]

x[2]

x[6]

x[1]

x[5]

x[3]

x[7]


Ordine bit-inversa

• În ce ordine se afla esantioanele semnalului de intrare ?

• Înaintea ultimei etape, elementele x[n], cu n par, se afla înjumatatea de sus a diagramei (adica sunt primele), iar celecu n impar se afla în jumatatea de jos

• Privind la reprezentarea binara a lui n, elementele cu ultimulbit al indicelui egal cu zero sunt în prima jumatate

• Înaintea penultimei etape, elementele cu indice par suntseparate în doua; cele cu indice par în aceasta secventa,adica cele pentru care penultimul bit al lui n este zero, seafla în sfertul de sus al diagramei; celelalte, pentru carepenultimul bit este 1, sunt în al doilea sfert

• Concluzie: esantioanele intrarii se afla în ordine bit-inversaa indicilor


Diagrama fluture ımbunatatita

•• Numarul de înmultiri din diagrama fluture se poate reduce• Observam ca

wk−N/2N = e−j( 2kπ

N−π) = −wk

N

• Pentru un divizor K al lui N putem scrie

wmK = w

mN/KN

• Concluzie: în diagrama fluture se pot utiliza doarconstantele wk

N , k = 0 : N/2 − 1

• În noua diagrama sunt doar 3N/2 log2 N operatii complexe,din care doar N/2 înmultiri

• Reducerea este datorata aparitiei constantelor −1, astfel caunele înmultiri dispar


Decimare ın timp—diagrama fluture ımbunatatita

−1

−1

−1

−1

X[0]

X[1]

X[2]

X[3]

X[4]

X[5]

X[6]

X[7]��

��

��

��

��

��

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

@@

@@

@@R

@@

@@

@@R

−1

−1

��

��

��

��

��

��

@@

@@

@@R

@@

@@

@@R

−1

−1

��*HHHHHHj−1

��*HHHHHHj−1

��*HHHHHHj−1

��*HHHHHHj−1

x[0]

x[4]

x[2]

x[6]

x[1]

x[5]

x[3]

x[7]

w08

w18

w28

w38

w08

w28

w08

w28

-

-

-

-

-

-

-

-

w08

w08

w08

w08


Decimare ın timp—forma iterativa

• Calculele se pot desfasura pe loc în vectorul x

functie x = FFT_decimare_timp(x,N)1. Ordoneaza x în ordine bit-inversa a indicilor2. pentru i = 1 : log2 N

1. K = 2i

2. pentru k = 0 : K : N − 11. pentru m = 0 : K/2 − 1

1. y = x[k + m]

2. z = wmN/KN x[k + K/2 + m]

3. x[k + m] = y + z4. x[k + K/2 + m] = y − z


Decimare ın frecventa—ideea de calcul (1)

• Idee duala celei folosite pentru decimarea în timp• Separarea se face în transformata Fourier discreta X[k]

• Consideram întâi indicii pari, k = 2ℓ, ℓ = 0 : N/2 − 1

X[2ℓ] =

N−1∑

n=0

x[n]w2ℓnN

• Separam primii N/2 termeni din suma de ultimii N/2 (pentrucare facem substitutia n → n + N/2)

X[2ℓ] =

N/2−1∑

n=0

x[n]wℓnN/2 +

N/2−1∑

n=0

x[n + N/2]wℓ(n+N/2)N/2



• Tinând seama ca wℓN/2N/2

= 1, obtinem

X[2ℓ] =

N/2−1∑

n=0

(x[n] + x[n + N/2]) wℓnN/2

• Egalitatea de mai sus este

X[2ℓ] = TFDN/2(x[n] + x[n + N/2]), ℓ = 0 : N/2 − 1

• Am exprimat jumatatea para a transformatei X[k] printr-oTFD de lungime N/2 a semnalului u[n] = x[n] + x[n + N/2]obtinut din semnalul initial x[n]



• Pentru indicii impari, k = 2ℓ + 1, ℓ = 0 : N/2 − 1, scriem înmod analog

X[2ℓ + 1] =

N−1∑

n=0

x[n]w(2ℓ+1)nN

=

N/2−1∑

n=0

x[n]w(2ℓ+1)nN +

N/2−1∑

n=0

x[n + N/2]w(2ℓ+1)(n+N/2)N

=

N/2−1∑

n=0

x[n]wnNwℓn

N/2 +

N/2−1∑

n=0

x[n + N/2]wnNwℓn

N/2wℓNN w

N/2N

=

N/2−1∑

n=0

wnN (x[n] − x[n + N/2]) wℓn

N/2



• Ultima relatie este echivalenta cu

X[2ℓ+1] = TFDN/2(wnN (x[n]−x[n+N/2])), ℓ = 0 : N/2− 1

• Am exprimat jumatatea impara a transformatei X[k] printr-oTFD de lungime N/2 a semnaluluiv[n] = wn

N (x[n] − x[n + N/2])

• Calculul unei TFD de lungime N se reduce la calculul adoua TFD de lungime N/2, ale unor semnale obtinute printransformari simple ale celui initial


Decimare ın frecventa—primul pas, schema de calcul

-

-

-

-

-

-

-

-

��

��

��

��

��

��@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

w0N

w1N

−1

−1

−1

−1

w2N

w3N

x[0]

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

TFDN/2(·)

TFDN/2(·)

-

-

-

-

-

-

-

-

X[0]

X[2]

X[4]

X[6]

X[1]

X[3]

X[5]

X[7]

u[0]

u[1]

u[2]

u[3]

v[0]

v[1]

v[2]

v[3]


Decimare ın frecventa—forma recursiva

functie X = FFT(x,N)1. daca N = 1 atunci

1. X = x2. altfel

1. u[n] = x[n] + x[n + N/2], pentru n = 0 : N/2 − 12. v[n] = wn

N (x[n] − x[n + N/2]), pentru n = 0 : N/2 − 13. Calculeaza Xp = FFT(u,N/2), Xi = FFT(v,N/2) (apel recursiv)4. X[2ℓ] = Xp[ℓ], X[2ℓ + 1] = Xi[ℓ], pentru ℓ = 0 : N/2 − 1


Decimare ın frecventa—diagrama fluture, N = 8

w08

w18

−1

−1

−1

−1

w28

w38

x[0]

x[1]

x[2]

x[3]

x[4]

x[5]

x[6]

x[7]

X[0]

X[4]

X[2]

X[6]

X[1]

X[5]

X[3]

X[7]

@@

@@

@@R

@@

@@

@@R

��

��

��

��

��

��

HHHHHHj��*

−1 w08

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

��

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

@@

@@

@@

@@

@@

@@R

-

-

-

-

-

-

-

-

w08

w28

HHHHHHj��*

−1 w08

@@

@@

@@R

@@

@@

@@R

��

��

��

��

��

��

HHHHHHj��*

−1 w08

w08

w28

HHHHHHj��*

−1 w08

−1

−1

−1

−1


Decimare ın frecventa—forma iterativa

• Esantioanele transformatei X[k] sunt în ordinea bit-inversaa indicilor

• Numarul de operatii este 3N/2 log2 N

• Calculele se pot desfasura pe loc în vectorul x

functie x = FFT_decimare_frecventa(x,N)1. pentru i = 1 : log2 N

1. K = N/2i−1

2. pentru k = 0 : K : N − 11. pentru m = 0 : K/2 − 1

1. u = x[k + m] + x[k + K/2 + m]

2. v = wmN/KN (x[k + m] − x[k + K/2 + m])

3. x[k + m] = u4. x[k + K/2 + m] = v

2. Ordoneaza x în ordine bit-inversa a indicilor


Calculul TFDI utilizand FFT

• Se cunosc coeficientii transformatei Fourier discrete X[k],k = 0 : N − 1, ai unui semnal x[n] cu suport 0 : N − 1

• Cum se pot calcula valorile semnalului folosind FFT ?• Din definitia TFDI rezulta

x∗[n] =1

N

N−1∑

k=0

X∗[k]wknN

• Rezulta ca Nx∗[n] = TFD(X∗[k])

• O alternativa este scrierea unor algoritmi speciali pentruTFDI, care sunt obtinuti prin modificarea algoritmilor FFT; îndiagramele fluture apar puteri negative ale constantei wN ,în locul celor pozitive.


Analiza ın frecventa a semnalelor

• Separare în cadre, eventual cu suprapunere• Aplicare fereastra pentru fiecare cadru• Exemple:

◦ Spectrograma◦ Spectrometru cu bare◦ Periodograma

• (Notiunile de aici vor fi explicate la tabla !)


Transformari bloc (ortogonale)

• Consideram un bloc (cadru) de lungime N al unui semnaldiscret

x =

x[0]

x[1]...

x[N − 1]

∈ RN

• O transformare bloc este o matrice U ∈ RN×N ortogonala

(UT U = I)

• Vectorul X = Ux ∈ RN se numeste transformata (prin U ) a

blocului x

• Transformarile ortogonale conserva energia:

‖X‖22 = XT X = xT UT Ux = xT x = ‖x‖2


TFD ca transformata bloc

• În cazul complex U ∈ CN×N este unitara: UHU = I

• De exemplu TFD se bazeaza pe matricea TFD de lapagina 7, iar transformarea bloc corespunzatoare este

U =1√N

FN

• Avantaje:◦ X este o esantionare a spectrului, deci semnificatia

transformarii e clara◦ Exista un algoritm rapid de calcul (FFT)

• Dezavantaj: X este în general complex, chiar dacasemnalul este real


Alte transformate bloc

• Rezultat real pentru semnal real• Transformata cosinus discreta (TCD):

ukn =αk√

2cos

[(

n +1

2

)

kπ

N

]

, αk =

{

1, k = 0 sau k = N − 1√2, altfel

• Transformata Hartley

ukn = cos

(

2π

Nkn

)

+ sin

(

2π

Nkn

)

• Aceste transformate (si altele) se pot calcula utilizând FFT(plus alte operatii înainte si dupa FFT)

• Coeficientii transformatelor au legatura cu spectrul: primiicoeficienti reprezinta frecventele joase etc.


Transformata Karhunen-Loeve

• Transformarile anterioare (TFD, TCD) sunt fixe• Ele dau rezultate bune pentru multe semnale, dar nu sunt

optime• Transformata Karhunen-Loeve este adaptata proprietatilor

statistice ale semnalului de intrare• TKL este optima, în sensul concentrarii energiei semnalului

într-un numar mic de coeficienti, proprietate utila pentrucodare


Aplicatii ale transformatelor bloc

• Exemplu 1: codare (compresie cu pierderi)• Exemplu 2: egalizor grafic• (Exemplele vor fi explicate la tabla !)


Bogdan Dumitrescu Facultatea de Automatica s¸i …Bogdan Dumitrescu Facultatea de Automatica s¸i...

Documents

Transcript of Bogdan Dumitrescu Facultatea de Automatica s¸i …Bogdan Dumitrescu Facultatea de Automatica s¸i...