Как работает ф-ция FFT ?
Добрый день.
Собственно в чем вопрос. Судя по названию fft - это есть БПФ. Однако:
1. Как достраивается / обрезается сигнал до размера степени двойки? (т.к. БПФ работает с массивами определенной длины)
2. Если мы добавляем в конец сигнала нули, то по факту этим мы "размазываем" спектр т.к. в сигнале появляется фронт.
3. Кстати в хелпе именно подобный пример. Под словом подобный, я говорю о том, что там в fft передается сигнал одной длины, а значение количества точек уже по степени двойки. И возвращается тоже спектр с количеством точек по степени двойки. И что там добавляется внутри этой ф-ции - нули или не нули - строго говоря есть вопрос.
4. Все бы ничего, но в хелпе пример. И хорошо. Но он не показательный, в нем нифига не увидишь разницы на глаз. Ниже пример. Красная кривая - БПФ. Проверял и на своих функциях, и с использованием fft в случае заполнения хвоста сигнала нулями. Сходство до 6-8 знака. Однако черная кривая - это таже самая fft без заполнения нулями до степени двойки. Т.е. есть подозрение, что внутри fft несколько вариаций алгоритмов?
5. Или может там окна сглаживающие используются?
6. Вопрос в скорости. БПФ и ДПФ по скорости сильно разниться должны. Однако этого нет.
Так как работает fft ?
Комментарии
Здравствуйте, aBoomest!
Функция fft вычисляет БПФ, когда размер входного вектора кратен степени двойки. В остальных случаях будет рассчитано ДПФ. Например, подадим на вход fft вектор длиной 10 и замерим скорость выполнения этой функции
x = (1:10).';
tic
X = fft(x);
toc
X - результат fft, это вектор длиной 10, т.е. преобразование Фурье было рассчитано по алгоритму ДПФ.
Аналогинчные операции можно проделать для вектора длиной 16. Причем время, за которое мы получим 16 точек окажется значительно меньше, того, которое было потрачено на расчет ПФ для 10 точек, это нам говорит о том, что применялся алгоритм БПФ.
Y = (1:16).';
tic
Y = fft(Y);
toc
https://docs.exponenta.ru/matlab/ref/fft.html?searchHighlight=fft
Спасибо. Добавление нулей искажает реальный спектр "размазывает", т.к. любой фронт - это (в пределе) сплошной спектр. Как быть тут?
Добавление нулей в БПФ не размывает спектр, а увеличивает разрешение БПФ. Важно, чтобы точки получаемого спектра попадали на те частоты, которые вы задаете в исходных гармониках, тогда никакого "размывания" не будет.
Вот пример, здесь можно изменять кол-во нулей в сигнале x и смотреть как будет меняться спектр. Например, при zerosNumber = 100, получим максимум на 99.455 кГц вместо исходных 100 кГц, т.е. мы не попали "корзиной" БПФ в нужную нам частоту. Если поставить zerosNumber = 1e4, то получим более отчетливый пик гораздо ближе к нашей исходной частоте.
Fs = 1e6;
Ts = 1/Fs;
T = 0:Ts:1000*Ts;
zerosNumber = 1e4; % Количество нулей в конце выборки
x = [(sin(2*pi*1e5*T)+sin(2*pi*2e5*T)).'; zeros(zerosNumber,1)];
X = fft(x);
figure
plot(-Fs/2:Fs/length(x):Fs/2-Fs/length(x),fftshift(abs(X)),'.-')
Более подробно можно почитать здесь:
bitweenie.com/listings/fft-zero-padding/