Здравствуйте

Столкнулся с задачкой реализации алгоритма БПФ на плис, на вход которого подается последовательность, состоящая из более чем миллиона отсчетов сигнала (дискр100Мгц, 16 разрядов). Ознакомился с известными алгоритмами, но в большинстве требуется подавать всю последовательность сразу или почти сразу (например, с реализацией бабочки по основаниям 2,4). Найденные варианты как правило работают с последовательностями до 1000 отсчетов. Не хотелось бы накапливать всю последовательность во входном буфере, и делать БПФ сразу над 10^6 отсчетов. Прореживание по времени и частоте требует иметь весь массив в памяти, а мне хочется реализовать некий вариант алгоритма псевдо-реального времени.
Как я понимаю, главная проблема - корректно разбить последовательность на меньшие части, чтобы обработать их уже известным способом. Подскажите, правильно ли я понимаю задачу, и как именно лучше сделать разбиение и объединение после обработки в один спектр. На крайний случай - подскажите хорошую литературу.

Вот тоже озадачился таким вопросом, только хочу решить его при помощи своего бпф блока с внешней ddr3. Может кто проверял, какой разрядности умножителей хватит для расчёта спектра такого длинного сигнала без существенных потерь динамического диапазона?

FFT real time длиной всего навсего 65536 дает 33 разряда на выходе динамического диапазона.(xilinx virtex-7 , 394 блока памяти, 31 умножитель 25х18). Можете прикинуть для миллиона. Куда столько динамического диапазона, это для астрономии? Может с моделирования начать??
В классике делается буфер на ПЛИС и затем fft на PC с плавающей запятой видимо с двойной точностью .

Да мне всего-то на полмиллиона надо. В рлс тоже бывает нужно большое время накопления, да ещё и многоканальность. А 394 блока памяти жирно будет и по цене и по тепловыделению, когда можно внешнюю ddr поставить.

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

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

у локатора сигналы короткие по времени. Длинное бпф их не увидит. мы используем короткие fft реального времени для обнаружения.

Ну это импульсный локатор, а у меня непрерывка.

Добрый день.
Как-то занимался данным вопросом(даже сделал собственное БПФ с плавающей точкой на 12 DSP Virtex4). У "хилых" по-моему также имеется бесплатная корка для БПФ с плавающей точкой(правда не заню про возможное число точек). Так вот собственные шумы округления данного ядра ниже 130 дБм, что значительно ниже шума квантования, который почти не зависит от числа точек. Можно брать и делать.
А вот насчёт вычисления "по частя" - ничего реально реализуемого(хотя, даже теоретического) найти не удалось. Берёте ДДР3 и постранично гоняете туда-сюда данные. Благо, скорости там с запасом. Даже реалтайм можно реализовать, так как у вас накопление миллиона точек будет(как я предполагаю) гораздо дольше вычисления БПФ. Т.е. пока по одной выборке вычисляется, другая записывается в ту же ДДР.
Других вариантов для решения "в лоб" Я не вижу - только изменение условий задачи.

Приветствую!



Ой поосторожнее с "реалтаймом". Для того чтобы для radix2 FFT посчитать надо (2+Log2(N) ) * 2N чтений/записи
что для 1M точек и 100/Ms 16Bit дает (2+20)*100M*2*4*2>35.8 GB/s требуемой полосы памяти и это при ограничении разрядности I/Q =32 bit 8-()
для radix4 (2+Log4(N) ) * 2N немного легче >16 GB/s
И надо еще учесть что из за неравномерности чтения надо будет городить хитрый кэширующий контроллер памяти для эффективной работы DDR3.
Лучше уж тогда QDR SRAM использовать - два одновременных порта на запись и чтение как раз то что надо! 4-8 контроллеров с QDR2 и порядок

Думаю тут можно и нужно попробовать скомбинировать структуры fft где первую половину считать через внешнюю память а часть потоково внутри FPGA.
Но это будет тот еще монстр!

Успехов! Rob.

Спасибо! У меня не больше мегагерца частота оцифровки после дециматоров, а то и меньше. Так что реал-тайм вполне можно. Только логикорный бпф внутри целочиселнную арифметику пользует, а результат для хранения переводит в плавающую. Хотя там ведь есть apu с любой шириной плавающих чисел, может на нём лучше?

Вы Rob всё верно подсчитали, только проблема не в потоке информации. DDR3 с 9-ми таймингами на частоте шины 469 МГц и при четвертьстраничной запись/чтение обеспечивает 46 Гбит/с суммарного потока.
Проблема в том, что стандартное ядро может работать только с внутренней памятью. Даже не так, стандартное ядро обеспечивает нужный ему порядок обращений к данным. А в этом случае от скорости ДДР ничего не останется А если всё же попытаться прилепить какой-нибудь свой контроллер, то, как вы верно сказали, это будет действительно нечто монстрообразное)
Как вариант, это сделать собственное ядро, которое отвечает заданному порядку обращения к данным. Правда это не очень быстро, зато надёжно)).


Что ж вы сразу не сказали, что там не напрямую с АЦП на 100МГц поток?
В таком случае ставите SRAM на несколько мегабайт, FFT с плавающей точкой, и горя не знаете))

Приветствую!



46 Gbit/s / 8 ~=6 GByte/s всего-то

Для меня ПРОБЛЕМЫ - это обычно физические ограничения в возможности реализации задуманного - а все остальное это просто производственные ТРУДНОСТИ



В этом случае естественно нужно делать свое FFT Но для входного потока ~ 300 MByte/s это не должно вызывать ни каких проблем (только возможны трудности ).

А для упрощения доступа к памяти оптимизировать порядок обработки для классического FFT или например посмотреть на структуру потокового fft R22 SDF там память организована как блоки кольцевых буферов поэтому доступ к ней всегда линеен. Плюс память для последних стадий (фактически с половины) можно будет делать в FPGA что уменьшает требования ко внешней.

Успехов! Rob.

В общем присоединяюсь к мнениям, озвученным выше. А может ст0ит дополнительно подсмотреть основы работы современных спектроанализаторов?.. Может буржуи дают какие-нибудь намеки?

Существую библиотеки UltraLong FFT - с интегрированным контроллером внешней памяти. Вот только они небесплатны очень. http://www.dilloneng.com/fft_ip