Fast Fourier Transform(FFT)

quote:

% This programme is open source code of fast fourier transform in matlab.
% Where y is the input argument and p is the normalized size of the input. Let
% y = [1 2 3 4 ];
% x= length(y);
% m= log2(x);
% p= ceil(m);
% To call the function use
% ft2(y,p);

function Y=ft2

size=length(input);
l=log2(size);
p=ceil(l);
Y=input;
N = 2^p;
N2=N/2;
YY = -pi*sqrt(-1)/N2;
WW = exp(YY);
JJ = 0 : N2-1;
W=WW.^JJ;
for L = 1 : p-1
u=Y(:,1:N2);
v=Y(:,N2+1:N);
t=u+v;
S=W.*(u-v);
Y=[t ; S];
U=W(:,1:2:N2);
W=[U ;U];
N=N2;
N2=N2/2;
end;
u=Y(:,1);
v=Y(:,2);
Y=[u+v;u-v];
Y

quote:

Orijinalden alıntı: emter

......

ifade etmektedir. Şimdi X[1] için hesap yapacak olursak ;
Gerçel X[1] = x[n]cos[2pi*1*n/N]

Buradaki n x[n] ve N ne olmalı ?

quote:

Orijinalden alıntı: Elektroniker

quote: Orijinalden alıntı: emter ...... ifade etmektedir. Şimdi X[1] için hesap yapacak olursak ; Gerçel X[1] = x[n]cos[2pi*1*n/N] Buradaki n x[n] ve N ne olmalı ?

X[1] = x[n]cos[2pi*1*n/N] değil. Toplam sembolü var orda bakın.

       
      N-1 
  Xk = ∑ x[n]*cos(2Π*k*n/N) 
      n=0 
   
   
      N-1 
  X[1] = ∑ x[n]*cos(2Π*1*n/N) 
      n=0 
  

Buradaki n toplam sembolü üzerinden bir döngüye girecek ve x[n] dizisine indis olacak. Yani x[1], x[2], x[3] değerlerini alıcaksınız. x[n] dizisi ise giriş. Yani sizin A vektörünüz. N ise örnek sayısı. Sizin örneğinizde 5.

Yalnız bu FFT değil DFT. Sinyalin ya da sistemin frekans tepkisini bulmak için DFT kullanılır. FFT ise DFT nin özel bir halidir.
DFT yapısından dolayı frekans spektrumunu hesaplamak için çok sayıda gereksiz işlem yapar. Yapılan bu gereksiz işlemler bazı temel özellikler kullanılarak (periyodiklik, simetri gibi) azaltılır, yapılan işlem sayısı azaldığı için frekans spektrumu çok daha hızlı ve efektif olarak hesaplanır. İşte bu gereksiz işlemlerin atılmış haline FFT diyebilirsiniz. Farklı FFT algoritmaları vardır, araştırırsanız göreceksiniz.

Fakat FFT yi öğrenmeden önce DFT yi öğrenmeniz gerekir. Yani işlemin nasıl yapıldığını öğrenin ki, daha efektif nasıl yapılabilir öğrenebilin. DFT en temel haliyle yukarıdaki formüllerde anlatıldığı gibidir.

Formül şudur :

      N-1 
     Xk = ∑ x[n]*e^(-i*(2Π*k*n/N)) 
         n=0

Basit bir uygulama yazdım sonuçları görün diye. Alttaki program yukarıdaki formülü kullanarak DFT hesaplar. Fakat bu şekilde pratikte kullanımı aşırı derecede gereksizdir çünkü çok işlem gücü ister. Bir deneme yaptım biraz önce,22 kHz de örneklenmiş 4-5 saniyelik bir ses kaydının frekans spektrumunu çıkarıyım dedim bunla, i7 işlemcili 6 GB ram olan bilgisayarım cevap veremedi

 
  % Temizlik 
  clc 
  clear all 
   
  % Giris dizisi 
  input = [523 176 912 349 277]; 
   
  % Sonuclarin daha belirgin olmasi icin 
  % giris dizisini 2 periyot yapalım 
  input = [input input]; 
   
  % Giris dizisinin boyutunu bul 
  N = length(input); 
   
  % Giris dizisiyle ayni boyutta "0" dolu dizi olustur 
  X = zeros(1,N); 
   
  % DFT hesaplanan bolum 
  for k = 0:N-1 
      for n = 0:N-1 
          X(k+1) = X(k+1) +  input(n+1) * exp((-i)*2*pi*k*(n)/N);       
      end  
  end 
   
  % DFT yi cizdirelim 
  subplot(2,1,1) 
  manual_ft = fftshift(abs(X)); 
  plot(manual_ft); 
   
   
  % Karsilastirmak icin, bilgisayar tarafından hesaplanan 
  % Fourier Donusumunu de kendi grafigimizin hemen 
  % altina cizdirelim 
  automatic_ft = fftshift(abs(fft(input)));     
  subplot(2,1,2) 
  plot(automatic_ft); 
  

Sonuç :

Üstteki bizim DFT algoritmamız, alttaki ise MATLAB ın hesapladığı FFT algoritması. Gördüğünüz gibi hiçbir fark yok.

Bu arada Allah kimseyi işsiz bırakmasın. Gece saat kaç olmuş üşenmeden oturup bunları yazdım.