PS Moduł 5

Rozdzielczość DTF jest definiowana jako liczba próbek widmowych przypadająca na jeden okres widma (równy ${\omega }_s$ w skali pulsacji lub $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 $T$ sygnału, bowiem $r_f=N/f_s=N{T}_s=T$ . Metoda uzupełniania zerami polega na przyjęciu zerowych wartości dodatkowych próbek sygnału w punktach $n=N,...,N_1-1$ i obliczeniu dla tak zdefiniowanego sygnału $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 $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 $X(0),X(1),X(2),X(3)$ . Jak widzimy tylko próbki $X(1)$ i $X(5)$ (lub równoważnie $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 $\theta =\pm \pi /3$ odpowiadających częstotliwościom nieunormowanym $f=\pm 1kHz$ .

---

Punkty ${\theta }_k=\pi k/4$ odpowiadają częstotliwością nieunormowanym $f_k=k\times 0,75kHz$ , nie pokrywającymi się z właściwą częstotliwością sygnału $1kHz$ . Można mówić o przecieku mocy sygnału skoncentrowanej w prążku widmowym o częstotliwości $1kHz$ do prążków widmowych występujących w fałszywych punktach osi częstotliwości. Obserwacja sygnału $x[n]$ w skończonym przedziale czasu $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 $x[n]$ w skończonym prostokątnym oknie czasowym $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 $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 $2\pi$ ) pary dystrybucji w punktach $\pm {\theta }_0$ (rys. a). Skończony czas obserwacji powoduje, że dystrybucje te rozmywają się na dwa widma listkowe rozmieszczone wokół punktów $\pm {\theta }_0$ .

---

Na rys. b i c pokazano wykresy widma amplitudowego sygnału harmonicznego z przykładu 5.2 o pulsacji unormowanej ${\theta }_0=\pi /3$ okienkowanego oknem prostokątnym w dwóch przypadkach: $N=6$ oraz $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 $\pm \pi /3$ (dla $k=\pm 1$ ). Pozostałe próbki widmowe, składające się na DFT, wypadają bowiem dokładnie w punktach zerowych rozmytego widma $X_0(e^{j\theta })$ . 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 $\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 $N=10$ .

---

Zauważmy, że obie krańcowe wartości okna Hamminga (rys. e) są różne od zeru (równe $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 $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ł $x[n]$ jest zespolony. Liczba $W=e^{j2\pi /N}$ ma ciekawe właściwości. Jest ona równa pierwiastkowi $N$ -tego z jedności. Jej $N$ -ta potęga jest równa jedności: $W^n=(e^{j2\pi /N}{)}^N=e^{j2\pi }=1$ . Ponadto w wyniku próbkowania $N$ razy w okresie w chwilach $n{T}_s$ zespolonego sygnału harmonicznego $e^{j{\omega }_{0}t}$ otrzymujemy próbki będące kolejnymi potęgami liczby $W$: $e^{j{\omega }_{0}n{T}_s}=e^{j2\pi n{T}_s/T_0}=(e^{j2\pi /N}{)}^n=W^n$. 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 $(N-1{)}^2$ , gdyż obliczenie próbki widmowej dla $k=0$ wymaga wykonania tylko dodawań. Dla większych $N$ można dla prostoty szacowania przyjąć, że liczba mnożeń jest równa $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 $N=256$ , $N=512$ lub $N=1024$. 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 $x_N^1[n]=x[2n]$ i $x_N^2[n]=x[2n+1]$ są utworzone z parzystych i odpowiednio nieparzystych próbek sygnału $x[n]$ . Obliczenie obu występujących we wzorze (5.8) $N$ -punktowych DFT $X_N^1[k]$ i $X_N^2[k]$ dla $k=0,...,N-1$ wymaga po $N^2$ mnożeń, a więc razem $2N^2$ mnożeń. Dodatkowe $N$ mnożeń należy wykonać obliczając iloczyny $W_{2N}^{-k}{X}_N^2(k)$. W sumie daje to $2N^2+N$ mnożeń.

---

Oba składniki wyrażenia (5.10) były już obliczone podczas obliczania $N$ -punktowych DTF $X_N^1[k]$ i $X_N^2[k]$ dla $k=0,...,N-1$. W celu obliczenia DTF $X_{2N}[k]$ dla $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ń $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 $2^m$ -punktowych DTF, począwszy od $m=1$. Na wyjściu każdego motylka obliczane są dwie próbki widmowe. Na ostatnim końcowym poziomie obliczeń $N$ -punktowej STF występuje zatem $N/2$ motylków, bowiem należy obliczyć łącznie $N$ próbek widmowych. Na wcześniejszych poziomach algorytmu występuje również $N/2$ motylków.

---

Schemat motylkowy algorytmu STF przedstawiony na rysunku został sporządzony dla przypadku $N=8=2^3$ . Ponieważ w ogólnym przypadku schemat motylkowy składa się z $lo{g}_{2}N$ kolumn (poziomów), z których każdy zawiera $N/2$ motylków, więc dla $N=8$ mamy 3 kolumny po 4 motylki. Danymi wejściowymi algorytmu są próbki sygnału $x(n)$ (w podanym przykładzie 8 próbek dla $n=0,...,7$ ) oraz znane liczby zespolone o postaci $W_{2^m}^{-j}$ , $m=2,3,...$ Na każdym poziomie wykorzystywane są wszystkie próbki $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 $N=8$ zysk obliczeniowy jest ponad pięciokrotny. Dla $N=10^2=1024$ zysk ten jest ponad 200-krotny.

---