Szybka transformacja Fouriera

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Szybka transformacja Fouriera (ang. Fast Fourier Transform, FFT) – algorytm wyznaczania dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej.

Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Sygnał to abstrakcyjny model dowolnej mierzalnej wielkości zmieniającej się w czasie, generowanej przez zjawiska fizyczne lub systemy. Tak jak wszystkie zjawiska może być opisany za pomocą aparatu matematycznego, np. poprzez podanie pewnej funkcji zależnej od czasu. Mówimy, że sygnał niesie informację lub też umożliwia przepływ strumienia informacji.

Czasem, w odniesieniu do tej metody, używane jest też określenie szybka transformata Fouriera, które jednak nie jest prawidłowe, gdyż pojęcie transformacja oznacza przekształcenie, a transformata jest wynikiem tego przekształcenia.

Niech będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem:

Kompresja danych (ang. data compression) – polega na zmianie sposobu zapisu informacji tak, aby zmniejszyć redundancję i tym samym objętość zbioru. Innymi słowy chodzi o wyrażenie tego samego zestawu informacji, lecz za pomocą mniejszej liczby bitów.MP3 ((ang.) MPEG-1/MPEG-2 Audio Layer 3) – algorytm kompresji stratnej dźwięku, przetworzonego uprzednio na sygnał cyfrowy. Popularnie zwany formatem MP3 lub standardem MP3. Jest zdefiniowany przez IETF w dokumencie RFC 5219.

Obliczanie sum za pomocą powyższego wzoru wymaga wykonania operacji (zob. asymptotyczne tempo wzrostu).

Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.MathWorld – encyklopedia matematyczna online, sponsorowana przez Wolfram Research, twórcę i producenta programu Mathematica; współsponsorem jest National Science Foundation (National Science Digital Library).

Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości na transformaty wielkości i z wykorzystaniem operacji mnożenia.

Próbkowanie (dyskretyzacja, kwantowanie w czasie) - proces tworzenia sygnału dyskretnego, reprezentującego sygnał ciągły za pomocą ciągu wartości nazywanych próbkami. Zwykle jest jednym z etapów przetwarzania sygnału analogowego na cyfrowy.Wydawnictwa Naukowo-Techniczne (WNT) – polskie wydawnictwo założone w 1949 z siedzibą w Warszawie, do 1961 działało pod firmą Państwowe Wydawnictwa Techniczne.

Najpopularniejszą wersją algorytmu FFT jest FFT o podstawie 2. Jest on bardzo efektywny pod względem czasu realizacji, jednak wektor próbek wejściowych (spróbkowany sygnał) musi mieć długość gdzie to pewna liczba naturalna. Wynik otrzymuje się na drodze schematycznych przekształceń, opartych o tak zwane struktury motylkowe.

Dyskretna transformata Fouriera (DFT z ang. Discrete Fourier Transform) jest transformatą Fouriera wyznaczoną dla sygnału próbkowanego, a więc dyskretnego.Encyklopedia Britannica (ang. Encyclopædia Britannica) – najstarsza wydawana do chwili obecnej i najbardziej prestiżowa encyklopedia angielskojęzyczna. Artykuły w niej zamieszczane uważane są powszechnie przez czytelników za obiektywne i wiarygodne.

Złożoność obliczeniowa szybkiej transformacji Fouriera wynosi w odróżnieniu od algorytmu wynikającego wprost ze wzoru określającego dyskretną transformatę Fouriera. Dzięki szybkiej transformacji Fouriera praktycznie możliwe stało się cyfrowe przetwarzanie sygnałów (DSP), a także zastosowanie dyskretnych transformat kosinusowych (DCT) do kompresji danych audio-wideo (JPEG, MP3, XviD itd.).

Kwantowa transformata Fouriera (ang. quantum Fourier transform, QFT) – kwantowa analogia dyskretnej transformaty Fouriera. Na dowolny n-kubitowy stan bazowy | j ⟩ {displaystyle |j angle } działa ona jak następuje:JPEG (wym. dżej-peg lub jot-peg) – metoda kompresji statycznych obrazów rastrowych, przeznaczony głównie do stratnego zapisu obrazów naturalnych (pejzaży, portretów itp.), charakteryzujących się płynnymi przejściami barw oraz brakiem lub małą ilością ostrych krawędzi i drobnych detali.

Zobacz też[ | edytuj kod]

  • FFTW
  • kwantowa transformata Fouriera
  • transformacja Fouriera


  • Podstrony: 1 [2] [3]




    Warto wiedzieć że... beta

    Algorytm Cooleya-Tukeya nazwany imieniem J.W. Cooleya i Johna Tukeya, jest najbardziej rozpowszechnionym algorytmem szybkiej transformacji Fouriera (FFT). Wyraża dyskretną transformację Fouriera (DFT) o dowolnej złożonej wielkości N = N 1 N 2 w członach mniejszych DFT wielkości N 1 i N 2, rekurencyjnie, w celu ograniczenia czasu obliczeń do O (N log N), szczególnie w przypadku N będącego liczbą wysoce złożoną (liczbą gładką). Ze względu na znaczenie algorytmu, poszczególne warianty i style implementacji są znane pod własnymi nazwami, jak opisano poniżej.
    Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
    Transformata – wynik przekształcenia operandu pod wpływem działania operatora. Innymi słowy, transformatą nazywa się wynik działania transformacji (zob. szybka transformacja Fouriera).
    Xvid (dawniej XviD) jest biblioteką kodeków video podążającą za standardem MPEG-4, a w szczególności MPEG-4 Part 2 Advanced Simple Profile (ASP). Używa takich funkcji ASP jak b-frames, globalnych i dzielnicowych pikseli kompensacji ruchu, maskowania lumi, kwantyzacji treliażowej, H.263, MPEG i niestandardowych kwantyzacji matryc.
    Dyskretna transformacja kosinusowa, (DCT – ang. discrete cosine transform, czyli dyskretna transformacja cosinusowa) – jedna z najpopularniejszych blokowych transformacji danych. Jest szczególnie popularna w stratnej kompresji danych.
    Kontrola autorytatywna – w terminologii bibliotekoznawczej określenie procedur zapewniających utrzymanie w sposób konsekwentny haseł (nazw, ujednoliconych tytułów, tytułów serii i haseł przedmiotowych) w katalogach bibliotecznych przez zastosowanie wykazu autorytatywnego zwanego kartoteką wzorcową.
    Cyfrowe przetwarzanie sygnałów, CPS (ang.) Digital Signal Processing, DSP – dziedzina nauki i techniki zajmująca się sygnałami cyfrowymi i metodami ich przetwarzania.

    Reklama