Дискретное преобразование Фурье

быстрый преобразование фурье Дискретное преобразование Фурье (ДПФ) периодического дискретного сигнала x (n) с периодом N определяется как.

(1.1),.

где — основная частота преобразования (бин ДПФ).

Выражение (1.1) можно переписать в виде.

(1.2),.

где.

(1.3).

Коэффициент W_N называется поворачивающим множителем. Легко показать, что является периодической функцией с периодом N.

(1.4).

Поэтому ДПФ X (k) также является периодической функцией по аргументу k с периодом N.

Дискретное преобразование Фурье может быть использовано и для представления сигнала x (n) конечной длины N, определенного при n=0,1,…, N-1 и равного нулю вне интервала [0,N-1]. Действительно, такой сигнал можно рассматривать как один период соответствующего периодического сигнала и использовать преобразования (12.2). Следует только считать, что вне интервала [0,N-1] X (k) и x (n) равны нулю.

Если сравнить ДПФ конечного дискретного сигнала со спектром этого же сигнала, определяемым выражением.

(1.5),.

то очевидно, что ДПФ представляет собой N отсчетов спектра, взятых на периоде с интервалом дискретизации по частоте, равным .

В случае, когда x (n) является комплексным, при прямом вычислении N-точечного ДПФ нужно выполнить для каждого значения k (N-1) умножений и (N-1) сложений комплексных чисел или 4(N-1) умножений и 2(N-1) сложений действительных чисел. Для всех N значений k=0,1,…, N-1 требуется (N-1)² умножений и N (N-1) сложений комплексных чисел. Для больших значений N (порядка нескольких сотен или тысяч) прямое вычисление ДПФ по выражению (12.2) требует выполнения весьма большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычислений в реальном масштабе времени.