Nowy 2 (9)

Jak działa FFT 223

1 sygnał 16-punktowy	0 1 2	3 4 5 6 7 8	9	10 11	12 13 14 15
		A
2 sygnały 8-punktowe	0 2 4	6 8 10 12 14	0	3 5	7 9 11 13 15
		A			A
4 sygnały 4-punktowe	0 4 8	12 | 2 6 10 14	1	5 9	13 | | 3 7 11 15
	A	A		A	A
8 sygnałów 2-punktowych	0 8 4	12 I 2 10 6 14	1	^9JLl	13 | 3 11 | | 7 15

A AA A A A A A

S^h.o • «    HB3B000

Rys. 12.2. Rozkład FFT. Sygnał N-punktowy jest rozkładany na N sygnałów, z których każdy zawiera pojedynczy punkt. W każdym etapie zastosowano rozkład z przeplotem, rozdzielając próbki o numerach parzystych i nieparzystych.

zrozumienia tej procedury jest dokładne przeanalizowanie rys. 12.2. W tym procesie rozkładania jest konieczne log^N etapów, tzn. sygnał 16-punktowy (2⁴) wymaga 4 etapów, sygnał 512-punktowy (2⁷) - 7 etapów, sygnał 4096-punktowy (2¹²) - 12 etapów itd. Zapamiętajmy to wyrażenie: /og₂N; będziemy się do niego wielokrotnie odwoływać w tym rozdziale. Teraz, kiedy już zrozumieliście procedurę rozkładania sygnału, można ją znacznie uprościć. Rozkład jest niczym innym, jak zmianą uporządkowania próbek w sygnale. Na rys. 12.3 pokazano wymagany schemat takiej zmiany. W lewej kolumnie zamieszczono listę numerów próbek sygnału oryginalnego, wraz z ich binarnymi równoważnikami. W prawej kolumnie podano listę numerów próbek po zmianie uporządkowania, także z binarnymi równoważnikami numerów. Ważną zasadą jest to, że liczby binarne przed i po zmianie uporządkowania są względem siebie odwrócone. Na przykład próbka 3 (0011) została zamieniona miejscami z próbką numer 12 (1100). Podobnie próbkę numer 14(1110) zamieniono miejscami z próbką numer 7 (0111) i tak dalej. Rozkład FFT w dziedzinie czasu jest zwykle wykonywany przez algorytm sortowania z odwróceniem bitowym. Obejmuje on zmianę uporządkowania N próbek w dziedzinie czasu przez zliczanie binarne ze zmianą kolejności bitów (bit najmniej znaczący z lewej strony), jak to przedstawiono w prawej kolumnie na rys. 12.3. Następnym krokiem w realizacji algorytmu jest wyznaczenie widm częstotliwościowych 1-punktowych sygnałów w dziedzinie czasu. Nic łatwiejszego, gdyż widmo częstotliwościowe sygnału 1-punktowego jest równe temu sygnałowi. Wynika stąd, że ten etap nie wymaga żadnych operacji. Chociaż nie trzeba w tym etapie wykonać żadnej pracy, to nie zapomnijmy, że każdy z 1-punktowych sygnałów jest teraz widmem częstotliwościowym, a nie sygnałem w dziedzinie czasu.

Ostatnim etapem w FFT jest połączenie ze sobą N widm częstotliwościowych w kolejności odwrotnej do tej, jaka miała miejsce przy rozkładzie w dziedzinie czasu. I tu w algorytmie powstaje pewien nieporządek. Niestety nie da się zastosować skróconego odwracania bitów, trzeba cofać się wstecz etap po etapie. W pierwszym etapie 16 widm częstotliwościowych 1-punktowych jest syntetyzowanych w 8 widm częstotliwościowych (każde po 2 punkty). W etapie drugim te 8 widm podlega syntezie w 4 widma częstotliwościowe 4-punktowe itd. Po ostatnim etapie uzyskuje się wynik FFT - 16-punktowe widmo częstotliwościowe.

Na rys. 12.4 pokazano, jak dwa 4-punktowe widma częstotliwościowe są ze sobą łączone w pojedyncze widmo o 8 punktach. Ta synteza musi anulować rozkład z przeplotem dokonany w dziedzinie czasu. Innymi słowy, operacja w dziedzinie częstotliwości powinna odpowiadać przeprowadzonej w dziedzinie czasu procedurze łączenia ze sobą dwóch sygnałów 4-punk-