Szybka Transformacja Fouriera (FFT) Vs. Dyskretna Transformacja Fouriera (DFT)

Technologia i nauka idą w parze. I nie ma lepszego przykładu na to niż cyfrowe przetwarzanie sygnałów (DSP). Cyfrowe przetwarzanie sygnałów to proces optymalizacji dokładności i wydajności komunikacji cyfrowej. Wszystko jest danymi – czy to obrazy z sond kosmicznych, czy drgania sejsmiczne i wszystko pomiędzy. Przetwarzanie tych danych na format czytelny dla człowieka przy użyciu komputerów to właśnie cyfrowe przetwarzanie sygnałów. Jest to jedna z najpotężniejszych technologii, która łączy w sobie zarówno teorię matematyczną, jak i fizyczną implementację. Badanie DSP rozpoczęło się jako kurs na poziomie absolwenta w inżynierii elektrycznej, ale z czasem stało się potencjalnym gamechangerem w dziedzinie nauki i inżynierii. Wystarczy powiedzieć, że bez DSP inżynierowie i naukowcy mogliby przestać istnieć.

Transformata Fouriera jest sposobem odwzorowania sygnału, w domenie czasowej lub przestrzennej w jego widmo w domenie częstotliwości. Domeny czasu i częstotliwości są tylko alternatywnymi sposobami reprezentacji sygnałów, a transformata Fouriera jest matematycznym związkiem pomiędzy tymi dwoma reprezentacjami. Zmiana sygnału w jednej domenie wpłynie również na sygnał w drugiej domenie, ale niekoniecznie w ten sam sposób. Dyskretna transformata Fouriera (DFT) jest transformatą podobną do transformaty Fouriera stosowaną w przypadku sygnałów zdigitalizowanych. Jak sama nazwa wskazuje, jest to dyskretna wersja FT, która postrzega zarówno domenę czasu, jak i domenę częstotliwości jako okresowe. Szybka transformata Fouriera (FFT) jest tylko algorytmem do szybkiego i wydajnego obliczania DFT.

Dyskretna transformacja Fouriera (DFT)

Dyskretna transformata Fouriera (DFT) jest jednym z najważniejszych narzędzi w cyfrowym przetwarzaniu sygnałów, które oblicza widmo sygnału o skończonym czasie trwania. Bardzo powszechne jest kodowanie informacji w sinusoidach tworzących sygnał. Jednak w niektórych zastosowaniach kształt przebiegu w dziedzinie czasu nie ma zastosowania dla sygnałów w takim przypadku zawartość częstotliwościowa sygnału staje się bardzo użyteczna w inny sposób niż jako sygnał cyfrowy. Istotna jest reprezentacja sygnału cyfrowego w kategoriach jego składowej częstotliwościowej 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 transformacja Fouriera (FFT)

Szybka transformata Fouriera (FFT) jest implementacją DFT, która daje prawie takie same wyniki jak DFT, ale jest niesamowicie wydajniejsza i znacznie szybsza, co często znacznie skraca czas obliczeń. Jest to po prostu algorytm obliczeniowy używany do szybkiego i wydajnego obliczania DFT. Różne techniki szybkiego obliczania DFT znane wspólnie jako szybka transformata Fouriera, czyli FFT. Gauss jako pierwszy zaproponował technikę obliczania współczynników w trygonometrii orbity asteroidy w 1805 roku. Jednak dopiero w 1965 r. przełomowa praca Cooley’a i Tukey’a przyciągnęła uwagę społeczności naukowej i inżynierskiej, co dało również podwaliny pod dyscyplinę cyfrowego przetwarzania sygnałów.

Różnica między FFT a DFT

Znaczenie FFT i DFT

Dyskretna Transformacja Fouriera, lub po prostu określana jako DFT, jest algorytmem, który przekształca sygnały w dziedzinie czasu do komponentów w dziedzinie częstotliwości. DFT, jak sama nazwa wskazuje, jest prawdziwie dyskretna; dyskretne zestawy danych w dziedzinie czasu są przekształcane w dyskretną reprezentację częstotliwości. W prostych słowach, ustanawia związek między reprezentacją domeny czasu i reprezentacją domeny częstotliwości. Szybka transformacja Fouriera, lub FFT, jest algorytmem obliczeniowym, który zmniejsza czas obliczeniowy i złożoność dużych transformacji. FFT to po prostu algorytm służący do szybkiego obliczania DFT.

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 dziel i zwyciężaj do maszynowego obliczania złożonych szeregów Fouriera. Rozbija on DFT na mniejsze DFT. Inne algorytmy FFT to algorytm Radera, algorytm transformaty Fouriera Winograda, algorytm transformaty Z Chirpa itp. Algorytmy DFT mogą być programowane na komputerach cyfrowych ogólnego przeznaczenia lub implementowane bezpośrednio przez specjalny sprzęt. Algorytm FFT służy do obliczania DFT ciągu lub jego odwrotności. DFT można wykonać jako O(N2) złożoności czasowej, natomiast FFT zmniejsza złożoność czasową rzędu O (NlogN).

Zastosowania FFT i DFT

DFT może być używane w wielu systemach przetwarzania cyfrowego w różnych zastosowaniach, takich jak obliczanie widma częstotliwościowego sygnału, rozwiązywanie zastosowań różniczkowania cząstkowego, wykrywanie celów z echa radaru, analiza korelacji, obliczanie mnożenia wielomianowego, analiza widmowa i inne. FFT była szeroko stosowana do pomiarów akustycznych w kościołach i salach koncertowych. Inne zastosowania FFT obejmują analizę spektralną w analogowych pomiarach wideo, mnożenie dużych liczb całkowitych i wielomianów, algorytmy filtrowania, obliczanie rozkładów izotopowych, obliczanie współczynników serii Fouriera, obliczanie konwolucji, generowanie szumu o niskiej częstotliwości, projektowanie kinoform, wykonywanie gęstych matryc strukturalnych, przetwarzanie obrazów i inne.

Podsumowanie FFT Vs. DFT

W dużym skrócie, Dyskretna Transformacja Fouriera odgrywa kluczową rolę w fizyce, ponieważ może być użyta jako narzędzie matematyczne do opisania relacji pomiędzy reprezentacją w dziedzinie czasu i w dziedzinie częstotliwości sygnałów dyskretnych. Jest to prosty, ale dość czasochłonny algorytm. Jednak, aby zmniejszyć czas obliczeniowy i złożoność dużych transformat, 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. W skrócie, FFT może zrobić wszystko, co robi DFT, ale bardziej wydajnie i znacznie szybciej niż DFT. Jest to wydajny sposób obliczania DFT.