Прямой метод вычисления дпф. Основные подходы к улучшению эффективности вычисления дпф.

Рассмотрим непосредственное вычисление прямого ДПФ

(1.147) где

Выражение для X(k) можно представить в виде следующей системы уравнений:

(1.148)

Видно, что для того, чтобы получить коэффициент X(0) необходимо выполнить N операций комплексного умножения и (N – 1) операцию ком­плексного сложения. Для получения X(1) требуется также N операций комплексного умножения и (N – 1) операций комплексного сложения.

Для того, чтобы вычислить два коэффициента X(0) и X(1) требуется 2N операций комплексного умножения и 2(N – 1) операция комплексного сложения.

Продолжив наши рассуждения дальше, получим, что, если требуется определить все N коэффициентов X(0), X(1), …, X(N – 1), то необходимо выполнить N² операций комплексного умножения и N(N – 1) операций комплексного сложения. Представив (1.147) в виде последовательности операций над вещественными числами, получим откуда следует, что на каждое умножение комплексных чисел требуется четыре умножения и два сложения вещественных чисел, а каждое сложение комплексных чисел получается за счет сложения двух вещественных. Таким образом, при прямом вычислении одного значения ДПФ необходимо выполнения 4N вещественных умножений и (4N – 2) вещественных сложений. Для полного вычисления N-точечного ДПФ общее число умножений вещественных чисел достигнет 4N², а сложений N(4N – 2).

Вдобавок к умножению и сложению при вычислении ДПФ на универсальных или специализированных ЭВМ необходимо хранить N значений входной последовательности x(n), столько же комплексных экспонент и постоянно обращаться к ним в процессе вычислений. Так как количество запоминаний и обращений к памяти в вычислительных алго­ритмах обычно пропорционально числу арифметических операций, то это число считается разумной мерой сложности вычислительного алго­ритма или времени, необходимого для выполнения вычислений. По­скольку количество операций, а, следовательно, и время вычислений приблизительно пропорциональны N², то при прямом методе вычисления ДПФ необходимое число арифметических операций становится весьма большим при больших значениях N.