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

Дискретное преобразование Фурье (ДПФ) используется для преобразования сигнала из временной области в частотную. С другой стороны, ДПФ может использоваться для вычисления нескольких частотных точек, например 20, 25 и 30 точек из 256 возможных. Обычно, если необходимо рассчитать более чем log₂N точек из N, то быстрее рассчитать БПФ, а затем исключить ненужные точки. Если необходимо рассчитать несколько точек, то ДПФ быстрее.

где и

ДПФ вычисляется для одной точки из N, например, с номером 15:

где и

Использование алгоритма Герцеля сокращает количество операций и экономит время. Для вычисления ДПФ, необходимо вычислить большое количество комплексных коэффициентов. Для ДПФ размером N используется N² комплексных коэффициентов. При использовании алгоритма Герцеля понадобится всего два коэффициента для каждой частоты: один вещественный и один комплексный.

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

Алгоритм Герцеля позволяет обрабатывать данные в темпе их поступления, при этом нет необходимости ждать, пока заполнится буфер из N элементов. Схема такого преобразования представлена на рис. 6.8.

Рис. 6.8 Структурная схема фильтра, реализующего алгоритма Герцеля

Фильтр, реализующий подобный алгоритм может быть представлен, как БИХ фильтр второго порядка.

Алгоритм Герцеля может быть использован для подсчета ДПФ. Однако, его реализация имеет много общего с фильтрами. ДПФ или БПФ получают результат размерности N из исходных данных размерности N. Но фильтры БИХ и КИХ получают новое значение на выходе, как только получают новые данные на входе. Алгоритм вычисляет новое значение y_k(n) (см. рис.), для каждого нового x(n). Результат вычисления ДПФ X(k) будет равен y_k(n), если n = N. Так как каждое новое значение y_k(n) (где ) не ведет к получению конечного результата X(k), нет необходимости вычислять y_k(n) до тех пор пока n = N. Это подразумевает, что алгоритм Герцеля функционально эквивалентен БИХ фильтру второго порядка за исключением того, что выходной результат фильтра появляется только после N отсчетов данных.

В фильтре Герцеля Вычисления можно выделить две части - правую (рис.6.9) и левую (рис. 6.10).

Рис. 6.9. Левая часть фильтра, реализующего алгоритм Герцеля.

В этой схеме при выполнении вычислений вида

два промежуточных значения ; ; хранятся в памяти , а ;.

Для каждого нового отсчета x(n) и считываются из памяти данных и используются для вычисления нового значения .

Рис. 6.10. Правая часть схемы фильтра, реализующего алгоритм Герцеля.