INSTITUTUL CENTRAL DE FIZICA INSTITUTUL DE FIZICA SI INGINERIE NUCLEARA

^MC-29-1977 Turtle

CALCULUL NUMERIC AL TRANSFORMATEI FOURIER DISCRETE SI APLICAŢII IN PRELUCRAREA STATISTICA A

DATELOR EXPERIMENTALE

PARTEA I, TEORIA TRANSFORMATEI FOURIER RAPIDE SI CALCULUL APROXIMATIV AL PERIODIOGRAMEI/

DENSITĂŢII SPECTRALE DE PUTEREV FUNCŢIEI DE AUTOCORELATIE; FILTRARE DIGITALA

P.C.MARINESCU Ai T.G.RAPULFSCU

MiriiprcTt _ poMANIA

- I -

CALCULUL NUMERIC AL TRANSFORMATEI FOURIER DISCRETE SI APLICAŢII IN PRELUCRAREA STATISTICA A

DATELOR EXPERIMENTALE

PARTEA I, TEORIA TRANSFOPMATEI FOURIER RAPIDE SI CALCULUL APROXIMATIV AL PERIODIOGRAME1,

DENSITĂŢII SPECTRALE DE PUTERE,' FUNCŢIEI Dfc AUTOCORELATIE: FILTRARE DIGITAL

V.C.UARINESCU ti T.G.XAVULESCU

Institutul de Fizici «1 Inginerie Nucleari, Bucureşti KoaSnia

C O N Ţ I N U T

1. Introducere 2. Transformata Fourier finite.

2.1. Relaţie dintre transformata Fourier finita si transformate Fourier integrele. 2.1.1. Transformata Fourier integrale. 2.1.2. Eşantionarea uniforme e unei funcţii continui,

» i 2.1.3 . Definiree transformatei Fourier f i r i t e .

2 .2 . Proprietăţi ale transformatei Fourier f in i t e .

- 2 -3- Transformata Fourier rapida ( FFT ).

3.1. Călcâiul numeric al transformatei Fourier finite. 3.2. 0 justificare intuitiva pentru algoritmii de FFT. 3.3. Descompunerea transformării Fourier finite in produs

de transformări elementare. 3.4. Calculul recuxsiv al transformatei Fourier finite -

w

transformata Fourier rapida. ° "î. Optimizarea algoritmilor de transformare Fourier rapida.

4. Aplicaţiile transformatei Fourier rapide. 4.1. Convolutia discreta si filtrarea digitals.

4.1.1. Convolutia discreta. »

4.1.2. Procedee de filtrare digitala* 4.2. Estimarea funcţiilor de autocovarianta si a funcţiilor

» * » de crosse o varianta. » 4.2.1. Estimare nepreferentiala si consistenta. 4.2.2. Estimarea funcţiei de autocovarianta. 4.2.3. Estimarea funcţiei de crosseovarianta.

i » 4.3. Estimarea periodiogramei si a densităţii spectrale de

i > putere.

*• 4 . 3 . 1 . Periodiograma s i densitatea spectrala de putere.

4 . 3 . 2 . Călcâiul periodiogramei.

4.3.3. Estimarea densităţii spectrale de putere prin netezirea periodiogramei.

4.3.4. Estimarea densităţii spectrale de putere folosind segmentarea înregistrărilor si efectumd

h » medierea m timp a periodiogramelor modificate a acertor înregistrări. "

- 3 -

Tki Integral fcui*.ci T rari term hai a taxge lange c; : ? c / i c « ( i o n s -in 4-ich axeat ai commun-tca^-ion tKco-ty, c-ilcu-i-t fr,O~*L/, p i t i /uc j , e t c .

In i".(ioi tc pexţcxm d<.icxete Fcuxiex T*ani|$cim the Finite Fcut-ter TtanA^oim <4 denned ; x.-£ opeta-te* upon H tâmplei d a

uni.icii>tly àamplzd ccntinucut tu.nc.tian. All the. pxopextiei .known

< n 'de co<ifinucu-j cate. can be ^ourtd in the ditcxete ca ie a£.jc.

The $<\it part c& the papzx pxeienti the xelatiomhip

betuven the Finite Fouxiex Txamtoxm and the Integxal one.

The computing oi a F-in^-te Fout-iel Txaniioxm in a pxoblem

in itteli nince in cxdex to txaniioxm a tet oi N data we have, to 2

pex&oxm M nopeiation6"ii the txantioxmation xtlationt axe uitd dixectty. An algcxithm known ai the fait FouxitX Txaniioxm [FFT)

xeducei thii iiguxe ixom N to a moxe xeionablt W log„H, when N

ii a powex o£ two. The oxiginal Cooley and Tuckey algoxithm iox

FFT can be ^axthex impxoved «hen hJ.ghex ba*ii axe uied. The pxice to be paid in thii caje ii the incxeate in complexity oi inch algoxithmi.

The xtccuxence xelationi and a compaxation among inch

algoxithmi axe pxtitnted.

The key point in undexitanding the application oi F T xetidtt in tht convolution theoxem which itatté that the con-

f volution ian N type pxoteduxe) oi tht pximitivt iunctiom Li equivalent to tki oxdinax multiplication oi tktix txaniţoxmi,

Sinte iittexing ii actually a convolu.ti.on pxocea we p*e*e»t< ieve*<U pxoctduxti. to ptxioxm digital filttxing by meant oi FFT. The btit ii the ont uiing tht itgmtntation oi xecoxdi and tht txaniioxmation oi paixi oi xtcoxdt.

In tht digital pxoctiiing oi iignatA, btiidti digital iiltexing a ipecial attention li paid to tht titimation o6 va-xioui itatittical thaxacttxiitid oi a iignal ai i autocoxxelation and coxxelation iunctiom, ptxiodiogxami, dentity pouiex ipectxum, etc.

<Ht give ievtxal algoxithmi iox tht comiittnt and un-bia&ed eitimation oi iuch iunctiom, by r.\eant oi FFT.

- A -

1. IIÎTROEUCSHB

Introducerea cranaformatei Fourier finite permite evaluarea -îumerica a transformatei Pourier. In analiza Fourier finita, se re­găsesc proprietăţile cunoscute din analiza Pourier continua; i.-une-

t

roasele aplicaţii ale analizei Fourier pot astfel beneficia de avantajele metodelor numerice de calcul/1/ .

Calculul direct al transformatei Fourier finite este insa deosebit de laborios i transformarea unul sir de N data Implica

2 A A *

efectuarea a N 'operaţii' astefftl incit chiar pentru valori rezo­nabile ale Iul N timpul de calcul este prohibitiv de mare*

Transformata Fourier rapida (PPT , Fast Fourier Transform) reprezintă un procedeu de calcul al transformatei Fourier finite care permite reducerea substanţiala a timpului de calcul al transfor­matei, numărul de operaţii fiind in acest caz proportional cu HloggH. Programele de calcul folosite astăzi se bazează exclusiv pe diferite versiuni ale algoritmilor de FFT.

Aplicaţiile practice in tehnica si în diferite ramuri ale ştiinţei ale transformatei Fourier /2/ , /3/,M/ elnt trecute succint în revista in cele ce urmează.

Rezolvarea sistemelor de ecuaţii incegro diferenţiale sau cu derivate partiale care descriu comportarea unui sistem fizic implica adesea dificultăţi care pot fi evitate folosindu-se metodele analizei prin transformare Fourier*

In general analiza p"*in transformare xsi propune sa diminueze complexitatea unui calcul dlerett intr-un domeniu dat .efectuind o transformare a elementelor care participa la calcul,in alt domeniu. In care operaţiile dintre transformatele elementelor sint mai uşor

» i

de efectuat) dupa efectuarea acestor operaţii se calculează transformata inversa a rezultatelor revenindu-ee astfel la domeniul original . un exemplu bine cunoscut Ém il reprezintă calculul cu ajutorul logaritmilor.

- 5 -

!.. a'.udiul s i s temelor l i n e a r e invar ian te in ciap ca lcu lu l

rsapuaaului s is temului se poate efectua folooind transforaarea

Fo urier pentru a se evita dificultăţile re*oivării ecuaţiilor uit-e^ro-diferentiale ale Bistemului; in domeniul transformatei

> r'ourier răspunsul aisteaului se poate calcula ca un produs dintre funcţia de transfer a ai et ei .ului si s tisului aplica; la intrarea sistemului. Calculul răspunsului circuitelor electrice liniare constituie numai una dintre aplicaţiile importante ale acestui

> domeniu/5/1/6/ .

Teoria proceselor Btochastice si calculul probabilităţilor folosesc transformata Fourier /7/,/8/./9/,/10/ * funcţia caracteristic câ a unei variabile aleatoare <•. «*•• definită ca transformata Courier a funcţiei de densitate de probabilitate. Deasemenea densitatea spectrală de putere a unei variabile aleatoare este definita drept transformata Fourier a funcţiei de autocovariantă. Teoria Btatiptica a comunicaţiilor /lî/,/12/ beneficiază nemijlocit de

» aceste metodei de exemplu extragerea informaţiei de sub zgomot se realizează cu filtre a căror funcţie de transfer satisface condiţia

> Winner-Hopf* /13/ , exprimată In termeni ai densităţii spectrale de putere a semnalului perturbat*

Studiul antenelor.optica,difracţia electronilor razelor JC si • A '- 3 J

neutronilor la imprastierea staţionara fac apel la transfoi • » • »

Fourier. De exemplu la difrac tarea de către un ansamblu constituit din centre punctiforme de imprastiere se arata /14/ ca distribuţia unghiulara a amplitudinilor după imprastiere depinde de transformata Fourier a distribuţiei spatiale a centrilor de imprastiere.

' * A l

Un domeniu nou,dar de mare interes ii reprezintă si prelucrarea optica a informaţiei cu ajutorul hologramelor Fourier.

3 A -Trebuie remarcat insa faptul ca deşi este un domeniu cu

numeroase aplicaţii , analiza Fourier a ajuns relativ tirziu sa j foloseasaa metodele numerice de calcul si aceasta numai dupa >

introducerea transformatei Fourier rapide. Dar ut i l izarea transforma-

- 6 -A

tei Fourier rapide in domeniile amintite nu decurge direct , ca o ~ — A

aplicaţie numerica imediata a metodelor analitice; in funcţie de ~ wJ

natura fenomenului studiat se cautâ o soluţie aproximativa care t

•«• w M

sa estimeze cu o precizie dorita valoarea pe care dorim s-o calculam. A — De exemplu in secţiunea rezervata aplicatiiloi din domeniul procese-

% J

lor stochastlce vom prezenta procedeee de estimare a valorii densită­ţii spectrale de putere . a periodiogramei , a funcţiei de autocova-» i

rianta , pornind delà o formula de calcul care asigura o estimare nepreferentiala,consistenta ei cu o eroare de estimare data.Uneori, ca de exemplu in cazul densităţii spectrale de putere , sînt trecute

> /* "• A A In revista mai multe procedee uimind a fi folosit in aplicaţii

A

procedeul cel mai potrivit in funcţie de caracteristicele fenomenului urmărit. Indiferent de domeniul de aplicaţii la care ne referam , cunoaş­terea in profunzime a fenomenului fizic si a modului in care au fost obţinute datele numerice caracterlzind mărimea fizica ce trebuie

— " A transformata este indispensabila; in cazul unui semnal electric de exemplu , daca eşantionarea nu este uniforma sau daca frcventa de

•» »

eşantionare nu satisface criteriul Nyquist rezultatele oricăror 3 „ A calcule de analiza spectrala isi pierd orice sens fizic.

- 7 -

2. Transformata Pourier finita.

2.1. Relaţia dintre transformata Fourier integrala si transformata » •

Pourier finită.

2.1.1. Transformata Pourier- integrala.

Integrala Fourier este definita de expresia t H(f) »]h(t)*exp(-2ti j*f»t)*dt (2.1.1.)

cu j s^-1 .

Daca aceaBtă integrală exiBta pentru fiecare valoare a parame­trului f atunci H(f) este transformata Fourier integrala a funcţiei h(t) .

In general H(f) este o cantitate complexa s H(f) -lH(f)lexp{j*e(f) ) (2.1.2.) Transformata Courier integrala inversa este definita de

relaţia t h(t) - \ H(f)«exp(2*Uj*f»t)»df (2.1.3.)

0 condiţie suficienta dar nu si necesara ca integrala 2.1.1. sa existe si ca transformata 11(f) să satisfacă relaţia de transformare inversa 2.1.3» este ca h(t) sa fie integrabila în sensul relaţiei!

i T <" >

|h(tj^dt < «O (2.1.4.) \Jn exemplu de funcţie ce nu satisface condiţia de integrabilitate 2.1.4. , dar care are transformata Fourier ce satisface relaţia 2.1.3. este funcţia s

i h(t) . (sin(a*t)/a»t) (2.1.5.)

Se arata /l5/ , că exista următoarea condiţie «ai puţin restrictiva i i

de existenta a transformatei Fourier integrale, condiţie pe care o uatisface si funcţia data de 2.1 ô . i

« i i Daca s

h(t) - q(t)»ain(2Ï»f»t*p) (2.I.6.)

cu f si p constante arbitrare si cu i

q(t*k)<q(t) (2.1.7.)

- 8 -ei daca i'u.'iciia h(t)/t este integrabila ia sensul relaţiei 2.1.4. pen'.ru 0<ici.l, atunci K(ţ) exiBta ai satisface 2.1.3* «

A A. A A ~* Majoritatea func iilor infinite in aplicaţii satisfac insa

condiţia 2.1.4. . In afara clasei de funcţii cu variaţie limitata , teoria

\ \ A

transformatei Fourier integrale se poate extinde s i in cazul

funcţ i i lor discontinue folosind teoria d i s t r i bu ţ i i l o r .

In cele ce urmează vom folosi terminologia tradiţionala din A teoria comunicaţiilor considerind pe m t j ca o l une t i e de variabila

» •»

timp ia r pe H(f) ca o funcţie de var iabi la frecventa. Dezvoltarea > ' -2>" f t

2 .1 .1 . a funcţiei h ( t ) pe fandlia de funcţi i exponentials e~ ' •' * - •) »

cu f fc R , va fi numita analiza spectrala i a r ;i(f) va purta au;;iele de spectrul lu i h( t ) .

- - — A Daca h(t) este o funcţie periodica cu perioada T0 a tu. ici in ' i 'J

locul unui spectru continu se obţine un spectru discret ,de liniii h(t) » } H(n)*exp(2Ï/n*t/r,) (2.1.6.)

cu T

H(n) - 1/f. I h(t)*exp(-2lî j*n*t/Ta)*dt (2.1.9.) o

Proprietatxle de convolutie ale transformatei Fourier integrale A A ""*

ne eint utile in cele ce urmează si le von prezenta succint; » demonstrarea acestor proprietăţi este i»aediata pornind delà defini-

•» tia transformatei Fourier integrale si va fi lăsata ca un exerciţiu. > _ \ > > _ Convolutia integrala a doui funcţii x(t) si y(t) este definita

de expresia! T. z(t) » x(t) • y(t) m j x(g)*y(t-C )*<iX (2.1.10.)

Teorema de convolutie in domeniul original (do;aeiiul timp) arata ca daca ( x(t) , X(f) ) si { y(t) , Y(f) ) sint perechi de transfor-.r.ate Fourier integrale atunci operaţia de convolutie in domeniul original este echivalenta cu )teratia de multiplicare in domeniul transformatei. Cu alte cuvinte,funcţiile . z(t) definita de expresia 2.1.10. si Z(D • X(f)*Y(f) , formează o pereche de tran—

1 ufornate Fourier integral:.

- 9 -2.1.2. Eşantionarea uniforma a unei funcţii continui. > » -,

Pentru a efectua un calcul numeric avem la dispoziţie un > A număr finit N de valori numerice b-(t^) • ics1,2,..,H , repreaentind

valorile funcţiei h(t) la momentele discrete de timp t^tg.*.^ . A, A A\

Deoarece in situaţiile practice Bintem interesaţi in studiul unor fenomene cu durata finita ^ vom face ipoteza ca pentru t > T.. h(t) - 0 { deasemenea in intervalul finit de observare a fenomenu­lui , (0,TJ) , vom considera cele K momente de observare egal epatiate in timp»

A •*

Prima intrebare la care trebuie formulat un răspuns este cea relativa la relaţia dintre şirul de valori numerice h(t.) si funcţia continua n(t) | daca funcţia h(t) poate fi unic determinata

» » cunoscind Birul de valori numerice h(t.) atunci vom putea afirma ca avem o reprezentare discreta a procesului continu iar rezulta­tele calculelor numerice de analiza spectrala vor fi consistente cu fenomenul fizic studiat*

Teorema de eşantionare arata ca daca h(t; are un spectru H(f) limitat ( H(i) «0 pentru f>f ) atunci condiţia necesara si suficienta ca h(t) sa poată fi reconstituit din slrul h(t.) •» » *

fc»0,1,...,U , este ca frecventa de eşantionare f sa fie cel. puţin dublul frecventei maxime t f din spectrul lui h(t) . Altfel spuB momentele de observare t̂ trebuie sa fie date de t

tJc " k*Te 1 S * * 1 (2.1.11.) cu perioada de eşantionare T data de i

•> e

Te - (1/fe)£(1/2»fc) (2.1.12.) Relaţia 2.1.12. este cunoscuta sub nunele de condiţia

> i Wyquiat iar frecventa i

fN q- 2 % (2.1.-3.)

se numeşte frecventa Myquist coreupunzatoare lui h(t) cu spectrul H(f) avînd frecventa maxima,f, . » c

Mu vom da o demonstrare acestei, teoreiue^care poate fi găsita in textele de teoria comunicaţiilor ,/ lU7,/l4/,/1^ . ci rom

- 10 -insista asupra Berusului ei fizic.

Fie h(t) si H(f) o pereche de transformate Fourier integrale, astfel incit H(f) este non-zero numai in intervalul ("f̂ »**"-)» figura 2.1.a. •

Figura 2.1.

Eşantionarea cu perioada T a funcţiei h(t) conduce la o reprezentare discreta hm(t) care poate fi aproximata cu ajutorul funcţiei delta , sub forma t

h^t) - ) h(n*T)*d(t-n*T) (2.1.14.) Spectrul H,p(f) al funcţiei esantionate h^t) va fi o repetare periodica cu perioada T (perioada de eşantionare) a spectrului H(f) al funcţiei continue h(t). Demonstrarea acestei aserţiuni

•»

eBte imediata pornind del» definiţia 2.1.1. a transformatei Fourier integrale aplicata funcţiei hp(t) exprimata de 2.1.14. •

A * ~ In cazul in care este satisfăcuta condiţia NyquiBt (figura

2.1.b. ) , aceasta repetare nu alterează forma spectrului original si printr-un procedeu de filtrare se poate reconstitui H(f) din li™ (f) • Acest lucru nu mai este posibil si in cazul in care condiţia Hyquist nu este satisfăcuta (figura 2.1.c.) ,căci spectrul rezultant are o forma diferita de cea a spectrului original datojita suprapunerii benzilor laterale.

Beferindu-ne la reprezentarea discreta , putem spune ca in primul caz exista suficiente valori numerice h(k*T.) , k«0,1,..I*-1 care printr-un procedeu de netezire (mediere) sa parmi ta aproxJuna- „

A -* , , A rea cu o precizie oricit de imne a valorii funcţiei h(i.) in orice

1 > pu:/;t. i.%(0,T9 (i'iyura 2.1.1-.).

- I l -

2.1.3* Definirea transformat»! Fourier f i n i t * .

Vom def ini o aproximai* numerica pantru transformata Fourier

integrala , directa ai invsrsa , s tab i l ind o r e l a ţ i e intre • > A x valori numerice repretentind valori ale funcţiei in unul dintre domenii si M valori numerice ale transfomatei, din cel d* al doilea domeniu.

"* •* A Funcţia continua h(t) va fi modificata in trai «tapa

(figura 2.2. ) ajungind în cela din urna an fis aproximata printr-o funcţia discreta si periodica h(t) . car* la rxndul si este

1 - . A , A descrisa prin I valori numtario* | deoarsoe h(t) est* periodica, transformata ei Fourier integrala>H(f)5 este discreta si periodica

A • •» C periodicitatea datorlndu-ee ssantionaril uniforma a lui h(t) ),

A *» puţind fi dsci descrisa prin S valori numeric*•

Operaţia ds diserstisar* a funcţiei h(t) (eşantion«e ou w A V * w i

perioada T,astfel aleaaa incit sa fi* satisfăcuta condiţia 2.1.12.) poate fi représentât» analitic oa o multiplicare a lui h(t) prin funcţia de eşantionare a_(t) fcart sete un sir periodic cu psrioa-da Tyds impulsuri delta},

Funotia ce résulta , hţ(t) , ar* o transformata Fourier into-grai» . Hţ(f), periodica | ea ae obtins prin repetarea cu perioada I a funcţiei H(f) conform teoremei d* convolutie din analisa Fourier integrala*

Deoarece h(t) poate fi definit* pe Întreaga axa r*ala , in „ -» A

aceasta etapa d* dlacretiaare , se obţin in oaşul general un număr infinit ds valori numerice. Operaţia A* truncar* . d* reţinere a unui număr finit li de eşantioane al* funcţiei h-(t), poate fi représentât» analitic ca o multiplicare prin funcţia d< trunoare s^ (t) (figura 2.4»g.) , care are o valoare unitara' in interiorul intervalului da observare (0,T#) si este zero In afara aoeatui interval i

- 12 -•ţ (O « 1 -T„/2Çt£T./2

•f (t) - 0 Itl >T0/2 (2.1.15.)

Funcţia rezultata la u n i eşantionării ai truncarii are expresia! » » *.o

. Yh(k*T) 4{t-k»T) (2.1.16.) Funcţia h-^ it) este erprimata m termeni a N valori

numerice h(t. ) k«0,',....,H-1 , obţinute pentru valori discrete t, » tc*T ale argumentului.

Semnificaţia fizica este transparenta i fenomenul descriu de h(t) este observat intr-un interval finit TD, la H momente discrete de timp , ansamblul celor N valori numerice -[Mt^H constituind tonalitatea informaţiei noastre asupra procesului h(t). Evident t

T. - H*T (2.1.17.) Funcţia de aproximare h,.,» (t) are o transformata Fourier

integrala H«ţ (f) (figura 2.2.J.) care consta din repetarea periodica (efect al eşantionării) a unei versiuni uşor dietoreiona-

» » te (efect al truncarii) a transformatei li(f) a funcţiei originale

•»

h(t) . Pasul următor este acela de a discretiza transformata Hm,„ (f)

Picura 2.2.

• funcţ ie i de aproximare i u T ( t ) . Punctia de eşantionare Q™ ( f )

din domeniul transformatei (f igura 2 . 2 . £ . ) u»e traneformala

Fourier integrala inversa ( f icuro 2.2.te.) de fon;;n :

qT ( t ) - T0 7 o(t-i'*T0) ( 2 . 1 . 1 0 . )

Diacreti»:ar'.)S tranciformatei II,,,- (fJ (oiullj-plicarcn orin funcţia A '

de eşantionare Q„, ( f ) ) efectuata in do.-nenj.ui ix-ancforinatei , ee te > i o

echivalenta cu operaţia de convolutie a funcţiei limm uin diiui-niul

or ig inal , prin funcţia q„. ( t ) { lunc l ia rezultanta va f i periodica

cu perioada Ta (perioada de eşantionare din domeniul transformatei)

Deci funcţ ia ce va aproxima in ce la din urma pe h ( w eete ' A h(t ) - h ^ ( t ) • qT<>(t) ( 2 . 1 . 1 9 . )

Dezvoltind obţinem t

U W.o rt-4 "* ** C > 4

• L ft, r f" (2.1.20.)

In notaţie compacta t t*-i h(t) - Tc y |£h(lc»T)* *(t-lc*T-f»T0)] (2.1.21.)

Funcţia de aproximare h(t; 8-a obţinut deci multiplicind funcţia originala h(t) prin t

- funcţia de eşantionare din domeniul original (domeniul timp) - funcţia de truncare

> - transformata Fourier inversa a funcţiei de eşantionare din

> ţ domeniul transformatei (domeniul frecventa) •

In aceste condiţii h(t) are o transformata Fourier integrala * A * A

H(f) ; in particular , datorita periodicităţii , h(t) poate fi A «**

dezvoltat in eerie Fourier , adică are un spectru discret. " A ** ** \ A — **

Ramlne de demonstrat ca H(f ) este la rindul sau o funcţie periodica A *•

puţind fi deci caracterizata de H valori numerice. Conform ecuaţiei 2*1.8. s A r"* * LCt) - 2_ H(n)»exp(j2*»»n»t/T.) (2.1.22.)

cu ^ VW« A f A H(n) - 1/T# l h(t)*exp(-J*2***n*t/T#) • dt (2.1.23.)

n-0,t1,S2 ,"Tw,i A ^ «

înlocuind in expresia 2.1.23* valoarea h(t) data de 2.1.21. obtinemt f

,Tj'a' H(n) - 1/T0 \ IT.J. £.hU«T)* o(t-k«T-l«Ta)J»exp(-j2»nt/T.)dfc

--*„k (2.1.24.) Deoarece integrarea se efectuează pe o singura perioada obtinemt

A n) -l[^hCk«î)» H(n) -II } hCk*î)*o(t-k*T)| exp(-j2înt/T.)*dt (2.1.25.)

TW2

- 14 -A -

Prerucn.-id expresia anurioju-a e i substituind T0 • LT obţinem l

expresia s 4.4 A «r H(n) - * ]hU*T!)*9Tpi~iZlaJli) ( 2 . 1 . 2 7 . )

km.0

/uneci» U(r.) este evident periodica cu perioada N t H(n+H) - H(n) (2.1.28.)

caci: exp(-j2î(i?+i*)k/ii) • exp(-j2~nic/N) (2.1.29.) Relaţia 2.1.27. defineşte transformata Fourier finita 1 )

directa. Transformata Fourier finita inversa este definita de relaţia » tf-A » ri A

h( VetJ» - > H(n)*exp( j2ihlc/H) lc-0,1 ,11-1 (2.1.30.) Pentru a verifica consistenta acestor transformări se poate iolocui 2.1.30. in 2.1.27. si se obţine transformarea identica*

> »

- 15 -L-.«d. Proprietăţi aie transfcroatei Fourier finite.

Proprietăţile trensformotei Fourier integrale se repaseso in s tur; iul transf ornate i Fourier finite.

Pornind de le definiţiile transformatei Fourier finite directe l

si inverse : 3i inverse . j.4

f.U) = Suin) !» î ( n , k ) k€(0,N-lî (2.2.1.)

H(n) = (l/N) H T h ( k ) » w"(n*k) nfc(Otlt-l) (2.2.2.)

cu »' = exp(2»ï«j'N) eu .i.^T (2.2.3.)

se demonstrează imediat proprietăţile tie liniaritate, deplasare a transformatei Fourier finite.

Proprietatea de linearitate : daca x(k),X(n) si v(k),Y(n) A l

sint pereeni de transformate Fourier finite atunci si z(k),Z(n) >

definite de: z(k) = x(k) • y(k) ktI0,N-l) Z(n) = X(n) • I(n) nt(0,N-l) (2.2.4.)

form aza o pereche d transformate Fourier finite. Proprietatea de deplasare in domeniul timp : daca h(k) si H(n)

» formează o pereche ăe transformate Fourier finite , atunci ai.

A ' z(k) si Z(n) formează o astfel de pereche, pentru orice întreg i :

j

z(k) = h(k-i) ke(O.N-l) Z(n) = H(n) * exp(-2»»»j»n»i/N) ne(0,N-l) (2.2.5.)

h w

Proprietatea de deplasare in domeniul transformatei : daca h(k) ni H(n) formează o pereche de transformate Fourier finite , iitunci ai z(k) si Z(n) formează o astfel de pereche, pentru crier-intrvf i , cu :

z(k) = h(k) » exp(3»MJ«n«i/N) ke-(C.N-l) ~(n) •-• H(n-i) n«,(C,N-l) (2.2.C.) L/«c»i h (k) este o funcţie para ut unei transformata s« Fourier

F i * • * ^ ^ finita , Hr(n) este o funcţie pora si reala : r *

>*-« - 16 -H ,n) = (1/N) » > h (k) • coe(a«»n»k/N) né(0,N-l) ( 2 . 2 . 7 . )

-Dacs h.(k) es te o funcţie impara, atunci transformata sa

Fourier f in i ta , H-(n) este o funcţie imDara ai imaginara data de :

H i(n) = - j ( l / N ) ) h t(k) » sin(2*Vnrk/N) ne(0,N-l) ( 2 . 2 . 8 . ) v«.-> w

- Orice h(k) periodic, cu perioada N, se poate descompune sub forma :

h(k) = h_!k) + h.(k) kfc(0,N-l) ( 2 . 2 . 9 . ) r 1

cu:

hp(k) = h(k)/2 + h(N-k)/2 (2 .2 .10 . )

hjCk) = h(k)/2 - h(N-k)/2 ( 2 . 2 . H . )

Transformata Fourier f in i ta a lui h(k) se scrie in acest caz :

H(n) = H (n) + H^n) nfe(O.N-l) (2.2.12.) cu H (n) dat de 2.2.7. si H-(n) dat de 2.2.8. . p i

- Teorema de convolutie in domeniul timp : daca x(k),X(n) si t >

y(k),Y(n) sint perechi de transformate Fourier finite ,atunci v

si z(k),Z(n) formează o pereche de transformate Fourier finite.cu : z(k) = £ x(i) * y(k-i) k fe(O.N-l)

• » • Z(n) = X(n) » Y(n) n*(0,N-l) (2.2.13.)

- Teorema de convolutie in domeniul frecventa : daca x(k),X(n)

si y(k),Y(n) sint perechi de transformate Fourier finite , atunci

si v(k),Z(n) formează o pereche de transformate Fourier finite, cu : z(k) = x(kj * y(k) k* (O.N-1)

*-« Z(n) = £X(i) » T(n-i) n*(0,N-l) (2.2.14.)

- Teorema do corelaţ ie : daca x(k),X(n) s i y(k),Y(n) s int

perechi de transformate Fourier f in i t e , atunci s i z(k),Z(n)

formează o pereche de transformate Fourier f i n i t e , cu : z(k) = £ x( i ) x y(k+i) k6(0,N-l)

• • 4

Z(n) = X^nî M / (n) n 6 ( 0 , N - l ) (2 .2 .15 . )

Prin Xc(n) s-a notat conjugatul complex al lui X(n)

- 17 -3. Transformata Fourier rapida.

3.1. Calculul nimeric al transformaiei Fourier finite.

Calculul transformatei Fourier finite directe si inverse, conforu relaţiilor 2.1.6 . ai 2.2*2 . conduce la un algoritm in car* numărul da operaţii este proportional cu pătratul numărului de

» » eleaente da transformat.

Utilizarea practica a unui algoritu de tip JT cunoaşte serioase limitări deoarece chiar la vitesele calculatoarelor moderne , pentru valorile de Interes ale lui M , timpul de calcul este considerabili de exemplu transformarea unui vector cu

11 â Vtm2 J «8192 componente cere circa 10 secunde unui calculator ce

" 6 ** efectueaea 0.5*10 operaţii pe secunda.

In 1963 Cooley si Tuckey /*6/ descriu un algoritm ic care numărul de operaţii cerut de transformarea Fourier finita a unui vector cu N componente , este proportional cu M*logo** daca 1. este de forma 2** • Noul algoritm care permite reducerea timpului de calcul cu un factor H/losgH cunoaşte o larga aplicare sub numele de transformare Fourier rapida ( F.F.T. • Past Fourier Trans for-a >j

ÎS A

pentru exemplul menţionat anterior ( M»2 " ). aplicarea FFT in locul algoritmului direct, are ca efect reducerea timpului ce­cale ui de la 10* secunde la 15 secunde.

Perfecţionarea algoritmului initial Cooley si Tuctcey are i.i * > o vedere efectuarea unui număr sporit de paai pe iteraţie, ceeace conduce la reducerea "umărului total de operaţii lacunari ei

w 1? multiplicări de numere reale ) . Pentru K-2 bcr^land /1^/ calculează numărul de operaţii pentru algoritmi de diferite clarei aceste date eint prezentate ai in tabelul 3.1. •

Se observa o acaùere considerabila (circ 40>) a numărului de operaţii la trecerea dala algoritmul 'basa 2' la algoritmul ' 'baza 4' • Keduoerea numărului de operaţii este de circa 1'jfr la trecerea de la algoritmul 'basa 4' la aljoritaul 'baza B' ei ce

Al^c r i ' - au l

Baza 2;:<-2 1 2

. . •> , . / ~ 2 v O

caza 4;.i»t«- ) Baza b; i . ' - (2 3 ) 4

ôaza 1é>;IU(24)-

Sua i r u l cie o p e r a ţ i i »

de m u l t i p l i c a r e r e a l a

81924

57344

4*152

4d132

Numărul de o p e r a ţ i i de adunare r e a l a

139266

126978

126978

125442

7aoel.il 3*1. a umărul de operaţii cerut de d i f e r i t ! algoritmi de F?T _ _ _ — — _ » >

t t numai. 2% la trecerea la algoritmul baza 16 . In practica reducerea reala a timpului da calcul este in

general jucatate din cea estimata teoretic, căci algoritmii sine dl.i ce in ce mai complex! , programarea algoritmilor in baze superioare 'oazei 4.' fiind deosebit de dificila iar eficienta acestor algoritmi necorespunzind aşteptărilor*

3.2* 0 justificare intuitiva pentru algoritmii de PPT.

In cale ce urmează vom arata ca in esenţa avantajele tranafor->

matei Fourier rapids rezulta din reducerea unei analize Fourier finite a unui set de 2*N date numerice la doua analize Pourier

A w

efectuate asupra cite unui sat de H date flecare. Daca H este da forma 2 H , atunci plecind de la o analiza pentru o mulţime iniţiala de doua dace numerica , prin q dublări succesive se ajunge la analiza setului de H-2q date.

Vom efectua in intervalul (0,T#) vom obţine 2*H valori numerice t

hjjH-C h(Jc) , k-0,1, 2*W-1 ) (3.2.1.) Transformata Fourier finita a acestui sir ds 2*ù valori numerice

» va fi notata prin i

Hg,, « C H ^ U ) , n-0.1 2*W-1 )

o eşantionare cu perioada T/2 a funcţiei h(t); i >

(3.2.2.) Funcţia continua si cu valori complexa h(t) va fi acum --—

«santionata uniform cu perioada T (fiind satisfăcuta condiţia A A

Nyquist), obtinindu-se in intervalul t fc(0,T#) , M valori numericei

- 19 -fcP - ( bj5PU) . k-0,1,...,H-1 ) (3.2.3.)

rranaforaata Fourier finita a Birului de mai BUB va fi notata prin t H,,p - ( Hjjp (n) , n-0,1,....,I-1 ) (3.2.*.)

Analiza Fourier finita bazata pa I valori ale funcţiei h(t> pu.ta ii rapetata conaiderind K eşantioane , luata la aljlocul interva­lelor precedente de eaantionare (figura 3*1*)

Figura 3.1.

In acest cas elrul de valori nuaerice ale funcţiei ai aie transformatei Fourier finita eint notate prin i

hj 1 - ( h / U ) . k-0.1,. K-1 ) (3.2.5.) ei respectivi

HJJ1 . ( H,,1^) , n-0,1 ,N-1 ) (3 .2 .6 . ) Cele doua analise , efectuata asupra punctelor indexate par ai cea efectuata asv -u punctelor indexate impar trebuie ea difere numai printr-o deplasare cu T/2 a facei .

Von arata ca daca n(t) eate o funcţie cu valori complexe atunci conaiderind uultlaea de 2*N puncte , cele indexate par ai cele indexate iapar avea următoarele relaţii t

H ^ U ) - 1/2 ( n/di) • Hj P(n)»W^ ) (3.2.7.)

HgjjdM-N) . 1/2 ( HHi(n) - H ^ U ) » * ^ (3.2.8.)

pentru naO,1,2 ,N-1 . In exprcL. l* de mai aus a-a foloelt notaţia i

W¥ '•• a*p(ii'"*j/N) cu (3.2.9.)

Pornind de la definiţia transformatei Fourier f ini te , avem următoarele re laţ i i i

h,P(k) . )Vp(n)»W ljn*k* k.0.1 «-1 (3.2.10.)

h / U ) . £ HBi(n)*H^n*k| k-0,1 t . . . ,N-1 (3.2.11.)

b ^ U ) - J Hja,(n)*W2Jjn"k> k-0,1 2Ji-1 (3.2.12.)

I

- 20 -

iU la t i» 3.2-12. poate f i r eac r i sa pentru i n d i c i pa r i e i pentru

Laaici impari sub forsa t r im\ 2 H - *

pentru «=rf),1,. . . 3*-1 v * ° (3 .2 .13 . )

^(2-^1 ) - ^ U ) . * ^ ^ , Ţn^n)'^.*^ pentru t - 0 , 1 , . . . ..f-l"**^ ^ i 0 (3 .2 .14 . )

In r e l a ţ i i l e de mai sua vom separa termenii pentru n>U

3cr i ina c i : e doua sume , pr ioa pentru nfc(0,U-1) s i a doua pentru

n t (11,23-1) . Cu s u b s t i t u ţ i a m-n+N cei de a i doi lea termeni a i )

sumelor de mai sus devin t , ,

H^U)»*^ 0"^ . l__ H2H(n+N)»#N(nk) k-0.1,...,N-1.

**?„.4 X I ° rf-1 (3.2.15.) ^H2a(a)»Wîr

(o,c)»W2HU) « -^H21J(n+N)»W1jnk^ fc-0,1.2....M-1.

* " N * s 0 (3.2.16,) căci i

I:ItH) - 1 (3.2.17.)

Wgl111'- -1 (3.2.18.)

Unind ae&ma de relaţiile 3.2.1$. si 3.2.16. expreaiile 3.2.13. si 3.2.14. devin : , _,

BaB(2*Jc) • ^ H2HCn)»*H(nJc) • 2 . H 2 M ( n * M > * f N ( n i C ) J , c - 0 ' 1 » ' " M - 1 -

•*'•-*_,, * » ° M-1 ( 3 . 2 . 1 9 . )

h2tf(2*k*i) -?HarU)n^^k>t2f^> - J H ^ ^ ) . * ^ 1 * ^ ^ X > J t -O, 1,2, If-1. * . a (3 .2 .20 . )

A « Evident iaaa i

h ^ U ' l c ) • fa^pU> Jc-0,1 N-1 (3 .2 .21 . )

h2IJ(2»lt*l) - n „ 1 ( k ) k " 0 » 1 ' N - 1 ( 3 .2 .22 . )

Sfectuind substituţiile precedente in relaţiile de mai sus obtinemi

H./U) - HgjjU) • Hgjjd.^B) n-0,1,..,H-1. (3.2.23.)

tt/U) - H2J ,(n)•W2K(n , - H2IJ(n*li)«W2H

(n) ( 3 .2 .24 . ) Rela ţ i i l e 3*2.7. s i 3*2.8. decurg imediat din precedentele.

•>

- 21 -A

. 3 . iteec opunerea transformării Fourier f ini t» in produs de

transformări elementare.

Ia notaţie matriciala transformarea Fourier f i n i s * es t* definita prin r e l a ţ i i l e i

i h -(••H) ( 3 . 3 . 1 . )

H . (1/N)»(w"*b) ( 3 . 3 . 2 . ) A eu h il H vectori complexi eu cite « componente iar W , matricea

H t N cu elemente w.. date de t lu

wii£ - exp(2Îjlc/H) ( 3 . 3 . 3 . )

In r e la ţ ia 3*3*2. W* este def init prin reiauia t

W*«W « W*** . H*I (3 .3*4 . )

cu I , matricea identica N*N.

Daca ii este factor isabi l t

timU^H^Kt *HM (3.3.5.) - , , A

atunci matricile W si 1 se descompun / / intr-un produs al permutării r" prin 11 transformări S i t

W . fS m P»(S||*Si;_1» •S1» S2*S1> (3.3.6.) WH« (r*S)* - P»S* (3.3.7.)

fiecare dintre paeii de transformare S, , ifc(1,M) , cere K/H, w w

transformări de dimensiune H^ | deoarece numărul de 'operaţii* la o transformare de dimensiune N, este H, uraeaaa ca fiecare 3^ implica efectuarea a i

^ - (N/Nj)»;^2 . «••j (3.3.B.) operaţii elementare. Deoarece numărul de operaţii cerut de permutarea J? este ne^liàakil fata de numărul ue operaţii cerut de

- w ' „ • transformările S^ ̂ rezulta ca putem aproxima nuioarul total de operaţii cerut de. transformările 3.3.1* aau 3.3.2. prin i

«. - 2Jit • 2_N*Ni " *2.Ki (3*3.9.) fata de calculul direct al expresiilor 3.3*1.-3.3*2. care

" 2 implica efectuarea a * operaţii , calculul uatat pe descompune­rile 3.3*<>*-3«3*7* implica efectuarea a I.' j li^ operaţii*

22 -A Vom analiza acum cazul da interes N • 2^ ; in acest caz

percutarea P interschimba elementele rezultate din calcul , A _

coreepunzind perechilor de indexi I si I unde t I = Y iic2U"K"1 V 0,1 (3.3.10.) 1 - ^ 1 " V~[k2't ik-0t1 (3.3.11.)

Evident interachimbarea ee face numai pentru r,> i ; pentn i-0,N-1,U/2-1,N/2+1,... etc. numărul Întreg i ai inversul sau

A -> ' binar rH eint egali si nu ae efectuează interachimbarea .

1 i Matrice* de permutare P aate simetrica t P*P • I (3*3.12*)

v A căci pentru orice intreg i t

P(P(i)) . P(ri) « I (3.3.13.) Rezulta deci ca procedura de permutare de la forma 'normala' la forma 'binar inversa' se aplica ai la permutarea de la forma 'binar inversa' la forma 'normala' a vectorului ca conţine datele

t de transformat.

A Tinind seama da relaţiile 3«3.o. ei 3*3.12. transformarea

3.3*1* poate fi scrisa sub forma s h «(?•*> )*H» (P*S*P*P)»H - (P*S«P)«P»H • « (P»Siî*P)(P»Su_1*P) (P*S2*P)(P*S1*P)(P*H) » " ( W l * •••• V R1 ) ( P H ) (3.3.14.)

cu 1 R± . P»S±*P (3.3*1%)

ielatia 3.3.14* defineşte o noua transformare 1 R - P*S*P (3.3*16.)

* ~ A * in cars oe efectuează mai lntli permutarea vectorului ce trebuie transformet. i»e observai cu transformarea inversa a lui 3 eote ue i'or...̂ :

U - (1/M)»(H") (3.3.17.) In adevăr avem 'relaţiile 1

(1/M»R*>-fl - l/îKK^U) - 1/M(P*S*P)*S - 1/H(P*S**P«3) -• iMJ»a*)(jf*s)-i/n(w**w)»i/H(N«i) «î 0.3.17.;

- 23 -3.4. Calculul recuraiv al transformatei Fourier finite , transfor-

:aata Courier rapida (FFT).

Descompunerea transformării Fourier finite intr-un produs de transfomari elementare sta la baza procedeului de calcul recuraiv cunoscut sub numele de transformata Fourier rapida*

Fie perechea de transformate Fourier finite h(k) , tc*0,1,.. ,il-1 ai \\{n.) , naO,1,.**,N-1 ; intre şirurile de numere complexe h(k) si H(n) exista deci relaţiile t rf-t »

h(lc) m £ H( n ) * W N( n * k ) k«0.1.....H-1 (3.4.1.)

*» j rt-i

H(n) . 4 ~ Ln(lc,*WIl(~n',l£) np0,1,...,lî-1 (3.4.2.)

cu i

WN « exp (2»»*j/N) J * \ R (3.4.3.)

Calculul lui h(k) pornind de la H(n) sau calculul invers (al lui

H(n) pornind de la h(k) ) sint fntutotul similare; din aceasta

cauza vom stabili relaţii de recurenta numai pentru una dintre transformări.

Teorema 3.4.1» Daca N • N«N2 • ••••MtI atunci calculul cerut de transformarea

A 3*4.1. se poate efectua in M paşi folosind următoarele relaţii * i

de recurenta t 'HL<k0'lc1'"*»lcl-1»nW-L-1 n 0 ) » =* £ HL-1 ( k0 k

I r.2' nU-L'— 1 10^ i'H U L- l U' 1" y L- l ) +"* l £ o )* i >

M L (3.4.4.) h<kU-1»kM-2»,,,lc0) " V k 0 ' k 1 K U - ^ (3.4.5.)

Se foloseşte notaţia t f" «M-L*(NlIl V (3-4'6->

Indicii Ic s i n din re laţ i i l e 3*4*1. sint descompuşi sub forma t » . » te • Ktt_«(W«M2#,,'^-1^*kH-2^NV:2",*#%-2^**,*k1'I1*k0

(3 .4 .7 . )

- 2< -

n • n14_1(:.'2;i3...SB)*nll_2(HJi+....llH)+,».+a1HM+a0 (3*4.8.)

Se observa ca fiecare dintre transformările S, Lfc(1,li) (ecuaţiile 3.3.6.) corespund* pasului I» al calcului efectuat

1

cu ajutorul relaţiilor 3.4.4. . Permutarea P corespunde transformări: descrise de relaţiile 3.4.5. •

Demonstrarea teoremei 3*4* 1.

Pentru ca rsprecentarile 3.4*7* si 3*4>S. sa fia uniroce trebuie satisfăcute următoarele condiţii*

kj , * (0 ,8, -1)

k,* (0,»2-1)

kj , . , * (0,H,f-1) IIQ cCO.ll^-l) n,*, ( 0 , 1 ^ , - 1 )

n,^* 6(0,11,-1) : 3 . 4 . 9 . ) A -

In ecuaţia 3*4*1* Însumam separat pe flecare dintre componentele

indicelui n t

b(kll_1,klk.2,....k0) « 2 £ 2H(nII-1' , , ,'n0 )* f ( ,Cn) O.4.10.)

fccpandxnd pe n s i pe k 1

w < W <*^VvrK-* f l ^ K - x K - M>--41(3.4.11.)

Pent.m s t a b i l i r e a acestor r e l a ţ i i s-a ţinut seama ca 1

Aceasta ultima r e l a ţ i e rezulta imediat* Pie 1

Par \X7* , (<*/)** ' * » V / - ^ ' V# CNfc "* ^ ~ f -^.,0^^..HMVWm-.ţ'."-M*-"'*-^ (3-4-14->

înlocuind Ca r e l a ţ i a 3.4*10* valor i le IP1011' date de 3*4.11* obţineai

% W *•**•! (W. O < w V l % B > , ^ . . * J . ^J]

( 3 V l S . " ) ]

» 4 o ^ a V t t •

U\ocu..Vc\ ?w 3 I, .15. cAiV'u« 'W\

ft. H «<&..*W-""-V

w ̂ K k ^ - «MV- ^-1 ( v i t .4>. )

D Q . 1

26 -

Pa baza unui raţionament "aaJ.03 ce lu i cerut de Btabilirea r e l a ţ i e i » »

3 . 4 . 1 2 . se obcina 1 V ^ ^ C r f A H ^ = W 0 C O ^ H ; K M _ X ( 3 . 4 . 1 9 . )

Daca notam t

*** ̂ -»^V.«V.X, > ^ « I H ^ X ^ , ^ , V 'T (3.4.20.) « - l

putem re se r ie r e l a ţ i a 3*4*10. folosind id—2 sume , sub forma t

» ( * . . . , ,V . - i , , . - • ,^0 - ^ ZJ O ^ . . ( ^ . V , , * , , , , - «a*V , V U U r i tf vT' ,VC~ KI X"-*1 ( 3 . 4 . 2 1 . )

Prin generalizarea expresiei 3.4.20. se obţine relaţia 3*4*4. din anuncui teoremei iar prin generalizarea relaţiei 3*4*21. se obţine 3*4*5. . '

Vom analiza acuma cazul in care N este de forma « . Repre-zentarea binara a indicilor k si n este 1

k * ̂ M -l 2"" 1^^" 2* •- +k12+k0 n - nM_l2M"1-»'nj|I_>22E,I"2+ +n^2+nQ (3*4.22.)

w A Relaţia de recurenta 3.4*4* devine in acest caz 1 » >

* - HL.A(\.,.iv„c>s,v,% v^-t-n l - i \ S l ( v > V i ^ j V i i , \ »W.

(3.4.23.) A

Fie X s i J numerele Întregi cu reprezentarea binara t

I m ( lc 0 f lc 1 , .>k I r - 2; - k02L"Vk12L"2+...+lc I (_2 J * ( n a - L - V n l l - L - 2 ' " , V " " M - L - 1 * + nM-L-2 r • . . • •»* 0

(3*4*24.)

Daca facem convenţia ca prin numărul Întreg KaCl.ltţ^ţ.J) ,

- 27 -amnarul cu următoarea reprezentare binara t

(3.4.25.) atunci relaţia 3.4.23. ae poate scrie condensat eub forma i

:'IU'KL-1»J) " Hj^U.O.JJ+U^U.I.J)'.^ " * ** *•" 'J (3.4.26.)

Pentru cele doua valori Ic, 1»0 ei kj«"1 reiatia precedenta devine:

IiL(I,1,J) « HL_1(I,0,J)-HL_1(It1,J)*WM (3.4.27.)

f i e 1 inversul biliar a l întregului I I

1 - <*L-2'*L-1 . . . ' V « V ^ 2 * . . . . ^ ( 3 . 4 . 2 6 . ) Kxpreuiile 3*4.27. ae rescr iu t

i i L ( I ,0 ,J) - H l _ 1 ( I t 0 , J ) * « l i _ 1 ( I , 1 , J ) * f 1 |1 ^ Xi

i^Cl, 1,J) . H j ^ U . i . i D - a ^ U . l . J ) » * ^ 2 *l)

(3 .4 .2 ' i . )

Vom «xaci-na acum euccint d e t a l i i l e de programare ale unui ai^oritni

cazat pe expres i i le 3.4*29* • Datele asupra cărora se efectuează

transformarea 3 . 4 . 1 . aint memorate intr-un vector U. £xpreti i i le

3 .4.2^. arata ca , la trecerea de l a pacul L-1 la patul 1 ,

ca lcu le le se efectuează nr parat aoupra unor frupe de c i t e coua

elemente , ce le coreepunzun;;.. . i c i l o r l

K0 « U , 0 , J )

K1 - (1,1,J^ 0 . 4 . 3 0 . ) A T I

Cind indicii I e i K parcurg retpect lv mulţimile de valcr i (0 ,2 ) "-L * J A

s i (0 ,2" ) , toate elementele vectorului H uxm ira:.:,; - ate conform r e l a ţ i i l o r 3 . 4 . 3 1 . i

- 28 -

V& ' HL-1(t0) • W V * (3.4.31.*) iLCi^) = ^ ( K Q ) - H ^ ^ K ^ ' P ( 3 . 4 . 3 1 . " )

cu k dat de expres ia t

( 3 . 4 .31 . "V De remarcat ca avem o transformare 'in place'; doua elemente ale

A vectorului H eint referite,transformate conform relaţiilor

A » 3*4.31. ai apoi rememorate in aceleaşi adrese.

Fie 117/(1) funcţia FORTBaH care calculează inverstil binar al A l

i r t r e ^ u l u i I i a r KO(I ,0 ,J ) 3 i K 1 ( I , 1 , J ) doua f u n c ţ i i care ca lcu leazc

' i r . trer i i K s . K, d a ţ i de exnreaia 3 . 4 . 3 0 . conform r e l a ţ i i l o r

•'.. .-i.r.5. . Fir '."(I,1I,L) f u n c ţ i a ce c a l c u l e a z ă expres ia 3 . 4 . S I . " '

i a r FlHH) subrutinB FORTRAN ce as igura permutarea r e z u l t a t e l o r .

Prorramul FORTRAN de FFT conţ ine următorul nuc leu:

IVJ.V. = 2 Y ( L-l ) - 1

JI.'.AX = 2 * ( li-L ) - 1

x 1 cc±:,:.:

ai - v - JJ

DC I I = O.ITAX

ALPHA =f( IHV(I ) f i : iU DC 1 ,T = C,J:.:/.X

J l = KCC ,G,J)

J2 - Kl( ! , ! , . " )

H(Ji) -- H(J1) f H(J2)*ALIiL'.

H (.71) :• H(J1) - H(Ji!)»ALI!L

1 CONŢI rrj*

CALL Pr.Rl(H)

%•,. u -̂. .„^zare» a i , ;on i-ulor de traaafomiare Fourier rapida.

Folosirea algoritmilor de traiiBforjare Fourier rapida a

ceierxina: larcirea considerabila a c la se i de a p l i c a ţ i i ale calcului

numeric al transformatei Fourier; Eiiaultan, dimensiunea problemelor

de rezolvat (nuiaarul de date dintr—un eet , ce trebuie transformat)

a creacut. itafinarea algoritmilor or ig ina l i , ceruta de aceete

c o n o i t n , a condus l a algoritmi, mai e f i c i e n ţ i sub raport al v i t e z e i

de lucru s i al memoriei ocupate, dar incontestabi l mai d i f i c i l de > A

programat. Derivarea unor algoritmi in oare ee efectuează mai

aulti paei pe f iecare i t e r a ţ i e reprezintă d irecţ ia principala de » > i »

rafinare a algoritmilor de FFT; de asemenea fo los irea unor algoritmi ~ A

eficienţi de calcul al inversului dinar I al numărului intrec I elimina necesitatea tabelarii acestor valori.

In versiunea originala a al^orltmului, vectorul ce conţine cele M=2 date este transformat 'in place' , in cadrul unui proces

_M-1 A

iterativ; Ic fiecare dintre cele M iteraţii , 2r grupe de cite doua elemente sint succesiv citite,transformate conform relaţiilor 3.4.31. si apoi rememorate.

1 - A Vom arata in cele ce urmează cum se poate deriva un alcoritiu w A w A

•baza 4' . in care se pot stabili relaţii de recurenta intre crupe A A ' J

de c i t e 4 elemente corespunzmd respectiv pacilor L s i L-2.

Frocesul de creBtere a numărului de paui pe i t e r a ţ i e poate f.'.

continuat printr-un procedeu analog ce lu i descris mai jo t , pentru ~ A

a se ol)tine algoritmi 'baza b' , 'baza 1t>' e tc . in care te efectuează * A A w

cite respectiv 3 fii 4 paşi pe iteraţiei avantajele sini ine-a minore fata de complexitatea algoritmilor. De notat ca ui algoritmii de FFÏ in baze superioare lui 2 , efectuează o transformare 'in place' ai Mint optimi din punctul de vedere al sisteuelor cu memorie virtuala deoarece refera un număr minim de padini.

* # w "•» w

Următoarea teorema fuudai:iem,eaza alcorituul ' uaza A' t

Teorema 3»5.1. Daca L eute uu Întreg par , 2 < L * k , atunci UUUL, oi-.,tiLu hour,-

li.iiia poa'.e ii calculata Ivloeind următoarele relaţii ne récure, m Ï )

'oreupunzatoare pac i lor L.L-1.L-2 t

'"wlVl.^.l^-U 1 (,.5.2.)

A -

bint folosite următoarele no tatiit

V .• ' " u (* 5 s . ) demonstrarea leoret i t^:

itelaiixxe oe recurenta coreopunzatoare pan i lo r L"1 BX L Be eo.riui

H---. ^ '•• ^ - , . V . - . , * „ . „ ^ W , . , , ^ ^ ^

0 5 - 0

- 31 -

^ ,w

( 3 . 5 . 1 . ) 5-a no tat 1

"•(jw'"x* ^ V v / i , , ' l < i (3.5-.^ P"^»^"*'-- * ̂ V^N.t*^" 1 , (3 5.*.')

Relaţiile 3.5.7. si 3.3.6. pot fi transformate folosind notaţiile 3*5.3. t

(>>.5. "3.1

Heletiile 3.!>.1.-3.5.4* din enunţul teoremei se obţin inlocuind in 3.3*9* cele doua valori (zero si unu) pentru kj^_2 ei respectiv inlocuind In 3.3 .10. cele doua valori pentru kj^*,*

Trebuie avut in vedere cai

- 32 -Vom folosi «cum teorema demonstrata pentru a Btabili relaţiile

A A — afective de calcul , intre grupe de cite 4 elemente corespunzătoare paailor L si I/-2. Pentru cele doua valori ale lui n-,_j(3.4.1*2^devin

( 3 5 . 1 3 )

In mod similar pentru kT 0 egal cu zero si cu unu , relaţiile 3.5.3. ei 3.5*4. devin :

>

(3.5.1O Relaţiile dintre valorile corespunzătoare pa&ulul L si cele

corespunzătoare pasului L-2 se obţin din 3*3.13* bi 3• '̂• 14• ; pentru simplificarea notaţiilor se foloeecc indici definiţi de

» ezp-eeiile 3.5.15. •

'<*. - U^,!)

<,. -- (lA°.ll

R e l a ţ i i l e 3 . 5 . 1 6 . - 3 . 5 . 1 9 . Btut>ileLc .Modalitatea ae culc ii A

a unor grupe de cite patru elemente indiciate ^00»Koi JM0'1:11 ' corespunzătoare pasului L mi elementele cu aceiaoi inci-ici , corespunzătoare pasului Ir-2 .

- 33 -

Daca folosim notaţiile i

A « Hw.x (K„\ , V ï k V ^ V *

A

putem scrie relaţiile precedente 3.5*1u.-3*5*19. in forme compacte de mai joe i

H . ^ < , . ^ - A ^ C (3.5.21.) * . t K , ^ ' A - C (3.5.22.) ^w (*,*\ * * T c (3.5.23.)

Algoritmul de calcul foloseşte relaţiile 3*5.21.-3.5*24. ai notaţiile 3.5*20* i daoa M eate un nuuar par atunci L ra lua valorile 2,4t..**.M iar daca M asta un număr impar ie calculează aeparat iteraţia pentru La1 ai apoi ae aplica algoritmul pentru 1*>3,5,7,*...,M • Caşurile laO ai I»1 pot fi programate separat

- 34 -pentru a se e n t a efectuare» mult ip l icăr i lor .

Cind 1-0 , atunci U-1.

Cind 1-1 , atunci U-1/2(1+j)

0-- 1/2(1-.)) i •

Pvxtru a compara eficienta algoritmilor 'baza 4' ai basa 2 vom da numărul da adunări reala Q_dd » numărul da multiplicări reala ^yi* si timpul de calcul,! Q__ pentru un calculator la care a si m sint respectiv timpul de efectuare a unei adunări si a unei multiplicări reale (tabelul 3*f>1>)

Qadd

Sault

T comp

BAZA. 2

H(31og2K-5/2)

S(2 logglî - 4 )

«cBfcloggH - f )

•C • 3«*2m

| - 5 (a/2+4/5 m)/.

BAZA 4

N(11/4log2H-2)

11(3/2 loggH - 4 )

«NUloggir - £ )

^ - 11/4 a • 3/2 n

ç - 4(a/2 • m)/«C

Tabelul 3.f»1.

- 35 -

4. Apl i ca ţ i i l e transformatei Fourier rapide.

«* «. 4.1. Convolutia discreta si filtrarea digitala. 1 •>

4.1.1. Convolutia discreta. Majoritatea aplicaţiilor transformatei Fourier decurg din

proprietăţile de convolutia si de corelaţie. Prelucrarea digitala a semnalelor purtătoare de informaţie ca

Bi prelucrarea statistica a datelor experimentale utilizează procedeu] de filtrare digitala bazat pe convolutia discreta dintre un sir de

J >

filtrare h(x) , ka0,1,... L-1 si un sir de date x(k) , k*0,1,.«tt-1. Reamintim ca pencru a calcula răspunsul unui sistem liniar

invariant in timp cu funcţia de răspuns la impuls h(t) ,1a un semnal de intrare x(t) se apelează la integrala de convolutie definita de j

Aceasta integrala calculează răspunsul y(t) al unui sistam cauzal ( h(t)aO pentru t*0 ) , la un semnal x(t) de durata finita ,T .

Cu ajutorul transformatei Fourier continue operaţia de convo-lutie se transforma într-o operaţie de multiplicare; intre transfor-toatele Fourier integrale a i semnalului de intrare,X(f), răspunsului, Y(f), si funcţiei de răspuns la impuls,H(f) existind relatiat

i 3 J Y(f)-I(f)»H(f) (4.1.2.)

A Atunci cind funcţia de transfer a sistemului este de format H(f)-H. fjififg H(f)-0 f t > f 8 i f > f 2 (4.1.3.)

sistemul efectuează o operaţie de filtrare retinlnd din spectrul X(f) o banda limitata.

Convolutia discreta a şirurilor x(k), Jc«0,1,...L-1 si a ' >

h(k) , k-0,1 11-1 este definita prin relaţia t --* *

y(i)-2 x(k)»h(i-k) i-0f1,...N-1 (4.1.4.) Şirurile x(ic) si h(k) de lungime respectiv M si L sînt extinse

- 3f -la lungiae N prin adougaxea de zerouri*

Figura 4.1. ilustrează grafic proceBul de convolutie discreta s

pentru carul in care M*L>4 iar Birurile h(lcj ai x(k) eint periodice cu periaada comuna egala cu lungimea lor .

Figura 4*1» Convolutia diacre ta J w A

Sa observa ca următoarele etape eint parcurae la conatruirea valorilor y(i) dafinite de relaţiile 4.1.4. « - ee conatruieac versiunile periodlcisaie.cu perioada H a Birurilor x(k) ai b(k) .

»

- se construieşte Birul h(-k). - se efectuează translaţia h(-k*i). - pentru fiecare valoare a deplasării i,i*(0,M-1) se calouleaca produsele x(k)*h(i-Jc) si se fneuaeata pentru ka0,1,2...N-1 . obtinindu-se un punct al graficului rezultant.

3 De notat ca definiţia 4*1.4. presupune ca şirurile x(k) si h(k>

t »

sint periodice, cu perioada U,astfel fncît translatarea h(-k*i) . i-0,1....M-1 nu introduce in carul general produse z(k)*h(i)k) , cu valoare zero.

In cesace priveşte alegerea perioadei M date fiind lungimile M si 1 ale şirurilor x U ) si h(k) se observa din figura 4*1.2» ca y(i) sste complet descrie det

H-ii+L-1 (4.1.5.) puncte din grafic, respectiv de li valori numerice.

Daca pentru ti se alege o valoare mal mare decil cea data de relaţia 4.1.5. şirului y(i) i sa adaugă un nuuar de zerouri *

> i

Daca ii este ales conform relaţiei 4.1.îi. atunci convolutia discreta produce un s i r periodic (cu perioada V), in oare flacăra

•a* perioada aproxlneazu rezultatele convolutiei continui.

itelatia dintre convolutia discreta si cea continua eate ilustra-

- 3 1 -

ta in figura 4.1.. . . Pentru funcţii definite pe un interval finit J

T0 de timp , convoluţi» discretă aproximează convoluţi» continua cu o eroare ce depinde de perioada de eşantionare; cind perioada de eşantionare devine suficient de mica aceasta eroare este neglijabila. j Atunci cînd una dintre funcţiile x(t) eau h(t) nu aste de durata fi-

j

uita convolutia discreta nu mal poate aproxima cu o predai» orieit de buna , convolutia continua căci apară aaa numitul1«fact de capăt'• Presupunem ca x(t) nu are o durata finita ; pentru a efectua convolut tia discreta trebuie sa ne limitam la un interval finit T« de 3

observare, sa construia versiunea periodicizata z^ ( t ) a lui x( t ) pe care apoi s-o esantionam uniform cu perioada T , obtinind M esantiaaaa x(k) , kaO,1,...M~1 •

Figura 4.Z.

Calculul primelor 1-1 valori y(i) ,date de 4*1*4* va fi afectat de aceasta truncare deoarece la calcul nu participa eşantioane ale funcţiei originale x(t) ci ale funcţiei periodicieate x™ (t) ,care

J •* Ae in cazul general diferă in aceasta regiune de x(t).

w w v A Teorema de convolutie discreta arata ca intre transformatele

3

Fourier finite ale şirurilor x(k), h(k) si y(k) din relaţia 4.1*4* .respectiv intre X(n),H(n) si Y(n) exista relatiai

î(n). N'X(n)»H(n) (4.1.6.) Relaţia precedenta fundamentează aplicaţiile transformatei

Fourier rapide la calculul integralelor de convolutie sau la resol-varea ecuaţiilor integrale de convolutie.

3 J

In paralel cu calculul convoluţiei ciclice definita de relaţiile 4*1*4* uneori se folosesc produse decalate (lagged products) defi:.:ic de relatiai *»"•

y(i) - j_ x(k)»h(k-l) (4.1.7.) k » u w

Pornind de la definiţia transformatei Fourier finite se arata direct, ca între Kn).II(n) si Y(n) exista iii acest caz relatiai

î(n) . N*X(n)*H(N-n) (4.1.9.)

A.1.2. Procedee de filtrare digitila

Pie date U valori observate x(lc) , k-0,1,. ..i*-1 aie unei realizări X, (u> ) a procesului stochastic X.(io) . Doris sa filt (ponderam) sirul de valori observate, folosind şirul de filtrare h(k) , lc-0,1,...L-1 cu L<U ; cu alte cuvinte dorim sa construia şirul y(i) t

y(i)-£x(i-k)*h(k) i*!,,1,4-1,...i2 (4.1.9.)

Calculul se efectuează in doua caşuri distinctes in primul cas i1«L-1 si ip"M-1 astfel incit h(k) este In Întregime cuprins in interiorul lui x(k); în cel de al doilea caz i^-O si i2-»t»-L-2 .

Primul procedeu de filrare digitala basât pe algoritmul de FFÎt permite filtrarea simultana a doua Biruri de date realei

x.,(k) k->0,1>....l»1-1 x2(k) k»0,1,....^2-1

prin şirul de filrare reali n(k) k=0,1,....L-1

algoritmul de calcul cuprinde următorii paşii PJ. &e alege ti max(k.. ,k2){ pentru a putea aplica algoritmul de 9FT

ti trebuie sa fie de forma 2q. £2. He construieşte şirul complext

xe(k)-x1e(k)+jx2c(j£) k«0,1,...N-1 (4.1.10.) eus

x1e(k)ox.,(k) k«0i1v...U1-1 X.r («i)=0 ţoi».., .»..].

x2f>U)~y.2U) K«O,1,...I.:2-1 y

X2e(k)-0 Ite-lj,....!! ($,1.11.) P3. tie calculează transformata Fourier f in i ba X„(n) a şirului __ e > complex x (k) • Datorita proprietăţii de l in ia i i tate a transformării Pouri*r f inite it. , (n), t réunionnât a şirului x, Ak.) ui X0 A >),

' » • » ' » ' > ' i t transformata siruluj. >:0 (/.; , ue regăsesc in X (n) , care eu te de j c »e e lor,; ai

Xe(n)«X1 (n) *j X^ r (ri> i*-0,1 .....H-1 (4.1.12.>

- 3Q -

P4. i>e a e f i a e s t e s i r u l ce f i l i r a r e e x t i n s i •» »

.". U ) - h(fc) * - 0 , 1 , . . .L-1

h UJ = 0 k-L N ( 4 . 1 . 1 3 . ) e

Se ca lcu lează transformata Fourier f i n i t a H(n) , n = 0 , 1 , . . . M - 1 Ok.

Birului de f i l t r a r e ex t ine h (k) . i e

Pt>.3e ca l cu lează produselei

Z(n) - N»H(n)*I e(n) n » 0 , 1 ; . . . N - 1 U . I . 1 4 . )

Pb.Se ca l cu lează transformata Fourier f i n i t a inversa a Biru lu i

complex Z(n) t

yCk) = y, _U) • j'y, (k) k=o,i N-1 (4.1.15.) Datorita linearităţii -raneformatei Fourier finite inverses

>.-A » y 1 f C U ) - J.jx1(i-k)«h(k) y2>e(i) - 2. x2(i-k)*h(k) (4.1.16. )

Vt.o

Pentru i»L-1,L-2 M..-1 (respectiv U^-l) se obţin valorile corespunzătoare priitului caz i pentru i»0,1,2,.. ..L+U..-1 (respectiv L+Mp-1) se obţin valorile corespunzătoare celui de al doilea caz. De notat câ pentru a calcula produse decalate de tipul 4.1.7. se poate aplica algoritmul de mai SUB9dar la pasul ?5 ee calculează

Z(«) - N*Xft(n)*H(N-n) (4.1.17.) Legat de modalitatea de programare a algoritmului not ami fie

FFT(X,H,K) subprogramul de calcul a transformatei Fourier rapide pentru vectorul complex X de dimensiune N , pentru K*1 ,efectuindu-e« traneformarea directa iar pentru K--1 transformarea inversa. liucleul programului FOKTHAN corespunzind paşilor P3-P6 • algoritmului

» prezentat estet

CALL WT(X|N,1) DO 1 1-1,N

1 Z(I) > N*X(I)»1I(I) CALL FFTU.N.-D

De remarcat ca aaca tubprogramul de transformare i'ourj er rapida este realizat sub forma modulara (acrie do eic.plu ca o succesiune

- 4P -

de ^acroinstructiuni care realizează permutarea P ei fiecare dintre tranaformariie ».,), deoarece se efectuează o transformare airecta si

1 3 una inversa a datelor ee poate elimina modulul care efectuează

/\ permutarea rezultatelor la efirsitul flecarei transformări ; ee obti-> i

ne aetfel un program mai eficient. In ceeace priveete timpul de calcul algoritmul bazat ne evalua-

rea directa a expresiilor 4.1.9. cere efectuarea a M*L operaţii ('o operaţie' implica o adunare si o inmultire reala ) iar algoritmul ce utilizează PFÎ cere efectuarea a U'logpM operaţii. Tiiupii de calcul corespunzători Binti

T d i r - 0,(^1) TPFT " CgCM'loe^î) (4.1.18.)

Algoritmul bazat pe folosirea PPT conduce la o reducere considerabila a timpului de calcul atunci cind lungimea M a şirului de date este

i ^

mare, iar Birul de filtrare are o lungime comparabila cu LI. Vom prezenta acuma un al doilea procedeu de filtrare digitala ,

prin segmentarea datelor; procedeul este op iini in cazul in care lungimea L a şirului de filtrare este mult mai mica decit lungimea

i U a Birului de date ce trebuiesc filtrate. Cele M date, x(k) ,

> k=0,1,.... .l»i— 1 se secţionează in K segmente x (k) de lungile fiecare, care ee suprapun pe lungime L-1 t

x^k) B x(k) k-0,1,....:J-1 z2(k) tz x(k+.J-Cl<-1)) ko0,1,....!!-1 x3(k) «= x(k+2(i.-(L-1))) k»0,1 H-1

x..(k) «= x(k+(m-1)(i;-(L-1))) kuO, 1,... .ii-1

x,.(k) o x(k*(K-1)(;,'-(L-1))) k=0,1 i-1 (4.1.1 .)

Daca k<K*H atunci segmentul Xy ee completeu::.: ca zerouri peni:;

a i i aduu Iu lungimea comuna I'.

lie ca lculează produce ue i'ox-.na J

- 41 -Zn(n; - N*H(n)»I.i(n) a=0,1,2,.. ..N-1 (4.1.20)

pentru a»1,2,...K . In expresia 4.1.20. *m(a) n*0,1,... H-1 eBte transformata Fourier fiai ta a Begmentului x (k) k«0,1,.. ..M-1 iar H(n) este tranaformatr şirului de filtrare h(k) extins la lungime M,

Daca y (k) k-0.1, • « N~1 este transformata Fourier finita inversa a lui Z (n) atunci produsul y(k} al filtrării digitale a Birului de date z(k) prin airul de filtrare h(k) ae obţine eub form Ï > a K segmente,fiecare continind N-L+1 valori semnificative, dupa cum

1 t

urmeazai

y(k) - y.,(k) k-L-1,L,L+1,...N-1

y(k) » y2(k) k-H,N+1 2»N-1

i(k) - ym(k) k-((m-1)(N-L*1)+(L-1)),...((m-1)(l,-Lf1)+(N-1))

(4.1.21.)

Putem da acuma o justificare a faptului ca segmentele slnt alese

pentru a se suprapune pe lungime .T#-11 primul segment x.(k) produce

valori semnificative pentru indicele k apartinind intervalului

ke (L-1,N-1)| segmentul x„(k) produce valori semnificative pentru

kt (N-L+1,N), Deci aceasta suprapunere pe lungime N-(N-L+1)«L-1

permite inlaturarea efectului de capăt ce afectează primele L-1 valori ale segmentului x2(k)

Iti ceeace priveşte alegerea valorii N a lungimii segmentulu^ reamintim că fiecare dintre segmentele x produce N-L+1 valori semnificative, fe de alta parte} dacă 1Ï este de forma 2^ atunci timpu de calcul al transformatei Fourier rapide eete proportional cu

i4*loc2N.

In aceste condiţii sa va ale^e aceea valoare N care minimireaze M raportul timp de calcul per număr de date calculate i I '

* « ( Jnoc 2N)/( lM*1) - (q»2 q ) / (2 q - I*1) ( 4 . 1 . 2 2 . ) •Igor,tmul de calcux bazat pe eenuentaxea datelor cuprinde

următorii «/«si l i

- 4? -

R1. Data furia valoarea L , ee a l ege M-2^ din c o n r i t i a q > lo^pL ,

care r e z u l t a dir, ' . 1 . 2 0 .

R2. He a lege numărul K de aegnente din c o n d i ţ i a t — t

KWii ( 4 . 1 . 2 3 . )

Caca auuarul * de dace i n i t i a l e nu eate d i v i z i b i l prin ii , a tunc i

£ e s t e partea Întreaga a raportu lu i II/W, piue unu, i a r segmentul

Xy(t.j se ext inae l a lungime ii pr in completarea cu zerouri*

H}.i>aca numărul K de segmente e s t e par , atunci Be c o n s t r u i e s c

vector i i , compleţi 1

V-JCK) B X^CK) • j^Xjdc)

V2(it) = Z-.U) • J * X £ ( K )

V _ ( K > = j ^ _ . j (k ) + u * z 2 (i ;

vK/2 = x i - 1 ( k ) + j ' ^ - U ) k » 0 , 1 , 2 , . . . i l - 1 ( 4 . 1 . 2 4 . )

Daca K e s t e impar atui:c i :

v (KVI) /2 *= yY. ( , c ) + • • °

f<4. Se a p l i c a Fti pentru date complexe vec toru lu i v (ic) ,

u d , 2 , . . K / 2 BI ce oht in traneformatele Fourier f i n i t e »

R m t a ) ~ .&•' * -'**., 2 ( n ) " » 1 | 2 , . . K / 2 ( 4 . 1 . 2 % )

i<5. i e a p l i c a pyî pentru date r e a l e vec toru lu i extinB de f i l t r a r e ,

L (/.) JccQ.1,2, U-ï oo t in indu- se transformata Fourier f i n i t a ,

i i ( n ) , n o C , ' 1 , . . . - « - ' 1 .

K6. Se calculează produsele t Z.fl(n) « N»;i(n)'i'v(n) n=0,1....J.-1 (4.1.26.)

pentru ui«1fk,...iVL . I<7» Se c a l c u l e a z ă transformatele Courier f i n i t e inverse a f i e c ă r u i a

d intre segment t i c Z (:i) obtin^ndu-ue L ( K ) ac i'or...a t :- j ..i

e (*) « 1;. , { • : ; • J*L„ 9 U ) i i - 0 , 1 , . . . i J - 1 ( 4 - 1 . 2 7 . )

p e . ; n a U i u l , 2 , . . . ; . / i .

i'. -. rtaupurxul i u f i l t r a r e a c i ; ; i t u l u a f i e c ă r u i a d intre c e l e 1

se,ferite se ob:ine din l

:•;>.,_,CO » B a ) 1 ( - )

y^CO » sm 2(lc) lc -0 t1,2, . . . . i f -1 (4.1.28.)

per.tru m»1t2 K/2 .

Pentru programarea algoritmului de f i l t r a r e d ig i ta la prin v. ' A uejnentarea datelor , prezentat mal SUB , dificultăţile sint minore. j

Daca DlGFH(X,H,N) este un subprogram care efectuează calculele de filtrare digitala a vectorului de date X prin vectorul de filtrare Ii , ambele de lungime N, atunci nucleul programului FORTRAN care corespunde paşilor H4-B7 ai algoritmului de mal sus este

K1*K/2 J-1 DO 1 1=1 ,K1 CALL DIGPIL(X(J),H,N)

1 J-J+-N

- 44 -

4 .2 . Bs tmarea i u n c - i i l o r ds autocovaxiar.ta oi a f u n c ţ i i l o r de ^ * •> x

croBBCovariauta»

4*2.1. Estimare nepreferentiala si consistenta.

Pie date U valori observate i(lc) , £*0,1,...àl-1 ale unei realizări particulare X. (^) a procesului stochastic X(w) ,despre care presupunem in cele ce urmează i

- este un proces stochastic de ordinul doi , A

- este staţionar in sens larg* 3

Doriis sa obţinem o estimare a unuia dintre momentele de ordinul doi, (funcţia de autocovarianta), date fiind cele M valori observate; vorbim de o estimare^deoarece noi nu cunoaştem densitatea de pro­babilitate corespunzătoare variabilei aleatoare a cărei momente dorim sa le calculam, ci numai U valori observate,intr-un experiment,.

Condiţiile pe care o astfel de estimare trebuie ea le indepli-neasca sin ti C1. Estimarea trebuie sa fie nepreferentiala (unbiased estimation). Pie p estimarea făcuta de noi pentru valoarea p. Evident p poate fi momentul de ordin unu, moment de ordin doi sau alta caracteris­tica statistica a variabilei aleatoare X; p este ea inaasi in acest

> caz o variabila aleatoare al carul moment de ordin unu va fi notat prin E(p). Condiţii ca p sa fie o estimare nepreferentiala a lui p este t

B(p) - E(p) (4.2.1.) C2. Estimarea trebuie sa fie consistenta; atunci cind numărul de valori observate M este mare, valoarea estimata p trebuie sa aibă o varianta care sa tinda la zero t

Var (p) * 0 (4.2.2.) Vom da acum un exemplu de estimare nepreferentiala si consistenta

> i a momentului rte ordin unu , E(X) , a variabilei aleatoare X,

- 45 -eetlmare definita de i

2 - 1/M ^ x U ) (4.2.3-) Condiţia C1 eate ia acest caz Îndeplinitat B(X) . 1/U I B(x(k)) - 1/U(M«S(X)) . B(I) (4.2.4.) ûeaeeaenea condiţia C2 ©Bte Îndeplini cat Var(X) - 1/U (Var(X)) (4.2.5.)

4.2.2. Batimarea funcţiei de autocovariantâ. t I

Fie dat eirul de variabile aleatoare x(k) , k-0,it-, — » i

staţionare in sena larg (momentele de ordinul unu si doi exista » » 8i eint Independente de Ic). Momentul de ordin doi eate definit de i

f (k) - B[( x(i) - B(x) )»( x(i*k) - B(x) )]-- B ( x(i)»x(i*k) ) - ( B(x) ) 2 -- y'OO - ( B(x) ) 2 (4.2.6.)

Pentru k»0 , Y(0) poarta numele de varianta iar pentru kţO , "f (k) se numeşte autocovarianta de distanta k»

Definim următoarele estimări ale funcţiei de autocovarianta t

Daca momentul de ordin unu este zero atunci i 1. Estimarea Ţ(k) este nepreferentiala t

2. Estimarea v(k) este preferenţiala pentru U finit dar asimptotic nepreferentiala.

Prezentam acum doua procedee de calcul a funcţiei de autocova-riantă, procedee bazate pe utilizarea PPT. Ple x(k) , kaO,1,....U-1 eirul de valori obeaervate ; ne propunem sa calculam valorile estimate V (k) si y (ii) pentru kfc.(0,K) .

Algoritmul pe care 11 prezentam impune efectuarea următorilor paai :

- 46 -PI. Se alege N de formm 2q cu condiţia N>M+1. P2. Se construieşte şirul extins de valori i — i i

xft(i) - x(i) - X i-0.1, M-1 xe(i) - 0 i-*,M>1 B-1 (4.2.8.)

P3. Se calculează prin PPT , transformata Pourier finita X(n), n-0,1, ...IJ-1 a Birului x_(i). » e P4. Se calculează z(k) , k-0,1,...N-1 , transformata Pourier finita inversa a produselor de formai

Y(n) - X(n)»X(N-n) n-0,1,...N-1 (4.2.9.) P5. Se calculează s

î U ) - M/(ii-lc) • z(k) k-0,1,...îl-1 (4.2.10.) ţ\k) - N A • z(k) k-0,1,...N-1 (4.2.10*.)

Procedeul de calcul decurge din faptul ca t y(k) - 1/3 2. x(i)«x(k-i) k-0,1,...21-1 (4.2.11.)

sit î(n) - I(n)»X(N-n) n»0t1 N-1 (4.2.11'.)

A 8int perechi de transformate Pourier finite.

Vom descrie acum procedeul de calcul simultan a doua funcţii de t

autocovarianta de distante k- si respectiv k? , pentru doua procese A A-

cu valori reale , X.. si X_ »in cazul in care valorile observate sint t

XjU^i-O.I ii.,-1 z2(i)9i-0,1l....U2-1

Procedura pe care o discutam consta din următorii paşii R1. Se alege o valoare U de forma 2q , care satisface relaţia t

II ̂ laaxdJ^k^i-Ig+kg) (4*2.12.) R2. 3e calculează valorile estimate ale momentelor de ordinul unu t

*< - * ' « * { £ * "*«l*0 (4.2.13.) X «/ ( ^ •» Y (4.2.13'.)

R3. Se construiesc şirurile extinse la lungime Ui l , t l O « X , l ^ *:VjA. *«"• (4.2.14.)

- 47 -

i Tits, ^ " x»l'i

O I t M . X ' V >**

R4. Se calculeată Y(n) , a«0,1,...N-l , transformala Fourier finita a şirului complax t

y(i) - x^i) • J^igd) i-0,1,...B-1 (4.2.15.) R5. Daca notam prin Y*(n), complex conjugatul loi Y(n) ,calculăm!

Z(n) . I*{a)ml^{n) • j^X^n^X^n) n-0,1,...N-1 (4.2.16.) cut

I^n) - ( Y(n)+Y*(N-n) )/2 n-0.1,...M-1 (4.2.17.)

Xg(n) - ( Y(n)-ï*(H-n) )/2 n-0,1,...I-1 (4.2.18.)

R6. Se calculează transformata Pour ier finita inversa a lui Z(n)i z(k) - z,(k) • J'z^k) (4.2.19.)

R7. Valorile estimate rezulta din expreeiilei ^ N/O^-k,) • z^kj) (4.2.20.)

fjj j- H/M^s^k,) (4.2.21.) jjk^ N/(M2-k2) • ^ ( k g ) ( 4 . 2 . 2 2 . )

•JjiVi- K/M2 • z2(k2) (4.2.23.) In oeeace priveşte timpii de calcul pentru estimarea funcţiei de

\ ; autocovariante prin metode directa e i prin cea ce ut i l i zează PPT

notam ca procedeul descrie de noi este mal rapid pentru valori K

satisfacind re la ţ ia t

K4 2*log2H ( 4 . 2 . 2 4 . )

Pie Tair(u*&) timpii de calcul ai estimatei funcţiei de autocovarian-

ta de distanta k, U ( 0 , K ) prin metoda directa iar TţpT(U,K), timpul

de calcul cind se ut i l i zează PPT* Tdir " Cl»(K+1)»(M-K/2) - C^K'M (4 .2 .25 . )

unde Cj es te o constanta ce depinde de timpul ae efectuare a unei

adunări reale s i a unei multiplicări r ea l e . TFPT " V ( N * 1 ° 6 2 N J ( 4 .2 .26 . )

unde C2 e s te o constanta ce depinde de timpul de efectuare a trei

operaţii de adunare reala e i a unei operaţii de multiplicare reala . » * i

Practic C1/C2 -2 (4.2.27.)

A

In cazul in care W- u «raportul celor doi timpi de calcul estet

1 - ?Tn/Tiilr " (21oe^O/K (4 .2 .28 . )

4*2.3. Estimarea funcţiei de croeec>varianta. * »

Fie x.(i) si x.(i) i-0,tl ........ .. eşantioane din doua realisari a proceselor etochaetice I 1 si X , staţionare In sena larg.

Croeecovarianta de distantă Ic a ş irului x^(i) , fata de » > •« % » şirul XjCi) oe defineşte pri

Y12u) - *' m 2

( x^i+lO-BU,) )•( x2(i)-B(x2) j= ( x ^ i + U ^ U ) )]- Mx^)*E(x2)) (4.2.29.)

pentru k»0,*1,T 2,..... Dotam următoarele proprietăţi ale funcţiei Y (ic).

!• H M ^ M V H ^ (4.2.30.) Croescovarianta nu eate o funcţie para ue >c. 2- V^W>^^(w> U.2.31.)

Dorim sâ estimam funcţia de crosecovarianta Y. 0(k) foloBin şirurile de valori observate:

x.jU) i«0,1,2,. ...Uţ-1 *2(i) i«o,i,2,....tf2-i

In cazul general \LAVL.~ s i vom presupune U.. > J»2 .

Estimarea propusa eoţet

{ • ^ at * U M c ) " *«.U\ " « - k-0,1 ,2 . . .U 1 - t .

• 4 '&* * - ' -CM 2 '

M.*u Z - V ^ * * ^ - " u .2 .3 2 i ) i « - V

cu t a . ( ! , ) • ( Xg) (4.2.33.)

Xţ - l / â l ţ ^ i ^ i ) (4.2.34.)

X2 - 1 /^ J x2(i> (4.2.35.)

- 49 -Procedeul de calcul al funcţiilor de crosscovarianta pentru

t o. t (-K,+K) este descria de următoarea succesiune de operatiit

1 P1. Se alege îi de forma 2q cu condiţia N^il^+K (4*2.36.) P2. Se calculează şirurile extinse x- „CD si x~ _(i) conform __ , i,e ^,e relaţiilor 4.2.H. P3. Se calculează ï(n) n«0,1,..U-1 , transformata Fourier finita a şirului complex y(i) definit de 4.2.15. P4. Se calculează z(k) dat de 4.2.19. folosind relaţiile — i

4.2.16. - 4.2.19. P5* Se calculează*

.I rf/U2*z(H) k»0,1 (Uj-Og) W/(M2-k)»z(k) k-dl-j-Iig+l)..., (il.,-1)

l{/(Uw»k)*s(k) ka-1,-2 -U„-1) (4.2.37.) A

Pentru a stabili in ce condiţii procedeul descris mai sus .procedeu ce utilizează PPT , este mai eficient decit procedeul bazat pe calculul direct al valorii estimate a funcţiei de crosscovarianta*, vom estima timpii de calcul prin cele doua metode. Fie P şiruri de observaţii , x (k) , pt(1,P) , k»0,1,...,irf-1 i puteri calcula P funcţii de autocovariantă oi PlP-D/2 funcvii de crosscovarianta'. Daca dorim «a estimam toate aceste funcţii prin algoritmul prezentat , atunci i - calculam P/2 transformate Fourier finite directe (transformind cite doua şiruri de date simultan) - transformatele trebuiesc separate«multiplicate si apoi calculate (P+P*(P-1)/2)/2 transformate Pourier finite inverse . Rezulta că pentru valori mori ale lui P timpii de calcul ai transformatelor directe este neglijabil fata de timpul de calcul al transformatelor

» inverse. Daca dorim sa calculam fiecare dintre funcţiile de cova-

>

riant a de distantă k«(0,K) cu K<M .f ie 2/ de forma 2q si f ie H 2 MU , Timpul de calcul prin PPT , Tyw(M,K,P) este aproximat de t

- 50 - -

TW(M,K,P) - C^N^log^ ( W 1 / ( H ( P - 1 ) / 2 ) / 2 (4 .2 .38 . )

Timpul de calcul prin metod* direct» «ste i Tdir " V * * 1 1 (4 .2 .39 . )

Raportul t

V W T d i r (4.2.40.) tinde către valoareat

* j # -dr»ao62î)/K«M (4 .2 .41 . )

cind F are ralorl a a r l .

- 51 -4.3- Ha'.iiJited perioaiotira^ei e i a d e n s i t ă ţ i i spec t ra l e de putere»

4 . 3 . 1 . Periodiograma a i densitatea spectrala de putere*

Pie XCu) , n - 0 , 1 , . . . . , N - 1 ş i r u l transformatei Fourier f i n i t e

corespunzătoare ş irului de valori observate x(k) , tca0,1 , . . .N-1 •» a v a r i a b i l e i aleatoare X.

Periodiograma este d e f i n i t a de r e l a ţ i a»

I(^j n ) = H / 2 l X ( n ) l 2 . N/2 •I(n)*X i l(n) n-0,1, . .H-1

cu W n = (2îl n)/N ( 4 . 3 . 1 . )

Se arata uşor ca periodiograma este o funcţie para , pucindu-ae defini i

I+(uJn) - 2*I(Wn) n-0,1,..., N/2 (4.3.2.) Pentru zgomot alb, gauesian, variabilele aleatoare x(i) sint distribuite normal si sint mutual necorelate. In acest cas de > considerabil interB practic, proprietăţile statistice ale periodio­gramei sint evidenţiate de relaţiile ce urmează t - funcţia de distribuţie a periodiogramei este t

Prob[l*(wn)> y,"} . exp (-y.fi /^ (0) ) (4.3.3.) pentru n-0,1,... W/2 . - momentul de ordin unu eate t

a l4(-;J) - Ţj(o)/Ti (4.3.4.) - momentul de ordin doi este t

Var I*(«n) - ^ / T > i (4.3.5.) - coeficientul de corelaţ ie este i

Corr [ l* (*> n )» I* (^ n ) ]» 0 ( 4 . 3 . 6 . )

Pentru un s i r de variabile aleatoare necorelate , rezultate le de

mal sus s int adevărate in mod asimptotic , cu o convergenta rapida.

Pornind delà def in i ţ ia periodiogramei s i a estimării Y (k) ,

a funcţ ie i de autocorelatie , pentru un s i r de variabile aleatoare * * »

necorelate s i cu momentul de ordin unu zero outem scrie i > -v» -«V t > r

K o n > .i\li-^)jp(lc)»cos(*>n*lc) n-0,1. . . .M-1 ( 4 . 3 . 7 . ) r

- 52 -In acest etc momentul de ordin unu al variabilei aleatoare I(<* )

i i «Bte t , „,

B [ I ( v y n > ] mp 5 ^ ( ^ • y U ) * coe(tOn«k) ( 4 . 3 . 8 . ) unde »-a notaţi V«-«*

A. (Ic) - { H (4.3.9. ) Densitatea spectrala da putere f ( c ° „ ) * procesului Z ţ(io ) este la

rlndul aau definita drept transformata Fourier a funcţiei de auto» 1

covarienta ï(k). In aceste condiţii, tinind seama de proprietatea de convolutle

» i din domeniul transformatei Fourier, putea exprima momentul de ordin unu al periodiograaai sub forma :

E[ I ( v*'a )ri h ( C On" t )* p ( t )* d t (4.3.10.) In aceasta expresie M^* n) ««te transformata Fourier a funcţiei A. (k)

h(u^) -l42«M^[sin(H*Wn/2) / (sin ( ^ / Z ) } 2 (4.3.11.) Funcţia h(vin) este numita 'fereastra spectrala asociata estimării cu ajutorul periodiogramei a densităţii spectrale de putere p(o )'. Hemarcao cu t

\h(vi ) d w n . 1 (4.3.12.) La limita "înd N tinde la Infinit , h(u ) tinde către funcţia

n » Uirac , iar asimptotic f

i i [ l (vJ n ) l . p(Wn) ( 4 . 3 .13 . )

Kelatia 4 .3 .10 . arata ca valoarea medie a periodiogramei se * A. obţine f i l t r ind densitatea spectrala de putere p( U J

n ) prin — -» ^

fereastra spectrala h ( w n ) . AceaBta f i l t rare reprezintă e lectul - A

unui număr finit de valori,in setul de date observate. Acebt elect A A I

poate f i luat in consideraţie ui in a l t mod, definind o periodio^ra-

ma modificata» datele obţinute in urma obscivari i , r.(i) , i - 0 , 1 , . .

k-1 , vor f i •pref i l trate ' ioiocind o 'fereautra de date' w(i)

de fonta i

v.(x) m 1 i - 0 , 1 , . . . , . - 1 (4.3.14.)

v;(i) - o i-ii,«i+i,..,;:

Daca X(n) , n « 0 , 1 , . . . . . . - 1 LI W(n) , n « 0 , 1 , * . . ,H-1 t int

- 53 -

transformateie rourior fioles a airuim de data al respectiv a

ferestrei ii date, atunci periodiograma modificata este dafini ta del

Iw(vjQ) « )x(a)«W(nM2 (4.3*15.)

In ceeace priveBte densitatea spectrala ùe putere p ( ^ )

definita drept transformata Pourier a funcţiei de autocovarianta, > >

notam ca pentru un proces cu valori reale X t(^) , p x , are următoarele proprietăţi i -1. este întotdeauna o funcţie reala. -2. este o funcţie para. -3. este o funcţie non-negativa. -4. Var(It) . ipx(^)«dto (4.3.16.)

Densitatea spectrala de putere reprezintă o caracteristica importanta a unul proces stochastic. Notam printre alte aplicaţii pe cele decurglnd din relaţiile Wienner-Hincin; daca unui sistem liniar cu funcţia de transfer H(u> ) i se aplică la intrare un proces cu densitatea spectrala de putere PinDUt^u>^ • a t U D C l

densitatea spectrala de putere la ieşire este t 'output**4* " Plnput^> * » « ^ ) l 2 (4.3.17.)

4.3*2. Calculul periodiogramei.

Fie date doua şiruri de date reale x^i) si x~(i) cu i-0,1,....,U-1 .; aceste şiruri de date vor fi folosite pentru

calculul periodiogramei definite de relaţia 4*3.1* sau al perie— diogramei modificate definite de relaţia 4.3*15* • In cazul in care dorim sa calculam periodiograma modificata, folosind fereastra

A * de date w(i), in calcule x..(i) si 2,(1) se Înlocuiesc prin t

x.(i) • x1(i)*w(l) 1«0,1,..M-1 (4,3,18.) w x2(i) . x2(i)*w(i) i-0,1,..M-1 (4.3.19.)

Procedeul de calcul consta in urmatoarelei P1. Se alege N de forma 2q cu condiţia N> If . — A " P2. 3e extind simultan şirurile de valori xJl) si xAi) pina la — "» ' lungimea H si se construieşte şirul complex*

3 i •>

_ 54 -

y(i) - x.,(i) • j*x2(i) i«0,1,... ,IJ-1 (4.3.20.) ?3. Se calculează transformata Fourier finita a şirului y(i), Y(n) , n-0,1,...N-1 , care este de forma s

Y(n) . Y^n) • j*ï2(n) (4.3.21.)

P4. Se calculează expresiile periodiogramelor : IjU) - ^ lY.,(n)l2 n«0,1,...,N-1 (4.3.22.)

lAni - U lY9(n)l2 n«0,1 tf-1 (4.3.23.)

4.3*3* Sstiaarea densităţii spectrale de putere prin netezirea

(medierea) periodiogramelor.

Pie date U valori observate x(i) , i«0,1f... ,i.l-1 a unei w w

realizări a procesului stochastic X+(^>) . In secţiunea precedenta A *

s-a arătat cum se poate calcula in acest caz periodiograma 1( **<> ) , cu vo . (2Û n)/U n«0,1,....,N/2 .

I(cj ) , n=0,1, ...ii/2 , formează un sir de variabile aleatoare pe care vrem sa le folosim pentru a furniza o estimare p (io ) fa densităţii spectrale de putere p(un).

In statistica un procedeu folosit pentru analiza t.eriilor tic

date este 'netezirea' , adică medierea pe valori adiacente , folotiinc un set de ponderi .

Hr(lc) , tc€(-K,4-iQ (4.3.24.) Estimarea p(w n) a densităţii spectrale de putere p(v>)n) • ebtinarr ce utilizează getul de ponderi H (k) va fi :

p(*%) m\ Iir(k)*I(con_k) (4.3.LO.)

Vom analiza acum ia ce condiţii relulid ^,'\.?.'j» lurnxzca: <> i >

est imare nepre fe ren t i a l a s i consistent/a a UCM.L Ui i i i i ><cnul< n<<

puiure p ( ° Jn ) «

Uomentul de ordin unu a l v a r i a u i l e i uiealoiir< !»(<-•> ) J>OL.I<

f i ~c r i s , t inind seu.ia de r e l a ţ i a 4.3*10. out; for. >u t

r- ' 1 r*

5S

^iide fereastra spectrala rezultsuua h (uj J se ooiine ca o

coabinatle l iniara ae n ( u ) deplasata ai ponderata pria ri (*) t

h (UJ ) . S H U)*h(«.«i - t u . ) (4 .3 .27 . ) r n / j r n .c

La nudul Bau hÇwo ) este dat de erpreaia i

ti(u)n) - (1/2 5 U)*(ain 2 (cj r i »i i /2) /a in 2 (^^a) ) (4 .3 .28 . )

/oa considera acum cazul de interes in care fereastra spectrala

rezultanta are arie unitara t I hr(vo)du>. 1 (4.3.29.) Aceasta se petrece atunci cind suma Donderilor satisface conditiat

/ H r U ) - 1 (4.3.30.) c ă c i i w * -^

i h(>* ) duo .1 (4.3.31.) i)aca p(>*>) este aproximativ plat in regiunea benzii de trecere

a ferestrei spectrale rezultante h (-->) si daca variabilele aleatoare x(i) au o distribuţie normala atunci momentele de ordin unu si doi ale variabilei aleatoare p(«o ) ,care estimează pe p(i*> ) A sint date de expresiile i

K[p(u>n)]- p(con) V5 (4.3.32.) /ar[p(u>n)].(2Îp2(vJn)/ii)* jh r(^)*d^ (4.3.33.)

Se observa ca atunci cind îl ia valori mari , abaterea valorii estimate delà media ei care este chiar valoarea exacta, este mica oi tinde la zero la limita.

Rezulta deci ca daca setul de ponderi U (Ic) satisface condiţia 4*3.30. , pentru multe dintre aplicaţiile de interes , ecuaţia 4.3.25. formează o estimare nepreferentiala ai consistenta a densităţii spectrale de putere p (»•*.>) •

Prezentam in cele ce urmează un exemplu in care şirul de ponderi este dat de 1

U r U ) - 1/(2»K*1) (4.3.34.) unde valoarea expresiei 2*K+1 reprezintă numărul de periodiograme care oint mediate (participa la procesul de netezire). Kvident condiţia 4.3*30. este satisfăcuta căci t

56

(4.3.35.)

in acest caz, pea:ru setul de ponderi dat de expresia 4.3*34*

eaûiaarea p(u ) este de forma t

p ( w a ) - (1/2*K+1)* 2_ I^UJri> lc) n-0.1 N/2 (4 .3 .3^ . )

- V.-K De notat faptul ca la calcule poate participa fie periodiograma

,fie periodiograca modificata* Daca w(i) este eetul de ponderi extins

la lungime S , se calculează in cazul periodiogramei modificate raai intii eirul modificat de date , x.(i) dat de expresiile t » e

i-0,1,....U-1 x6(i) - x(i)»w(i) xe(i) - 0 i«tf,M+1f..N-1 (4*3*37.)

~ A Periodiograma modificata 1 (^ _) este definita in funcţie de transformata Fourier finita X(n) a şirului extins de date t

eu i

Iw(voQ) « N2/2(M»U»X2(a) n-0,1,...N/2

U- (1/U)»2_w2(i)

(4*3.38.)

(4.3.39.) Funcţia t i . 0

M-» h V o ) , (1/2"ÏM»U)| 2]w(i)«exp(j»*o*k) l 2 (4.3.40.)

poarta numele de 'fereastra spectrala asociata ferestrei de date w'.

Se pot construi ferestre de date w(i) care sa alba ferestre

spectrale asociate h (<-* ) cu proprietăţi de rejectie a lobilor laterali mai accentuate decit funcţia h(*>) folosita In cazul periodlogranelor nemodificate drept fereastra spectrala •

0 astfel de fereastra de date,cu bune proprietăţi de rejectie este i

w(l) . 1 - ( i - (M-D/2 ) 2 / ((M+D/2)2

In acest caz t U- 8/15

Funcţia hw(-o ) este t

C,._i_ ia '

V ((M+1)/2r

- t f 1 ) . L O M

2

(4.3.41.)

(4*3.42.)

. coî> —

.

(4.3.43./

•

- 57 -4.3.4. Eat marea densităţii spectrale de putere folosind segmentarea

înregistrărilor si efectuind medierea xn timp a periodiogramelor

modificate ale acestor înregistrări.

Vom prezenta acuma o metoda de estimare care are doua avantaje fata de metoda ce consta in netezirea periodiogramelor sau a periodiogramelor modificate si anume :

<•» A w - este mai eficienta in termeni ai numărului de operaţii »

«» A - are o rezo.ut ie crescute m domeniul timp.

Vom considera II valori observate , x ( i ) , i e ( 0 , M - l ) . Aceste

date se segmentează in K segmente de lungime L fiecare t segmentele A

adiacente suprapunindu-se pe lungim" D . Segmentele x ( i ) , r € ( l , K ) A

oint def inite do :

x ^ i ) = x ( i )

x 2 ( i ) = x(i+D)

x r ( i ) = x ( i - ( r - l )*D)

x K ( i ) = x(i+(K-l)»D) i * (0,L-1) ( 4 .3 .44 . )

Se alege o fereastra de date w(i ) , i * ( 0 , L - l ) ai se calculează

cele K periodiograme modificote , I rw ( w n > , re( l ,K) . In acest scop;

- se calculează prin FFT transformatele Fourier f i n i t e , Xw(n) ,

n «r(0,N) , r fc( l ,K) , cu N>L s i N de forma 2q ale aefjnentelor > i

f i l trate , x r(i)»w(i) . - se calculează periodiogramele modificate :

I > n ) - ^ U U 2 ! Xj(n)ţ 2 ( 4 . 3 .45 . )

cu:

*** (?*n)/n

U = ( l /L) l w 2 ( i ) ( 4 . 3 . 4 6 . ) pentru i e ( l t K ) ai n %(0,N-1) ,

Valoarea estimata^ pentru P( fco_) «"te : i p(H.n) - ( l 'K)» 2_ I* < w n > ( 4 . 3 . 4 7 . )

- 58 -Relativ la fereastra de date w(i) data de expresia 4.3.41. not"am ca fereastra spectrala asociata ei, h (i) este normată si cu o

i aemilergine de ordinul 2H/L . Un a l t t i p de fereastra de date

•" _» folosita este si cea data de :

w(i) = 1 - ( i - (L-D/2 ) 2 / (Ul)2/4 (4.3.48.) Fereastra spectrala asociata este :

hwfcâ) = (2T )/(LU) ( [ (L*l ) /« ]«(s in 2 (w n /4 (L4- l ) )/(yo n/2 (L* l ) ) 2

(4.3.4S.)

Semilargimee aces te i ferestre es te :

A u = 5 6 l i / ( I ^ l ) (4 .3 .50 . )

In eeeace priveşte calculul efectiv al expresiei de aproximare a densităţii spectrale de putere :

P(«"V = < N 2 / 2 l L U K ) £ U j ( n ) \ 2 ( 4 .3 .51 . )

cu : t.„ X*A

U = (1/L)£ w2(i) (4.3.52.)

presupunem ca numărul K de segmente este par, calculele efectuindu-ee prin aplicarea de K/2 ori a algoritmului de transformare prin F5T a datelor sub forma complexe.

Procedeul propus consta in efectuarea următorilor paşi: FI. Se alege tipul ferestrei w(i) de date. P2. Se aleg valorile lf,L,K. P3. Se calculează U conform relaţiei 4.3.5?!.

\ P4. Se construiesc vectorii comolexi y„(i) definiţi de : _ n »

y"(i) = x1(i)»w(i) • jxg(i)inr(i) yj(i) = x3(i)îfW{i) +jx4(i)*w(i)

yK/2 ( i ) * «K.!**)»»»^) •JXj,{i)*w(i) (4.3.53.) Daca K este impar atunci se defineşte si:

» i

y*K+1)/2(i) - xK(i)ifw(i) +jO (4.3.54.) PS» Se calculează transformatele Fourier finite Yr(n) , o *»(l,K^)ei nelO.H).

- 59 -:j.osir." vaicril-' Y o , se calcuieara valoarea aproximativa

•"er.sitetii spectrale se rutere .conform r-'latiei : r(««jti) i ^ l / U Î L U K ) ) l Y* (n)l2 + lYw (N-n)t2 ^ • - r"" " " " r-

1 A (4.3.55.) In practica mărimea L a segmentului se alege astfel incit

L^N ; cu alte cuvinte L este o putere a lui doi si algoritmul de » FFT se poate aolica direct unui segment fara a mai fi necesar ca eegmentul sa fie extins. In acest caz semilărgimea ferestrei spectrale este :

à^ = 2ÎT/L (4.3.56.) Se considera optima suprapunerea segmentelor pe jumătate din lungimea lor , adică cu:

D = 1/2 (4.3.57.) Numărul K de segmente este atunci :

K = 2M/L (4.3.58.) Deoarece se transforma simultan perechi de segmente iar

timpul de calcul Dentru transformarea unei perechi eate proportiona" cu L logoL , atunci timpul total de calcul cerut de procedeul descris mai sus este :

TFFr(M,L) = C± U log2L (4.3.59.) Timpii pentru premultiplicarea iniţiala a datelor prin fereastra de

» date w(i) si timpii pentru medierea periodiogramelor modificate a celor K segmente sint neglijaţi fata de timpii de transformare prin FFT.

Procedeul ue estimare a d e n s i t ă ţ i i spectrale de putere de sc r i s K * in secţiunea 4.3.3. tccre un timp de calcul estimat r.c expresia :

T^pjdl) = (1/2) CjM log2y (4.3.60.) Compararea: expresiilor 4.3.59. ei 4.3.60. conduce la concluzia

W V ce daca :

LC>fir (4.3.61.) metoda segmentării datelor este de preferat.

- 6C -

BIB LI OG RAFIE

/ 1 / Bracewel l ,R.

/ 8 /

/ 9 /

/ 10 /

/ 11 /

/ 12 /

The Fourier Transform and I t s A p p l i c a ­

t i o n s . Mc.Graw H i l l 1965.

Fourier Transforms and the Theory of

D i s t r i b u t i o n s . Prent i ce Hal l 1966.

The Fourier I n t e g r a l and I t s Appl ica­

t i o n s . Mc.Graw H i l l 1962 .

Numerical Methods f o r S c i e n t i s t s and

E n g i n e e r s , tic.Grew H i l l 1970 .

Transform and S t a t e Variable Method

in Linear Systems . Wi l ley 1966.

Pol lak snd Wong,E.- Lecture Notes on System Theory

Berkeley , Van Nostrand 1971 .

P r o b a b i l i t y Theory with A p p l i c a t i o n s

Wiley 1971 .

- S t o c h a s t i c Proces ses . Wiley 1971 .

- P r o b a b i l i t y , Random Variables and

S t o c h a s t i c Proces se s . Mc.Qraw H i l l I9f>5.

Cramer and Lesdbertter - S t a t i o n a r y and Related r t o c h a s t i c

P r o c e s s e s . Wiley 1967 .

Champe ney ,D.C. - Fourier Transforms and t h e i r Phys ica l

A p p l i c a t i o n s . Accademic Press 1973.

Middletone - S t a t i s t i c u l Communication Theory

/ 2 / Arase , J .

/ 3 / P a p o u l i s , A.

/ 4 / Hamming, R.W.

/ 5 / Gupta, S .C.

/ 6 /

/ 7 / A.J.Thoma8i8n

Wong, E.

P a p o u l i s , A.

/ 13 / Gold,B. and Reader ,6 . - D i g i t a l Process ind of Si/Twin

Mc.Graw H i l l l'JC'j.

/ 28 / A .Rosenfe ld . - P ic ture Proceso iw: by Computer

Accademic Prceo I'.iO'.».

/ l i / Spetaru , A l . - Teoria I n f o r m a t i c i . Editura Tehnico j/.)7l

/ lb / Sakriuon,I i .J . - Communication Theory. Mc.Grr<w H i l l 1970.

Jo<" 1>\Y ,«."fï.'. un: Tuckey ,«J.'.'.'. - Math, o:" Coan. vo l l à , n r .'0

l" / S i n g l e t o n , R . C .

1- J . D . Bergland

19 , Berglan*!, §.D.

20 / Newberg.A.C.R.

/ XI T.Kaneko and B.

/ 22 / Gentleman, '*.I t .

/ 23 / P o l l a r d , J , M .

/ 24 / N icho l son , H.

/ 25 / Brigham,E.O.

/ 26 / Panter.P.F.

/ 27 / Stockham.T.G.

- Coma, cjf ACU vol. iC,nr. 1C ,1967 . - Math, cf Comp. vol 21 nr. .'8 , 1967. - Math, of Comp. vol 22 nr.108 , 19C8. - Math, of Comp. vol 27 nr.123 , 1973

Liu - JCAM vol 17 , 1970 . - Boll Systems Tech. J. vol 47 , 1963 . - Math, of Coiap. vol 25 nr 114 , 1971 .

International Journal of Computer Math, section B vol 3 ,1972.

- The Fast Fourier Transfona. Prentice Hall 1974 .

- Modulation, Noise and Spectral Analysis Mc.Graw Hill 1965.

- AFIPP Proc. 1966 Fall Joint Computer Con-̂ . v«l 28. Soartan.

Legenda figurilor.

Figura 2.1. Eşantionarea uniforma a unei funcţii continui » > a. Funcţia continua h(t) si spectrul sau H(f).

i > b. Eşantionarea cu

c. perioada T,4 T„ ; h^ (t) ai H™ (f).

„ 1 ,,Ci ll » ~ 1 Eşantionarea cu perioada T 0>T M : tu,{t\ si H„, (f)

îgura 2.2. Construirea transformatei Fourier finite pornind d«.> la transformata Fourier integrala, a.-b. Funcţia continua h(t) si transformata Fourier

integrala H(f). c.-d. Funcţia discreta de eşantionare cu perioada T,

q_,(t) si transformata ei Fourier integrala^Q.(f ),

- 62 -

e.-f. Funcţia discreta h_(t) .(versiunea esantionata, cu perioada ? a funcţiei continui h ( t ) ) s i

» •> transformata aa H_(f).

g.-h. Punctia de truncare (limitare la o durata finita > de observare T )s^ si transformata sa , S-, .

** *o ' w o i.-j. Funcţia h_T (t) , versiunea discretizata cu

perioada T ai truncata LJ un interval finit de observare T , si transformata sa Rpm (f) . ° l.-k. Funcţia discreta de eşantionare cu perioada T a spectrului,Q„ , si transformata 9a Fourier

- A ° : integrala inversa q_ (t).

0 v A m.-n. Funcţia discreta h(t) obţinută din h(t) in urma > > eşantionării cu perioada T, truncarii la intervalu T si multiplicării prin transformata inversa a funcţiei de eşantionare din domeniul transfor-

1 >

matei ; m. transformata sa H(f). Figura 3.1. Reducerea unei analize Fourier efectuate asupra unui

set de 2N date la doua analize efectuate asupra cite unui set de N date, fiecare.

Figura 4.1. Convolutia discreta . ^ "Sgar74.2. Relaţia dintre convolutia discret si convolutia continua

H|f)-i|1.co»|ft» lll«t

- 0 '">«<

Fig. 2.1

K f . " '

H t I t M M » > U M M M U (

i i ! • i i M i i i i i i i 1 1 ' ••• I 1 : i : • • ! i i i i i i I •

Mh T ( f ) -h ( t ) . q

4

•sA

in

]W (e)

•'Sun

-W2 (g) -V2

h r y t f hTitimStiti

•t

A k (i)

- t

V>

Ik)

V h ry t ) 'V>

h *

ill (m)

N

H

h D l

(f)

ta rr-

(n)

"FT

- f

Fig. 2.2

Fig. 3.1

y 1(1-KIT]

yfl3-K)T]

VW . l i , . ' , J l~ ' KT -3T-2T * T 2T 3T 4T 5T 6f 7T 6T

Fig. 4.1

*lt> • *m

-r xlkT)

ft

XXXX

^F x lkT l

X X X X X X X X

x a » • •» X

X

M*U . ' H=2T

x(KT)

XX XX

. H-il . ' N-2%

x|kT)

- I t l

1 2

y(kT)

1 2 3 4

< z(kTl

XXXXXXKMX XXXXXXXXI

• X M M • Ţ Ţ

*x » ». *

N15 ylkT)

X X K X X X X X X

. UH •

N-15

z.*kT)

X •

M

X X

a a

X

» *" -«.

X

* X

N-24 ylkT) *lkT)

i i i n n i n

^ =

N-29

a" »

ylkT) N-24

z(kT)

Fig 4.2.