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

---

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

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

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

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

В случае, когда требуется вычислить только мощность сигнала, а его фаза не важна, на втором этапе алгоритма вместо комплексного значения частотного компонента вычисляется квадрат его модуля по формуле

---