[es] - DFT vs Fourier Series

Andrej013

Član broj: 157053
Poruke: 321
37.19.111.*

+694 Profil

^{24.06.2012. u 15:10 - pre 144 meseci}

Ucim neku teoriju iz signal processinga, pa mi se cini da sam nesto lose skontao.

Ovako ja razumem ono sto sam procitao:
furijeov red-koristi se za periodicne signale, resenje koje dobijemo su harmonici, tj moduo i frekvenciju kosinusa(sinusa) cijom sumom pocetni signal mozemo da predstavimo. ako je u pitanju obican sinus, resavanjem furijeovog reda cemo dobiti samo jednu vrednost, ako je nesto malo komplikovanije, nekoliko frekvencija, a ako je na primer pravougaoni impuls, onda cemo dobiti beskonacno mnogo harmonika.

furijeova transformacija-koristi se za neperiodicne signale, tako sto pretpostavimo da je perioda beskonacna, pa od neperiodicnog dobijamo periodican, sa beskonacnom periodom. za razliku od furijeovog reda, resenje furijeove transformacije je kontinualna funkcija u frekventnom domenu. znaci, ne dobijamo posebne diskretne harmonike u frekventnom domenu, vec kontinualnu funkciju koja govori koliko je jak signal na 0Hz, 0.1Hz, 5Hz, 5.0001Hz, 5.1Hz, 21.6204Hz i sl.

furijeova transformacija diskretnog signala je furijeova transformacija signala ciju smo vrednost uzeli u diskretnim vremenskim trenucima, ali je u frekventnom domenu i dalje kontinualna funkcija.

DFT je furijeova transformacija diskretizovanog signala, ali je ona i u frekventnom domenu diskretizovana tako da dobijamo diskretne harmonike kao resenje. DFT posmatra signal kao periodican i daje kao resenje diskretne harmonike u frekventnom domenu. kako se diskretizuje npr sinc funkcija? ona ide do beskonacnosti. da li moramo da je isecemo posle odredjene frekvencije(pustimo kros low pass filter)?

ako je sve ovo tacno, meni DFT dosta lici na pocetni furijeov red, ali definitivno nisu isti, zato sto onda ne bi imali drugacije ime :)

dakle, pomozite mi da shvatim sta sam pogresno razumeo(ocigledno pravim neku kardinalnu gresku ili previd) i koja je razlika izmedju DFT-a i furijeovog reda.
do skoro sam samo radio zadatke iz furijeove analize, ali nisam dublje zalazio u znacenje.
hvala

_{[Ovu poruku je menjao Andrej013 dana 24.06.2012. u 16:21 GMT+1]}

Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.hsd1.ca.comcast.net.

+1001 Profil

Re: DFT vs Fourier Series

^{24.06.2012. u 21:50 - pre 144 meseci}

Citat:

ako je sve ovo tacno, meni DFT dosta lici na pocetni furijeov red, ali definitivno nisu isti, zato sto onda ne bi imali drugacije ime :)

Kad je u pitanju DFT, osim puke matematike bitna je i jedna predpostavka koja se
obicno ne izrazava formulom:

Od diskretnog vremenskog signala kojim raspolazemo (koji vrlo lako moze da bude
potpuno aperiodican), uzimamo ono sto imamo - N semplova u vremenskom domenu.

Sa time sto imamo, pravimo jednu hrabru predpostavku: da je tih N semplova koje
imamo zapravo nesto sto se periodicno ponavlja (iako znamo da je to prilicno luda
predpostavka).

Pod tom predpostavkom, primenjujujemo formulu diskretnog Furieovog reda, i dobijamo
diskretne vrednosti spektra.

Odakle nam hrabrost za ovakvo ludilo, i zbog cega to ima smisla ?

Ima smisla sto sa ovom laznom predpostavkom znamo tacno gde sebe lazemo i koliko.

Lazemo sebe pametno sto unapred znamo da nam laz nece vredeti ni pisiva boba za bilo
koji vremenski trenutak pre i posle tih N semplova. Znaci, s tim smo nacisto u startu, i
to je OK. Zasto je OK ? Zato sto se spektar inace menja svakog trenutka kako se i signal
menja, i kukati za buducnoscu unapred nema smisla - stici ce i to na red.

Za vreme od t=0 do t= N*Ts, nasa laz ima mnogo smisla i mnogo koristi.

Zasto ?

Poznata je ova relacija (nisam siguran da li se matematicki tretira kao aksiom ili dokaziva
teorema, ali je istina) koja glasi:

- Ako aperiodican signal x(t) ima spektar X(f), onda periodicna verzija istog signala koja
se ponavlja sa periodom T ima diskretan (linijski) spektar X(k/T) koji nije nista drugo nego
semplovi spektra X(f) uzeti u tackama na frekvencijskoj osi u kojima je f = k/T (ovo ti je
za domaci da proveris).

Dakle - sta smo uradili time sto smo jednu malu usamljenu kolekciju od N semplova proglasili
periodicnom povorkom ? Dobili smo to sto smo (zlo)upotrebom matematickog aparata
diskretnog Fourier-ovog reda zapravo predvidivo tacno procenili prave vrednosti
spektra X(f) u tackama f = k/NTs koje signal ima u trenucima [0 - NTs].

Jos ocitije - N vremenskih semplova smo pretabali u N semplova spektra (kod realnih signala
N/2 je dovoljno, jer je spektar simetrican).

U toj prostoj cinjenici lezi i epohalna vrednost ovog postupka je sto je omogucila da se
racunanje Fourier-ove transformacije definitivno preseli sa papira na stolu matematicara
u diskretnu memoriju kompjutera, odatle u sve moguce uredjaje koje danas znamo, od
radara i satelitskih komunikacija do ekvilajzera u tonskom studiju i telefonskog aparata.

Naravno, posle su smisljeni i racunski efikasnije metode (Cooley-Tukey FFT "butterfly"),
pa posle toga jos dosta brzih/efikasnijih/razlicitijih.

Da se osvrnem jos i na ono 'predvidivo tacno' - to znaci da cemo sa vecim N dobiti gusce
premrezenu frekventnu osu i veci broj semplova spektra, ali i vece usrednjavanje i losiju
lokalizaciju promena signala (tj. da li talasa od pocetka, ili pocne iz tisine negde od sredine),
sto su kasnije odklonili wavelets. Takodje, povecana ucestanost semplovanja u kombinaciji
sa vecim N moze da pruzi bolju preciznost uz bolju lokalizaciju promene signala u vremenu,
uz naravno - vecu cenu cipova, vise potrosenog napajanja. Dakle - cena vs. kvalitet je pod
nasom kontrolom.

milanche: edit: malo sam korigovao neke nepreciznosti

_{[Ovu poruku je menjao milanche dana 25.06.2012. u 20:50 GMT+1]}

Odgovor na temu

Andrej013

Član broj: 157053
Poruke: 321
*.dynamic.isp.telekom.rs.

+694 Profil

Re: DFT vs Fourier Series

^{27.06.2012. u 11:10 - pre 144 meseci}

Jako si lepo ovo objasnio.

Kada sam prvi put čitao, zato što nisam u potpunosti razumeo odgovor,
pomislio sam da sam nejasno postavio pitanje.

Sada sam našao nešto slobodnog vremena pa sam seo da detaljno izanaliziram odgovor,
i mogu da ti kažem da sam mnogo naučio.
Mislim da je ovo suština koja mi je promicala, a i profesorima promakne da daju objašnjenje
na ovaj način:

Citat:

- Ako aperiodican signal x(t) ima spektar X(f), onda periodicna verzija istog signala koja
se ponavlja sa periodom T ima diskretan (linijski) spektar X(k/T) koji nije nista drugo nego
semplovi spektra X(f) uzeti u tackama na frekvencijskoj osi u kojima je f = k/T

Super! Uzeo sam box signal vrednosti 1 i trajanja 1s. Pošto nije periodičan, morao sam
da uradim furijeovu transformaciju i dobio sam kontinualni sinc.

kada uzmem periodičan square wave, gde je square trajanja 1 a periode 2 s, tačno se
furijeovim redom dobije ovo što si rekao-diskretne vrednosti koje prate sinc.

E sada, još uvek se borim da pohvatam i sažvaćem sve što si napisao(a pri tom me sve ovo navodi
na beskrajno guglanje) pa, iako mi se čini da sam naučio dosta, imam još jedno pitanje(a možda
je ono besmisleno, što bi značilo da nisam ništa shvatio :)

znači,
-furijeova transformacija box-a 1 sa 1, mi daje beskonačno dugačak, kontinualni sinc spektar
čija apsolutna vrednost se smanjuje sa porastom frekvencije.(više frekvencije manje utiču na
rekonstrukciju signala)
-furijeov red istog boxa, ali periodičnog, mi daje beskonačno dugačak diskretizovan sinc spektar
harmonika čiji moduli se smanjuju sa porastom frekvencije.
-DFT jediničnog boxa(aperiodičnog, Ts=1-20, sa 20 tačaka, prvih 10 vrednosti=1, drugih 10 vrednosti=0)
posmatra taj box kao periodičan, periode 20, i daje diskretizovan sinc, koji nije beskonačan,
već je konačan i periodičan, periode 20(iako je prvih 10 dovoljno za analizu jer su isti kao drugih 10,
ali suprotnog redosleda). Znači, DFTom sam efektivno dobio module 10 harmonika sa kojima mogu
da uradim inverzni DFT i dobijem neku aproksimaciju početnog signala(sa greškom, zato što nemam
vrednost svih harmonika, već samo njih 10).

na osnovu svega što sam pročitao, dobijam ideju da su harmonici DFT-a i harmonici furijeovog reda
vrlo slični, ali to nigde nisam pročitao pa verujem da možda grešim i da mi se samo sve pomešalo.

ono što mene zanima je da li su ovih 10 harmonika DFTa isti kao prvih 10 harmonika koje mi daje
furijeov red, ako nisu isti, da li su bar u nekoj direktnoj vezi(pomnozeni nekom konstantom i sl) i
ako nisu, da li postoji ikakva povezanost među njima?

Hvala @milanche za prethodni odgovor!

izvinjavam se ako je post haotičan.

Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.hsd1.ca.comcast.net.

+1001 Profil

Re: DFT vs Fourier Series

^{29.06.2012. u 07:22 - pre 144 meseci}

Citat:

a i profesorima promakne

....hmmm.....hmmmm....da, da, promakne im....pricao sam o tome u jednoj od
predhodnih DSP tema.

Najvolim kad pocnu predavanje sa 'dato je izrazom' - ni ko ga je dao, ni zasto je
dato, ni koja je elementarna fizika (ili filozofija) iza cele price, ni ko koga ni zasto,
samo ti servira matematicku formulu, sto kvrgaviju to je prica ozbiljnija.

A cemu to sluzi (a i ne radi) - boli koga ona stvar da objasni. Ko razume - shvatice.

No, da ne duzim:

Odgovor na sve sto si pitao je 'tacno'.

Pre nego sto ti razvejem i tih poslednjih par nedoumica, moram da ti dam jednu
korisnu analogiju:

zidarskom spahtlom se obicno stavlja malter na zid, ali se ista moze upotrebiti i
da se probusi karton, pa cak i da se otvori flasa piva.

Potpuno analogno tome:

Matematicki aparat Fourier-ovog reda se normalno upotrebljava da se periodicnom
signalu izracunaju diskretne spektralne komponente, znaci to mu je originalna i
primarna namena.

Medjutim, kao sto sam ti objasnio u svom prvom odgovoru, moze se sasvim suvislo
iskoristiti i za drugu svrhu - da se tacno i brzo odradi procena spektra aperiodicnih
signala (tacnije, jednog kratkog snapshota u vremenskom periodu [0 - NTs]).

Matematika je ista u oba slucaja, ali je fizicka interpretacija rezultata razlicita.

U prvom slucaju rezultati znace apsolutnu istinu (nema drugih spektralnih komponenti
mimo tih izracunatih) u beskonacnom trajanju (spektralne vrednosti se ne menjaju
doveka jer signal periodicno pici odavde do vecnosti).

U drugom slucaju, vrednost i primenjivost rezultata je sasvim drugacija - rezultati su
kratkotrajne vrednosti, odnose se samo na signal u vremenu [0 - NTs] i ni nasta drugo
ni pre ni posle toga. Takodje, svesni smo da je to sto radimo relativno bedan pokusaj
da u snapshot uhvatimo idealno - ne mozemo ni priblizno uhvatiti vrednosti spektra na
svim frekvencijama, nego samo na tom nekom periodicnom gridu (f = k/NTs). Opet,
srecni smo ko kucici, jer to sto smo sracunali ipak nije lose - daje nam neku procenu
sa nekom finocom, to sve moz' da se turi u kompjuter/procesor, i s tim moze nesto
da se uradi.

Konkretno - ako uradis DFT na N = 2¹⁶ = 65536 tacaka audio signala semplovanog na
Fs=44100, dobices procene spektra na frekvencijama na rastojanju 0.67 Hz, sto je
do yaya ako mene pitas.

_{[Ovu poruku je menjao milanche dana 29.06.2012. u 08:40 GMT+1]}

Odgovor na temu

milanche
San Francisco

Član broj: 2447
Poruke: 1200
*.hsd1.ca.comcast.net.

+1001 Profil

Re: DFT vs Fourier Series

^{29.06.2012. u 07:30 - pre 144 meseci}

Citat:

ako nisu isti, da li su bar u nekoj direktnoj vezi(pomnozeni nekom konstantom i sl) i
ako nisu, da li postoji ikakva povezanost među njima?

Ovo pitanje zasluzuje jos malo neke paznje.

Pazi ovako - Furijeova transformacija ima jednu jedinu sustinu - signal je suma sinusoida
raznih frekvencija/amplituda/pocetnih faza. To je pocetak i kraj price.

E, sada, rade se jos kojekakvi sitni frizeraji sa konstantama.

Neko se dosetio da ako ispred sume u formuli direktne Furijeove transformacije stavi 1/koren(N)
da ce moci isto da uradi i sa formulom za inverznu Furijeovu transformaciju. Kud ces vece srece
sto smo ostvarili jos jednu lepu simetriju.

Tako da - ako me pitas - da li su u direktnoj vezi i koja konstanta treba da se tura u kojem slucaju -
preporucio bih ti da vidis sta profesor kaze i/ili sta pise u knjizi i/ili sta ce da ti trazi na ispitu.

Te konstante su od relativno male sustinske vaznosti (osim za zezanje studenata na ispitu),
bitno je da znas fizicku sustinu. Prema nekoj normalnoj 'bread-n-butter' iliti 'srpskoj/seljackoj/pravoslavnoj'
varijanti u jednom smeru ne treba nikakvo mnozenje, dok u inverznom smeru treba mnozenje sa 1/N
da bi rezultati bili u saglasnosti.

Odgovor na temu