Podręcznik

Istnieje wiele metod numerycznej optymalizacji obliczeń dyskretnej transformaty Fouriera oraz jej odwrotności (IDFT), których celem jest znaczące ograniczenie liczby wymaganych operacji arytmetycznych. W wyniku tych prac opracowano tzw. algorytmy szybkiej transformaty Fouriera (FFT, ang. Fast Fourier Transform), które stanowią obecnie podstawowe narzędzie w analizie częstotliwościowej sygnałów dyskretnych.

FFT to rodzina algorytmów, które obliczają DFT w sposób znacznie bardziej efektywny niż bezpośrednie podstawienie do wzoru. Zamiast wykonywać \( \mathcal{O}(N^2) \) operacji, jak ma to miejsce w klasycznym podejściu, FFT redukuje złożoność obliczeniową do \( \mathcal{O}(N \log N) \), co ma kluczowe znaczenie przy przetwarzaniu dużych zbiorów danych.

Algorytmy FFT wykorzystują zasadę „dziel i zwyciężaj”, powszechnie stosowaną w informatyce. Polega ona na rekurencyjnym dzieleniu problemu na mniejsze, prostsze podproblemy, aż do momentu, gdy każdy z nich może być rozwiązany szybko i bezpośrednio. Jedną z najbardziej znanych i szeroko stosowanych wersji FFT jest algorytm Cooleya–Tukeya, który wymaga, aby długość sygnału była potęgą dwójki. Podstawową operacją w strukturze FFT jest tzw. „motylek”, który łączy pary próbek wejściowych w sposób umożliwiający ich dalsze przekształcanie w kolejnych etapach algorytmu. Struktura motylkowa pozwala na wykorzystanie symetrii i okresowości zespolonych wykładników w DFT, co umożliwia przyspieszenie obliczeń.

W literaturze często omawia się algorytm FFT typu radix-2, w którym długość analizowanego sygnału (liczba próbek) musi być potęgą liczby dwa. Jest to najprostszy i najbardziej efektywny wariant, pozwalający w pełni wykorzystać strukturę „motylków” i redukcję obliczeń. Jeżeli długość sygnału nie jest potęgą dwójki, a zależy nam na maksymalnym przyspieszeniu obliczeń, można zastosować technikę zero-padding, czyli dopełnienie sygnału zerami do najbliższej długości będącej potęgą dwóch. Nie zmienia to informacji zawartych w sygnale ani rzeczywistej rozdzielczości częstotliwościowej wynikającej z czasu obserwacji, ale zwiększa gęstość próbek w widmie i pozwala wykorzystać szybszy algorytm radix-2.

Implementacja FFT w Pythonie jest jednak znacznie bardziej elastyczna i potrafi obsługiwać sygnały o dowolnej długości. Najszybciej działa w przypadku, gdy liczba próbek jest potęgą dwójki, lecz może również przetwarzać sygnały, których długość jest inną liczbą całkowitą. W takich sytuacjach czas obliczeń może ulec wydłużeniu. Najmniej korzystny przypadek występuje wtedy, gdy liczba próbek jest dużą liczbą pierwszą. Wówczas algorytm nie może zostać zoptymalizowany poprzez podział na mniejsze bloki, co prowadzi do konieczności obliczania DFT bezpośrednio z definicji i wiąże się z największym kosztem obliczeniowym.

Odwrotna szybka transformata Fouriera (IFFT, ang. Inverse Fast Fourier Transform) jest algorytmem służącym do szybkiego wyznaczania odwrotnej dyskretnej transformaty Fouriera (IDFT). Podobnie jak FFT, opiera się na optymalizacji obliczeń, redukując złożoność z \( \mathcal{O}(N^2) \) do \( \mathcal{O}(N \log N) \).

IFFT przekształca sygnał z dziedziny częstotliwości do dziedziny czasu, przy czym dane wejściowe mają postać zespolonych wartości widma (amplitudy i fazy). Matematycznie, IFFT różni się od FFT jedynie znakiem w wykładniku funkcji zespolonej i dodatkowym współczynnikiem skalującym \( 1/N \). W praktycznych implementacjach ten sam algorytm może być użyty zarówno do FFT, jak i IFFT, zmienia się jedynie kierunek obliczeń. Dzięki IFFT możliwe jest np. odtworzenie sygnału w dziedzinie czasu po modyfikacjach widma, takich jak filtracja, zmiana fazy czy wzmocnienie wybranych składowych częstotliwościowych.