Hızlıfourierdonusumu

HIZLI FOURİER DÖNÜŞÜMÜ ( FAST FOURİER TRANSFROM-FFT ) Hızlı Fourier dönüşümü titreşim analizinde kullanılan istatistik tabanlı matematiksel bir işlemdir. Karışık halde bulunan sinyalleri birbirinden ayrıştırır ve hangi frekansta hangi şiddette bir titreşim olduğunu gösterir. Kısaca FFT sinyallerimizi frekans alanına geçirirken kullandığımız bir işlemdir. FFT tekrarlanmayan sinyalleri dikkate almazken karmaşık sinyaller içinde periyodik olanları belirleyip bunları harmonik bileşenlerine ayırır. FFT, zaman düzlemindeki sinyali eşdeğer frekans düzlemindeki sinyale dönüştürmekte kullanılan bundan bir önceki yöntem olan DFT ( Ayrık Fourier Dönüşümü ) tabanlı verimli bir algoritmadır. Bazen bu dönüşümler zaman düzlemindeki alanların frekans düzlemindeki alanlara dönüştürülmesi olarak da tanımlanabilir. Bu da zamana bağlı olarak algılanan olguların analizinde kullanılan oldukça etkili bir yöntemdir. Fourier dönüşümlerini incelediğimizde karmaşık veriler içeren bilgi ya da işlemlerin çözülmesinin çok karışık ve zor olduğunu görürüz. Eğer elimizde 8 değişkenli bir sinyalimiz varsa bunu DFT ile analiz etmek istersek 49 karmaşık çarpma ve 56 karışık toplama işlemlerinin olduğunu görürüz. Bu veriler uzun zamanda hesaplanabilir veriler olmasına rağmen çok daha büyük sayıda değişkenli verilerde hesaplama oldukça zor olacak ve de büyük zaman kayıplarına sebebiyet verecektir. DFT den FFT ye geçişte özellikle çarpma işleminden bahsedilmesinin sebebi çarpma işleminin diğer işlemlerden daha fazla zamanda yapılmasındandır. Başka bir deyişle; FFT eğri üzerinde eşit aralıklarla çok sayıda örnek alarak çözüm yapan bir algoritmaya sahiptir. Örnek sayısı yarıya düşürüldüğünde eğrinin analizi için gereken çarpan sayısı da yarıya düşer. Örneğin ; 16 örnekten oluşan bir eğri için 16nın karesi yani 256 çarpma gerekecektir ve eğer eğriyi iki tane 8 örnekten oluşan parçaya ayırırsak, her parça için 8in karesi yani 64 çarpma; iki çarpma için 128 çarpma olacaktır ki bu da önceki durumun yarısına eşittir. Yani örnek serisini alt bölümlere ayırmaya devam edersek 8 ana noktadan oluşan ve bölünemeyen parçalar elde ederiz. Bu iki noktadan oluşan ve bölünemeyen parçaların Fourier Dönüşümleri çarpma yapmadan hesaplanabilir ancak dönüşümün tamamını hesaplarken parçaları birleştirmek gerekeceğinden buradaki çarpma işlemlerini yapmak yeniden zorlaşacaktır. Fourier dönüşümünün üstün bir yanı fiziksel olguların gösterilmesinde daha uygun olmasıdır. Pek çok durum örneğin basit bir sistemin titreşime gösterdiği tepki, sinüzoidal fonksiyonların karmaşık toplamı şeklinde gösterilebilir bu nedenle Fourier Dönüşümünün doğanın davranışlarını göstermek için daha uygun olduğu söylenebilir. FFT algoritması N kompleks noktalı bir data serisinin sonlu Fourier Dönüşümünü yaklaşık Nlog2N işlemle hesaplayan bir metottur. Fourier analizi ilk açıklandığında N^2 işlemle orantılı olan ve orantı faktörünün trigonometrik fonksiyonların simetri özellikleri kullanılarak azaltılabileceğine inanan birçok kişinin ilgisini çekerken ; o yıllarda N^2 işlemli metotları kullanan bilgisayarlar yüzlerce saatlik bir işlem süresine ihtiyaç duymaktaydı. Cooley ve Tukey’in hızlı Fourier dönüşümü algoritması N kompozit (yani iki ya da daha fazla sayının çarpımı gibi) veya 2’nin bir kuvveti olmadığında bile uygulanabilir olmasından dolayı genel bir algoritmadır. Ve böylelikle eskiden saatlerce süren hesaplamalar Cooley ve Tukey’in algoritması ile dakikalar içerisinde gerçekleştirilebilir bir hale gelmiştir. Fourier dönüşümü kullanılarak algoritmaların hesaplanması ve oldukça azalmış işlem yükünün elde edilmesi sinyal işlemedeki uygulamaları ve oldukça verimli hesaplama algoritmalarının bulunmasını etkilemiştir. Genel anlamda FFT dönüşümünü yazacak olursak; FFT N noktayı den e azaltan ve bunun için çok daha az sayıda işlem kullanan bir matematiksel işlemler

topluluğudur ve de DFT‘nin basitleştirilmiş halidir. bu fonksiyonda dönüşümler harmonik değillerdir baz alınan frekans aralığına ya da frekansa göre değişiklik gösterirler. FFT bir çeşit sinüs fonksiyonu gibidir ve gittikçe azalan fonksiyonlarla istenilen işlem yapılır. FFT algoritmaları genellikle zaman kırımı ve frekans kırımı olmak üzere iki kısımdan oluşur ve genel mantığı 2’ye bölme üzerine dayanmaktadır. FFT fonksiyonlarını yazacak olursak:

Örneklerle çözecek olursak : Örnek 1: hftG: Hızlı Fourier Dönüşümü’nün gerçek kısmı hftS: Hızlı Fourier Dönüşümü’nün sanal kısmı x: dönüşüm yapılacak dizi x=Array(0,2,3,1); donusum = hftG(x); olarak kullanılabilir function hftG(x){G = new Array();N=x.length;for(k=0;kkx[n]X[k]|X[k]|");for(k=0;k"+k+""+x[k] +"")document.write(""+g[k]+"j("+s[k] +")");document.write(""+Math.sqrt(Math.pow(g[k],2)+Math.pow(s[k],2 ))+"")}document.write("");}genlik(Array(1,0,-1,0,0,1,0,1));

Çıktı: k 0 1 2 3 4 5 6 7

x[n] 1 0 -1 0 0 1 0 -1

X[k] 0 -0.41421356237309515 2.000000000000001 2.414213562373094 0 2.414213562373093 1.9999999999999978 -0.41421356237309614

j(0) j(-0.9999999999999998) j(2) j(0.9999999999999992) j(0) j(-1.0000000000000013) j(-2.0000000000000004) j(1.0000000000000042)

|X[k]| 0 1.0823922002923938 2.8284271247461907 2.613125929752752 0 2.613125929752752 2.828427124746189 1.0823922002923982

Örnek 2: FTT , tipik karşılaştırma sinyalimiz: FTT(x,N) X : dönüştürülmek istenen x[n] N: FTT deki ana noktaların sayısı ve en az x[n] örnekleme sayısı kadar olmalı N’nin değeri her 30 örnekte değişen kosinüs ile her 10 örnekle değişen periyoda göre değişsin. N ‘nin 3 farklı değerini belirleyelim ve her 3 değer için x[n] dönüşümünü yapalım. n = [0:29]; x = cos(2*pi*n/10); N1 = 64; N2 = 128; N3 = 256; X1 = abs(fft(x,N1)); X2 = abs(fft(x,N2)); X3 = abs(fft(x,N3)); F1 = [0 : N1 - 1]/N1; // frekans aralığı 0 dan başlayıp N-1 e kadar N noktada FFT için. F2 = [0 : N2 - 1]/N2; // örnekleme yapar. Bu durumda aralığımız 0 den 1-1/N e kadar F3 = [0 : N3 - 1]/N3; // olmalıdır. subplot(3,1,1) // her bir dönüşümün çizimi diğeri üzerindedir. plot(F1,X1,’-x’),title(’N = 64’),axis([0 1 0 20]) subplot(3,1,2) plot(F2,X2,’-x’),title(’N = 128’),axis([0 1 0 20]) subplot(3,1,3) plot(F3,X3,’-x’),title(’N = 256’),axis([0 1 0 20])

Şekil 2’de görülen çizimde her dönüşümün aynı alanı kapladığını tek değişenin farklı sayıdaki örnekleme olduğunu ve bunlarının toplamının yaklaşık olarak aynı alanı gösterdiğini görmüş olduk. Örnek 3: Üstte verilen örnekte x[n] uzunluğu 3 örnekle sınırlanmıştı. N değerini istenilen kadar sayıda yapmak isteseydik nasıl bir dönüşüm programı yazardık bunu inceleyelim: n = [0:29]; x1 = cos(2*pi*n/10); x2 = [x1 x1]; x3 = [x1 x1 x1]; N = 2048; X1 = abs(fft(x1,N)); X2 = abs(fft(x2,N));

% 3 periods % 6 periods % 9 periods

X3 = abs(fft(x3,N)); F = [0:N-1]/N; subplot(3,1,1) plot(F,X1),title(’3 periods’),axis([0 1 0 50]) subplot(3,1,2) plot(F,X2),title(’6 periods’),axis([0 1 0 50]) subplot(3,1,3) plot(F,X3),title(’9 periods’),axis([0 1 0 50]) Bir önceki yapılan örnekteki kod 3 grafik çizimini üretecektir. İlk grafik kosinüsün 3 periyot boyunca dönüşümünü sinüs’ün ilk olarak 0.1 . periyotta ve ikinci olarak ise 0.9 uncu periyodundakine benzer olarak gösterecektir.

İkinci grafik 0.1 ve 0.9 uncu periyotlar arasında daha büyük ve daha geniş genlikli bir sinüs görünümü vermektedir. Buna benzer olarak 3. grafik ise daha geniş frekanslı ve büyüklüklü bir sinüs eğrisine benzemektedir. x[n], daha geniş aralıklı periyotlar arasında uzandıkça, sinüs eğrisi gittikçe daha çok impulse görünümünü alacaktır. Bunu açıklayacak olursak; FFT dönüşümü x[n] içinde daha geniş sayıda örneklemelerle N ile kıyaslanır ve x[n] değerleri örneklemelerde 0’lar ile doldurulur. 3.

örnekte görüldüğü gibi x[n] 30 örnekleme yapmış ancak FFT ‘ de N=2048 olmuştur. Matlab FFT’yi hesapladığında varolan boşlukları n=30 dan n=2047 ye kadar 0’larla dolduracaktır. HIZLI FOURİER DÖNÜŞÜMLERİYLE SPERKTRUM ANALİZİ FFT bize direk olarak sinyalin spektrumunu vermez. Yukarıda yapmış olduğumuz örneklerde FFT’nin alınan örnekleme sayısıyla (N) ve sinyalin değişen periyot aralıklarıyla değiştiğini gördük. FFT, ilk frekans değerindeki bilgiyle son frekans değerindeki bilgi arasındaki değerlei içerir ve bu frekans aralığında alınan örneklemelerde en az iki adet en yüksek frekans içeriği olmalıdır. Böylelikle işaretin spektrumu fs/2 aralığında olacaktır. Bununla birlikte gerçek bir sinyalin dönüşümü yapılırken simetrik olarak pozitif ve negatif frekanslar için de yapılmalıdır. Böylelikle spektrum –fs/2 den fs/2 ye kadar uzanan frekans aralığında olacaktır. Matlab da bunun için “fftshift” fonksiyonunu kullanarak aşağıdaki kodu elde edebiliriz. n = [0:149]; x1 = cos(2*pi*n/10); N = 2048; X = abs(fft(x1,N)); X = fftshift(X); F = [-N/2:N/2-1]/N; plot(F,X); xlabel(’frequency / fs’);