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]