В большинстве книг по БПФ рекомендуется не заморачиваться, а брать готовое.
Вот только с готовым бывают проблемы.
Делаю convolution processor на stratix.
Можно использовать готовое ядро от altera (пока так и делаю), но помимо того, что оно стоит денег, оно еще и не очень оптимальное для моей задачи, так как целочисленное. При анализе спектра это нормально, но при свертке между прямым и обратным преобразованиями делается умножение, которое приводит либо к округлениям, либо к увеличению разрядности обратного преобразования.
Хочется сделать FFT/iFFT, который бы работал с плавающей запятой, но не в формате 1 знак, 23 мантисса, 8 порядок (такое для stratix существует в продаже), а 6 - 9 бит мантисса, а порядок 7 или 8 бит.
Пока не понимаю, можно ли организовать память так, что бы параллельно работали 8 или 16 бабочек, но памяти при этом использовалось меньше, чем в два раза больше блока.

PS: Заранее извиняюсь, если off-topic, подозрение вызвано противоречием между темами сообщений и названием раздела.

1.А как это ты себе представляешь работу 8 или 16 бабочек одновременно?Интересен вопрос организации памяти.
2.И с каким основанием бабочки?
3.Сколько точек обрабатывать собираешься?
4.Данные комплексные или как?
Я когда-то заморачивался целочисенным фурье на 1024 точки.И пришёл к выводу(а как оказалось,что до меня до этого додумалисьуже подавно ) что оптимальным является вычисление с помощью бабочки по основанию 4.Т.к. памяти используется столько же что и по основанию 2, а считает в 2 раза быстрей.

А почему convolution именно через Фурье, а не какое ТЧП/Хаара? Спектр тоже нужен?

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

to Mad Makc:
1. Работа нескольких бабочек - это проблема. Памяти нужно примернов вдвое болье, чем для хранения блока. Рассматривается такой вариант:
Памятей две, одна на входе, другая на выходе бабочек.
Вход. На кажду бабочку столько банков памяти, какое основание. Банк хранит данные, которые должны поступить на этот вход этой бабочки на этом цикле.
Выход. Скорее это сдвиговые регистры. Их количество равно количеству выходов всех бабочек. Регистры поочередно защелкивают все выходы всех бабочке, затем эти данные выдвигаются и поступают на в входную память так, чтобы к следующему проходу были подрядидущие данный для каждой бабочки.
Это еще не алгоритм, а первая идея, пришедшая в голову, нужно
2. основание видимо, 4.
3. нужно делать два варианта: 2048 или 4096
4. комплексные

to yornik:
Свертка через Фурье потому что исходная программа, которую нужно повторить в железе, делает это через Фурье. Задача формулировалась именно через эту программу, это уже я догадался, что это свертка, но я совсем не математик, другие преобразования начал разглядывать. Пока только убедился, что Walsh/Hadamard для этого не годится
Спектр не нужен.
Большое спасибо за наводку про Catapult C, посмотрю и на Хаара тоже.

to Shtirlits:
С такими запросами,у меня такое ощущение у Вас никакой памяти не хватит.Имейте ввиду,что кроме того,что нужна память для хванения данных,нужно ещё и коэффициенты домножения считать.А это ещё ПЗУ.И не маленькая.А если и несколько бабочек,то и ПЗУ несколько будет.
Модет не стоит заморачиваться и хватит одной бабочки?В конвеер всё запихать-и вперёт!Посчитайте по времени.
А вообще перед реализацией полезно сначало накатать на чём-нибуть модель того,что делать собираетесь(на Сях,там,или Паскале том же).
З.ы.А 2048 и 4096 считаются в одном устройстве?Если да-то мне вас жалко...

FPGA Stratix EP1S60.
Памяти около мегабайта в сумме, все поместится.
Задача максимально все это необъятное хозяйство употребить.

На C уже все писано, переписано. И в разных float point и в целых числах.
Данные получаются хорошие или очень хорошие, но в целых числах нужно довольно много разрядов для обратного преобразования.

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

Ну, если памяти много,то и флаг в руки.
А сколько по времени нужно делать Фурье ?

Задачи опять же две:
1) Обрабатывать поток, который удается прокачать через PCI-X.
speed grade у меня 6-ой, altera говорит, что максимум 100MHz 64 бита,
не исключено, что все потуги сделать 133 исправляя и оптимизируя
PLDA-шное ядро PCI-X будут безуспешными.
Требуется иметь в виду и 133MHz, так как может появиться задача все это собрать на другой плате, где будет стоит stratix со speed grade 5.
Входные данные комплексные, 5 бит на составляющую, на выходе 16 битная амплитуда.
На 100MHz получается теоретический предел 200MSample/sec.

2) Как можно быстрее. В DDR2 или в распределенную память загружаются данные, а фильтры генерируются, результат используется только для подсчета качества фильтра, то есть, никакая шина уже не держит.

to yornik:
В CataputC нет float point, есть числа с фиксированной запятой.
Все float и double конвертируются в sc_fixed/sc_ufixed, вот у них можно задать количество бит на целую и дробну часть
Использовать float и double сильно не советуют, разве что для констант, иначе будут отличия в работе железа и кода, выполняемого на процессоре для тестирования алгоритма.

Вещь впечатляющая!

Не совсем понимаю, почему такая заострённость на плавающей точке. Когда на машине/процессоре имеешь 80 бит, то да, все хорошо. Но реально с АЦП получаем целочисленное значение. Переводить его в плавающее значение с ограниченой разрядностью - ошибки набегут и не заметите. А уж реализовывать такой алгоритм на FPGA - муторно и не естественно.
Или я чего-то упускаю?

Конечно упускаешь. Когда умножаешь 10 на 10 в итоге получаешь 20 разрядов, затем тебе опять приходится умножать только уже 20 на 20, получается - 40. Смекаешь, что произойдет, на пятом шаге при 1024 точках. А если на входе у нас 16 разрядов? Естественно что даже более слабый DSP с плавающей точкой в этом случае уделает своего даже более шустрого целочисленного собрата. Господин Shtirlits, если у вас получится, дайте знать, если не жалко будет поделится плодами труда. Спасибо.

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

Немножечко не согласен.
Конечно можно получить 20 разрядов после умножения 10-ти разрядных. Но зачем ???
Если вы помните, то поворачивающие множители для БПФ всегда меньше 1. Следовательно после умножения число будет меньше умножаемого. Необходимо сделать только округление после умножения. Т.е. если на входе 16 разрядов, то после первой бабочки (Radix-2) нам достаточно на 2 разряда больше (умножение и затем сложение комплексных чисел). А если идти еще дальше и рассматривать скажем 1024 точки, то можно заметить, что после каждой бабочки увеличивать разрядность необязательно.

Привет всем!
Может я немного не в тему, но не подскажет ли кто из знающих ссылочку на простенькую реализацию FFT на VHDL. Хочу разобраться в этом вопросе.

Спасибо!

>To Jools
Сходи на www.opencores.org. Простоты, правда не обещаю - извиняй .

Можете попробывать написать на Confluence
http://www.confluent.org/wiki/doku.php
Писать всеж меньше чем на чистом HDL'е, да и удобнее все же.
Еще Celoxica DK, на сях как ни как FFT писать попроще будет, нежели на hdl,
сам писал как то 256 точечный с пипилайнингом. Как вспомню так вздогну.

Насколько я помню = разрядность увеличиваеться в среднем на 1.5 разряда на на одну бабочку --- т.о. на 1024 точки - 2**10 = 1.5 р *10 = 15раз
Т.о. чтобы не потерять информации необходимо иметь дело на выходе с разрядностью вх.разр+15 разр. (для 1024 т. фурье)