Б. Прямой метод вычисления ДПФ. Алгоритм Герцеля.

С тем чтобы пояснить сказанное в об эффективности прямого метода, раскроем формулу для случая, когда последовательность комплексных величин, причем вещественная часть коэффициент в мнимой части

Таким же образом представим комплексную величину

При этом согласно формуле (3.39) представляется в следующем виде:

где .

Из формулы (3.59) следует, что для нахождения при каждом значении к действительно нужно выполнить операций умножения вещественных чисел, тогда как общее их количество для всех к равно Эта величина была указана в когда говорилось о прямом методе вычисления ДПФ.

Согласно алгоритму Герцеля вычисление для -точечной последовательности при производится следующим образом. Для определения при каждом значении к N-точечная последовательность представляется как последовательность, получаемая на выходе искусственно вводимой в рассмотрение системы, для которой есть входная последовательность, является импульсной характеристикой этой системы, при принятии затем

Таким образом, находится как свертка заданной последовательности затем просто получается принятием в значения равным

Формулы (3.60) и (3.61) получаются следующим образом. Так как

то можно умножить в выражении правую его

часть на

Полученное выражение можно представить в виде

Эта формула равносильна взятым вместе формулами (3.60) и (3.61). Однако, применяя последние, можно как это было указано выше, использовать для нахождения ДПФ операцию свертки.