Быстрое преобразование Фурье

Для вычисления одного коэффициента ДПФ по формуле

                                     (4)

необходимо выполнить N комплексных умножений и сложений. Таким образом, расчет всего ДПФ, содержащего N коэффициентов, потребует N² пар операций «умножение-сложение». Число операций возрастает пропорционально квадрату размерности ДПФ. Однако если N не является простым числом и может быть разложено на множители, процесс вычислений можно ускорить, разделив анализируемый набор отсчетов на части, вычислив их ДПФ и объединив результаты. Такие способы вычисления ДПФ называются быстрым преобразованием Фурье (БПФ; английский термин – Fast Fourier Transform, FFT) и повсеместно используются на практике.

При реализации БПФ возможно несколько вариантов организации вычислений в зависимости от способа деления последовательности отсчетов на части (прореживание по времени либо по частоте) и от того, на сколько фрагментов производится разбиение последовательности на каждом шаге (основание БПФ).

Познакомиться с алгоритмами БПФ можно в [1].

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

Пример 1.Поиск частотных компонентов зашумленного сигнала. Данные дискретизированны на частоте 1000 Гц. Сигнал содержит частоты 50 Гц и 120 Гц и поврежден неким шумом.

t = 0:0.001:0.6;

x = sin(2*pi*50*t)+sin(2*pi*120*t);

y = x + 2*randn(size(t));

plot(1000*t(1:50),y(1:50))

title('Signal Corrupted with Zero-Mean Random Noise')

xlabel('time (milliseconds)')

Рис.8. Зашумленный сигнал

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

Y = fft(y,512);

Определим спектр мощности

Pyy = Y.* conj(Y) / 512; 

Построим график первых 257 точек (остальные 255 точек избыточны):

f = 1000*(0:256)/512;

plot(f,Pyy(1:257))

title('Frequency content of y')

xlabel('frequency (Hz)')

Рис.9. Частотный состав сигнала y

На рис.9 хорошо видны частотные составляющие сигнала на 50Гц и 120Гц.