Nowy 1 (8)

222 12. Szybkie przekształcenie Fo

Tab. 12.1.

6000 'GENERACJA CZĘSTOTLIWOŚCI UJEMNEJ

6010 'Ten podprogram tworzy sygnał w zespolonej dziedzinie częstotliwości z sygnału 6015 'w rzeczywistej dziedzinie częstotliwości.

6020 'Po wejściu do tego podprogramu N% zawiera liczbę punktów w sygnałach a

6030 •REX[ ] i IMX! ] zawierają rzeczywiste widmo częstotliwościowe w próbkach od 0 do N%/2.

6040 'Po powrocie REX[ ] i IMX[ ] zawierają zespolone widmo częstotliwościowe w próbkach od 0 do N%-1. 6060 FOR K* = (N%/2+l) TO (N%-1)

6070    REX[K%] = REX[N%—K%]

6080    IMX[K%J = -IMX[N%-K%]

6090 NEXT K%

6100 ’

6110 RETURN

jącego zrozumienie tej symetrii. W praktyce wprowadza się widmo częstotliwościowe wistego DFT do próbek od O do N/2 w matrycach zespolonego DFT i następnie korzysta „ z podprogramu do wytworzenia częstotliwości ujemnych w próbkach od N/2 + 1 do N- 1. X program zamieszczono w tablicy 12.1. W celu sprawdzenia, czy istnieje właściwa syn należy - po wykonaniu odwrotnego przekształcenia FFT - przyjrzeć się części urojonej w dżinie czasu. Powinna ona zawierać same zera, jeśli wszystko jest w porządku (poza szu o wartości kilku części na milion, przy użyciu obliczeń o pojedynczej dokładności).

Jak dziafa FFT

FFT jest skomplikowanym algorytmem i poznanie jego szczegółów pozostawia się zwy tym, którzy specjalizują się w tej problematyce. W tym podrozdziale będzie opisane og działanie FFT, jednak z ominięciem jednego istotnego zagadnienia - zastosowania liczb zesp lonych. Jeśli jednak macie odpowiednie przygotowanie z matematyki liczb zespolonych możecie między wierszami wyczytać prawdziwą naturę tego algorytmu. Nie martwcie się. >, nie wychwycicie niektórych szczegółów. Bardzo niewielu naukowców i inżynierów potraf-ręki napisać program FFT.

W zapisie zespolonym każda z dziedzin - tak czasu, jak i częstotliwości - zawiera j sygnał złożony z N punktów zespolonych. Każdy z tych punktów zespolonych zaw dwie liczby, wyrażające część rzeczywistą i część urojoną. Na przykład, gdy mówimy o spolonej próbce X[42], odnosi się to do kombinacji Re X[42] i Im X[42]. A zatem k' zmienna zespolona zawiera dwie liczby. W przypadku mnożenia dwóch zmiennych ze lonych trzeba wykonać kombinację czterech oddzielnych składników w celu utwórz dwóch czynników iloczynu (takich jak we wzorze 9.1). W poniższych rozważaniach temat ,Jak działa FFT” zastosowano specyficzne słownictwo związane z zapisem zz lonym. W tym języku pojęcia sygnał, punkt, próbka i wartość odnoszą się do kombi części rzeczywistej i urojonej.

FFT działa na zasadzie rozłożenia Ahpunktowego sygnału w dziedzinie czasu na N sygn też w dziedzinie czasu, z których każdy zawiera jeden punkt. Następnym krokiem jest czenie N widm częstotliwościowych odpowiadających tym N sygnałom w dziedzinie c Wreszcie, N widm podlega syntezie, tworząc jedno widmo częstotliwościowe.

Na rys. 12.2 przedstawiono przykład rozkładu w dziedzinie czasu z zastosowaniem W tym przykładzie 16-punktowy sygnał jest rozkładany w czterech etapach. W pierws etapie 16-punktowy sygnał jest rozdzielany na dwa sygnały 8-punktowe. W drugim pie dane są rozkładane na cztery sygnały zawierające po 4 punkty. Takie rozkładanie kontynuowane aż do uzyskania N sygnałów zawierających po jednym punkcie. Za k razem, gdy sygnał jest dzielony na dwa, stosuje się rozkład z przeplotem, a więc sy jest rozdzielany na próbki o numerach parzystych i nieparzystych. Najlepszym spos