41922

Strona 28

Szybka transformata Fouriera - FFT

FFT jest algorytmem, który pozwala nam uprościć obliczenie dyskretnej transformaty Fouriera. Za pomocą tej metody możemy znaleźć widmo częstotliwościowe spróbkowanego sygnału analogowego, czyli przejść z dziedziny czasu do dziedziny częstotliwości.

Dla funkcji ciągłej przekształcenie Fouriera opisane jest całką:

Fija>= J7(Oe‘“da.

My jednak mamy doczynienia z sygnałem spróbkowanym, dlatego do obliczenia transfomaty stosujemy postać dyskretną tr. Fouriera. Wyliczenie kolejnych współczynników wielomianu Fouriera realizuje się na podstawie wzoru:

A.=P„,+w”Q„ m = 0,1,2 ...2N-1 gdzie:

są odpowiednio dyskretnymi transformatami Fouriera rzędu N wyrazów o num. parzystych p_k i wyrazów o num. nieparzystych q_k

Z obliczeń wynika, że algorytm FFT wymaga średnio o 40% mniej mnożeń i dodawań niż metoda liczenia dyskretnej transformaty Fouriera z definicji. Dokładność wyników otrzymanych z FFT, a co za tym idzie szybkość obliczeń zależy od wartości N. Im większe N tym dokładniejsze widmo sygnału. Istnieje kilka metod obliczania numerycznego FFT. Najbardziej znane to metoda Cooleya - Turkiego oraz algorytm motylkowy. Na iysunkach w dalszej części tego opracowania przedstawiłem kilka sygnałów ciągłych i ich widma obliczone za pomocą szybkiej transformaty Fouriera.

Odwrotna szybka transformata Fouriera - IFFT

Algorytm, który pozwala nam przejść z sygnałem z dziedziny częstotliwości w dziedzinę czasu Możemy odtworzyć pierwotną funkcję z jej widma częstotliwościowego. Stosuje się do tego celu zmodyfikowaną metodę Cooleya-Turkiego.

Dla postaci dyskretnej kolejne próbki sygnału możemy wyliczyć wg. wzoru:

1 J=l

Dla postaci ciągłej odwrotna transformata Fouriera wygląda tak:

2.7C „

Wiele nowoczesnych metod kompresji dźwięku powszeclinie używa FFT i IFFT.