Wikipedia

Szybka transformacja Fouriera: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m Szybka transformata Fouriera przeniesiono do Szybka transformacja Fouriera: Bardziej ścisła, a też używana nazwa (patrz dyskusja artykułu)
m wymiana tytułu
Linia 1:
'''Szybka transformatatransformacja 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
Linia 9:
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ętransformację 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 transformatytransformacji 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]].
 
Źródło: „https://pl.wikipedia.org/wiki/Szybka_transformacja_Fouriera”