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
transformata nie tranformacja
Anulowanie wersji nr 12736935 autora 80.50.55.106 zob. Transformata Laplace'a
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 13:
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 kosinusowych (DCT)]] ([[JPEG]], [[MP3]] itd.) do [[kompresja|kompresji]].
 
Źródło: „https://pl.wikipedia.org/wiki/Szybka_transformacja_Fouriera”