Алгоритм Гёрцеля: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
Mbalabin (обсуждение | вклад) |
Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0 |
||
(не показано 29 промежуточных версий 18 участников) | |||
Строка 1: | Строка 1: | ||
Алгоритм Гёрцеля ( |
'''Алгоритм Гёрцеля''' ({{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>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^{ |
||
Преобразуем исходное определение <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, |
{{Формула|<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>| |
{{Формула|<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(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 |
Передаточную функцию <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( |
{{Формула|<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>| |
{{Формула|<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} |
||
|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</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'' частотных компонентов, то применение алгоритма Гёрцеля выгоднее при условии |
||
⚫ | |||
⚫ | |||
Кроме того, алгоритмы БПФ должны применяться к полным блокам данных длины ''N'' и могут требовать хранения таблиц коэффициентов для эффективной реализации. Семейство алгоритмов быстрого преобразования Фурье включает алгоритмы с различными свойствами и вычислительной эффективностью, в том числе и так называемые усечённые алгоритмы БПФ<ref> |
Кроме того, алгоритмы БПФ должны применяться к полным блокам данных длины ''N'' и могут требовать хранения таблиц коэффициентов для эффективной реализации. Семейство алгоритмов быстрого преобразования Фурье включает алгоритмы с различными свойствами и вычислительной эффективностью, в том числе и так называемые усечённые алгоритмы БПФ<ref> |
||
{{cite web |
{{cite web |
||
| |
|url = http://www.fftw.org/pruned.html |
||
| |
|title = Pruned FFTs with FFTW |
||
| |
|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]. В отличие от быстрого преобразования Фурье, вычисляющего все частотные компоненты ДПФ, алгоритм Гёрцеля позволяет эффективно вычислить значение одного частотного компонента.
Алгоритм Гёрцеля является популярным алгоритмом для решения задачи детектирования и декодирования тональных сигналов в телефонии.
Варианты названия алгоритма
[править | править код]В русскоязычной литературе нет устоявшегося варианта транскрипции фамилии автора алгоритма. Распространены варианты «Алгоритм Герцеля», «Алгоритм Гертцеля», «Алгоритм Горцеля» и другие.
Описание алгоритма
[править | править код]Пусть — измеренные значения сигнала, которые являются входными данными для дискретного преобразования Фурье, а — частотные компоненты дискретного преобразования Фурье, по определению равные . Для расчёта с помощью алгоритма Гёрцеля:
- Последовательно вычисляются члены последовательности для по рекуррентной формуле , где .
- Искомое значение частотного компонента получается как .
В случае, когда требуется вычислить только мощность сигнала, а его фаза не важна, на втором этапе алгоритма вместо комплексного значения частотного компонента вычисляется квадрат его модуля по формуле
Для удобства записи введём обозначение . Определение k-го частотного компонента дискретного преобразования Фурье тогда примет вид . Также заметим, что , и для любого действительного выполняется равенство
Преобразуем исходное определение :
Процесс последовательного вычисления стоящих во вложенных скобках выражений мы теперь можем записать с помощью рекуррентной формулы:
При этом для вычисления примем , а искомое значение k-го частотного компонента выражается как . Полученное выражение для представляет собой БИХ-фильтр первого порядка:
(1) |
Применив z-преобразование к обеим частям выражения (1), получим
где и — образы дискретных временных сигналов и соответственно. Из этого выражения выразим передаточную функцию фильтра (1) и преобразуем её, домножив числитель и знаменатель на :
Передаточную функцию можно представить в виде произведения функций и , что во временно́й области соответствует последовательному соединению двух фильтров с передаточными функциями и . Таким образом, исходный фильтр (1) может быть представлен в виде комбинации двух фильтров:
(2) |
(3) |
Поскольку для вычисления не требуется всех выходных значений фильтра (3), а только значение , то вычисление можно опустить благодаря тому, что фильтр (3) является КИХ-фильтром, выход которого зависит только от входов и . Значение можем тогда выразить следующим образом:
Мощность сигнала тогда может быть вычислена как
Устойчивость алгоритма
[править | править код]Процесс рекуррентного вычисления членов последовательности является цифровым БИХ-фильтром второго порядка. Как и любой БИХ-фильтр, он чувствителен к ошибкам, которые возникают в результате квантования и использования арифметических операций со словами конечной длины. Более того, поскольку оба полюса фильтра ( и ) лежат на единичной окружности, ошибки округления могут привести и к неустойчивости фильтра. В связи с этим, алгоритм Гёрцеля следует применять с осторожностью при больших длинах окон (большие значения ), особенно при использовании арифметики с низкой разрядностью.
Вычислительная эффективность алгоритма
[править | править код]Для вычисления одного частотного компонента ДПФ комплексной последовательности отсчётов длины с помощью алгоритма Гёрцеля требуется умножений и сложений / вычитаний (для действительной последовательности — умножения и сложений), не считая затрат на вычисление постоянных коэффициентов и . При этом метод не требует хранения каких-либо таблиц коэффициентов, а основной объём арифметических вычислений метода может производиться по мере поступления входных отсчётов .
Вычисление одного частотного компонента непосредственно по формуле-определению дискретного преобразования Фурье требует большего числа арифметических действий (в комплексном случае умножений и сложений, а в действительном умножений и сложений), чем алгоритм Гёрцеля, хотя асимптотически требует также действий. Кроме того, для эффективного проведения вычислений по прямой формуле требуется хранить таблицу коэффициентов.
Другой альтернативой алгоритму Гёрцеля является быстрое преобразование Фурье. БПФ-алгоритм Кули — Тьюки по основанию 2 требует умножений и сложений на вычисление одного частотного компонента (а в случае действительной входной последовательности количество арифметических действий уменьшается вдвое относительно приведённых значений), однако все частотные компоненты должны вычисляться одновременно. Когда число частотных компонентов, подлежащих вычислению, невелико, то применение алгоритма Гёрцеля эффективнее, чем применение БПФ. Если необходимо вычислить M частотных компонентов, то применение алгоритма Гёрцеля выгоднее при условии
Кроме того, алгоритмы БПФ должны применяться к полным блокам данных длины N и могут требовать хранения таблиц коэффициентов для эффективной реализации. Семейство алгоритмов быстрого преобразования Фурье включает алгоритмы с различными свойствами и вычислительной эффективностью, в том числе и так называемые усечённые алгоритмы БПФ[2], позволяющие вычислять подмножество набора частотных компонентов. В каждом случае решение вопроса о предпочтительности использования алгоритма Гёрцеля или БПФ зависит от выбора конкретного варианта БПФ, длины блока входных данных и количества частотных компонентов, которые необходимо вычислить.
Примечания
[править | править код]- ↑ G. Goertzel, «An Algorithm for the Evaluation of Finite Trigonometric Series» // American Mathematical Monthly, Vol. 65, Jan. 1958, pp. 34-35.
- ↑ 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.