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

[psilogic]

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

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

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

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

Comments

[odinokov.livejournal.com]

а паскакалем не замутишь? 8)

[psilogic.livejournal.com]

Паскаль ацтой! :o)))
*смущенно* Да и забыл я яго нафик :)

[odinokov.livejournal.com]

ох...
а мне ему ещё детишек учить8))

[psilogic.livejournal.com]

Надо же: паскаль почти умер, а детишек ему все еще учат...

[nazarovsky.livejournal.com]

дык это.. а готовую БПФ процедуру использовать и нулями добить до степени двойки религия мешает? :)

[ex-neo-is-fl156.livejournal.com]

У меня где-то валялось на паскале. Могу посмотреть, если надо.

P.S. FYI: Счастливые читатели Д. Кнута "Искусство Программирования" т.3. могли реализовывать FFT за O(NlogN) ещё задолго до того, как Википедия появилась на свет ;)

[cybister.livejournal.com]

Я тож забыл, но далеко не отстой.
Недвано девушка мне сказала что ей потнесли си-ди со скринсеверами,
и там мой скринсевер (кажися фигуры лисажу в3д... что-то типа).
Под винду ! 4.5кб !!!
На Борланд паскакале. (На турбо кажись при навешивании соответствующих либ тоже пахало).Такие вот пирожки.
Если нужно - поищу, где-то валялось.

В порядке саморекламы...

[sanitareugen.livejournal.com]

dsp-book.narod.ru

[vorobioff.livejournal.com]

Куда я попал???

Re: В порядке саморекламы...

[psilogic.livejournal.com]

Твою мать!!!!!!!!!!!!!!!!!
Как давно я искал что-нибудь эдакое!!!!!!!!!!

[psilogic.livejournal.com]

Только для числа отсчетов, равного степени двойки. Знаменитый алгоритм Кули-Тьюки. Здесь не о нем.

[psilogic.livejournal.com]

Если добить нулями до степени двойки, то в спектре получится бордель, а не только те частоты, которые формировали исходный сигнал. :) Попытка синтезировать длительный сигнал суммированием синусоид из полученного набора частот приведет к тому, что будет периодически возникать тишина в том месте, где забиты нули.

[psilogic.livejournal.com]

На процедурку...

Рад быть полезен...

[sanitareugen.livejournal.com]

Существуют зеркала, но я давно не отслеживаю, увы...

[sanitareugen.livejournal.com]

Поищите ещё Винограда.
Есть в Гольденберг, Матюшкин, Поляк. "Цифровая обработка сигналов".

[sanitareugen.livejournal.com]

Но если пытаться синтезировать при ровно правильном количестве точек - тоже может ничего хорошего не выйти...

Дельфи живы...

[sanitareugen.livejournal.com]

А это Object Pascal + кое-что ещё...

[ex-neo-is-fl156.livejournal.com]

Да, не обратил внимание вначале.
Тогда это действительно ценно. Спасибо.

У меня к Вам два вопроса (чисто из любопытства)

1. Для какого приложения Вы заинтересовались FFT в данный момент?

2. Что означает слово "freeware", написанное Вами в исходниках - это в смысле GPL / Open Source, или в смысле "делайте что хотите бесплатно" (в т.ч. можно копирайтить derived code, зарабатывать миллиарды, используя этот код, ни копейки Вам не заплатив, и т.п.)?

[metaclass.livejournal.com]

в 9 строке fft.cpp #include без имени файла.

[metaclass.livejournal.com]

math.h что ли?

[metaclass.livejournal.com]

В ипостали Object Pascal/Delphi он еще долго существовать будет. На нем написано достаточно немаленькое количество всяких учетных и около того систем, в основном заказных.

[psilogic.livejournal.com]

Кстати, заглянул в 3-й том и увидел, что вы меня наипали. Не видно там вообще упоминания Фурье. Разве что я плохо искал.

[nazarovsky.livejournal.com]

Я вроде думал, что в результате добивания "нулями" спектр просто интерполируется на дополнительные точки, и никакого борделя там быть не может...

Re: Дельфи живы...

[psilogic.livejournal.com]

Не знаю, не знаю... после того, как Борланд стал подыхать, дельфи как-то тоже стали резко терять популярность...

[psilogic.livejournal.com]

То, что уже написано - да, но как насчет новых программ? Детишкам ведь это будет в 1 очередь важно.