Доброго времени суток!

Имеется следующая проблема: известные мне алгоритмы преобразования Фурье обрабатывают массив исходних данных целиком. А хотелось бы иметь алгоритм который может делать ПФ (дискретное, трехмерное) по мере поступления данних. Просто во время сбора данных (время которого сократить не удается) хотелось бы производить часть вычислений, и что бы после сбора всех данных оставалось минимум вычислений. Общая сложность алгоритма роли не играет. Может кто подскажет алгоритм (и, если можно, его реализацию на С/С++)?

Заранее спасибо!

на сколько мне известно для БПФ преобразования по части данных не возможно

Да, для БПФ нет, а для обычного дискретного?

имхо, тоже нет

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

Может сгодится.
" Ничего не мешает нам взять, допустим, 1000 отсчетов, дополнить их еще 64536 нулями справа и подвергнуть получившуюся штуку разложению с FFT = 65536. Таким образом мы получим большое разрешение и по времени, и по частоте. Побочные эффекты? Лишь уменьшение амплитуды спектра и изменение до неузнаваемости фазовых компонент. Но мы ведь их и так не используем, мы лишь строим спектр! Амплитуду можно поправить, её изменение вычисляется. Вывод: при одном лишь анализе мы можем получить какое угодно разрешение по времени и по частоте одновременно."

http://websound.ru/index.cgi?articles/theory/fft

В зависимости от задачи для которой используется ПФ можно уменьшить буфер для расчёта...
Например в моей программе он составляет 10 отсчётов.. но ПФ работает ТОЛЬКО для моей задачи...
так что напиши немного про основную задачу..

Цитата

при одном лишь анализе мы можем получить какое угодно разрешение по времени и по частоте одновременно

К сожалению, одновременно этого достичь нельзя: либо хорошее разрешение по частоте, либо по времени. Ибо работает принцип неопределенности Гейзенберга.

Кстати, и в той самой статье не забыли написать

Цитата

выигрывая в разрешении по времени, мы проигрываем в разрешении по частоте, и наоборот.

- это оттуда

Цитата

http://websound.ru/index.cgi?articles/theory/fft

Но не могу согласиться с автором этой статьи, который заявляет, что сие утвердение неверно.
Пусть докажет обратное.
Тот самый прием, которым хвалится автор, на самом деле является операцией вычисления БПФ, страшно сказать, ДРУГОГО сигнала, который уже не похож на исходный.

Цитата

Тот самый прием, которым хвалится автор, на самом деле является операцией вычисления БПФ, страшно сказать, ДРУГОГО сигнала, который уже не похож на исходный

Но тогда,само по себе выхватывание "куска" непрерывного сигнала для БПФ тоже делает его другим(импульс), а применение оконных функций вообще -преступление.Что же тогда делать?

Цитата(podval @ 19.8.2003, 20:23)

Цитата выигрывая в разрешении по времени, мы проигрываем в разрешении по частоте, и наоборот. Но не могу согласиться с автором этой статьи, который заявляет, что сие утвердение неверно. Пусть докажет обратное.

Прием повышения разрешения по частоте путем добавления нуле в конец массива очень широко используется в радиолокации. Что разрешение увеличивается доказывается очень элементарно.

Пусть есть реализация сигнала длиной T секунд. Мы его дискретизируем с периодом dt. При этом получаем N=T/dt выборок. (T=N*dt)
Тогда частотное разрешение dF=1/T=1/(N*dt).
Если перед нахожденеим спектра добить нулями в два раза, то колличество выборок будет 2N, и при неизменных остальных параметрах частотное разрешение будет dF=1/(2*N*dt), то есть в два раза выше.

По поводу изменения до неузнаваемости фазовых компонент, вопрос спорный. Например, для оптимальной фильтрации ЛЧМ сигналов есть так называемый метод прыгающего БПФ.
Суть: ищется спектр сигнала (выше изложенным методом), затем спектр умножается на комплексную характеристику оптимального фильтра и делается обратное БПФ. На выходе получаем мощный выброс в месте нахождения ЛЧМ сигнала.
А если бы фаза искажалась бы то сигнал в таком фильтре не сжимался бы.

Цитата

Тот самый прием, которым хвалится автор, на самом деле является операцией вычисления БПФ, страшно сказать, ДРУГОГО сигнала, который уже не похож на исходный.

Сам себя сейчас перечитал и немного ... того...

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

Цитата

Но тогда,само по себе выхватывание "куска" непрерывного сигнала для БПФ тоже делает его другим(импульс), а применение оконных функций вообще -преступление.Что же тогда делать?

Да не такое уж оно и преступление. Окнами пытаются как-то компенсировать недостатки БПФ - невозможность полного знания о поведении сигнала на всей оси времени (надо знать будущее поведение сигнала) и невыполнение требования стационарности реальных сигналов.
С другой стороны, фиксированное окно не может быть полностью адаптировано к локальным свойствам сигнала. Для преодоления этого недостатка пользуются вейвлет-преобразованием. Оно дает на высоких частотах лучшее разрешение по времени, а на низких - по частоте. Т.е. для высокочастотной компоненты можно точнее указать ее временную позицию, а для низкочастотной - ее значение частоты.

Мы уже немого углубляемся (не могу сказать, что отклоняемся), поэтому для автора темы нелишним будет напомнить ответ на поставленный в теме вопрос:

maxim1000

Цитата

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

Цитата

Но тогда,само по себе выхватывание "куска" непрерывного сигнала для БПФ тоже делает его другим(импульс), а применение оконных функций вообще -преступление.Что же тогда делать?

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

Я предлагал: ввести ,скажем 1024 отсчетов, дополнить их 64 тыс. нулей и считать, параллельно вводя следующие 1024...
Убивание двух зайцев, и разрешение по времени никуда не денется.

Цитата

а выхватывание куска сигнала можно опустить, если доопределить оконную функцию нулями по краям (при этом желательно посмотреть, что стало со спектром оконной функции)

2maxim1000 И реально поможет?

Unregistered -это я

Цитата

Я предлагал: ввести ,скажем 1024 отсчетов, дополнить их 64 тыс. нулей и считать, параллельно вводя следующие 1024... Убивание двух зайцев, и разрешение по времени никуда не денется.

Боюсь, это не решит поставленную задачу.
И разрешение по времени здесь не при чем.

P.S. Alexei, предлагаю зарегистрироваться. Будет намного удобнее и появится масса дополнительных возможностей.

Интересная дикуссия получилась, немного в сторону, правда, но все равно много интересного узнал

Такое преобразование (см. начало темы) возможно, в книгах на dsp-book.narod.ru об этом написано. Там e^(...) представляется в виде матрицы, а дальше к элементам вектора результата приплюсовывается произведение элементов матрицы на элементы исходного массива. Алгоритм для одномерного случая я написал, сложность получается O(N^2), зато время выполнения операций на последнем шаге в несколько раз меньше чем FFT (из Numeral Recipes) на этом массиве целиком (этого я и добивался).

Цитата

2maxim1000 И реально поможет?

это не может ни помочь, ни помешать, это - просто другой взгляд на то же самое