Ayyıldız2 | 2008 TR Yapısı • 1-99 Orta Emek Destan • Oto Avsız • 10 Temmuz 21:00 HEMEN TIKLA!
Tanım
\{x_k\}_{k=1}^N şeklinde bir dizi verilmiş olsun. Bu dizinin Ayrık Fourier dönüşümü
c_k = \sum_{j=1}^N x_k w_N^{(j-1)(k-1)}\quad, k=1,\ldots,N
ve Ters Fourier dönüşümü ise
X_j=\frac{1}{N}\sum_{k=1}^N c_k w_N^{-(j-1)(k-1)}\quad, j=1,\ldots,N
şeklindedir. Yukarıdaki eşitliklerde görünen w_N aşağıdaki gibidir.
{\displaystyle w_N=e^{-2\pi i/N}}
Ayrık Fourier dönüşümü ile elde edilen c_k katsayıları karmaşık sayılardır. Ancak c_1 öğesi gerçeldir. Geri kalan karmaşık sayılar aşağıdaki bağıntıya göre birbirlerinin eşlenikleridir.
c_2=\bar c_{N}
c_3=\bar c_{N-1}
\vdots
Ayrık zamanlı Fourier dönüşümü
Ayrık zamanlı Fourier dönüşümü (DTFT), ayrık zamanlı sinyal işleme algoritma ve sistemlerinin analizi, tasarımı, gerçekleştirilmesi ile doğrusal filtreleme, korelasyon analizi ve spektrum analizi gibi sinyal işleme uygulamalarında önemli bir rol oynar. DTFTnin bu öneme sahip olmasının ardındaki temel neden DTFTyi hesaplamakta kullanılan verimli algoritmaların varlığıdır[1][2].
DTFT, Fourier dönüşümünün eşit aralıklı frekanslardaki örneklerine özdeştir. Sonuç olarak N-noktalı bir DTFTnin hesaplanması Fourier dönüşümünün N örneğinin, N eşit aralıklı frekanslarla (w_k=2*pi*kn), z-düzlemindeki birim çember üzerinde N nokta ile hesaplanmasına karşılık gelir. Burada temel amaç N-noktalı DTFTnin hesaplanması için verimli algoritmaların kullanılmasıdır. Bu algoritmalar ortak olarak hızlı Fourier dönüşümü (FFT) algoritmaları adını alır. En yüksek verimin elde edilebilmesi için FFT algoritmaları DTFTnin N değerlerinin hepsini hesaplamalıdır.
Bir algoritmanın ya da gerçeklemenin karmaşıklığını ve verimini ölçmenin birçok yolu vardır. Bunun sonucundaki final değerlendirme hem mevcut teknolojiye hem de uygulamaya bağlıdır. Hesaplama karmaşıklığını ölçmek için aritmetik çarpma ve toplamaların sayısı kullanılacaktır[1]. Algoritmalar, genel amaçlı dijital bilgisayarlarda ya da özel amaçlı mikroişlemcilerde gerçekleştirildiklerinde hesaplama hızı, çarpma ve toplamaların sayısıyla doğrudan ilişkilidir.
Hızlı Fourier Dönüşümü (İngilizce: FFT, Fast Fourier Transform), bir zaman domeni sinyalini eşdeğer frekans domeni sinyaline dönüştürmekte kullanılan DTFT (İngilizce: Discrete Fourier Transform - Ayrık Fourier Dönüşümü) tabanlı verimli bir algoritmadır. Bu bölümde çeşitli gerçek zamanlı FFT örnekleri gerçekleştirilecektir.
Hızlı Fourier Dönüşümü algoritması, Nkompleks noktalı bir data serisinin sonlu Fourier dönüşümünü yaklaşık Nlog2N işlemle hesaplayan bir metottur[3]. Algoritmanın gerçekten de büyüleyici bir tarihi vardır. Bu algoritma, 1965de James Cooley ve John Tukey tarafından açıklandığında[4], Fourier analizinin 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şi tarafından büyük ilgi topladı. O yıllarda N^2 işlemli metotları kullanan bilgisayarlar yüzlerce saatlik bir işlem süresine ihtiyaç duymaktaydı. Cooley ve Tukeyin makalesinin etkisiyle Rudnick, 1942de Danielson ve Lanczosun önerdiği bir metodu geliştirerek Nlog2N sayıda işlem yapan kendi bilgisayar programını tanımladı.
Cooley ve Tukeyin hızlı Fourier dönüşümü algoritması N kompozit (yani iki ya da daha fazla sayının çarpımı gibi) veya 2nin bir kuvveti olmadığında bile uygulanabilir olmasından dolayı genel bir algoritmadır. Eskiden saatlerce süren hesaplamalar Cooley ve Tukeyin algoritması ile dakikalar içerisinde gerçekleştirilebilir bir hale gelmiştir[4].
Trigonometrik fonksiyonların hem simetri hem de periyodiklik özelliğini kullanan hesaplama algoritmaları, yüksek hızlı dijital bilgisayarlar çağının çok daha öncesinde bilinmekteydi. O zamanlarda manüel hesaplamayı 2 kat dahi azaltacak yeni bir düzen bile literatürde yerini almaktaydı. Runge 1905de ve daha önce bahsedildiği üzere Danielson ve Lanczos da 1942de N^2 işlem yerine Nlog2N ile orantılı sayıda işlem yapan algoritmaları tanımlamışlardı. Fakat ta ki 1965de Cooley ve Tukey ayrık Fourier dönüşümünü hesaplamak için algoritmalarını yayınlamadan önce oldukça azaltılmış hesap yükü elde etme olasılığı görmezlikten gelinmişti. Bu makale, ayrık Fourier dönüşümünün sinyal işlemedeki uygulamalarını ve oldukça verimli hesaplama algoritmalarının bulunmasını tetikledi.
DTFT, zaman alanı dizisini eş değer frekans alanı dizisine çevirir. Ters DTFT ise geri işlemi gerçekleştirerek frekans alanı dizisinden eş değer zaman alanı sinyali geri elde eder. FFT, DTFTye göre daha az hesap yapmasına karşın oldukça verimli bir algoritma tekniğidir. FFT DSPde frekans spektrum analizi için en yaygın olarak kullanılan operasyondur. FFT algoritmaları, uzunluğundaki bir dizinin ayrık Fourier dönüşümü hesabını daha küçük DTFTlere ayrıştırma temel prensibine dayanmaktadır[1]. Bu temel prensip çeşitli farklı algoritmalarla gerçekleştirildiğinde hesaplama hızında kayda değer bir artış elde edilmektedir. Bir FFTyi hesaplamak için iki farklı prosedür uygulanmaktadır. Bunlar; x[n] zaman dizisinin daha küçük alt dizilere bölündüğü zamanda desimasyon (örnek seyreltme) ve ayrık Fourier dönüşümü dizisi katsayıları X[k]nın daha küçük alt dizilere ayrıştırıldığı frekansta desimasyon algoritmalarıdır. FFTin Ayrık Kosinüs dönüşümü (İngilizce: DCT, Discrete Cosine Transform), Goertzel algoritması ve Hızlı Hartley dönüşümü (İngilizce: Fast Hartley Transform) gibi birkaç varyasyonu da kullanılmaktadır. Özellikle son yıllarda DCT, sağladığı yüksek sıkıştırma oranı sayesinde gerçek zamanlı uygulamalarda tercih edilmektedir[5].
\{x_k\}_{k=1}^N şeklinde bir dizi verilmiş olsun. Bu dizinin Ayrık Fourier dönüşümü
c_k = \sum_{j=1}^N x_k w_N^{(j-1)(k-1)}\quad, k=1,\ldots,N
ve Ters Fourier dönüşümü ise
X_j=\frac{1}{N}\sum_{k=1}^N c_k w_N^{-(j-1)(k-1)}\quad, j=1,\ldots,N
şeklindedir. Yukarıdaki eşitliklerde görünen w_N aşağıdaki gibidir.
{\displaystyle w_N=e^{-2\pi i/N}}
Ayrık Fourier dönüşümü ile elde edilen c_k katsayıları karmaşık sayılardır. Ancak c_1 öğesi gerçeldir. Geri kalan karmaşık sayılar aşağıdaki bağıntıya göre birbirlerinin eşlenikleridir.
c_2=\bar c_{N}
c_3=\bar c_{N-1}
\vdots
Ayrık zamanlı Fourier dönüşümü
Ayrık zamanlı Fourier dönüşümü (DTFT), ayrık zamanlı sinyal işleme algoritma ve sistemlerinin analizi, tasarımı, gerçekleştirilmesi ile doğrusal filtreleme, korelasyon analizi ve spektrum analizi gibi sinyal işleme uygulamalarında önemli bir rol oynar. DTFTnin bu öneme sahip olmasının ardındaki temel neden DTFTyi hesaplamakta kullanılan verimli algoritmaların varlığıdır[1][2].
DTFT, Fourier dönüşümünün eşit aralıklı frekanslardaki örneklerine özdeştir. Sonuç olarak N-noktalı bir DTFTnin hesaplanması Fourier dönüşümünün N örneğinin, N eşit aralıklı frekanslarla (w_k=2*pi*kn), z-düzlemindeki birim çember üzerinde N nokta ile hesaplanmasına karşılık gelir. Burada temel amaç N-noktalı DTFTnin hesaplanması için verimli algoritmaların kullanılmasıdır. Bu algoritmalar ortak olarak hızlı Fourier dönüşümü (FFT) algoritmaları adını alır. En yüksek verimin elde edilebilmesi için FFT algoritmaları DTFTnin N değerlerinin hepsini hesaplamalıdır.
Bir algoritmanın ya da gerçeklemenin karmaşıklığını ve verimini ölçmenin birçok yolu vardır. Bunun sonucundaki final değerlendirme hem mevcut teknolojiye hem de uygulamaya bağlıdır. Hesaplama karmaşıklığını ölçmek için aritmetik çarpma ve toplamaların sayısı kullanılacaktır[1]. Algoritmalar, genel amaçlı dijital bilgisayarlarda ya da özel amaçlı mikroişlemcilerde gerçekleştirildiklerinde hesaplama hızı, çarpma ve toplamaların sayısıyla doğrudan ilişkilidir.
Hızlı Fourier Dönüşümü (İngilizce: FFT, Fast Fourier Transform), bir zaman domeni sinyalini eşdeğer frekans domeni sinyaline dönüştürmekte kullanılan DTFT (İngilizce: Discrete Fourier Transform - Ayrık Fourier Dönüşümü) tabanlı verimli bir algoritmadır. Bu bölümde çeşitli gerçek zamanlı FFT örnekleri gerçekleştirilecektir.
Hızlı Fourier Dönüşümü algoritması, Nkompleks noktalı bir data serisinin sonlu Fourier dönüşümünü yaklaşık Nlog2N işlemle hesaplayan bir metottur[3]. Algoritmanın gerçekten de büyüleyici bir tarihi vardır. Bu algoritma, 1965de James Cooley ve John Tukey tarafından açıklandığında[4], Fourier analizinin 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şi tarafından büyük ilgi topladı. O yıllarda N^2 işlemli metotları kullanan bilgisayarlar yüzlerce saatlik bir işlem süresine ihtiyaç duymaktaydı. Cooley ve Tukeyin makalesinin etkisiyle Rudnick, 1942de Danielson ve Lanczosun önerdiği bir metodu geliştirerek Nlog2N sayıda işlem yapan kendi bilgisayar programını tanımladı.
Cooley ve Tukeyin hızlı Fourier dönüşümü algoritması N kompozit (yani iki ya da daha fazla sayının çarpımı gibi) veya 2nin bir kuvveti olmadığında bile uygulanabilir olmasından dolayı genel bir algoritmadır. Eskiden saatlerce süren hesaplamalar Cooley ve Tukeyin algoritması ile dakikalar içerisinde gerçekleştirilebilir bir hale gelmiştir[4].
Trigonometrik fonksiyonların hem simetri hem de periyodiklik özelliğini kullanan hesaplama algoritmaları, yüksek hızlı dijital bilgisayarlar çağının çok daha öncesinde bilinmekteydi. O zamanlarda manüel hesaplamayı 2 kat dahi azaltacak yeni bir düzen bile literatürde yerini almaktaydı. Runge 1905de ve daha önce bahsedildiği üzere Danielson ve Lanczos da 1942de N^2 işlem yerine Nlog2N ile orantılı sayıda işlem yapan algoritmaları tanımlamışlardı. Fakat ta ki 1965de Cooley ve Tukey ayrık Fourier dönüşümünü hesaplamak için algoritmalarını yayınlamadan önce oldukça azaltılmış hesap yükü elde etme olasılığı görmezlikten gelinmişti. Bu makale, ayrık Fourier dönüşümünün sinyal işlemedeki uygulamalarını ve oldukça verimli hesaplama algoritmalarının bulunmasını tetikledi.
DTFT, zaman alanı dizisini eş değer frekans alanı dizisine çevirir. Ters DTFT ise geri işlemi gerçekleştirerek frekans alanı dizisinden eş değer zaman alanı sinyali geri elde eder. FFT, DTFTye göre daha az hesap yapmasına karşın oldukça verimli bir algoritma tekniğidir. FFT DSPde frekans spektrum analizi için en yaygın olarak kullanılan operasyondur. FFT algoritmaları, uzunluğundaki bir dizinin ayrık Fourier dönüşümü hesabını daha küçük DTFTlere ayrıştırma temel prensibine dayanmaktadır[1]. Bu temel prensip çeşitli farklı algoritmalarla gerçekleştirildiğinde hesaplama hızında kayda değer bir artış elde edilmektedir. Bir FFTyi hesaplamak için iki farklı prosedür uygulanmaktadır. Bunlar; x[n] zaman dizisinin daha küçük alt dizilere bölündüğü zamanda desimasyon (örnek seyreltme) ve ayrık Fourier dönüşümü dizisi katsayıları X[k]nın daha küçük alt dizilere ayrıştırıldığı frekansta desimasyon algoritmalarıdır. FFTin Ayrık Kosinüs dönüşümü (İngilizce: DCT, Discrete Cosine Transform), Goertzel algoritması ve Hızlı Hartley dönüşümü (İngilizce: Fast Hartley Transform) gibi birkaç varyasyonu da kullanılmaktadır. Özellikle son yıllarda DCT, sağladığı yüksek sıkıştırma oranı sayesinde gerçek zamanlı uygulamalarda tercih edilmektedir[5].
