[DaddyTorque 0]

Суть проблемы:

данные приходят постоянно, над ними надо делать БПФ, естественно, делать его надо с перекрытием.

Как хотелось бы решить:

данные класть в циклический буфер, чтоб не заниматься их постоянным перетаскиванием в начало буфера по мере обработки старых.

Дополнительное пожелание:

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

 

Подозрения:

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

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

 

Вопрос:

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

[eugen_pcad_ru 0]

Можно сделать так:

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

Если нужно "инерционное отображение" можно ввести усреднение результатов преобразования.

 

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

P.P.S.: Можно использовать не БПФ:)

[DaddyTorque 0]

Можно сделать так:

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

Если нужно "инерционное отображение" можно ввести усреднение результатов преобразования.

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

 

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

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

 

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

[thermit 1]

Daddy Torque:

Вопрос:

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

 

Дык, в чем проблема-то? Делаем бпф над буфером как есть и умножаем результат на комплексную экспоненту.

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

 

ps

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

[mihalevski 0]

Суть проблемы:

данные приходят постоянно, над ними надо делать БПФ, естественно, делать его надо с перекрытием.

Как хотелось бы решить:

данные класть в циклический буфер, чтоб не заниматься их постоянным перетаскиванием в начало буфера по мере обработки старых.

Дополнительное пожелание:

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

 

Подозрения:

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

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

 

Вопрос:

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

 

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

[DaddyTorque 0]

Дык, в чем проблема-то? Делаем бпф над буфером как есть и умножаем результат на комплексную экспоненту.

В вашем случае 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 _

 

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

Изменено 20 апреля, 2012 пользователем Daddy Torque

[Alexey Lukin 0]

Вопрос:

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

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