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

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

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

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

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

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

Пусть $x_n, ~ n = 0,\dots,N-1,$ — измеренные значения сигнала, которые являются входными данными для дискретного преобразования Фурье, а $X_k, ~ k = 0,\dots,N-1,$ — частотные компоненты дискретного преобразования Фурье, по определению равные $X_k = \sum_{n=0}^{N-1} {x_n e^{ -\frac{2 \pi i}N k n}}$. Для расчёта $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}$.

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

$\left| X_k \right|^2 = s_{N-1}^2 - 2 \cos \left( \frac{2 \pi k}N \right) s_{N-1} s_{N-2} + s_{N-2}^2$

({{{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$:

$\begin{align} 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} \end{align}$

Процесс последовательного вычисления стоящих во вложенных скобках выражений мы теперь можем записать с помощью рекуррентной формулы:

$y_n = W^{-k} y_{n-1} + x_n, \; n=0,1,2,\dots,N-1$

({{{2}}})

При этом для вычисления $y_0$ примем $y_{-1}=0$, а искомое значение k-го частотного компонента выражается как $X_k = W^{-k} y_{N-1}$. Полученное выражение для $y_n$ представляет собой БИХ-фильтр первого порядка:

$y_n - W^{-k} y_{n-1} = x_n$

((1))

Применив z-преобразование к обеим частям выражения (1), получим:

$(1 - W^{-k} z^{-1}) Y(z) = X(z)$

({{{2}}})

где $X(z)$ и $Y(z)$ — образы дискретных временных сигналов $x_n$ и $y_n$ соответственно. Из этого выражения выразим передаточную функцию фильтра (1) и преобразуем её, домножив числитель и знаменатель на $1 - W^k z^{-1}$:

$\begin{align} H(z) & = \frac{Y(z)}{X(z)} =\\ & = \frac 1 {1 - W^{-k} z^{-1}} = \\ & = \frac{1 - W^k z^{-1}}{(1 - W^k z^{-1})(1 - W^{-k} z^{-1})} = \\ & = \frac{1 - W^k z^{-1}}{1 - (W^k +W^{-k})z^{-1} + z^{-2}} = \\ & = \frac{1 - W^k z^{-1}}{1 - 2 \cos \left( \frac{2 \pi k}N \right) z^{-1} + z^{-2}} \end{align}$

Передаточную функцию $H(z)$ можно представить в виде произведения функций $P(z) = \frac 1 {1 - 2 \cos \left( \frac{2 \pi k}N \right) z^{-1} + z^{-2}}$ и $Q(z) = 1 - W^k z^{-1}$, что во временной области соответствует последовательному соединению двух фильтров с передаточными функциями $P(z)$ и $Q(z)$. Таким образом, исходный фильтр (1) может быть представлен в виде комбинации двух фильтров:

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

((2))

$y_n = s_n - W^k s_{n-1}$

((3))

Поскольку для вычисления $X_k$ не требуется всех выходных значений фильтра (3), а только значение $y_{N-1}$, то вычисление $y_0, y_1, \dots, y_{N-2}$ можно опустить благодаря тому, что фильтр (3) является КИХ-фильтром, выход которого $y_n$ зависит только от входов $s_n$ и $s_{n-1}$. Значение $X_k$ можем тогда выразить следующим образом:

$X_k = W^{-k} y_{N-1} = W^{-k} (s_{N-1} - W^k s_{N-2}) = W^{-k} s_{N-1} - s_{N-2}$

({{{2}}})

.

Мощность сигнала тогда может быть вычислена как:

$\begin{align} \left| X_k \right|^2 & = X_k \cdot \overline X_k = \\ & = (W^{-k} s_{N-1} - s_{N-2})(\overline{[W^{-k}]} s_{N-1} - s_{N-2}) = \\ & = (W^{-k} s_{N-1} - s_{N-2})(W^k s_{N-1} - s_{N-2}) = \\ & = s_{N-1}^2 - (W^k + W^{-k}) s_{N-1} s_{N-2} + s_{N-2}^2 = \\ & = s_{N-1}^2 - 2 \cos \left( \frac{2 \pi k}N \right) s_{N-1} s_{N-2} + s_{N-2}^2 \end{align}$

Устойчивость алгоритма

Процесс рекуррентного вычисления членов последовательности $s_n$ является цифровым БИХ-фильтром второго порядка. Как и любой БИХ-фильтр, он чувствителен к ошибкам, которые возникают в результате квантования и использования арифметических операций со словами конечной длины. Более того, поскольку оба полюса фильтра ($z=e^{ -\frac{2 \pi i}N}$ и $z=e^{ \frac{2 \pi i}N}$) лежат на единичной окружности, ошибки округления могут привести и к неустойчивости фильтра. В связи с этим, алгоритм Гёрцеля следует применять с осторожностью при больших длинах окон (большие значения $N$), особенно при использовании арифметики с низкой разрядностью.

Вычислительная эффективность алгоритма

Для вычисления одного частотного компонента ДПФ комплексной последовательности отсчётов длины $N$ с помощью алгоритма Гёрцеля требуется $2N+4$ умножений и $4N+4$ сложений / вычитаний (для действительной последовательности — $N+2$ умножения и $2N+1$ сложений), не считая затрат на вычисление постоянных коэффициентов $2 \cos \left( \frac{2 \pi k}N \right)$ и $e^{ \frac{2 \pi i}N k}$. При этом метод не требует хранения каких-либо таблиц коэффициентов, а основной объём арифметических вычислений метода может производиться по мере поступления входных отсчётов $x_n$.

Вычисление одного частотного компонента непосредственно по формуле-определению дискретного преобразования Фурье требует большего числа арифметических действий (в комплексном случае $4N$ умножений и $4N$ сложений, а в действительном $2N$ умножений и $4N$ сложений), чем алгоритм Гёрцеля, хотя асимптотически требует также $O(N)$ действий. Кроме того, для эффективного проведения вычислений по прямой формуле требуется хранить таблицу коэффициентов.

Другой альтернативой алгоритму Гёрцеля является быстрое преобразование Фурье. БПФ-алгоритм Кули-Тьюки по основанию 2 требует $2 \log_2 N$ умножений и $3 \log_2 N$ сложений на вычисление одного частотного компонента (а в случае действительной входной последовательности количество арифметических действий уменьшается вдвое относительно приведённых цифр), однако все частотные компоненты должны вычисляться одновременно. Когда число частотных компонентов, подлежащих вычислению, невелико, то применение алгоритма Гёрцеля эффективнее, чем применение БПФ. Если необходимо вычислить M частотных компонентов, то применение алгоритма Гёрцеля выгоднее при условии

$M < \frac{5}{6} \log_2 N$

({{{2}}})

Кроме того, алгоритмы БПФ должны применяться к полным блокам данных длины N и могут требовать хранения таблиц коэффициентов для эффективной реализации. Семейство алгоритмов быстрого преобразования Фурье включает алгоритмы с различными свойствами и вычислительной эффективностью, в том числе и так называемые усечённые алгоритмы БПФ^[2], позволяющие вычислять подмножество набора частотных компонентов. В каждом случае решение вопроса о предпочтительности использования алгоритма Гёрцеля или БПФ зависит от выбора конкретного варианта БПФ, длины блока входных данных и количества частотных компонентов, которые необходимо вычислить.

Примечания

1. ↑ G. Goertzel, «An Algorithm for the Evaluation of Finite Trigonometric Series» // American Mathematical Monthly, Vol. 65, Jan. 1958, pp. 34-35.
2. ↑ Pruned FFTs with FFTW. Архивировано из первоисточника 5 мая 2012. Проверено 23 сентября 2010.

Литература

• Эммануил С. Айфичер, Барри У. Джервис. Цифровая обработка сигналов: практический подход = 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

Ссылки

• Алгоритм Герцеля (Goertzel algorithm)
• Динамический пересчет спектральных отсчетов на каждом такте дискретизации. Модифицированный алгоритм Герцеля