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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Гёрцеля (англ. 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}}})

.

Устойчивость алгоритма[править | править вики-текст]

Процесс рекуррентного вычисления членов последовательности 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. Проверено 23 сентября 2010. Архивировано из первоисточника 5 мая 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

Ссылки[править | править вики-текст]