Отправлено SM 04 апреля 2003 г. 11:08 В ответ на: если кому-нибудь не лень - расскажите про алгоритм Герцеля, для чего и как... отправлено yes 04 апреля 2003 г. 10:33

Одна точка 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 если интересны только несколько спектральных отсчетов.