Różnica między FFT i DFT

Szybka transformata Fouriera (FFT) vs. Dyskretna transformata Fouriera (DFT)

Technologia i nauka idą w parze. I nie ma lepszego przykładu tego niż cyfrowe przetwarzanie sygnału (DSP). Cyfrowe przetwarzanie sygnałów to proces optymalizacji dokładności i wydajności komunikacji cyfrowej. Wszystko to dane - czy to obrazy z sond kosmicznych, wibracje sejsmiczne i wszystko pomiędzy. Konwersja tych danych do formatu czytelnego dla człowieka za pomocą komputerów jest cyfrowym przetwarzaniem sygnału. Jest to jedna z najpotężniejszych technologii, która łączy zarówno teorię matematyczną, jak i fizyczne wdrożenie. Badanie DSP rozpoczęło się jako kurs dla absolwentów elektrotechniki, ale z biegiem czasu stało się potencjalnym zmieniaczem gier w dziedzinie nauki i inżynierii. Wystarczy powiedzieć, że bez DSP inżynierowie i naukowcy mogą przestać istnieć.

Transformacja Fouriera jest sposobem mapowania sygnału w dziedzinie czasu lub przestrzeni do jego widma w dziedzinie częstotliwości. Domeny czasu i częstotliwości są po prostu alternatywnymi sposobami reprezentacji sygnałów, a transformacja Fouriera jest matematyczną zależnością między dwiema reprezentacjami. Zmiana sygnału w jednej domenie wpływałaby również na sygnał w drugiej domenie, ale niekoniecznie w ten sam sposób. Dyskretna transformata Fouriera (DFT) to transformacja podobna do transformaty Fouriera używana z sygnałami cyfrowymi. Jak sama nazwa wskazuje, jest to dyskretna wersja FT, która postrzega zarówno dziedzinę czasu, jak i częstotliwość jako okresowe. Szybka transformata Fouriera (FFT) to tylko algorytm do szybkiego i wydajnego obliczania DFT.

Dyskretna transformata Fouriera (DFT)

Dyskretna transformata Fouriera (DFT) jest jednym z najważniejszych narzędzi w cyfrowym przetwarzaniu sygnału, które oblicza widmo sygnału o skończonym czasie trwania. Bardzo często koduje się informacje w sinusoidach, które tworzą sygnał. Jednak w niektórych aplikacjach kształt fali w dziedzinie czasu nie ma zastosowania do sygnałów, w którym to przypadku zawartość częstotliwości sygnału staje się bardzo przydatna na inne sposoby niż jako sygnały cyfrowe. Ważna jest reprezentacja sygnału cyfrowego pod względem jego składowej częstotliwości w dziedzinie częstotliwości. Algorytm, który przekształca sygnały w dziedzinie czasu na składowe w dziedzinie częstotliwości, jest znany jako dyskretna transformata Fouriera lub DFT.

Szybka transformata Fouriera (FFT)

Szybka transformata Fouriera (FFT) to implementacja DFT, która daje prawie takie same wyniki jak DFT, ale jest niewiarygodnie bardziej wydajna i znacznie szybsza, co często znacznie skraca czas obliczeń. Jest to tylko algorytm obliczeniowy używany do szybkiego i wydajnego obliczania DFT. Różne techniki szybkiego obliczania DFT, znane łącznie jako szybka transformata Fouriera lub FFT. Gauss jako pierwszy zaproponował technikę obliczania współczynników w trygonometrycznym orbicie asteroidy w 1805 r. Jednak dopiero w 1965 r. Praca naukowa Cooleya i Tukeya zwróciła uwagę społeczności naukowej i inżynieryjnej, która również zwróciła uwagę podstawa dyscypliny cyfrowego przetwarzania sygnałów.

Różnica między FFT i DFT

1. Znaczenie FFT i DFT

Dyskretna transformata Fouriera, lub po prostu nazywana DFT, jest algorytmem, który przekształca sygnały w dziedzinie czasu do składników w dziedzinie częstotliwości. DFT, jak sama nazwa wskazuje, jest naprawdę dyskretne; zestawy danych dyskretnych w dziedzinie czasu są przekształcane w dyskretną reprezentację częstotliwości. Mówiąc najprościej, ustanawia związek między reprezentacją w dziedzinie czasu a reprezentacją w dziedzinie częstotliwości. Szybka transformata Fouriera (FFT) to algorytm obliczeniowy, który zmniejsza czas obliczeń i złożoność dużych transformacji. FFT to tylko algorytm wykorzystywany do szybkiego obliczania DFT.

2. Algorytm FFT i DFT

Najczęściej stosowanym algorytmem FFT jest algorytm Cooleya-Tukeya, który został nazwany na cześć J. W. Cooleya i Johna Tukeya. Jest to algorytm dzielenia i zdobywania do obliczeń maszynowych złożonych szeregów Fouriera. Dzieli DFT na mniejsze DFT. Inne algorytmy FFT obejmują algorytm Radera, algorytm transformacji Winograda Fouriera, algorytm Chirp Z-transformacji itp. Algorytmy DFT można zaprogramować na komputerach cyfrowych ogólnego zastosowania lub bezpośrednio za pomocą specjalnego sprzętu. Algorytm FFT służy do obliczania DFT sekwencji lub jej odwrotności. DFT można wykonać jako O (N²⁾) w złożoności czasowej, podczas gdy FFT zmniejsza złożoność czasową w kolejności O (NlogN).

3. Zastosowania FFT i DFT

DFT może być stosowany w wielu systemach przetwarzania cyfrowego w różnych aplikacjach, takich jak obliczanie widma częstotliwości sygnału, rozwiązywanie częściowych aplikacji różnicowych, wykrywanie celów z echa radaru, analiza korelacji, obliczanie mnożenia wielomianowego, analiza spektralna i wiele innych. FFT jest szeroko stosowany do pomiarów akustycznych w kościołach i salach koncertowych. Inne zastosowania FFT obejmują analizę spektralną w analogowych pomiarach wideo, mnożenie dużej liczby całkowitej i wielomianu, algorytmy filtrowania, obliczanie rozkładów izotopowych, obliczanie współczynników szeregu Fouriera, obliczanie zwojów, generowanie szumu o niskiej częstotliwości, projektowanie form kinematycznych, wykonywanie gęsto ustrukturyzowanych matryc, przetwarzanie obrazów i więcej.

FFT vs. DFT: Tabela porównawcza

Podsumowanie vs. FFT DFT

Mówiąc w skrócie, dyskretna transformata Fouriera odgrywa kluczową rolę w fizyce, ponieważ może być używana jako narzędzie matematyczne do opisu związku między reprezentacją w dziedzinie czasu i reprezentacji w dziedzinie częstotliwości sygnałów dyskretnych. Jest to prosty, ale dość czasochłonny algorytm. Jednak w celu skrócenia czasu obliczeń i złożoności dużych transformacji można zastosować bardziej złożony, ale mniej czasochłonny algorytm, taki jak szybka transformata Fouriera. FFT jest implementacją DFT używaną do szybkiego obliczania DFT. Krótko mówiąc, FFT może robić wszystko, co robi DFT, ale bardziej wydajnie i znacznie szybciej niż DFT. Jest to skuteczny sposób obliczania DFT.