14. Общая характеристика ряда и интеграла Фурье, дискретного ряда Фурье и дискретного преобразования Фурье. Равенство Парсеваля.

1.4.2.2. Равенство Парсеваля. Пусть имеются две последовательности конечной длины и ДПФ которых равны и соответственно. В этом случае последовательность можно представить в виде обратного дискретного преобразования Фурье:

(1.141)

Умножим правую и левую часть данного выражения на и найдём среднее значение полученного произведения:

(1.142)

Изменив порядок суммирования в правой части последней формулы, получим:

(1.143)

Так как

(1.144)

то будем иметь:

(1.145)

Если то и тогда

(1.146)

где – энергия сигнала, вычисленная по переменной n (во вре­менной области), с новой строки – энергия сигнала, вычисленная по переменной k (в частотной области).

Это и есть равенство (теорема) Парсеваля, устанавливающее связь меж­ду энергией последовательности и её преобразованием Фурье

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

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

(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.