Hızlı Fourier dönüşümü

Hızlı Fourier dönüşümü (Fast Fourier Transform–FFT) bir dizinin ayrık Fourier dönüşümünü (DFT) ya da ters ayrık dönüşümünü hesaplayan bir algoritmadır. Fourier analizinde bir sinyal bulunduğu uzaydaki (genellikle zaman uzayı) gösteriminden frekans uzayıki gösterimine ya da tersine dönüştürülür. DFT'de ise ayrık veri dizileri farklı frekans öğelerine ayrılır.^[1] Bu operasyon her ne kadar birçok alanda kullanışlı olsa da, doğrudan formüllerle hesabı hızlı ve pratik değildir; bu nedenle DFT hesabı için FFT algoritmaları kullanılmaktadır.

FFT algoritmaları DFT dönüşüm matrisinin seyrek matrislere ayrıştırılması ile çalışır.^[2] Bu şekilde DFT'nin karmaşıklığı $O\left(N^{2}\right)$ 'den $O(N\log N)$ 'e düşürülebilmektedir; burada N veri boyutunu ifade eder. Veri boyutunun binler veya milyonlar mertebesinde olması durumunda FFT standart DFT'den çok daha hızlı çalışır. Yuvarlama hatası olması durumunda ise birçok FFT algoritmasının daha doğru sonuç verdiği belirtilebilir. Karmaşık sayı, grup teorisi ve sayılar teorisi temelli birçok farklı FFT algoritması bulunmaktadır. En yaygın FFT yöntemi Cooley–Tukey FFT algoritmasıdır.

FFT algoritmaları mühendislik, bilim, matematik ve müzikte sıklıkla kullanılmaktadır. Her ne kadar temelleri 1965'te popülerlik kazanmış olsa da, bazı temel yöntemlerinin geliştirilmesi 1805 yılına kadar dayanmaktadır.^[1] Matematikçi Gilbert Strang, 1994 yılında FFT'yi "insan hayatındaki en önemli sayısal algoritmalardan biri" olarak tanımlamıştır.^[3]^[4] IEEE'nin Computing in Science & Engineering dergisi ise FFT'ye "20. Yüzyılın En Önemli 10 Algoritması" listesinde yer vermiştir.^[5]

Farklı programlama dillerinde FFT

Dil	Komut/Fonksiyon	Önkoşullar
R	stats::fft(x)	Yok
Octave/MATLAB	fft(x)	None
Python	fft.fft(x)	numpy
Mathematica	Fourier[x]	None
Julia	fft(A [,dims])	FFTW

Ayrıca bakınız

Kaynakça

^ ^a ^b Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1984). "Gauss and the history of the fast Fourier transform" (PDF). IEEE ASSP Magazine. 1 (4): 14-21. CiteSeerX 10.1.1.309.181 $2. doi:10.1109/MASSP.1984.1162257. 7 Mart 2022 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 8 Temmuz 2020.
^ Van Loan, Charles (1992). Computational Frameworks for the Fast Fourier Transform. SIAM.
^ Strang, Gilbert (May–Haziran 1994). "Wavelets". American Scientist. 82 (3): 250-255. JSTOR 29775194.
^ Kent, Ray D.; Read, Charles (2002). Acoustic Analysis of Speech. ISBN 0-7693-0112-6.
^ Dongarra, Jack; Sullivan, Francis (Ocak 2000). "Guest Editors Introduction to the top 10 algorithms". Computing in Science & Engineering. 2 (1): 22-23. Bibcode:2000CSE.....2a..22D. doi:10.1109/MCISE.2000.814652. ISSN 1521-9615.

Dış bağlantılar

MIT FFT ders notları 12 Kasım 2020 tarihinde Wayback Machine sitesinde arşivlendi.
Fast Fourier Transforms 26 Ağustos 2021 tarihinde Wayback Machine sitesinde arşivlendi., bir online kitap (ed. Charles Sidney Burrus, 2008).
C++ dilinde Cooley–Tukey FFT algoritması 8 Temmuz 2020 tarihinde Wayback Machine sitesinde arşivlendi.
İnteraktif FFT 12 Mayıs 2020^{[Tarih uyuşmuyor]} tarihinde Wayback Machine sitesinde arşivlendi.

İlgili Araştırma Makaleleri

Fourier dönüşümü, fizik, mühendislik ve matematikte, bir fonksiyonu, içerdiği frekansların belirtildiği bir biçime dönüştüren bir integral dönüşümüdür. Dönüşümün çıktısı, frekansa bağlı karmaşık değerli bir fonksiyondur. "Fourier dönüşümü" terimi, hem bu karmaşık değerli fonksiyon için hem de buna karşılık gelen matematiksel operasyon için kullanılmaktadır. Bu ayrımın netleştirilmesi gerektiğinde, Fourier dönüşümü bazen orijinal fonksiyonun frekans uzayında temsili olarak adlandırılır. Fourier dönüşümü, bir müzik akorunun sesini, onu oluşturan tonlara ayrıştırmaya benzer.

Ayrık Fourier Dönüşümü, Fourier analizinde kullanılan özel bir Fourier dönüşümüdür.

<span class="mw-page-title-main">Titreşim</span>

Titreşim bir denge noktası etrafındaki mekanik salınımdır. Bu salınımlar bir sarkaçın hareketi gibi periyodik olabileceği gibi çakıllı bir yolda tekerleğin hareketi gibi rastgele de olabilir.

<span class="mw-page-title-main">Hızlı sıralama</span>

Hızlı sıralama, günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, $\text{[math]}$ karmaşıklığıyla, en kötü durumda ise $\text{[math]}$ karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.

Matematikte, Fourier serileri bir periyodik fonksiyonu basit dalgalı fonksiyonların toplamına çevirir.

Dizi eşleme algoritmaları olarak da adlandırılan dizi arama algoritmaları, bir ya da birkaç dizinin (örüntü) daha büyük bir dizi ya da metin içindeki yerinin bulunmasını konu edinen önemli bir dizi algoritması sınıfıdır.

Matematikte, harmonik analiz alanında, kesirli Fourier dönüşümü (FRFT) Fourier dönüşümüne genelleştirilecek doğrusal dönüşümlerin bir ailesidir. Bu nedenle, -zaman ve frekans- arasında bir ara etki alanı için bir işlev dönüştürebilir - Fourier dönüşünde n'in bir tam sayı olması gerekmez n'inci kuvvet dönüşümü olarak da düşünülebilir. Onun uygulamaları faz geri alma ve örüntü tanıma için,filtre tasarımı ve sinyal analizi arasında değişir.

Sayı teorisinde, asal çarpanlara ayırma bir bileşik sayının, çarpıldıklarında yine aynı sayıyı verecek şekilde, bir ve kendisi dışındaki bölenlerine ayrılmasıdır.

Matematikte, özellikle soyut cebir ve uygulamalarında, ayrık logaritma, genel logaritmanın grup kuramındaki karşılığıdır. Genel olarak bakıldığında, log_a(b) ifadesi, a^x = b ifadesinin gerçel sayılar kümesi içindeki çözümlerine karşılık gelir. Benzer olarak, g ve h sonlu devirli grup G'nin elemanları olduğunda, g^x = h ifadesinin çözümü olan x sonuçlarına h'nin g tabanındaki ayrık logaritması denir.

Bu matematikte dönüşümlerin bir listesidir.

John Wilder Tukey ForMemRS 20. yüzyılın en ünlü Amerikalı istatistikçilerinden biridir. FFT algoritmasını ve kutu grafiğini geliştirmiştir. Ayrıca kendi adını taşıyan çoklu karşılaştırma testi Tukey Testi'ni ve Tukey'in Lambda dağılımını geliştirmiştir.

Güç spektrumunun $\text{[math]}$ zaman serileri $\text{[math]}$ bu sinyale sebep olan frekans bileşenlerinin dağılımını tanımlar. Fourier analizine göre herhangi bir fiziksel sinyal, farklı frekanslara ayrışabilir ya da devamlı bir sıra boyunca frekans spektrumlarına dönüşebilir. Belirli bir sinyal veya herhangi bir sinyal çeşitlerinin istatistiksel ortalaması içerdiği frekans bileşenlerine göre analiz edilir.Buna da spektrum denir.

Zamanda sonlu farklar yöntemi, kısaca FDTD ya da Yee yöntemi, hesaplamalı elektromanyetizmada kullanılan bir sonlu farklar tekniğidir. Zaman düzleminde çalışan bir yöntem olduğundan ötürü, elektromanyetik spektrumun mikrodalga veya görünür ışık gibi farklı bölgelerinde anten veya fotonik aygıt tasarımı gibi çeşitli problemlerin çözümünde kullanılır. Aynı zamanda bu özellik, simülasyonu yapılan sistemin geniş bir frekans yelpazesine tepkisinin gözlenebilmesini sağlamaktadır. Matris tersinmesi gerektirmeyen bu FDTD, en yaygın elektromanyetik simülasyon yöntemlerinden biri olarak kabul edilir.

Video izleme/ Nesne Takip, bir kamera kullanarak zaman içinde hareket eden bir veya birden çok nesneyi bulma işlemidir. İnsan-bilgisayar etkileşimi, güvenlik ve gözetim, video iletişimi ve sıkıştırma, artırılmış gerçeklik, trafik kontrolü, tıbbi görüntüleme ve video düzenleme gibi çeşitli kullanımları vardır. Video izleme, videonun içerdiği veri miktarı nedeniyle zaman alıcı ve yavaş çalışabilen bir süreç olabilmektedir. Tek başına kullanımda bile zor bir problem olan bu metot, nesne tanıma teknikleriyle birlikte de kullanılarak daha işlevsel hale getirilmektedir.

Veri analizinde, anomali tespiti, verilerin çoğunluğundan önemli ölçüde farklılaşarak şüphe uyandıran nadir öğelerin, olayların veya gözlemlerin tanımlanmasıdır. Tipik olarak anormal öğeler, banka dolandırıcılığı, yapısal bir kusur, tıbbi sorunlar veya bir metindeki hatalar gibi bir tür soruna dönüşecektir. Anormallikler ayrıca aykırı değerler, yenilikler, gürültü, sapmalar ve istisnalar olarak da adlandırılmaktadır.

Otomatik hedef tanıma, bir algoritmanın veya cihazın, sensörlerden elde edilen verilere dayanarak hedefleri veya diğer nesneleri tanıma yeteneğidir.

Otomatik kümeleme algoritmaları, veri kümeleri hakkında önceden bilgi sahibi olmadan kümeleme yapabilen algoritmalardır. Diğer küme analizi tekniklerinin aksine, otomatik kümeleme algoritmaları, gürültü ve aykırı noktaların varlığında bile en iyi küme sayısını belirleyebilir.

Matematik dünyasında, Parseval teoremi Fourier dönüşümünün bir üniter ifade olduğu sonucunu bize açıklar. Basit bir şekilde açıklarsak, bir fonksiyonun karesinin toplamı ile Fourier dönüşümün fonksiyonunun karesinin toplamının birbirine eşit olduğunu söyler. Teorem, Marc-Antoine Parseval'in 1799 yılındaki seriler hakkındaki bir teoreminin Fourier serilerine uygulanması sonucu ortaya çıkmıştır. Lord Rayleigh ile John William Strutt'tan sonra Rayleigh Enerji Teoremi veya Rayleigh Özdeşliği olarak da bilinir.

Matematikte, trigonometrik fonksiyon tabloları bir dizi alanda yararlıdır. Küçük hesap makinelerinin varlığından önce, trigonometrik tablolar navigasyon, bilim ve mühendislik için gerekliydi. Matematiksel tabloların hesaplanması önemli bir çalışma alanıydı ve bu da ilk mekanik hesaplama cihazlarının geliştirilmesine yol açtı.

Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.