Суть проблемы:
данные приходят постоянно, над ними надо делать БПФ, естественно, делать его надо с перекрытием.
Как хотелось бы решить:
данные класть в циклический буфер, чтоб не заниматься их постоянным перетаскиванием в начало буфера по мере обработки старых.
Дополнительное пожелание:
Хотелось бы делать БПФ на том же циклическом буфере, но ни одна из имеющихся функций, реализующих БПФ, не поддерживает возможность работы с массивами данных, которые wrap-ятся в конце буфера на его начало.
Подозрения:
1) Операция сдвига данных во временном домене на тау - есть свёртка с дельта-функцией от тау, а свёртка во временном домене эквивалентна умножению в частотном.
2) Циклические буферы и БПФ - очень часто используются в ЦОС. Раз штатные функции FFT не позволяют работать с циклическими буферами - может это и не нужно?
Вопрос:
Можно ли как-то сделать БПФ над данными вида 6 7 8 1 2 3 4 5 (цифрами обозначены моменты времени, т.е. видно, что данные закругляются) не переставляя местами части (1 2 3 4 5) и (6 7 8), и при этом получить тот же результат? Я понимаю, что чтоб получить тот же результат, надо домножать на вектор фазосдвигающих коэффициентов, который и будет соответствовать Фурье образу нашей дельта-функции, но может можно как-нибудь смухлевать и обойтись без умножения? Например, подсунуть какую-нибудь сдвинутую twidle-таблицу ?
Полная версия этой страницы: FFT над циклическим буфером
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Можно сделать так:
завести себе ДВА буфера и считать БПФ по содержимому одного из них, пока второй заполняется. Потом менять местами.
Если нужно "инерционное отображение" можно ввести усреднение результатов преобразования.
P.S.: Алгоритм БПФ основан на том, что есть массив неизменных данных, над которыми надо произвести преобразование. Во время преобразования данные менять нельзя. Собственно за счет этого и алгоритмический выигрыш во времени.
P.P.S.: Можно использовать не БПФ
завести себе ДВА буфера и считать БПФ по содержимому одного из них, пока второй заполняется. Потом менять местами.
Если нужно "инерционное отображение" можно ввести усреднение результатов преобразования.
P.S.: Алгоритм БПФ основан на том, что есть массив неизменных данных, над которыми надо произвести преобразование. Во время преобразования данные менять нельзя. Собственно за счет этого и алгоритмический выигрыш во времени.
P.P.S.: Можно использовать не БПФ
Цитата(eugen_pcad_ru @ Apr 19 2012, 14:54) 
Можно сделать так:
завести себе ДВА буфера и считать БПФ по содержимому одного из них, пока второй заполняется. Потом менять местами.
Если нужно "инерционное отображение" можно ввести усреднение результатов преобразования.
завести себе ДВА буфера и считать БПФ по содержимому одного из них, пока второй заполняется. Потом менять местами.
Если нужно "инерционное отображение" можно ввести усреднение результатов преобразования.
Думал об этом... тогда придётся по два раза копировать, да и памяти много потребуется... (у меня достаточно специфическое приложение - количество параллельных каналов около 1000, разрядность БПФ от 1024 до 16384 (меняется в зависимости от режима работы)), вобщем хотелось именно сэкономить на использовании цикличности одного буфера.
Цитата(eugen_pcad_ru @ Apr 19 2012, 14:54)
P.S.: Алгоритм БПФ основан на том, что есть массив неизменных данных, над которыми надо произвести преобразование. Во время преобразования данные менять нельзя. Собственно за счет этого и алгоритмический выигрыш во времени.
С этим проблем как раз нет, хотя копирование и идёт по DMA, но манипуляция с полученными данными запускается когда одна пересылка закончилась, и заканчивается до того, как начнётся следующая...
В любом случае спасибо... что-нить буду думать.
Цитата
Daddy Torque:
Вопрос:
Можно ли как-то сделать БПФ над данными вида 6 7 8 1 2 3 4 5 (цифрами обозначены моменты времени, т.е. видно, что данные закругляются) не переставляя местами части (1 2 3 4 5) и (6 7 8), и при этом получить тот же результат? Я понимаю, что чтоб получить тот же результат, надо домножать на вектор фазосдвигающих коэффициентов, который и будет соответствовать Фурье образу нашей дельта-функции, но может можно как-нибудь смухлевать и обойтись без умножения? Например, подсунуть какую-нибудь сдвинутую twidle-таблицу
Вопрос:
Можно ли как-то сделать БПФ над данными вида 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
Если интересует только модуль дпф - умножать ничего не надо.
Цитата(Daddy Torque @ Apr 19 2012, 17:32)
Суть проблемы:
данные приходят постоянно, над ними надо делать БПФ, естественно, делать его надо с перекрытием.
Как хотелось бы решить:
данные класть в циклический буфер, чтоб не заниматься их постоянным перетаскиванием в начало буфера по мере обработки старых.
Дополнительное пожелание:
Хотелось бы делать БПФ на том же циклическом буфере, но ни одна из имеющихся функций, реализующих БПФ, не поддерживает возможность работы с массивами данных, которые wrap-ятся в конце буфера на его начало.
Подозрения:
1) Операция сдвига данных во временном домене на тау - есть свёртка с дельта-функцией от тау, а свёртка во временном домене эквивалентна умножению в частотном.
2) Циклические буферы и БПФ - очень часто используются в ЦОС. Раз штатные функции FFT не позволяют работать с циклическими буферами - может это и не нужно?
Вопрос:
Можно ли как-то сделать БПФ над данными вида 6 7 8 1 2 3 4 5 (цифрами обозначены моменты времени, т.е. видно, что данные закругляются) не переставляя местами части (1 2 3 4 5) и (6 7 8), и при этом получить тот же результат? Я понимаю, что чтоб получить тот же результат, надо домножать на вектор фазосдвигающих коэффициентов, который и будет соответствовать Фурье образу нашей дельта-функции, но может можно как-нибудь смухлевать и обойтись без умножения? Например, подсунуть какую-нибудь сдвинутую twidle-таблицу ?
данные приходят постоянно, над ними надо делать БПФ, естественно, делать его надо с перекрытием.
Как хотелось бы решить:
данные класть в циклический буфер, чтоб не заниматься их постоянным перетаскиванием в начало буфера по мере обработки старых.
Дополнительное пожелание:
Хотелось бы делать БПФ на том же циклическом буфере, но ни одна из имеющихся функций, реализующих БПФ, не поддерживает возможность работы с массивами данных, которые wrap-ятся в конце буфера на его начало.
Подозрения:
1) Операция сдвига данных во временном домене на тау - есть свёртка с дельта-функцией от тау, а свёртка во временном домене эквивалентна умножению в частотном.
2) Циклические буферы и БПФ - очень часто используются в ЦОС. Раз штатные функции FFT не позволяют работать с циклическими буферами - может это и не нужно?
Вопрос:
Можно ли как-то сделать БПФ над данными вида 6 7 8 1 2 3 4 5 (цифрами обозначены моменты времени, т.е. видно, что данные закругляются) не переставляя местами части (1 2 3 4 5) и (6 7 8), и при этом получить тот же результат? Я понимаю, что чтоб получить тот же результат, надо домножать на вектор фазосдвигающих коэффициентов, который и будет соответствовать Фурье образу нашей дельта-функции, но может можно как-нибудь смухлевать и обойтись без умножения? Например, подсунуть какую-нибудь сдвинутую twidle-таблицу ?
Как я понял вы делаете скачущее преобразование Фурье. Сделайте два условно независимых параллельно протекающих процесса. Первый процесс заполнение буфера входными данными с закругляемыми порядковыми номерами по размеру выделенного буфера. Размер этого буфера должен быть больше размеров FFT. Второй процесс вычисление номеров элементов буфера в качестве входных отсчетов FFT с учетом их цикличности.
Цитата(thermit @ Apr 19 2012, 15:48)
Дык, в чем проблема-то? Делаем бпф над буфером как есть и умножаем результат на комплексную экспоненту.
В вашем случае exp(j*2*pi*3*(0:7)/8). Иначе - надо изобретать собственное бпф под ваш порядок входных данных.
ps
Если интересует только модуль дпф - умножать ничего не надо.
В вашем случае exp(j*2*pi*3*(0:7)/8). Иначе - надо изобретать собственное бпф под ваш порядок входных данных.
ps
Если интересует только модуль дпф - умножать ничего не надо.
К сожалению, интересует не только модуль.
Умножать весь массив на фазосдвигающие коэффициенты займёт практически столько же времени (если не больше) сколько и сдвигание массива перед тем, как делать БПФ.
Я думал, может трюк есть, вот и спросил... сейчас понял, что трюка нет
Цитата(mihalevski @ Apr 20 2012, 09:21)
Как я понял вы делаете скачущее преобразование Фурье. Сделайте два условно независимых параллельно протекающих процесса. Первый процесс заполнение буфера входными данными с закругляемыми порядковыми номерами по размеру выделенного буфера. Размер этого буфера должен быть больше размеров 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 19 2012, 14:32)
Вопрос:
Можно ли как-то сделать БПФ над данными вида 6 7 8 1 2 3 4 5 (цифрами обозначены моменты времени, т.е. видно, что данные закругляются) не переставляя местами части (1 2 3 4 5) и (6 7 8), и при этом получить тот же результат?
Можно ли как-то сделать БПФ над данными вида 6 7 8 1 2 3 4 5 (цифрами обозначены моменты времени, т.е. видно, что данные закругляются) не переставляя местами части (1 2 3 4 5) и (6 7 8), и при этом получить тот же результат?
Если к вашему FFT есть исходники, то достаточно поменять индексы перестановки отсчётов в бит-реверс алгоритме. Если исходников нет — придётся разворачивать буфер в линейный либо домножать выход на экспоненту.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.