Алгоритм Гёрцеля: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[непроверенная версия][отпатрулированная версия]
Содержимое удалено Содержимое добавлено
Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0
 
(не показано 29 промежуточных версий 18 участников)
Строка 1: Строка 1:
Алгоритм Гёрцеля ([[Английский язык|англ.]] Goertzel algorithm) — это специальная реализация [[Дискретное преобразование Фурье|дискретного преобразования Фурье]] (ДПФ) в форме [[БИХ-фильтр|рекурсивного фильтра]]. Данный алгоритм был предложен Джеральдом Гёрцелем в 1958 году <ref>G. Goertzel, "An Algorithm for the Evaluation of Finite Trigonometric Series," American Mathematical Monthly, Vol. 65, Jan. 1958, pp. 34-35.</ref>. В отличие от [[Быстрое преобразование Фурье|быстрого преобразования Фурье]], вычисляющего все частотные компоненты ДПФ, алгоритм Гёрцеля позволяет эффективно вычислить значение одного частотного компонента.
'''Алгоритм Гёрцеля''' ({{lang-en|Goertzel algorithm}}) — это специальная реализация [[Дискретное преобразование Фурье|дискретного преобразования Фурье]] (ДПФ) в форме [[БИХ-фильтр|рекурсивного фильтра]]. Данный алгоритм был предложен Джеральдом Гёрцелем в 1958 году<ref>G. Goertzel, «An Algorithm for the Evaluation of Finite Trigonometric Series» // American Mathematical Monthly, Vol. 65, Jan. 1958, pp. 34-35.</ref>. В отличие от [[Быстрое преобразование Фурье|быстрого преобразования Фурье]], вычисляющего все [[частотная компонента | частотные компоненты]] ДПФ, алгоритм Гёрцеля позволяет эффективно вычислить значение одного частотного компонента.


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


== Варианты названия алгоритма ==
== Варианты названия алгоритма ==
Строка 8: Строка 8:
== Описание алгоритма ==
== Описание алгоритма ==


Пусть <math>x_n,\ n = 0, \dots, N - 1</math> — измеренные значения сигнала, которые являются входными данными для дискретного преобразования Фурье, а <math>X_k,\ k = 0, \dots, N - 1</math> — частотные компоненты дискретного преобразования Фурье, по определению равные <math>X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}N k n}</math>. Для расчёта <math>X_k</math> с помощью алгоритма Гёрцеля:
Пусть <math>X_k = \sum_{n=0}^{N-1} {x_n e^{ -\frac{2 \pi i}N k n}}</math> — k-й частотный компонент компонент дискретного преобразования Фурье (здесь и далее будут использоваться обозначения, принятые в статье «[[Дискретное преобразование Фурье]]»). Для расчёта <math>X_k</math> с помощью алгоритма Гёрцеля:
# Последовательно вычисляются члены последовательности <math>s_n</math> для <math>n = 0, \dots, N - 1</math> по рекуррентной формуле <math>s_n = 2 \cos\left(\frac{2 \pi k}N\right) s_{n-1} - s_{n-2} + x_n</math>, где <math>s_{-1} = s_{-2} = 0</math>.
# Искомое значение частотного компонента получается как <math>X_k = e^{\frac{2 \pi i}N k} s_{N-1} - s_{N-2}</math>.


В случае, когда требуется вычислить только мощность сигнала, а его фаза не важна, на втором этапе алгоритма вместо комплексного значения частотного компонента вычисляется квадрат его модуля по формуле
# Последовательно вычисляются члены последовательности <math>s_n</math> для <math>n = 0, \dots, N-1</math> по рекуррентной формуле <math>s_n = 2 \cos \left( \frac{2 \pi k}N \right) s_{n-1} - s_{n-2} + x_n</math> ,где <math>s_{-1} = s_{-2} = 0</math>;
# Искомое значение частотного компонента получается как <math>X_k = e^{ \frac{2 \pi i}N k} s_{N-1} - s_{N-2}</math>.
{{Формула|<math>|X_k|^2 = s_{N-1}^2 - 2 \cos\left(\frac{2 \pi k}N\right) s_{N-1} s_{N-2} + s_{N-2}^2.</math>}}


{{Вывод |
В случае, когда требуется вычислить только мощность сигнала, а его фаза не важна, на втором этапе алгоритма вместо комплексного значения частотного компонента вычисляется квадрат его модуля по формуле:
{{Формула|<math>\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</math>}}.


Для удобства записи введём обозначение <math>W = e^{-\frac{2 \pi i}N}</math>. Определение ''k''-го частотного компонента дискретного преобразования Фурье тогда примет вид <math>X_k = \sum_{n=0}^{N-1} x_n W^{kn}</math>. Также заметим, что <math>W^{-N} = e^{2 \pi i} = 1</math>, и для любого действительного <math>k</math> выполняется равенство
{{Вывод|
: <math>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).</math>

Для удобства записи введём обозначение <math>W = e^{ -\frac{2 \pi i}N }</math>. Определение k-го частотного компонента дискретного преобразования Фурье тогда примет вид <math>X_k = \sum_{n=0}^{N-1} {x_n W^{kn}}</math>. Также заметим, что <math>W^{-N} = e^{2 \pi i} = 1</math> и для любого действительного <math>k</math> выполняется равенство <math>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)</math>.


Преобразуем исходное определение <math>X_k</math>:
Преобразуем исходное определение <math>X_k</math>:


<math>
: <math>
\begin{align}
\begin{align}
X_k & = \sum_{n=0}^{N-1} {x_n W^{kn}} = \\
X_k & = \sum_{n=0}^{N-1} {x_n W^{kn}} = \\
& = W^{-kN} \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}} = \\
& = \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} = \\
& = 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}
& = \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}
\end{align}
</math>
</math>
Строка 34: Строка 34:
Процесс последовательного вычисления стоящих во вложенных скобках выражений мы теперь можем записать с помощью рекуррентной формулы:
Процесс последовательного вычисления стоящих во вложенных скобках выражений мы теперь можем записать с помощью рекуррентной формулы:


{{Формула|<math>y_n = W^{-k} y_{n-1} + x_n, \; n=0,1,2,\dots,N-1</math>}}
{{Формула|<math>y_n = W^{-k} y_{n-1} + x_n,\ n = 0, 1, 2, \dots, N - 1.</math>}}


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


{{Формула|<math>y_n - W^{-k} y_{n-1} = x_n</math>|(1)}}
{{Формула|<math>y_n - W^{-k} y_{n-1} = x_n.</math>|1}}


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


{{Формула|<math>(1 - W^{-k} z^{-1}) Y(z) = X(z)</math>}}
{{Формула|<math>\big(1 - W^{-k} z^{-1}\big) Y(z) = X(z),</math>}}


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


<math>
<math>
\begin{align}
\begin{align}
H(z) & = \frac{Y(z)}{X(z)} =\\
H(z) & = \frac{Y(z)}{X(z)} =\\
& = \frac 1 {1 - W^{-k} z^{-1}} = \\
& = \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 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 - (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}}
& = \frac{1 - W^k z^{-1}}{1 - 2 \cos \left( \frac{2 \pi k}N \right) z^{-1} + z^{-2}}.
\end{align}
\end{align}
</math>
</math>


Передаточную функцию <math>H(z)</math> можно представить в виде произведения функций <math>P(z) = \frac 1 {1 - 2 \cos \left( \frac{2 \pi k}N \right) z^{-1} + z^{-2}}</math> и <math>Q(z) = 1 - W^k z^{-1}</math>, что во временной области соответствует последовательному соединению двух фильтров с передаточными функциями <math>P(z)</math> и <math>Q(z)</math>. Таким образом, исходный фильтр (1) может быть представлен в виде комбинации двух фильтров:
Передаточную функцию <math>H(z)</math> можно представить в виде произведения функций <math>P(z) = \frac 1 {1 - 2 \cos\left(\frac{2 \pi k}N\right) z^{-1} + z^{-2}}</math> и <math>Q(z) = 1 - W^k z^{-1}</math>, что во временно́й области соответствует последовательному соединению двух фильтров с передаточными функциями <math>P(z)</math> и <math>Q(z)</math>. Таким образом, исходный фильтр (1) может быть представлен в виде комбинации двух фильтров:
{{Формула|<math>s_n - 2 \cos \left( \frac{2 \pi k}N \right) s_{n-1} + s_{n-2} = x_n</math>|(2)}}
{{Формула|<math>s_n - 2 \cos \left(\frac{2 \pi k}N\right) s_{n-1} + s_{n-2} = x_n,</math>|2}}
{{Формула|<math>y_n = s_n - W^k s_{n-1}</math>|(3)}}
{{Формула|<math>y_n = s_n - W^k s_{n-1}.</math>|3}}
Поскольку для вычисления <math>X_k</math> не требуется всех выходных значений фильтра (3), а только значение <math>y_{N-1}</math>, то вычисление <math>y_0, y_1, \dots, y_{N-2}</math> можно опустить благодаря тому, что фильтр (3) является [[КИХ-фильтр]]ом, выход которого <math>y_n</math> зависит только от входов <math>s_n</math> и <math>s_{n-1}</math>. Значение <math>X_k</math> можем тогда выразить следующим образом:
Поскольку для вычисления <math>X_k</math> не требуется всех выходных значений фильтра (3), а только значение <math>y_{N-1}</math>, то вычисление <math>y_0, y_1, \dots, y_{N-2}</math> можно опустить благодаря тому, что фильтр (3) является [[КИХ-фильтр]]ом, выход которого <math>y_n</math> зависит только от входов <math>s_n</math> и <math>s_{n-1}</math>. Значение <math>X_k</math> можем тогда выразить следующим образом:
{{Формула|<math>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}</math>}}.
{{Формула|<math>X_k = W^{-k} y_{N-1} = W^{-k} \big(s_{N-1} - W^k s_{N-2}\big) = W^{-k} s_{N-1} - s_{N-2}.</math>}}
Мощность сигнала тогда может быть вычислена как:


Мощность сигнала тогда может быть вычислена как
<math>
: <math>
\begin{align}
\begin{align}
\left| X_k \right|^2 & = X_k \cdot \overline X_k = \\
|X_k|^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})(\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}) = \\
& = (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 - (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
& = 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}
\end{align}
</math>
</math>

}}
}}


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


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


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

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


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


Другой альтернативой алгоритму Гёрцеля является быстрое преобразование Фурье. БПФ-алгоритм Кули-Тьюки по основанию 2 требует <math>2 \log_2 N</math> умножений и <math>3 \log_2 N</math> сложений на вычисление одного частотного компонента (а в случае действительной входной последовательности количество арифметических действий уменьшается вдвое относительно приведённых цифр), однако все частотные компоненты должны вычисляться одновременно. Когда число частотных компонентов, подлежащих вычислению, невелико, то применение алгоритма Гёрцеля эффективнее, чем применение БПФ. Если необходимо вычислить ''M'' частотных компонентов, то применение алгоритма Гёрцеля выгоднее при условии
Другой альтернативой алгоритму Гёрцеля является [[быстрое преобразование Фурье]]. БПФ-алгоритм Кули — Тьюки по основанию 2 требует <math>2 \log_2 N</math> умножений и <math>3 \log_2 N</math> сложений на вычисление одного частотного компонента (а в случае действительной входной последовательности количество арифметических действий уменьшается вдвое относительно приведённых значений), однако все частотные компоненты должны вычисляться одновременно. Когда число частотных компонентов, подлежащих вычислению, невелико, то применение алгоритма Гёрцеля эффективнее, чем применение БПФ. Если необходимо вычислить ''M'' частотных компонентов, то применение алгоритма Гёрцеля выгоднее при условии
{{EF|:|<math>M < \frac{5}{6} \log_2 N.</math>}}

{{Формула|<math>M < \frac{5}{6} \log_2 N</math>}}


Кроме того, алгоритмы БПФ должны применяться к полным блокам данных длины ''N'' и могут требовать хранения таблиц коэффициентов для эффективной реализации. Семейство алгоритмов быстрого преобразования Фурье включает алгоритмы с различными свойствами и вычислительной эффективностью, в том числе и так называемые усечённые алгоритмы БПФ<ref>
Кроме того, алгоритмы БПФ должны применяться к полным блокам данных длины ''N'' и могут требовать хранения таблиц коэффициентов для эффективной реализации. Семейство алгоритмов быстрого преобразования Фурье включает алгоритмы с различными свойствами и вычислительной эффективностью, в том числе и так называемые усечённые алгоритмы БПФ<ref>
{{cite web
{{cite web
| url = http://www.fftw.org/pruned.html
|url = http://www.fftw.org/pruned.html
| title = Pruned FFTs with FFTW
|title = Pruned FFTs with FFTW
| accessdate = 2010-09-23
|accessdate = 2010-09-23
|archiveurl = https://www.webcitation.org/67PvHwY75?url=http://www.fftw.org/pruned.html
|archivedate = 2012-05-04
}}
}}
</ref>, позволяющие вычислять подмножество набора частотных компонентов. В каждом случае решение вопроса о предпочтительности использования алгоритма Гёрцеля или БПФ зависит от выбора конкретного варианта БПФ, длины блока входных данных и количества частотных компонентов, которые необходимо вычислить.
</ref>, позволяющие вычислять подмножество набора частотных компонентов. В каждом случае решение вопроса о предпочтительности использования алгоритма Гёрцеля или БПФ зависит от выбора конкретного варианта БПФ, длины блока входных данных и количества частотных компонентов, которые необходимо вычислить.
Строка 99: Строка 101:


== Литература ==
== Литература ==
*{{книга
* {{книга
|автор = Эммануил С. Айфичер, Барри У. Джервис.
|автор = Эммануил С. Айфичер, Барри У. Джервис.
|заглавие = Цифровая обработка сигналов: практический подход
|заглавие = Цифровая обработка сигналов: практический подход
Строка 110: Строка 112:
|isbn = 5-8459-0710-1
|isbn = 5-8459-0710-1
}}
}}
*{{книга
* {{книга
|автор = Блейхут Р.
|автор = Блейхут Р.
|заглавие = Быстрые алгоритмы цифровой обработки сигналов
|заглавие = Быстрые алгоритмы цифровой обработки сигналов
Строка 121: Строка 123:
}}
}}


== Ссылки ==
[[Категория:Цифровая обработка сигналов]]
* [https://web.archive.org/web/20161128050447/http://ru.dsplib.org/content/goertzel.html Алгоритм Герцеля (Goertzel algorithm)]
* [http://www.dsplib.ru/content/goertzelmod/goertzelmod.html Динамический пересчет спектральных отсчетов на каждом такте дискретизации. Модифицированный алгоритм Герцеля ]


[[Категория:Цифровая обработка сигналов]]
[[en:Goertzel algorithm]]
[[Категория:Преобразование Фурье]]
[[de:Goertzel-Algorithmus]]
[[it:Algoritmo di Goertzel]]
[[he:אלגוריתם גרצל]]
[[pl:Algorytm Goertzla]]

Текущая версия от 08:10, 29 августа 2019

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

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

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

[править | править код]

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

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

[править | править код]

Пусть  — измеренные значения сигнала, которые являются входными данными для дискретного преобразования Фурье, а  — частотные компоненты дискретного преобразования Фурье, по определению равные . Для расчёта с помощью алгоритма Гёрцеля:

  1. Последовательно вычисляются члены последовательности для по рекуррентной формуле , где .
  2. Искомое значение частотного компонента получается как .

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

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

[править | править код]

Процесс рекуррентного вычисления членов последовательности является цифровым БИХ-фильтром второго порядка. Как и любой БИХ-фильтр, он чувствителен к ошибкам, которые возникают в результате квантования и использования арифметических операций со словами конечной длины. Более того, поскольку оба полюса фильтра ( и ) лежат на единичной окружности, ошибки округления могут привести и к неустойчивости фильтра. В связи с этим, алгоритм Гёрцеля следует применять с осторожностью при больших длинах окон (большие значения ), особенно при использовании арифметики с низкой разрядностью.

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

[править | править код]

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

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

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

Кроме того, алгоритмы БПФ должны применяться к полным блокам данных длины 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. Дата обращения: 23 сентября 2010. Архивировано 4 мая 2012 года.

Литература

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