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

Подозрения:
1) Операция сдвига данных во временном домене на тау - есть свёртка с дельта-функцией от тау, а свёртка во временном домене эквивалентна умножению в частотном.
2) Циклические буферы и БПФ - очень часто используются в ЦОС. Раз штатные функции FFT не позволяют работать с циклическими буферами - может это и не нужно?

Вопрос:
Можно ли как-то сделать БПФ над данными вида 6 7 8 1 2 3 4 5 (цифрами обозначены моменты времени, т.е. видно, что данные закругляются) не переставляя местами части (1 2 3 4 5) и (6 7 8), и при этом получить тот же результат? Я понимаю, что чтоб получить тот же результат, надо домножать на вектор фазосдвигающих коэффициентов, который и будет соответствовать Фурье образу нашей дельта-функции, но может можно как-нибудь смухлевать и обойтись без умножения? Например, подсунуть какую-нибудь сдвинутую twidle-таблицу ?

Можно сделать так:
завести себе ДВА буфера и считать БПФ по содержимому одного из них, пока второй заполняется. Потом менять местами.
Если нужно "инерционное отображение" можно ввести усреднение результатов преобразования.

P.S.: Алгоритм БПФ основан на том, что есть массив неизменных данных, над которыми надо произвести преобразование. Во время преобразования данные менять нельзя. Собственно за счет этого и алгоритмический выигрыш во времени.
P.P.S.: Можно использовать не БПФ

Думал об этом... тогда придётся по два раза копировать, да и памяти много потребуется... (у меня достаточно специфическое приложение - количество параллельных каналов около 1000, разрядность БПФ от 1024 до 16384 (меняется в зависимости от режима работы)), вобщем хотелось именно сэкономить на использовании цикличности одного буфера.


С этим проблем как раз нет, хотя копирование и идёт по DMA, но манипуляция с полученными данными запускается когда одна пересылка закончилась, и заканчивается до того, как начнётся следующая...

В любом случае спасибо... что-нить буду думать.

Дык, в чем проблема-то? Делаем бпф над буфером как есть и умножаем результат на комплексную экспоненту.
В вашем случае exp(j*2*pi*3*(0:7)/8). Иначе - надо изобретать собственное бпф под ваш порядок входных данных.

ps
Если интересует только модуль дпф - умножать ничего не надо.

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

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

Я думал, может трюк есть, вот и спросил... сейчас понял, что трюка нет



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

6 7 8 _ _ _ _ _ _ _ _ 1 2 3 4 5

И тогда никак...

Можно сделать вот так вот (циклический буфер остаётся, но к нему добавляются уши слева и справа):

_ _ _ _ 6 7 8 1 2 3 4 5 _ _ _ _

и можно тогда так сделать:

_ _ _ _ 6 7 8 1 2 3 4 5 6 7 8 _

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

Сообщение отредактировал Daddy Torque - Apr 20 2012, 11:19

Если к вашему FFT есть исходники, то достаточно поменять индексы перестановки отсчётов в бит-реверс алгоритме. Если исходников нет — придётся разворачивать буфер в линейный либо домножать выход на экспоненту.