81182 Nowy 5 (7)

226 12. Szybkie przekształcenie Fou

Ta prosta sieć przepływu sygnałów jest, ze względu na swój kształt, nazywana motylkiem. Motylek jest podstawowym elementem obliczeniowym w FFT, przekształcającym dwa pum-ty zespolone w dwa inne punkty zespolone.

Na rys. 12.7 przedstawiono strukturę całego FFT. Rozkład w dziedzinie czasu jest re wany algorytmem sortowania z odwróceniem bitowym. Przeniesienie poddanych rozkP danych w dziedzinę częstotliwości nie wymaga żadnych operacji i dlatego nie jest uwi nione na rysunku.

Synteza w dziedzinie częstotliwości wymaga trzech pętli. Pętla zewnętrzna przeć przez log₂N stopni. Stopniem nazywamy tu każdy poziom na rys. 12.2, poczynając dołu i przesuwając się ku górze. Środkowa pętla przechodzi przez każde przetwarz indywidualne widmo częstotliwościowe w danym stopniu (tj. przez każdą z ramek kolejnych poziomach na rys. 12.2). W pętli najbardziej wewnętrznej zastosowano tyłek do obliczania punktów w każdym widmie częstotliwościowym, a więc jest to tla przechodząca przez próbki wewnątrz każdej ramki na rys. 12.2. Ramki „nagłów. (overhead) na rys. 12.7 określają indeksy początkowe i końcowe dla pętli, jak również obliczania sinusoid w motylkach. Przejdziemy teraz do sedna tego rozdziału, a więc programów FFT.

Dane w dziedzinie czasu

Rozkład / w dziedzinie czasu

Synteza S w dziedzinie częstotliwości

Dane w dziedzinie częstotliwości

Rys. 12.7. Sieć przepływu sygnałów w FFT. Sieć zawiera trzy etapy: 1) rozkład N-punktowego sygnafi w dziedzinie czasu na N sygnałów 1-punktowych, 2) wyznaczenie widma każdego z sygnałów N-pumm-wych (nie wymaga żadnej operacji) oraz 3) synteza N widm częstotliwościowych w pojedyncze widm: częstotliwościowe