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

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

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

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

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

1. Последовательно вычисляются члены последовательности sn для  по рекуррентной формуле , где s − 1 = s − 2 = 0;

2. Искомое значение частотного компонента получается как .

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

({{{2}}})

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

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

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

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

({{{2}}})

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

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