FFT i DFT
Szybka transformata Fouriera (FFT) vs. Dyskretna transformata Fouriera (DFT)
Technologia i nauka idą w parze. I nie ma lepszego przykładu niż cyfrowe przetwarzanie sygnału (DSP). Digital Signal Processing to proces optymalizacji dokładności i wydajności komunikacji cyfrowej. Wszystko to dane - czy to obrazy z sond kosmicznych, czy wibracje sejsmiczne i wszystko pomiędzy. Aby przekonwertować te dane do formatu czytelnego dla człowieka za pomocą komputerów, jest przetwarzanie cyfrowego sygnału. Jest to jedna z najpotężniejszych technologii, która łączy zarówno teorię matematyczną, jak i fizyczną implementację. Studia nad DSP rozpoczęły się jako studia podyplomowe w dziedzinie elektrotechniki, ale z biegiem czasu stały się potencjalnym gamechangeriem w dziedzinie nauki i inżynierii. Dość powiedzieć, bez DSP, inżynierowie i naukowcy mogą przestać istnieć.
Transformata Fouriera jest sposobem mapowania sygnału w dziedzinie czasu lub przestrzeni na jego widmo w dziedzinie częstotliwości. Domeny czasu i częstotliwości są po prostu alternatywnymi sposobami reprezentacji sygnałów, a transformata Fouriera jest matematyczną relacją między dwiema reprezentacjami. Zmiana sygnału w jednej domenie wpłynąłaby również na sygnał w innej domenie, ale niekoniecznie w ten sam sposób. Discrete Fourier Transform (DFT) to transformacja taka jak transformata Fouriera wykorzystywana do sygnałów cyfrowych. Jak sama nazwa wskazuje, jest to dyskretna wersja FT, która postrzega zarówno domenę czasu, jak i dziedzinę częstotliwości jako okresową. Szybka transformata Fouriera (FFT) to tylko algorytm szybkiego i wydajnego obliczania DFT.
Dyskretna transformata Fouriera (DFT)
Dyskretna transformata Fouriera (DFT) jest jednym z najważniejszych narzędzi cyfrowego przetwarzania sygnału, który oblicza widmo sygnału o skończonym czasie trwania. Bardzo powszechne jest kodowanie informacji w sinusoidach, które tworzą sygnał. Jednak w niektórych zastosowaniach kształt fali czasu w dziedzinie czasu nie jest stosowany do sygnałów, w którym to przypadku zawartość częstotliwości sygnału staje się bardzo użyteczna w inny sposób niż jako sygnały cyfrowe. Reprezentacja sygnału cyfrowego pod względem jego składowej częstotliwościowej w dziedzinie częstotliwości jest ważna. Algorytm, który przekształca sygnały w dziedzinie czasu na komponenty domeny częstotliwości, jest nazywany dyskretną transformatą Fouriera lub DFT.
Szybka transformata Fouriera (FFT)
Szybka transformata Fouriera (FFT) jest implementacją DFT, która daje prawie takie same wyniki jak DFT, ale jest niewiarygodnie wydajniejsza i znacznie szybsza, co często znacznie skraca czas obliczeń. Jest to tylko algorytm obliczeniowy stosowany do szybkiego i wydajnego obliczania DFT. Różne szybkie techniki obliczeń DFT znane są łącznie jako szybka transformata Fouriera lub FFT. Gauss był pierwszym, który zaproponował technikę obliczania współczynników w trygonometrycznej orbicie asteroidy w 1805 r. Jednak dopiero w 1965 r. Przełomowa praca Cooleya i Tukeya zwróciła uwagę społeczności naukowej i inżynieryjnej, która także podstawa dyscypliny cyfrowego przetwarzania sygnałów.
Różnica między FFT i DFT
Dyskretna transformata Fouriera, lub po prostu określana jako DFT, jest algorytmem, który przekształca sygnały w dziedzinie czasu na komponenty domeny częstotliwości. DFT, jak sama nazwa wskazuje, jest naprawdę dyskretne; dyskretne zbiory danych w domenie czasu są przekształcane na dyskretną reprezentację częstotliwości. W prostych słowach ustala związek między reprezentacją w dziedzinie czasu a reprezentacją w domenie częstotliwości. Szybka transformata Fouriera, czyli FFT, jest algorytmem obliczeniowym, który zmniejsza czas obliczeń i złożoność dużych transformacji. FFT to tylko algorytm używany do szybkiego obliczania DFT.
Najczęściej stosowanym algorytmem FFT jest algorytm Cooleya-Tukeya, nazwany tak od nazwiska J. W. Cooleya i Johna Tukeya. Jest to algorytm dziel i podbijaj do obliczania maszyny złożonej serii Fouriera. Przerywa on DFT na mniejsze DFT. Inne algorytmy FFT obejmują algorytm Radera, algorytm konwersji Winogradu Fouriera, algorytm konwersji Z Chirp 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 obliczenia DFT sekwencji lub jej odwrotności. DFT można wykonać jako O (N2) w złożoności czasowej, podczas gdy FFT zmniejsza złożoność czasu w porządku O (NlogN).
DFT może być używany w wielu cyfrowych systemach przetwarzania w różnych aplikacjach, takich jak obliczanie spektrum częstotliwości sygnału, rozwiązywanie częściowych aplikacji różnicowych, wykrywanie celów z echa radarowego, analiza korelacji, obliczanie mnożenia wielomianu, 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żych liczb całkowitych i wielomianowych, algorytmy filtrowania, obliczanie rozkładów izotopowych, obliczanie współczynników szeregu Fouriera, obliczanie zwojów, generowanie szumów o niskiej częstotliwości, projektowanie kinoformów, wykonywanie gęstych uporządkowanych macierzy, przetwarzanie obrazu i więcej.
FFT vs. DFT: Tabela porównawcza
Podsumowanie FFT vs. DFT
W skrócie, Discrete Fourier Transform odgrywa kluczową rolę w fizyce, ponieważ może być użyte jako matematyczne narzędzie do opisania zależności między domeną czasu a reprezentacją w domenie częstotliwości sygnałów dyskretnych. Jest to prosty, ale dość czasochłonny algorytm. Jednakże 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żywanego do szybkiego obliczania DFT. W skrócie, FFT może zrobić wszystko, co DFT, ale bardziej wydajnie i znacznie szybciej niż DFT. Jest to skuteczny sposób obliczania DFT.
