Lab.ps Pachet Fft l3
5
Sumar Sumar Bibliografie Bibliografie Algoritmul Algoritmul FFT FFT bazat bazat pe pe segmentarea segmentarea semnalului semnalului în în timp timp Notaþii Notaþii ºi ºi convenþii convenþii Algoritmul Algoritmul lui lui Goertzel Goertzel Obiectivul Obiectivul lucrãrilor lucrãrilor de de laborator laborator Algoritmul Algoritmul FFT FFT bazat bazat pe pe segmentarea segmentarea semnalului semnalului în în frecvenþã frecvenþã Algoritmul Algoritmul FFT FFT bazat bazat pe pe segmentarea segmentarea semnalului semnalului în în frecvenþã frecvenþã Date de Date de intrare intrare , , prezentarea prezentarea rezultatelor rezultatelor ºi ºi punctaje punctaje 15
description
fft
Transcript of Lab.ps Pachet Fft l3
-
SumarSumarBibliografieBibliografie
AlgoritmulAlgoritmul FFT FFT bazatbazat pepe segmentareasegmentarea semnaluluisemnalului nn timptimp
NotaiiNotaii i i conveniiconvenii
AlgoritmulAlgoritmul luilui GoertzelGoertzel
ObiectivulObiectivul lucrrilorlucrrilor de de laboratorlaborator
AlgoritmulAlgoritmul FFT FFT bazatbazat pepe segmentareasegmentarea semnaluluisemnalului nn frecvenfrecvenAlgoritmulAlgoritmul FFT FFT bazatbazat pepe segmentareasegmentarea semnaluluisemnalului nn frecvenfrecven
Date de Date de intrareintrare, , prezentareaprezentarea rezultatelorrezultatelor i i punctajepunctaje
15
-
AlgoritmulAlgoritmul FFT FFT bazatbazat pepe segmentareasegmentarea nn frecvenfrecven.. PrincipulPrincipul segmentriisegmentrii nn frecvenfrecven
Exprimare echivalent a TFD, pentru N = 2M
ExprimareExprimare echivalentechivalent a TFD, a TFD, pentrupentru N = N = 22MM
Segment cu Segment cu eeantioaneantioanede de ordinordin 00--(M(M--1)1)
1,0,][][1
0
=
=
NkwnxkXN
n
nkN
def
Segment cu Segment cu eeantioaneantioanede de ordinordin MM--(2M(2M--1)1)
=
=
+=12
2
1
02 ][][][
M
Mm
mkM
M
m
mkM wmxwmxkX 1,0 Nk
1,0 Nk
=
+
=
++=1
0
)(2
1
02 ][][][
M
m
kmMM
M
m
mkM wmMxwmxkX 1,0 Nk
( )
=
++=1
02][)1(][][
M
m
mkM
k wmMxmxkX
Calculul TFD2M se poateefectua folosind 2 semnalecu suporturi de lungime M.
CalcululCalculul TFDTFD2M2M se se poatepoateefectuaefectua folosindfolosind 2 2 semnalesemnalecu cu suporturisuporturi de de lungimelungime MM..
=+=
=++=
imparpentru,][][][
parpentru,][][][
kmMxmxmh
kmMxmxmgdef
def
1,0 Mm
=+
=
=
=
1
02
1
0
][]12[
][]2[
M
m
mkM
mM
M
m
mkM
wmhwkX
wmgkX
1,0 Mk
mkM
mkM ww =
22
n calculul TFD2M se poate utiliza o pereche de TFDMaplicate semnalelor i .nn calcululcalculul TFDTFD2M2M se se poatepoate utilizautiliza o o perechepereche de TFDde TFDMMaplicateaplicate semnalelorsemnalelor i .i .g hw M
2 16
kkMkM ww )1(22 ==
-
AlgoritmulAlgoritmul FFT FFT bazatbazat pepe segmentareasegmentarea nn frecvenfrecven.. PrincipulPrincipul segmentriisegmentrii nn frecvenfrecven
Schema de calculSchema de Schema de calculcalculSegment 1Segment 1
Segment 2Segment 2
]0[x]1[x
]1[ Mx
][Mx]1[ +Mx
]12[ Mx
Segment parSegment par
Segment Segment imparimpar
]0[X]2[X
]22[ MX
]1[X]3[X
]12[ MX
)0( =k
)2( =k
)22( = Mk
)12( = Mk
)3( =k
)1( =k1
1
1
MTFD
H""
MTFD
G""
]0[g]1[g
]1[ Mg
]0[h]1[h
]1[ Mh
02Mw12Mw
12
MMw
Dac N = 4M, semnalul poate fi partajat n 4 segmente (fiecare segment din perecheaanterioar este mprit ntr-o nou pereche de segmente, mai scurte). Rezult c TFD4Mpoate fi evaluat cu ajutorul a 4 TFDM.
DacDac N = N = 44MM, , semnalulsemnalul poatepoate fi fi partajatpartajat nn 4 4 segmentesegmente ((fiecarefiecare segment din segment din perecheaperecheaanterioaranterioar esteeste mpritmprit ntrntr--oo nounou perechepereche de de segmentesegmente, , maimai scurtescurte). ). RezultRezult cc TFDTFD4M4Mpoatepoate fi fi evaluatevaluat cu cu ajutorulajutorul a 4 TFDa 4 TFDMM..
n general, dac N = 2L, semnalul poate fi partajat n 2L-1 segmente (fiecare segment avnddoar 2 eantioane). Rezult c TFDN poate fi evaluat cu ajutorul a (L-1) TFD2.nn general, general, dacdac N = 2N = 2LL, , semnalulsemnalul poatepoate fi fi partajatpartajat nn 22LL--11 segmentesegmente ((fiecarefiecare segment segment avndavnddoardoar 2 2 eantioaneeantioane). ). RezultRezult cc TFDTFDNN poatepoate fi fi evaluatevaluat cu cu ajutorulajutorul a a ((LL--1)1) TFDTFD22..
17
-
AlgoritmulAlgoritmul FFT FFT bazatbazat pepe segmentareasegmentarea nn frecvenfrecven
ExempluExempluExemplu 328 ==N
Segment 1Segment 1--22]0[x]1[x
Segment 3Segment 3--44
]3[x]2[x
]5[x
Segment 5Segment 5--66]4[x
Segment 7Segment 7--88]6[x]7[x
]0[X]4[X
]2[X]6[X
]1[X]5[X
]3[X]7[X
1v 2v Xv ~3xv 0
1
1
1
138w
28w
18w
08w
34w
24w
14w
04w
1
1
1
1
1
1
1
1
3 trepte de calcul paralel3 3 treptetrepte de de calculcalcul paralelparalel
.. PrincipulPrincipul segmentriisegmentrii nn frecvenfrecven
Schema de calculSchema de Schema de calculcalcul
Aceast schem poate fi obinut din cea aferentAlgoritmului FFT cu segmentarea semnalului ntimp i celule elementare de calcul de tip fluture (butterfly), aplicnd 2 operaii: intrrile se inverseazcu ieirile; toate arcele i schimb sensurile.
AceastAceast schemschem poatepoate fi fi obinutobinut din din ceacea aferentaferentAlgoritmuluiAlgoritmului FFT cu FFT cu segmentareasegmentarea semnaluluisemnalului nntimptimp i i celulecelule elementareelementare de de calculcalcul de tip de tip fluturefluture (butterfly)(butterfly), , aplicndaplicnd 2 2 operaiioperaii: : intrrileintrrile se se inverseazinverseazcu cu ieirileieirile; ; toatetoate arcelearcele i i schimbschimb sensurilesensurile. .
Aranjarea semnalelor nvectorii v0 i v3 este similaralgoritmului precedent.
AranjareaAranjarea semnalelorsemnalelor nnvectoriivectorii vv00 i i vv33 esteeste similarsimilaralgoritmuluialgoritmului precedent.precedent.
18
-
.. VariantaVarianta eficienteficient de de calculcalcul
Relaiile de calcul ntre semnalele intermediare succesive:RelaiileRelaiile de de calculcalcul ntrentre semnalelesemnalele intermediareintermediare succesivesuccesive::[ ] [ ] [ ][ ] [ ] [ ]( )
+++=++
++++=+
+
+
mkvmkvwmkv
mkvmkvmkvlLlL
llL
lmlLlL
l
lLlLl
lLl
lLl
lL11
21
1
11
22222
2222
12,0
2,1
1,01
l
lL
k
m
Ll
Schema generic de calculSchema Schema genericgeneric de de calculcalcul
]2[ mkv lLl +
]22[ 1 mkv lLlLl ++ 1
]2[1 mkvlL
l +
+
]22[ 11 mkvlLlL
l ++
+
Numr de operaii
NumrNumr de de operaiioperaii
[ ] [ ] 220 4~)12(24][ NNNNN ++=O[ ] [ ] NNNNNNN 2222 log2~log2log2][ ++=O
DFT :DFT :DFT :
FFT-f :FFTFFT--f :f :
12
mlLw
butterflybutterfly
Acelai. AcelaiAcelai. .
O singur nmulire i douadunri complexe!
O O singursingur nmulirenmulire i i doudouadunriadunri complexecomplexe! !
19Se Se recomandrecomand totuitotui implementareaimplementarea bazatbazat pepe o o funciefuncie autoauto--recursivrecursiv..
AlgoritmulAlgoritmul FFT FFT bazatbazat pepe segmentareasegmentarea nn frecvenfrecven
Sumar Algoritmul FFT bazat pe segmentarea n frecven Algoritmul FFT bazat pe segmentarea n frecven Algoritmul FFT bazat pe segmentarea n frecven Algoritmul FFT bazat pe segmentarea n frecven
