Введение
Техника в цифровой обработке сигналов
Алгоритм Гёртцеля — это техника в цифровой обработке сигналов (DSP) для эффективного вычисления отдельных членов дискретного преобразования Фурье (DFT). Он полезен в определенных практических приложениях, таких как распознавание тонов многочастотной сигнализации (DTMF), генерируемых кнопками клавиатуры традиционного аналогового телефона. Алгоритм был впервые описан Джеральдом Гёртцелем в 1958 году. Как и DFT, алгоритм Гёртцеля анализирует одну выбранную частотную компоненту из дискретного сигнала. В отличие от прямого вычисления DFT, алгоритм Гёртцеля применяет один вещественный коэффициент на каждой итерации, используя арифметику с вещественными числами для вещественных входных последовательностей. Для охвата полного спектра (за исключением использования для непрерывного потока данных, где коэффициенты повторно используются для последующих вычислений, что имеет вычислительную сложность, эквивалентную скользящему DFT), алгоритм Гёртцеля имеет более высокую вычислительную сложность, чем алгоритмы быстрого преобразования Фурье (FFT), но для вычисления небольшого числа выбранных частотных компонент он более численно эффективен. Простая структура алгоритма Гёртцеля делает его хорошо подходящим для небольших процессоров и встраиваемых приложений. Алгоритм Гёртцеля также может быть использован "в обратном порядке" как функция синтеза синусоиды, требующая всего 1 умножения и 1 вычитания на сгенерированный отсчет.
The Goertzel algorithm is a technique in digital signal processing (DSP) for efficient evaluation of the individual terms of the discrete Fourier transform (DFT). It is useful in certain practical applications, such as recognition of dual tone multi frequency signaling (DTMF) tones produced by the push buttons of the keypad of a traditional analog telephone. The algorithm was first described by Gerald Goertzel in 1958. Like the DFT, the Goertzel algorithm analyses one selectable frequency component from a discrete signal. Unlike direct DFT calculations, the Goertzel algorithm applies a single real valued coefficient at each iteration, using real valued arithmetic for real valued input sequences. For covering a full spectrum (except when using for continuous stream of data where coefficients are reused for subsequent calculations, which has computational complexity equivalent of sliding DFT), the Goertzel algorithm has a higher order of complexity than fast Fourier transform (FFT) algorithms, but for computing a small number of selected frequency components, it is more numerically efficient. The simple structure of the Goertzel algorithm makes it well suited to small processors and embedded applications. The Goertzel algorithm can also be used "in reverse" as a sinusoid synthesis function, which requires only 1 multiplication and 1 subtraction per generated sample.
Численная стабильность
Можно наблюдать, что полюса Z-преобразования фильтра расположены в точках и на окружности единичного радиуса с центром в начале комплексной плоскости Z-преобразования. Это свойство указывает на то, что процесс фильтрации является гранично устойчивым и подвержен накоплению численных ошибок при вычислениях с использованием арифметики низкой точности и длинных входных последовательностей. Численно устойчивую версию предложил Кристиан Рейнш.
Фассовое обнаружение
Для этого приложения требуется та же оценка члена ДПФ, как обсуждалось в предыдущем разделе, с использованием входного потока, содержащего действительные или комплексные значения. Затем фаза сигнала может быть оценена следующим образом:
с соблюдением необходимых мер предосторожности при вычислении обратного тангенса для учета особенностей, квадранта и других подобных факторов.
Сложные сигналы в реальной арифметике
Поскольку сложные сигналы линейно раскладываются на действительную и мнимую части, алгоритм Гёртцеля можно вычислить с использованием арифметики с плавающей точкой отдельно для последовательности действительных частей, получая , и для последовательности мнимых частей, получая . Затем эти два комплексных частичных результата можно объединить: