[ Dejan Lozanovic @ 15.01.2002. 20:56 ] @
Ajde da malo priblizim matematiku programiranju, pa zato javno saljem svoj domaci zadatak vezan, za FFT. Jeste da je ipak tema iz neke vise matematike ali cu pokusati da spustim celu stvar na srednjoskolski nivo, tj da svako zna sta je to i npr gde bi to mogao da iskoristi.

Malo teorije:
Sta su Furijeovi redovi ?
Pa furijevi redovi su jedna vrsta aproksimacije(uproscavanje, zamenjivanje jednostavnijom) periodicnih funkcija. Mi dakle neku funkciju pokusavamo da zamenimo sa sumom sinusa i kosinusa; sum(alpha[i ]*sin(i*x)+beta[i ]*cos(i*x), gde su nam alpha[i ] i beta[i ] intenziteti,a da vas podsetim malo predpostavljam da znate kako izgleda sinus i kosinus od x, pa npr sinus(2*x) izgleda isto kao i sinus(x) samo on dvaput brze uradi onu krvulju, tj izgleda isto kao i sinus x samo sto treba sinusu da naravi na intervalu od [0,2*Pi] to isto Sin(2*x) napravi na intervalu [0,Pi]. Razlog zasto koristimo i sinus i kosinus, je da bismo neku frekvenciju mogli da opsemo kako stoji u celoj skupini, tj da bismo mogli da opisemo njeno kasnjenje u odnosu na osnovnu sinusoidu(sinus kasni za kosinusom Pi/2, a mi koriscenjem sinusa o kosinusa smo u stanju da opisemo kasnjenje za bilo koju vrednost ugla). I postupak kojim se odredjuju sinusi i kosinusi za datu funkciju u furijeov red naziva se furijeva transformacija. (ako nekog zanima dokaz neka se obrati na ovom forumu i odgovoricu mu, mada verujem i da je nasa moderatorka dovoljno strucna da odgovori pogotovo ako uzmemo u obzir da studira teorisku matematiku :) )

Ako nasoj funkciji izmerimo njene vrednosti na n tacaka, kolicina racunanja za furijevu transformaciju je oko n*n koraka. sto je sa nekog matematickog aspekta a i vremenskog jako mnogo ( svi vi znate kako izgleda funkcija x*x). E sada vi kazete lepo je sve to, ali sta mi vredi kada je to neupodrebljivo :(( .

Tu nam se javlja Brza Furijeva transformacija koja je brzinu od n*n popravila i vreme svela na n*log(n) sto je znacajan dobitak. Uz poruku vam saljem i svoju implementaciju na C jeziku koja racuna FFT. Jedino ogranicenje kod FFT-a je da broj tacaka n da bude jednak 2^p gde je p neki prirodan broj.

Malo prakse:
Ma koji ce mi FFT sta ja mogu sa njim da radim ?

Pa primena FFT-a je velika, cela elektrotehnika bazirana na FFT zbog neizmenicnih struja. A evo jedan mozda zanimljiviji primer celokupno DJ-isanje, techno i ostale elektornske muzike, je opet primena FFT-a mozda to DJ-jevi ne znaju jer oni to rade instiktivno. Prva stvar koju urade jeste usklade jaciinu zvuka obe pesme( to obicno urade preko jacine basa) matematicki gledano izjednace vrednosti baseva srqt(alpha[i ]sin(i*x)+beta[i ]*cos(i*x)) jedne pesme sa vrednoscu srqt(alpha[j]sin(j*x)+beta[j]*cos(j*x)), zatim gledaju da podese istu frekvenciju basa jedne i druge pesme popularno nazvano BPM, matematicki gledano translatorno pomere vrednosti indexa tako da se koeficijenti koji su bili uz index j postanu budu uz index i ( huh nadam se da vas nisam zbunio). i treca stvar koju urade podese ugao kasnjenja, da se pududara, tj da se udar basa cuje u isto vreme na obe pesme.

A sada malo o fonkciji koja ide uz poruku:
fft (int direct_fft, int p,
double *re_in, double *im_in, double *re_out, double *im_out)

direct_fft znaci u kom smeru radimo trasformaciju ukoliko je direktna transformacija onda iz funkcije racunamo sinuse i kosinuse, u suprotnom smislu iz datih sinusa i kosinusa racunamo vrednosti tacaka funkcije. broj tacaka n je izrazen u obliku 2^p, ostali parametri su relativno razulnjivi realne vrednosti su vezane za kosinuse a imaginarne za sinuse.

PS Nadam se da vas nisam ugusio sa svime ovime, i opet kazem ako ima nekih nejasnoca oko svega ovoga slobodno se obratite

[Ovu poruku je menjao kajla dana 27.06.2002 u 07:05 PM GMT]
[ nervozna @ 16.01.2002. 00:09 ] @
Sta se trazi ovde?Meni zaista nije jasno.
Mogu da prepoznam elemente KOMPLEKSNE ANALIZE(transformacije),ali se u primenu ne razumem. :(
Lepo si rekao da je ovo kombinacija nasih dragih nauka.Detaljno o tome ne znam nista.
[ Ivan Dimkovic @ 16.01.2002. 01:05 ] @
Bacio sam pogled na tvoju implementaciju FFT-a i mogu da primetim da nije bas optimizovana za brzinu izvrsavanja, ali ako je domaci - onda ok :)

Za zainteresovane imam sajt: http://www.fftw.org/ koji ima vrlo optimizovanu implementaciju FFT transformacije. U digital signal processingu je uvek neophodno imati najbrze implementacije FFT-a i ostalih derivata (DCT, DST, MDCT, MDST)

Primena FFT-a je vrlo siroka, obicno se koristi bilo gde gde je potrebno dobiti spektralnu sliku (razloziti signal u frekvencije) - na primer, u efektima za analizu zvuka, u MP3 kompresiji (kao transformacioni filter za psihoakusticki model), moze cak da izigrava i frekventni filter (mada se za ovo vise koriste FIR filteri), itd.. itd...
[ Dejan Lozanovic @ 16.01.2002. 13:49 ] @
Da u pravu si radi se o domacem zadatku kod A. Samardzica, ali posto je kod cini mi se jako detaljno izkomentarisan, mislio sam da bi mozda bilo zanimljivo i ostalima.



Evo jos par primera kod zvuka gde se koristi, ekvilajzeri npr, i u zadnje vreme svaka susa u studiju moze da snimi kompakt CD :), jer jednostavno one frekvencije sa kojima pevaljka ima losu boju glasa budu utisane, ili pak srede da pevaljka peva za oktavu vise :))).

Bojan Bašić: obrisan nepotreban citat

[Ovu poruku je menjao Bojan Basic dana 12.08.2004. u 00:48 GMT]
[ Ivan Dimkovic @ 16.01.2002. 14:30 ] @
Citat:
SyStemOuT:
Da u pravu si radi se o domacem zadatku kod A. Samardzica, ali posto je kod cini mi se jako detaljno izkomentarisan, mislio sam da bi mozda bilo zanimljivo i ostalima.


:) Heh... znaci AcO Samardzic voli da daje ovakve zezalice.. pa fino fino :)


Citat:

Evo jos par primera kod zvuka gde se koristi, ekvilajzeri npr, i u zadnje vreme svaka susa u studiju moze da snimi kompakt CD :), jer jednostavno one frekvencije sa kojima pevaljka ima losu boju glasa budu utisane, ili pak srede da pevaljka peva za oktavu vise :))).


Hmm.. mislim da na netu ima dosta primena FFT transformacije - manje-vise se koristi za bilo sta sto ima veze sa spektralnom analizom (high-pass, low-pass, band-pass, ekvilajzeri, raznorazni efekti). Ne treba zaboraviti da je ponekad ulaz potrebno pomnoziti sa tzv. "prozorom" (Hann, Hamming, Blackmann, Blackman-Hariss, Sin, Sin^2, Kaiser, Kaiser-Bessel) - ovi koeficijenti su odabrani da bi se dobio sto bolji odziv odredjenih frekventnih koeficijenata, a i da bi se izbegao tzv. "aliasing"

Inace, kao zanimljivu primenu FFT-a sam video kontrolu rada turbine, gde se preko FFT analize ulaza (semplovan zvuk motora) i identifikacije najjacih spektralnih koeficijenata dobija brzina rada motora - ukoliko ta frekvencija opadne ispod odredjenog praga daje se signal da nesto nije u redu, itd..

[ Ivan Dimkovic @ 17.01.2002. 17:27 ] @
Citat:

E sada me bas pogodi u zicu i to onu zlatnu :)) posto moji imaju servis turbina, i recimo da mi FFT bas treba za izradu balans masine :)), da bih mogao da balansiram same turbine :))


Hehe :) Elem, taj rad sam negde procitao ali nije bio direktno vezan za procesiranje signala (tj. kompleksnu analizu Furijeovim redovima) - vec je bio vezan za neuronske mreze. Pretpostavljam da su koristili neural network kako bi eliminisali neke slucajne greske ili napravili threshold kada se signalizira da nesto ne valja... ne bih znao...

Ja koristim FFT za jednu drugaciju primenu (tj. koristio sam ga, sad koristim pogodniju transformaciju) - za ulaznu analizu spektra u MPEG-4 audio kompresoru. Cilj je odrediti prag maskiranja, FFT koeficijenti se grupisu u grupe koje odgovaraju ljudskom sluhu (25 kriticnih opsega), izracuna se prosecna vrednost - proceni tonalitet (predikcija amplitude i faze kompleksnog FFT spektra) a onda izvrsi konvolucija sa funckijom prostiranja - i time se dobija maksimalni dozvoljeni sum. U kasnijim koracima se vrsi kvantizacija uz kontrolu koeficijentima dobijenim gore pomenutom metodom... Sve to radi u praksi, tako da na stepenu kompresije od 11:1 90% ljudi ne moze da razazna komprimovani signal od originala :) Inace, ja koristim vrlo brzu radix FFT implementaciju, preuzetu sa fftw.org :)
[ Mr. Rejn @ 10.05.2002. 22:44 ] @
Zar realni primer Fourierove transformacije nije hologram?
Koliko sam cuo,holograme je moguce dobiti u audio-frekvencijama
(frekvencija magnetnog polja).O ovim stvarcicama ima interesantnih
tvrdnji na Internetu:pogledajte neki clanak o bio-hologramima...
Nacicete elektronsku shemu uredjaja za dobijanje holograma (koristi se magnetno polje u audio frekvencijama,beli shum se dobija iz tranzistora).
Hologrami imaju i neke filozofske konotacije (holografski univerzum),
sto se moze koristiti za objasnjavanje fenomena ESP (ekstra-senzorna percepcija).
Recite mi sta mislite o ovome,veoma me zanima!
[ Dejan Lozanovic @ 26.06.2002. 13:04 ] @
Kod koji sam poslao nije hteo da radi jer sam jednu promeljivu pogresno krstio pa nije moglo da se kopmajlira.


Zahvaljujuci FireballKiller-u koji je uocio da sa kodom nesto nije u redu, i ovom prilikom mu se zahvaljujem.