Algorytm Goertzela
Sposób obliczenia jednej składowej częstotliwościowej sygnału, tańszy od pełnego FFT, gdy interesuje nas tylko kilka tonów.
Opublikował go w 1958 roku Gerald Goertzel. Algorytm wylicza pojedynczy prążek dyskretnej transformaty Fouriera za pomocą rekurencyjnego filtru drugiego rzędu: jedno mnożenie i dwa dodawania na próbkę, a po ostatniej próbce krótki krok końcowy dający moduł. Stan roboczy to dwie liczby.
FFT podaje od razu wszystkie częstotliwości, ale jeśli szukamy tylko ośmiu, wygrywa Goertzel. Tak właśnie wygląda problem wybierania tonowego: cyfry DTMF to pary złożone z jednej z czterech niskich i jednej z czterech wysokich częstotliwości, a osiem filtrów Goertzela na taniutkim DSP wystarcza, by rozpoznać wciśnięty klawisz. Ta sama sztuczka działa w tunerach gitarowych i w modemach nasłuchujących konkretnej fali nośnej. Tak jak FFT, cierpi na przeciek widmowy, gdy ton nie trafia w środek prążka.