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

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

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

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

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

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

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

1. Последовательно вычисляются члены последовательности $s_{n}$ для $n=0,\dots ,N-1$ по рекуррентной формуле $s_{n}=2\cos \left({\frac {2\pi k}{N}}\right)s_{n-1}-s_{n-2}+x_{n}$ ,где $s_{-1}=s_{-2}=0$;
2. Искомое значение частотного компонента получается как $X_{k}=e^{{\frac {2\pi i}{N}}k}s_{N-1}-s_{N-2}$.

Доказательство алгоритма

Нужен ли вообще раздел с доказательством алгоритма?

Для удобства записи введём обозначение $W=e^{-{\frac {2\pi i}{N}}}$. Определение k-го частотного компонента дискретного преобразования Фурье тогда примет вид $X_{k}=\sum _{n=0}^{N-1}{x_{n}W^{kn}}$. Также заметим, что $W^{-N}=e^{2\pi i}=1$ и для любого действительного $k$ выполняется равенство $W^{k}+W^{-k}=e^{-{\frac {2\pi i}{N}}k}+e^{{\frac {2\pi i}{N}}k}=2\cos \left({\frac {2\pi k}{N}}\right)$.

Преобразуем исходное определение $X_{k}$:

$X_{k}=\sum _{n=0}^{N-1}{x_{n}W^{kn}}=W^{-kN}\sum _{n=0}^{N-1}{x_{n}W^{kn}}=\sum _{n=0}^{N-1}{x_{n}[W^{-k}]^{N-n}}=x_{0}[W^{-k}]^{N}+x_{1}[W^{-k}]^{N-1}+\dots +x_{N-2}[W^{-k}]^{2}+x_{N-1}W^{-k}={\bigg (}{\Big (}{\big (}\dots (x_{0}W^{-k}+x_{1})W^{-k}+\dots {\big )}W^{-k}+x_{N-2}{\Big )}W^{-k}+x_{N-1}{\bigg )}W^{-k}$

Литература

• Эммануил С. Айфичер, Барри У. Джервис. Цифровая обработка сигналов: практический подход = Digital Signal Processing: A Practical Approach. — 2-е издание. — М.: Издательский дом «Вильямс», 2004. — 992 с. — ISBN 5-8459-0710-1.
• Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов = Fast Algorithms for Digital Signal Processing. — М.: Мир, 1989. — 448 с. — ISBN 5-09-001009-2.