Goertzelův algoritmus

Goertzelův algoritmus je algoritmus používaný při digitálním zpracování signálu (DSP) pro efektivní vyhodnocení jednotlivých členů diskrétní Fourierovy transformace (DFT). Je užitečný v určitých praktických aplikacích, jako je rozpoznávání tónů tonové volby (DTMF) na straně telefonní ústředny tradičního analogového telefonu. Algoritmus popsal poprvé Gerald Goertzel v roce 1958.

Stejně jako DFT analyzuje Goertzelův algoritmus jednu vybranou frekvenční komponentu diskrétního signálu. Na rozdíl od přímých výpočtů DFT aplikuje Goertzelův algoritmus v každé iteraci jediný koeficient s reálnou hodnotou. Používá reálnou aritmetiku pro vstupní sekvence s reálnou hodnotou. Při pokrytí celého spektra má Goertzelův algoritmus vyšší řád složitosti než algoritmy rychlé Fourierovy transformace (FFT), ale pro výpočet malého počtu vybraných frekvenčních komponent je numericky efektivnější. Jednoduchost Goertzelova algoritmu jej činí vhodným pro malé procesory a vestavěné systémy.

Reference

V tomto článku byl použit překlad textu z článku Goertzel algorithm na anglické Wikipedii.