[an error occurred while processing this directive]
|
Одна точка DFT является линейной комбинацией входных выборок окна. То есть ее можно определить как дискретный фильтр. Что и сделано в алгоритме герцеля. ДПФ представлен в виде БИХ-фильтра.
Его передаточная функция имеет следующий вид:
N-1 -1 n
H(z) = sum ((exp(-j*k*2*pi/N)*z ))
n=0
что есть
-N
1 - z
H(z) = ----------------------------
-1
1 - exp(-j*k*2*pi/N)*z
Немного помудрив с комплексными числами (опущено), получаем фильтр второго порядка:
Wk = 2*pi*k/N
q(n) = x(n) + 2*cos(Wk)*q(n-1) - q(n-2).
y(n) = q(n) - q(n-1)*exp(-j*Wk)
Итого для получения результата в одной точке k DFT в окне длиной N надо N раз посчитать q(n), для чего нужно одно вещественное умножение, одно сложение и одно вычитание на одну выборку. И потом, один раз для получения результата DFT посчитать y(N), для чего требуется одно комплексное умножение и одно вычитание. Как правило после алгоритма Герцеля интересует только модуль, по этому последний шаг из комплексного умножения превращаем в вещественное:
|y(k)| = q(n)*q(n) - 2*cos(Wk)*q(n)*q(n-1) + q(n-1)*q(n-1)
повторю - это вычисление делается всего один раз. В конце. После N вычислений q(n).
Окончательный итог: имеем необходимость держать всего один коэффициент на каждую частотную точку анализа - это 2*cos(Wk). Требуется на каждую точку ресурсов - N+4 умножений, 2N+2 сложений. Сравните это например с корреляцией. Дает большой выигрыш перед FFT если интересны только несколько спектральных отсчетов.
E-mail: info@telesys.ru