Rozdzielczość DTF jest definiowana jako liczba próbek widmowych przypadająca na jeden okres widma (równy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \omega_s\}
, w skali pulsacji lub Parser nie mógł rozpoznać (błąd składni): {\displaystyle f_s\}
, w skali częstotliwości). Jest to zarazem odwrotność odległości między kolejnymi próbkami widma.
Rozdzielczość DTF jest cechą zależną tylko od czasu obserwacji Parser nie mógł rozpoznać (błąd składni): {\displaystyle T\}
, sygnału, bowiem .
Metoda uzupełniania zerami polega na przyjęciu zerowych wartości dodatkowych próbek sygnału w punktach Parser nie mógł rozpoznać (błąd składni): {\displaystyle n=N,...,N_1-1\}
, i obliczeniu dla tak zdefiniowanego sygnału Parser nie mógł rozpoznać (błąd składni): {\displaystyle N_1\}
, -punktowej DTF.
Dodanie do ośmiu właściwych próbek sygnału ośmiu dodatkowych próbek zerowych zwiększa rozdzielczość DTF dwukrotnie.
Próbki widmowe leżą zawsze na krzywej ciągłej Parser nie mógł rozpoznać (błąd składni): {\displaystyle A(e^{j\theta})\}
, .
Wraz ze wzrostem dodatkowych zer wzrasta nakład obliczeniowy.
Zgodnie z właściwością symetrii wystarczy obliczyć tylko próbki widmowe Parser nie mógł rozpoznać (błąd składni): {\displaystyle X(0), X(1), X(2), X(3)\}
, . Jak widzimy tylko próbki Parser nie mógł rozpoznać (błąd składni): {\displaystyle X(1)\}
, i Parser nie mógł rozpoznać (błąd składni): {\displaystyle X(5)\}
, (lub równoważnie Parser nie mógł rozpoznać (błąd składni): {\displaystyle X(-1)\}
, ) są niezerowe.
Gdy analogowy sygnał harmoniczny jest obserwowany dokładnie tylko przez jeden jego okres, wówczas DTF wyznaczone na podstawie jego próbek daje prawidłowy obraz jego widma. Niezerowe próbki widmowe otrzymujemy tylko dla pulsacji unormowanych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \theta =\pm \pi/3\}
, odpowiadających częstotliwościom nieunormowanym .
Punkty odpowiadają częstotliwością nieunormowanym , nie pokrywającymi się z właściwą częstotliwością sygnału .
Można mówić o przecieku mocy sygnału skoncentrowanej w prążku widmowym o częstotliwości do prążków widmowych występujących w fałszywych punktach osi częstotliwości.
Obserwacja sygnału Parser nie mógł rozpoznać (błąd składni): {\displaystyle x[n]\}
, w skończonym przedziale czasu Parser nie mógł rozpoznać (błąd składni): {\displaystyle n=0,...,N-1\}
, odpowiada mnożeniu tego sygnału przez prostokątne okno czasowe. Mówimy wówczas o okienkowaniu sygnału.
Obserwacja sygnału Parser nie mógł rozpoznać (błąd składni): {\displaystyle x[n]\}
, w skończonym prostokątnym oknie czasowym Parser nie mógł rozpoznać (błąd składni): {\displaystyle g[n]\}
, odpowiada splataniu widma tego sygnału przez widmo okna opisane wzorem (5.2).
Na zniekształcenia widma amplitudowego nie ma wpływu czynnik wykładniczy widma (5.2), a decyduje o nich drugi czynnik, którego struktura jest listkowa.
W przypadku okna prostokątnego stosunek wysokości pierwszego listka bocznego do wysokości listka głównego nie może być mniejszy od Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0,212\}
,.
Przykład 5.2 dobrze ilustruje zjawisko przecieku w przypadku sygnału harmonicznego. Dokładne widmo tego sygnału składa się z (okresowo powtarzanej z okresem Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2\pi\}
, ) pary dystrybucji w punktach Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pm \theta_0\}
, (rys. a). Skończony czas obserwacji powoduje, że dystrybucje te rozmywają się na dwa widma listkowe rozmieszczone wokół punktów Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pm \theta_0\}
, .
Na rys. b i c pokazano wykresy widma amplitudowego sygnału harmonicznego z przykładu 5.2 o pulsacji unormowanej okienkowanego oknem prostokątnym w dwóch przypadkach: Parser nie mógł rozpoznać (błąd składni): {\displaystyle N=6\}
, oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle N=8\}
, .
Wykres wyjaśnia dlaczego w przypadku wyznaczenia 6-punktowej DTF (rys. b) nie występuje zjawisko przecieku, tzn. otrzymujemy prawidłowe próbki widma sygnału harmonicznego w punktach Parser nie mógł rozpoznać (błąd składni): {\displaystyle \pm \pi/3\}
, (dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle k=\pm 1\}
, ). Pozostałe próbki widmowe, składające się na DFT, wypadają bowiem dokładnie w punktach zerowych rozmytego widma . Natomiast w przypadku wyznaczania 8-punktowej DTF (rys. c) próbki widmowe wypadają między zerami widma i przeciek występuje.
Zjawisko przecieku objawia się w podobny sposób w przypadku, gdy w skończonym oknie czasowym są obserwowane sygnały nieokresowe. Energia (lub moc) sygnału przecieka wówczas nie do obcych prążków, ale w inne ciągłe przedziały osi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \theta\}
, .
Widma wszystkich pokazanych na wykresach okien czasowych mają strukturę listkową. Zniekształcenia widma sygnału spowodowane skończonym czasem jego obserwacji są tym mniejsze im mniejszy jest poziom listków bocznych i jednocześnie węższy jest listek główny. Wymagania te są jednak sprzeczne.
Dobierając inne od prostokątnego okna czasowe, zmniejszamy poziom listków bocznych. Powoduje to jednak jednoczesny wzrost szerokości listka głównego.
Na wykresach pokazano przykłady okien czasowych różnych od prostokątnego dla przypadku Parser nie mógł rozpoznać (błąd składni): {\displaystyle N=10\}
, .
Zauważmy, że obie krańcowe wartości okna Hamminga (rys. e) są różne od zeru (równe Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0,08\}
,). Ta drobna różnica powoduje, że poziom listków bocznych jest dla tego okna mniejszy w porównaniu np. z oknem Hanna (rys. d) lub oknem Blackmana (rys. f).
W porównaniu z oknem prostokątnym wszystkie okna pokazane na rys. a-f zapewniają mniejszy poziom listków bocznych, ale kosztem wzrostu szerokości listka głównego. Dla okien tych wielkości te przy zadanym Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, są ustalone i nie można na nie wpływać. Istnieją jednak bardziej złożone okna, w których poziom listków bocznych i szerokość listka głównego można regulować i dobierać ich wartości w drodze kompromisu.
Im poziom listków bocznych widma okna jest mniejszy, tym większa jest tzw. rozróżnialność częstotliwościowa DTF. Natomiast im szerokość listka głównego jest mniejsza, tym większa jest tzw. rozróżnialność amplitudowa DTF.
W szacowaniu złożoności obliczeniowej DTF zakładamy, że sygnał Parser nie mógł rozpoznać (błąd składni): {\displaystyle x[n]\}
, jest zespolony.
Liczba ma ciekawe właściwości. Jest ona równa pierwiastkowi Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, -tego z jedności. Jej Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, -ta potęga jest równa jedności: . Ponadto w wyniku próbkowania Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, razy w okresie w chwilach Parser nie mógł rozpoznać (błąd składni): {\displaystyle nT_s\}
, zespolonego sygnału harmonicznego Parser nie mógł rozpoznać (błąd składni): {\displaystyle e^{j\omega_0 t}\}
, otrzymujemy próbki będące kolejnymi potęgami liczby Parser nie mógł rozpoznać (błąd składni): {\displaystyle W\}
,: .
O złożoności obliczeniowej DTF decyduje liczba mnożeń. Dlatego przy jej szacowaniu nie uwzględnia się dodawań. Liczba mnożeń wynosi dokładnie Parser nie mógł rozpoznać (błąd składni): {\displaystyle (N-1)^2\}
, , gdyż obliczenie próbki widmowej dla wymaga wykonania tylko dodawań. Dla większych Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, można dla prostoty szacowania przyjąć, że liczba mnożeń jest równa Parser nie mógł rozpoznać (błąd składni): {\displaystyle N^2\}
,.
Szybka transformata Fouriera STF jest powszechnie znana pod nazwą angielską FFT (Fast Fourier Transform).
Dostępne komercyjnie pakiety programów zawierają najczęściej algorytmy obliczeniowe STF dla , lub .
Prezentujemy tu wersję podstawową algorytmu STF. Znanych jest obecnie wiele wersji tego algorytmu o jeszcze mniejszej złożoności obliczeniowej.
Ponieważ w algorytmie STF będą występować DTF o różnych wymiarach, w oznaczeniu transformat będziemy dodatkowo podawać ich wymiar (liczbę punktów, w których są one obliczane).
Sygnały i są utworzone z parzystych i odpowiednio nieparzystych próbek sygnału Parser nie mógł rozpoznać (błąd składni): {\displaystyle x[n]\}
, .
Obliczenie obu występujących we wzorze (5.8) Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, -punktowych DFT Parser nie mógł rozpoznać (błąd składni): {\displaystyle X_N^1 [k]\}
, i Parser nie mógł rozpoznać (błąd składni): {\displaystyle X_N^2 [k]\}
, dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle k=0,...,N-1\}
, wymaga po , mnożeń, a więc razem Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2N^2\}
, mnożeń. Dodatkowe Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, mnożeń należy wykonać obliczając iloczyny Parser nie mógł rozpoznać (błąd składni): {\displaystyle W_{2N}^{-k} X_N^2 (k)\}
,. W sumie daje to Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2N^2+N\}
, mnożeń.
Oba składniki wyrażenia (5.10) były już obliczone podczas obliczania Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, -punktowych DTF Parser nie mógł rozpoznać (błąd składni): {\displaystyle X_N^1 [k]\}
, i Parser nie mógł rozpoznać (błąd składni): {\displaystyle X_N^2 [k]\}
, dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle k=0,...,N-1\}
,. W celu obliczenia DTF Parser nie mógł rozpoznać (błąd składni): {\displaystyle X_{2N} [k]\}
, dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle k=N,...,2N-1\}
, nie trzeba więc wykonywać żadnych dodatkowych mnożeń.
Zyski obliczeniowe na każdym poziomie obliczeń kumulują się, dając w efekcie radykalne zmniejszenie złożoności obliczeniowej STF w porównaniu ze złożonością wynikającą z obliczania DTF ze wzoru definicyjnego.
Pojedynczy motylek przedstawiony na rysunku stanowi ilustrację graficzną schematu obliczeń Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2N\}
, -punktowej STF według wzorów (5.11). Stanowi on elementarne powtarzające się ogniwo algorytmu STF na różnych poziomach obliczeń, tj. dla kolejnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2^m\}
, -punktowych DTF, począwszy od .
Na wyjściu każdego motylka obliczane są dwie próbki widmowe. Na ostatnim końcowym poziomie obliczeń Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, -punktowej STF występuje zatem Parser nie mógł rozpoznać (błąd składni): {\displaystyle N/2\}
, motylków, bowiem należy obliczyć łącznie Parser nie mógł rozpoznać (błąd składni): {\displaystyle N\}
, próbek widmowych. Na wcześniejszych poziomach algorytmu występuje również Parser nie mógł rozpoznać (błąd składni): {\displaystyle N/2\}
, motylków.
Schemat motylkowy algorytmu STF przedstawiony na rysunku został sporządzony dla przypadku . Ponieważ w ogólnym przypadku schemat motylkowy składa się z Parser nie mógł rozpoznać (błąd składni): {\displaystyle log_2 N\}
, kolumn (poziomów), z których każdy zawiera Parser nie mógł rozpoznać (błąd składni): {\displaystyle N/2\}
, motylków, więc dla mamy 3 kolumny po 4 motylki.
Danymi wejściowymi algorytmu są próbki sygnału Parser nie mógł rozpoznać (błąd składni): {\displaystyle x(n)\}
, (w podanym przykładzie 8 próbek dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle n=0,...,7\}
, ) oraz znane liczby zespolone o postaci Parser nie mógł rozpoznać (błąd składni): {\displaystyle W_{2^m}^{-j}\}
, , Parser nie mógł rozpoznać (błąd składni): {\displaystyle m=2,3,...\}
, Na każdym poziomie wykorzystywane są wszystkie próbki Parser nie mógł rozpoznać (błąd składni): {\displaystyle x(n)\}
, , ale w różnej kolejności.
Na wyjściach poszczególnych motylków otrzymujemy próbki widmowe obliczane na kolejnych poziomach. Na wyjściach motylków ostatniego poziomu otrzymujemy zbiór próbek widmowych składających się na obliczaną DTF (w naszym przypadku 8 próbek).
Już dla zysk obliczeniowy jest ponad pięciokrotny. Dla zysk ten jest ponad 200-krotny.
