Алгоритм Гёрцеля

Алгоритм Гёрцеля (англ. Goertzel algorithm) — это специальная реализация дискретного преобразования Фурье (ДПФ) в форме рекурсивного фильтра. Данный алгоритм был предложен Г. Гёрцелем в 1958 году . В отличие от быстрого преобразования Фурье, вычисляющего все частотные компоненты ДПФ, алгоритм Гёрцеля позволяет эффективно вычислить значение одного частотного компонента.

Алгоритм Гёрцеля является популярным алгоритмом для решения задачи детектирования и декодирования тональных сигналов в телефонии.

Варианты названия алгоритма

В русскоязычной литературе нет устоявшегося варианта транслитерации фамилии автора алгоритма. Распространены варианты «Алгоритм Герцеля», «Алгоритм Гертцеля», «Алгоритм Горцеля» и другие.

Описание алгоритма

Пусть $X_{k}=\sum _{n=0}^{N-1}{x_{n}e^{-{\frac {2\pi i}{N}}kn}}$ — k-й частотный компонент компонент дискретного преобразования Фурье (здесь и далее будут использоваться обозначения, принятые в статье «Дискретное преобразование Фурье»). Последовательно вычислим члены рекуррентной последовательности $s_{n}$ для $n=0,\dots ,N-1$:

$s_{n}=2\cos \left({\frac {2\pi k}{N}}\right)s_{n-1}-s_{n-2}$

где $s_{-1}=s_{-2}=0$. Получим искомое значение частотного компонента как:

$X_{k}=e^{-{\frac {2\pi i}{N}}k}s_{N-1}-s_{N-2}$.