Szybka transformacja Fouriera: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m Przeniesienie artykulu do "Szybka transformacja Fouriera". Uzasadnienie w dyskusji tegoż. |
m Przywrócono przedostatnią wersję, jej autor to Tdc6502. Autor wycofanej edycji to Maciek pazur. |
||
Linia 1:
'''Szybka transformata Fouriera''' ([[Język angielski|ang.]] '''FFT''' od '''F'''ast '''F'''ourier '''T'''ransformation) to [[algorytm]] liczenia [[dyskretna transformata Fouriera|dyskretnej transformaty Fouriera]] oraz transformaty do niej odwrotnej.
Niech ''x''<sub>0</sub>, ...., ''x''<sub>''N''-1</sub> będą liczbami zespolonymi, wtedy DFT jest określona wzorem
:<math> X_k = \sum_{n=0}^{N-1} x_n e^{-{2\pi i \over N} nk }
\qquad
k = 0,\dots,N-1. </math>
Obliczanie tych sum za pomocą powyższego wzoru zajęłoby O(''N''<sup>2</sup>) operacji.
Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformatę Fouriera bazują na metodzie 'dziel i zwyciężaj' rekurencyjnie dzieląc transformatę wielkości ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> na transformaty wielkości ''N''<sub>1</sub> i ''N''<sub>2</sub> z wykorzystaniem O(''N'') operacji mnożenia.
Najpopularniejszą wersją FFT jest ''FFT o podstawie 2''. Jest to bardzo efektywna operacja, jednak wektor próbek wejściowych ([[Próbkowanie|spróbkowany]] [[sygnał]]) musi mieć długość <math>N=2^k</math>, gdzie <math>k</math> to pewna liczba naturalna. Wynik otrzymuje się na drodze schematycznych przekształceń, opartych o tak zwane ''struktury motylkowe''.
[[Złożoność obliczeniowa]] '''Szybkiej transformaty Fouriera''' wynosi <math>O(N \log_2 N)</math>, zamiast <math>O(N^2)</math> algorytmu wynikającego wprost ze wzoru określającego DFT.
Dzięki istnieniu takiego algorytmu praktyczne możliwe stało się [[cyfrowe przetwarzanie sygnałów|cyfrowe przetwarzanie sygnałów (DSP)]], a także zastosowanie [[Dyskretna transformata kosinusowa|dyskretnych transformat cosinusowych (DCT)]] ([[JPEG]], [[MP3]] itd.) do [[kompresja|kompresji]].
== Zobacz też ==
* [[FFTW]]
[[Kategoria:cyfrowe przetwarzanie sygnałów]]
[[Kategoria:Multimedia]]
[[Kategoria:Algorytmy numeryczne]]
[[ar:تحويل فوريي السريع]]
[[ca:Transformada Ràpida de Fourier]]
[[da:Fast Fourier Transform]]
[[de:Schnelle Fourier-Transformation]]
[[en:Fast Fourier transform]]
[[es:Transformada rápida de Fourier]]
[[fa:تبدیل سریع فوریه]]
[[fr:Transformée de Fourier rapide]]
[[ko:고속 푸리에 변환]]
[[hi:त्वरित फुरिअर रूपान्तर]]
[[id:Transformasi Fourier cepat]]
[[it:Trasformata di Fourier veloce]]
[[nl:Fast Fourier Transform]]
[[ja:高速フーリエ変換]]
[[pt:Transformada rápida de Fourier]]
[[ru:Быстрое преобразование Фурье]]
[[sr:Брза Фуријеова трансформација]]
[[sv:Snabb fouriertransform]]
[[zh:快速傅里叶变换]]
| |||