В википедии есть код прямого преобразования Фурье на С++.

Насколько понимаю, они программировали эту формулу: http://upload.wikimedia.org/math/f/6/9/f69...8608c59a2bb.png

Постоянно запутываюсь в этом коде) может кто-то сможет отследить как из этого прямого сделать обратное преобразование Фурье. По теории, чтобы это сделать нужно экспоненту возвести в степень -1 (не ошибаюсь я?). Т.е. остаётся найти где они считают "exp", ну и сделать: "1/exp(...)". Только вот в этом поиске и заключается проблема.. ) Может кто-нибудь поможет?

Вот рабочий код прямого преобразования Фурье:

Да, реализация не самая лучшая (с точки зрения понятности; слишком она наоптимизированная, чтобы такую в вики пихать)...

В их обозначения переменных я не углублялся, но кажется, что здесь может быть единственный вариант:

здесь всё умножить на -1 (или у isign, который может быть для этого и предназначен, изменить значение на противоположное).

И вообще, чтобы из прямого БПФ получить обратное, надо не только заменить экспоненту на противоположную, но и разделить потом каждый элемент результата на n.

Опробовал, но не прокатило :(

В конце кода ФФТ, есть такая штука: dOut[ i ] = sqrt( .... ), случаем не может ли быть из-за неё?

У меня получаются вот какие графики: http://s001.radikal.ru/i196/1008/f5/65fd8b141fac.png
Тут видите, абсолютно какие-то другие числа получаются. Такое впечатление, что это кепстр исходного получается)))

Алгоритм такой:

ффтМассив = ФФТ( исходные_данные, 1024-окно );
ффтОбратноеМассив = рФФТ( ффтМассив, 1024 ); // рФФТ - обратное ффт, в котором заменён isign = -1 на +1.

И чего-то ерунда какая-то получается. Может у кого есть прямое и обратное FFT на C++?

Proger10, 
// http://psi-logic.shadanakar.org/fft/fftf.htm
/// http://student.kuleuven.be/~m0216922/CG/fo...ml#introduction

А покороче ничего нет?  Чего там кода-то столько?)

Я вот нашёл некоторый код, короткий (он был комплексный, я им пользуюсь как не комплексным):


Он преобразование для 1024 точек считает секунд 20 на двуядерном 2.24GHz, что неприемлемо для меня (мне в рил-тайме обрабатывать надо сигнал). Вышеприведённый код считает меньше, чем за пол секунды.

Если я начну реализовывать самостоятельно, он, скорее всего, получится у меня таким же тормозом.. а почему же первый работает так быстро? Накрутили его нехило, зато, чёрт, очень работоспособный.. И то на половину. Обратное сделать в нём не получается.

Proger10, 
2 код тормазит из-за vector. Используй указатель.
Хочешь скорость используй fftw
http://www.fftw.org/

Вряд ли из-за vector он тормозит. Покуда прошлый код у меня тоже работает на vector. (я поменял с указателя на vector). Видимых отличий в скорости не оказалось, а работать удобнее, поэтому и оставил. 

Спасибо за совет. Попробую. Я как-то смотрел уже те мануалы.. первое впечатление - чёрт ногу сломит. Посмотрим ещё раз.

У меня на сайте есть вполне короткий и адекватно быстрый код:



Для ста тысяч элементов отрабатывать должен где-то за секунду.

maxdiver
А не в комплексном случае, а вещественном, инициироваться wn должна каким значением? Инициировал косинусом от ang - получилось что-то не очень походящее на спектр Фурье  Нужно ли делать какую-то пост-обработку получившихся коэффициентов после этой функции? (я ещё прологорифмировал каждый получившийся коэффициент). И тем не менее, что-то не то получается..

Код у меня сейчас вот так модифицирован:


В первом коде вычислялся ещё квадрат суммы для каждого выходного коэффициента, тут тоже надо сделать так же?
Вообще спектр, чуток похож на спектр.. но как-то как будто у него малая точность коэффициентов. Коэффициенты почему-то все почти равные друг другу, а кодом первого сообщения они сильно выделяются.. 

Добавлено
Квадраты суммы высчитал - стало уже получше, но всё равно очень уж много шума.. совсем непонять какие там частоты наиболее активны. Сигнал разный, а они практически одинаковые везде  заметно, что чуток разнятся, но на глаз я бы не сказал ничего по такому спектру.. слишком сложно) а у первого кода - легко всё различимо..

Это сообщение отредактировал(а) Proger10 - 16.8.2010, 21:16

Чтобы было более понятно о какой такой точности двух кодов я говорю, вот картинка:
http://i064.radikal.ru/1008/c7/63134840417c.gif

левая колонка - верхний код этой темы, а правая - последний код (аналогичный сигнал). Вот о чём я и говорю.. блин, код хороший, короткий, но какой-то не очень точный  как такой поаанлизируешь? 

Это сообщение отредактировал(а) Proger10 - 16.8.2010, 21:31

В БПФ числа всегда комплексные. Внутри функции ничего менять не надо. Входные параметры (а они вещественные - например, vector<double>) надо перевести в комплексные, для чего просто сделать вектор комплексных чисел и присвоить ему вектор вещественных (конвертация пройзойдет автоматически). Результат потом обратно надо перевести в действительные, для чего можно взять только действительную часть каждого комплексного числа (ну мнимая часть как бы = 0 в теории), или можно, как в коде в первом посте, взять модули всех чисел.

В коде, приведённом в первом посте, комплексные числа тоже есть, просто они хранятся не в виде отдельной структуры, а как два соседних дабла (опять же, ничего не скажешь, "удобно" для человека, пытающегося разобраться в БПФ и видящего перед собой этот код).

а где там модули берутся? не могу пока найти... Квадраты суммы квадратов, имеете ввиду?)

Опробовал с комплексными - это уже намного интереснее!!  

Это сообщение отредактировал(а) Proger10 - 17.8.2010, 00:09

Вот где там брался модуль:


А не можете описать в паре слов, как ДПФ у вас применяется для анализа сигналов? Просто времени нет изучать литературу, а вопрос очень интересный. (я БПФ всегда использовал только для быстрого перемножения двух длинных чисел или для других смежных задач)

А я тоже пока только БПФ использую