Różnica między FFT i DFT

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

Technologia i nauka idą w parze. I nie ma lepszego przykładu tego niż cyfrowe przetwarzanie sygnałów (DSP). Cyfrowe przetwarzanie sygnałów to proces optymalizacji dokładności i wydajności komunikacji cyfrowej. Wszystko jest danymi - niezależnie od tego, czy są to obrazy z kosmicznych sond kosmicznych, czy wibracje sejsmiczne i wszystko pomiędzy. Aby przekonwertować te dane na format czytelny ludzki za pomocą komputerów, to cyfrowe przetwarzanie sygnałów. Jest to jedna z najpotężniejszych technologii, która łączy zarówno teorię matematyczną, jak i fizyczną wdrożenie. Badanie DSP rozpoczęło się jako kurs na poziomie absolwentów w zakresie inżynierii elektrycznej, ale z czasem stał się potencjalnym grą 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 w jego widmo w dziedzinie częstotliwości. Domeny czasowe i częstotliwości są po prostu alternatywnymi sposobami reprezentowania sygnałów, a transformacja Fouriera to matematyczny związek między dwoma reprezentacjami. Zmiana sygnału w jednej domenie wpłynęłaby również na sygnał w drugiej domenie, ale niekoniecznie w ten sam sposób. Dyskretna transformacja Fouriera (DFT) to transformacja taka jak transformacja Fouriera używana z cyfrowymi sygnałami. Jak sama nazwa wskazuje, to dyskretna wersja FT postrzega zarówno domenę czasową, jak i domenę częstotliwości. Szybka transformacja Fouriera (FFT) to tylko algorytm do szybkiego i wydajnego obliczenia DFT.

Dyskretna transformacja Fouriera (DFT)

Dyskretna transformacja Fouriera (DFT) jest jednym z najważniejszych narzędzi w cyfrowym przetwarzaniu sygnału, które oblicza widmo sygnału skończonego. Bardzo często jest kodowanie informacji w sinusoidach, które tworzą sygnał. Jednak w niektórych zastosowaniach kształt przebiegu domeny czasowej nie jest zastosowaniem dla sygnałów, w którym to przypadku zawartość częstotliwości sygnału staje się bardzo przydatna w sposób inny niż sygnały cyfrowe. Reprezentacja sygnału cyfrowego pod względem jego składnika częstotliwości w dziedzinie częstotliwości jest ważna. Algorytm, który przekształca sygnały domeny czasowej w składniki domeny częstotliwości, jest znany jako dyskretna transformacja Fouriera lub DFT.

Szybka transformacja Fouriera (FFT)

Szybka transformacja Fouriera (FFT) to implementacja DFT, która daje prawie takie same wyniki jak DFT, ale jest niezwykle wydajniejszy i znacznie szybszy, co często znacznie skraca czas obliczeń. Jest to tylko algorytm obliczeniowy stosowany do szybkiego i wydajnego obliczania DFT. Różne szybkie techniki obliczania DFT znane zbiorowo jako szybka transformacja Fouriera lub FFT. Gauss jako pierwszy zaproponował technikę obliczania współczynników w trygonometrii orbity asteroidy w 1805 r. Jednak dopiero w 1965 r. Sieciowy artykuł Cooleya i Tukeya zwrócił uwagę społeczności naukowej i inżynierskiej, która również położyła podstawę dyscypliny cyfrowego przetwarzania sygnałów.

Różnica między FFT i DFT

1. Znaczenie FFT i DFT

Dyskretna transformacja Fouriera lub po prostu określana jako DFT, jest algorytmem, który przekształca sygnały domeny czasowej w składniki domeny częstotliwości. DFT, jak sama nazwa wskazuje, jest naprawdę dyskretny; Dyskretne zestawy danych w dziedzinie czasu są przekształcane w dyskretną reprezentację częstotliwości. Mówiąc prosto, ustanawia związek między reprezentacją dziedziny czasu a reprezentacją dziedziny częstotliwości. Szybka transformacja Fouriera, czyli FFT, jest algorytmem obliczeniowym, który skraca czas obliczeń i złożoność dużych transformacji. FFT to tylko algorytm stosowany do szybkiego obliczania DFT.

2. Algorytm FFT i DFT

Najczęściej stosowanym algorytmem FFT jest algorytm zbiornika Cooley, który został nazwany na cześć J. W. Cooley i John Tukey. Jest to algorytm podziału i podboju do obliczania maszyny złożonej serii Fouriera. Łamie DFT na mniejsze DFT. Inne algorytmy FFT obejmują algorytm Radera, algorytm transformacji Winograd Fouriera, algorytm-transform chirp z itp. Algorytmy DFT można zaprogramować na komputerach cyfrowych ogólnego przeznaczenia, albo wdrażane bezpośrednio przez specjalne sprzęt. Algorytm FFT służy do obliczenia DFT sekwencji lub jej odwrotnej. DFT można wykonać jako O (n²) W złożoności czasowej, podczas gdy FFT zmniejsza złożoność czasu w kolejności O (NLOGN).

3. Zastosowania FFT i DFT

DFT może być używany w wielu cyfrowych systemach przetwarzania w różnych zastosowaniach, takich jak obliczenie widma częstotliwości sygnału, rozwiązywanie częściowych zastosowań różnicowych, wykrywanie celów z echa radaru, analiza korelacji, obliczanie wielomianowego mnożenia, analiza spektralna i inne. FFT jest szeroko stosowany do pomiarów akustycznych w kościołach i salach koncertowych. Inne zastosowania FFT obejmują analizę widmową w analogicznych pomiarach wideo, mnożenie dużej liczby całkowitej i wielomianowej, algorytmy filtrowania, obliczanie rozkładów izotopowych, obliczanie współczynników serii Fouriera, obliczanie zbiorów, generowanie szumów o niskiej częstotliwości, projektowanie kinoform, wykonywanie gęstych macierzy strukturalnych. więcej.

FFT vs. DFT: Wykres porównawczy

Podsumowanie FFT vs. DFT

Krótko mówiąc, dyskretna transformacja Fouriera odgrywa kluczową rolę w fizyce, ponieważ może być stosowana jako narzędzie matematyczne do opisania związku między domeną czasową a dziedziną częstotliwości reprezentacji dyskretnych sygnałów. To prosty, ale dość czasochłonny algorytm. Jednak w celu skrócenia czasu obliczeniowego i złożoności dużych transformacji można zastosować bardziej złożony, ale mniej czasochłonny algorytm, taki jak szybka transformacja Fouriera. FFT to implementacja DFT używana do szybkiego obliczania DFT. Krótko mówiąc, FFT może zrobić wszystko, co robi DFT, ale wydajniej i znacznie szybciej niż DFT. To skuteczny sposób obliczania DFT.