fft

• herhangi bir karmasik sinyali frekans eksenine yaymak icin yapilan fourier transform isleminin hizli hesaplanmasini saglayan bir algoritma. fourier'e gore butun karmasik sinyaller belirli frekans,genlik ve fazdaki sinuslerin toplamidir.
• fft fourier tarafindan bulunmamistir. boyle olduunu dusunenler eblektir. cooley ve tukey denen iki adam 1965 yilinda bu algoritmayi modern dunyanin hizmetine sunmustur. zaten "digital signal processing"'in olmadigi yillarda boyle bi olaya girmenin hicbi alemi yoktur. bu yuzden fourier kendi transformasyonunu bulduktan sona koyverip "sikerim ben yapcaimi yaptim, bunun hızlı yapılanını da benden sonakiler bulsun" demistir. lakin bu algoritmanin taa 1805'te gauss tarafindan bulunduunu soyleyenler de var. olay kisaca soyledir: once elindeki discrete ve finite sinyali tutup 2^n'e kadar zero pad edersin. sona bunu 2'ye bole bole gidersin her basamakta bi transform daha almaya kalkarsin, ama kolaya kacip bu transformu da fast yapmak istersin, en sonunda birde bakarsin ki transform pat diye cikmis meydana. yada cikistiramazsan matlab'ı açarsın fft(sinyal) dediin anda o her$eyi yapar mutlu olursun...
• zaman domenindeki bir veriyi frekans domenine çevirmek için kullanılan bir dönüşüm. joseph fourier'in yaklaşık 200 sene evvel önerdiği teoreme göre tüm sürekli işaretler sinus ve cosinus dalgalarının toplamları şeklinde ifade edilebilirler. daha anlaşılır bir ifadeyle fourier dönüşümü bir işaretin sinusoidal dekompozisyonudur. bilgisayar işin içine girince ayrık fourier dönüşümünden bahsetmek durumundayız. (sürekli fourierdeki integral işaretleri toplam sembolüne dönüşüyor yani). hızlı fourier dönüşümü ise bir algoritma dahilinde fourier dönüşümünü çok hızlı hale getirmektedir. sonucun kalitesi için hesaplama yapılacak nokta sayısını büyütmekte fayda vardır ayrıca matlabdeki fft() ve fft2() fonksiyonları tevatirdir :)
• bazi dsp chiplerine, daha da hizli calistirilabilmesi icin ozel instructionlar eklenmesine sebep olmus algoritma. fourier'e gore, her periyodik sinyal, farkli frekans ve genlikteki sinuslerin toplami ile ifade edilebilir. fourier donusumu, continuous bir sinyalin sinuslerin toplami ile ifade edilmesidir. ancak belirli sayida ard arda alinmis sample'in olusturdugu isaret soz konusu oldugunda dft, yani discrete fourier transform alinabilir. aslinda temel olarak ikisi de ayni seydir. fft ise dft almak icin optimize edilmis bir algoritmadir.
  fft'nin calisma hizi, ne cesit dft alindigina ve kac sample'in islenecegine baglidir.
• nxn'lik matris carpmasindan ibaret olan dft islemini, n^2 carpma yerine 1/2*n*log2(n) carpma yaparak gerceklestirme metodu.
  
  ornegin 1024x1024 dft matrisi icin duz yoldan yapilacak bir hesapta yaklasik 1 milyon carpma islemi yapmaniz gerekirken, fft ile ayni islem 5120 carpma ile gerceklestirebilir. log(n) sevimli ve cok yavas artan bir fonksiyondur.
  
  (bkz: twiddle factor), (bkz: tekler ve ciftler)
• elinizde tem'den gelen bir resim varsa bunun icindeki kristal yapilari bulabilmek icin once fft'si alinir. fft isleminin size verdigi resimdeki tepe noktalarinin frekans degerleri kristalin periyodik ozelliklerine tekabul eder.
  eger bu tepeler yeterince belirgin degilse veya arka plandaki gurultuden filtrelemek istiyorsaniz fft resminizdeki dusuk frekanslari filtreleyip^* cikan resmin ifft'sini almak lazimdir.
• (bkz: four four two)
• ce$it ce$it fft algoritmasi vardir. sinyalin uzunluguna gore farkli algoritmalar secilebilir. misal uzunlugu 2^n olan sinyalin dft'sini almanin en bariz yolu radix-2 iken (sinyali her basamakta 2'ye bolerek ilerleyeninden) ayni algoritma rahatlikla 3^n, 5^n uzunlugundaki sinyallere genellenebilir (radix-3, radix 5 vs.) rasgele uzunlukta bir sinyal icin bu uzunlugu asal carpanlarina ayirip asal carpanlara gore karma bir algoritma kullanilabilir (2^n*5^m uzunlugundaki sinyal icin radix (2,5) kullanmak gibi). eger sinyalin uzunlugu (n) asal sayiysa once n-1'lik kisim alinir. bu sayi asal olamayacagindan asal carpanlarina ayrilip karma-radix algoritmasiyla dft'si hesaplanir, son elemanin katkisi da ayrica bu sonuca ilave edilir.
• cooley ve tukey'den önce, gauss zaten bunu satürn halkalarıyla ilgili bir hesap yaparken bulmuş.
  
  http://www.wikiwand.com/en/fft#algorithms
• fft gunluk hayatta ne isime yarayacak sorusunu soran arkadaslariniz varsa, adamlarin^* bunu kullanarak isigi filtreleyip 300 farkli frekansta renklerine ayirarak fiber optik uzerinden her bir renk bir kanal olacak sekilde veri ilettigini ve bu sayede saniyede 26tb'lik data transferi yapmayi basardiklarini ornek verebilirsiniz. aslinda bu ornek gosteriyor ki neyi nasil kullanabilecegini bulmak bilimin gelismesindeki en onemli sey aslinda. birisi fft'den yararlanip fotograflarinda yuzunu daha bulaniklastirip sivilcelerini gorunmez yapip facebook'a koymak icin kullanir, digeri internet kullanim hizini yuzlerce kat arttirabilecek bir sey bulmak icin kullanir. ha belki kimisine gore ilki daha onemlidir tabi.