Быстрое преобразование Фурье (халява)

[psilogic]

Все-таки Википедия рулит. Надыбал там то, о чем давно мечтал:
математические выкладки, позволяющие делать преобразование Фурье за время порядка N log(N). Причем, для произвольного N, а не только для степени двойки.

Поковырявшись с ними, поразбиравшись, пооптимизировав, родил описалово, как, что и почему, а главное - файлец на C++ с готовым работающим модулем, который не требует никаких специальных библиотек.

http://psi-logic.shadanakar.org/fft/fftf.htm

Можете юзать - ибо халява :)

Comments

[psilogic.livejournal.com]

Хрена лысого он интерполируется... Сами подумайте: шли себе колебания, а потом - нули. Звучит это как внезапный щелчок и тишина. Какой там у нас спектр щелчка? Бесконечный... Генерация сигнала по синусоидам даст примерно вот такую картину:

/\/\/\/\/\____/\/\/\/\/\____/\/\/\/\/\____/\/\/\/\/\____...

[nazarovsky.livejournal.com]

Ну понятно, что если "добьешь" нулями, сделаешь БПФ а потом обратное БПФ - "добитые" нули никуда не денутся, надо запоминать сколько было реальных отсчетов в исходном сигнале :-) А насчет интерполяции я имею в виду вот что:
Пусть у нас имеется сигнал и мы его "добиваем" нулями до степени двойки и делаем БПФ.
Тогда у нас будет наблюдаться следующая картина:

21кб PNG иллюстрация.
http://i67.photobucket.com/albums/h296/nazerru/fftwithpad.png

----[код на Матлабе, генерирующий это все]----
x=[1,2,-2,-2,1,2,-2,1,-2];
z1=[x,zeros(1,(32-length(x)))];
z2=[z1,zeros(1,32)];
z3=[z2,zeros(1,64)];
z4=[z3,zeros(1,128)];

figure(1);
subplot(6,1,1);
stem(x);
title('original signal');
subplot(6,1,2);
stem(fft(x));
title('FFT of original signal');
subplot(6,1,3);
stem(fft(z1));
title('FFT of padded with zeros to 32 points signal');
subplot(6,1,4);
stem(fft(z2));
title('FFT of padded with zeros to 64 points signal');
subplot(6,1,5);
stem(fft(z3));
title('FFT of padded with zeros to 128 points signal');
subplot(6,1,6);
stem(fft(z4));
title('FFT of padded with zeros to 256 points signal');
----[код на Матлабе, генерирующий это все]----

т.е. чем больше у нас количество точек, по которым мы делаем БПФ тем точней у нас будет представление спектра данного сигнала. Вот это я имел в виду под "интерполируется" :-)

[psilogic.livejournal.com]

Гут. А я говорю вот о чем.
Пусть у нас есть сигнал. Ну самый простой, синусоида:



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



Теперь обнуляем кусок синусоиды справа:



И красивому спектру приходит пипец:



Соответственно понять, какие там частоты, намного труднее.

[nazarovsky.livejournal.com]

Ок. В общем, понял...