тогда какой смысл в данных с разрядностью более 12 бит ?

В данных? Или в разрядности поворачивающего множителя (W)?
Для примера:
1) возьмите последовательность данных с разрядностью 8 и с разрядностью поворачивающего множителя то же 8 и сделайте над ними БПФ, а потом ОБПФ. Зафиксируйте результат.
2) возьмите такую же разрядность данных, но для операций вычисления БПФ и ОБПФ возьмите разрядность поворачивающего множителя равной к примеру 6. Зафиксируйте результат.
Сравните результаты в п.1 и п.2. В идеале должна получится та же последовательность данных что и была, легко догадаться где будут различия.

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

К сожалению, нету fixed модели по рукой БПФ. Может кто-нибудь сможет привести подобное иследование и ответить на вопрос, какую разрядность W необходимо иметь для входных данных 16бит ?

Это исследование необходимо для понимания (т.е. в образовательных целях=)) на что влияет разрядность W.
Для 16 бит, чтобы вычислять БПФ с максимальной точностью, необходимо иметь поворачивающие множители с разрядностью 16 бит.

А может мне кто ни будь подсказать как этот fft модуль использовать в другом проекте ?
Вот например, у меня есть шина данных 16 бит (оцифрованный звук) и куда её подцепить?
Я пытался создать символ файла FFT_2048.vhd в Quartus 11 он не создает, пишет что не поддерживает пользовательский тип complex_data_bus.
Error (10017): Can't create symbol/include/instantiation/component file for entity "FFT_2048" because port "EXT_DATA_i" are not currently supported by the Quartus II symbol/include/instantiation/component file generator

Вы, очевидно, пытаетесь вставить модуль в графическую схему. В этом случае придется написать "обертку" у которой в качестве входов и выходов будут std_logic/std_logic_vector и которая подключит эти сигналы стандартных типов к сигналам с пользовательским типом (complex_data_bus, например).



Увы, на данный момент его еще рано использовать в другом проекте. К сожалению, пока БПФ остается не завершенным. Использовать Вы его сможете, только если доделаете его сами.





Если для 16-ти разрядных данных взять 16-ти разрядные коэффициенты, то это не даст максимальную точность вычислений. Разрядность данных, причем не входных, а внутренних, для хранения промежуточных результатов, должна быть больше, чем коэффициентов. Т.е. если для 16-ти разрядных коэффициентов разрядность данных взять, к примеру, 18, то точность вычислений будет выше, чем для 16-ти разрядных данных.

Когда разрядность данных == разрядности коэффициентов, то при умножении на коэффициенты с малыми значениями будет "ощутимое" количество раз происходить обнуление результата.

Например, возьмем 5-ти разрядные коэффициенты и данные. Тогда за 1.0 у нас будет 8 (01000b). 00001b будет соответствовать 0.125. Если 0.875 * 0.125, то в арифметике с плавающей точкой получим 0.109375, но в арифметике с фиксированной точкой получим 0: (00111b * 00001b) >> 4.

Так что точность вычислений складывается из многих факторов. Потери точности также зависят и от того каким именно образом делать вычисления.

Возникла идея сделать в ПЛИСе не только само вычисление FFT, но и усреднение результата по нескольким прогонам. Используется стандартная корка от Xilinx, на выходе она выдает действительную и мнимую части отсчетов. Как правильнее подойти к задаче - усреднять по модулю или усреднять действительную и мнимую части, а потом уже брать модуль?

Согласен с Вами, но я имел в виду что при прочих равных. Так то понятно, ошибки округления никуда не деть.



Ключевые слова для поиска: Когерентное и не когерентное накопление.

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


Не думаю. В данном случае оба варианта - некогерентное накопление. Если только каждые "прогоны"сигнала не набирались засинхронизированными, как в осциллографах. А будет ли раздельное усреднение мнимой и действительной части давать лучший результат? Не знаю. Наверное...

Лучший результат по какому критерию? К примеру для когерентных РЛС, которые ведут единую обработку с нескольких каналов не когерентное накопление сродни чуме, т.е. там где фазовая информация важна то стопроцентно надо усреднять/накапливать когерентно. Но, к примеру в РСА иногда для избавления от "спекл шума" производят не когерентное накопление уже когерентно накопленных пачек и картинка существенно улучшается.

Когерентное накопление - когда пачки (кадры, реализации) накоплены засинхронизированными по какому-то событию. Скажем, в РЛС, по зондирующему импульсу. В осциллографах - по срабатыванию триггера синхронизации.
А что такое некогерентное усреднение когерентно накопленных пачек, мне не понятно. И обратное - когерентное усреднение некогерентно накопленных пачек - выглядит нонсенсом.

Я бы немного уточнил бы, сказал что когерентные сигналы уже созданы "синхронизированными" между собой, к примеру в РЛС сигналы синтезировались от одного опорного генератора. Т.е. их и оцифровывать для сохранения когерентности надо от того же источника, что бы в дальнейшим можно было оптимально накопить (когерентно сложить).



Сугубо для борьбы со "спекл шумом" это делается. А вот обратное делать реально нонсенс.

Я согласен с вами, только уточню свою мысль еще раз.
Не бывает когерентного или некогерентного усреднения. А бывает усреднение когерентных (собранных синхронно) или некогерентных данных.
И усреднение модуля или поотдельности действительной и мнимой частей спектра к когерентности не имеют отношения.

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

Ну, два варианта уже высказаны - синхронизация в осциллографе, синхронизация в РЛС.
Например, микроконтроллер оцифровывает напряжение сети ~230V. Собирает некоторое количество выборок (кадр данных) для измерения, вычисления спектра.
Как обнаружилось, что напряжение перешло через 0 (можно прямо по коду АЦП), отсчитываем нужное количество выборок до конца кадра. Каждый раз одно и то же. Вот и синхронность (когерентность). Из-за шума будет некоторый сдвиг по времени от кадра к кадру. И из-за несинхронности частоты сети и частоты преобразования. Но это небольшие сдвиги.
А дальше вычислить спектр для каждого собранного кадра. А дальше усреднить действительные и мнимые части.

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

Теперь рассмотрим тот же случай, но только прогон Вы начинаете со случайной фазы входного синуса. В этом случае, в каждом прогоне будут разные значения мнимой и действительной части на выходе БПФ, но модуль ( sqrt( im^2 + re^2) ) будет всегда одинаковый. Усредняя модуль Вы будете получать всегда одно и то же значение среднего модуля. Если Вы будете усреднять отдельно действительную и мнимую части, то при усреднении небольшого количества прогонов получите сильно заниженное значение модуля вычисляя его по отдельно усредненным re и im. При увеличении количества прогонов модуль, вычисленный по отдельно усредненным re и im будет неуклонно стремиться к 0.

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

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

Да. При таком раскладе усреднять нужно модуль.

нельзя ли об этом подробнее?
почему-то тот же Xilinx CoreIP FFT wizard предлагает только варианты реализаций Radix-2 & Radix-2 Lite
да и гугл говорит что больше всего ищут "FFT radix 2" & "FFT radix 8"


>> 4-х точечный БПФ, где все поворачивающие множители равны либо 1, либо -1

означает ли это что можно вообще обойтись без умножителей?


ЗЫЖ как насчёт Radix-8 FFT ?

ЗЫЫЖ интересуют данные алгоритмы в применении к БПФ на относительно большое число точек (2048)

upd
вот какое сравнение в слайдах нашёл

На мой взгляд, нет смысла вычислять FFT быстрее, чем заполняется входной буфер, а Radix-2 этому требованию, вроде как, удовлетворяет.

ну, еще есть такая штука как latency, которая м.б. критична во многих приложениях. ей и меряются наравне с ресурсами



а cмысл, которого хочется достичь -
1) экономия площади (поэтому сравнивается обычно количество наиболее ресурсозатратных примитивов - умножителей )
2) при фиксированном количестве точек память особо не поэкономишь, поэтому переходят на экономию обращений к памяти (уменьшение конфликтов)


в ПЛИС как раз-таки благодяря использованию сегментов блочной двухпортовой памяти снимается ограничение по обращениям (много операций чтения/записи из многих сегментов BlockRAM одновременно)

в VLSI же как правило имеется 1 большой кусок DualPort RAM и там уже эти обращения становятся критичными

Так количество умножений в алгоритме FFT и количество использованных аппаратных умножителей в IP-core это не одно и тоже..

Конечно нет! Речь идет только о вычислении самой бабочки. 2-х и 4-х точечные бабочки имеют тривиальные коэффициенты и поэтому для их вычисления умножителей не требуются. Для всех остальных бабочек не все коэффициенты тривиальны (для 3-х, 5-ти и т.д. точечной бабочки все не тривиальны) и для вычисления самой бабочки требуются умножители. Стоит заметить, что требуются умножители на константу и если в ПЛИС нет DSP-блоков и все реализуется на простых лог. элементах, то умножители на константу занимают меньше площади (площадь зависит от значения константы) .

Однако, до или после бабочки (в зависимости от схемы) нужно домножать данные на поворачивающие коэффициенты. И здесь без умножителей не обойтись.



Непонятно что значит "Complexity" и в каких попугаях.



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

Например, можно вычислять БПФ "переливая" из одного модуля памяти в другой и обратно, а можно сделать так называемое inplace БПФ и сэкономить память. Можно все вычисления выполнить одной бабочкой, а можно несколько бабочек считать в параллель. Да и саму бабочку можно вычислять параллельно, а можно последовательно. Если параллельно, то, скажем, для 4-х точечной бабочки нужно поставить параллельно 3 умножителя, а если последовательно вычислять, то 1.

Если, к примеру, бабочка вычисляется последовательно, то нужно учитывать количество математических операций умножения . Скажем, 16-ти точечное БПФ при вычислении 2-х точечной бабочкой требует 4 этапа и, соответственно, нужно вычислить 4 этапа * 8 бабочек * 2 точки = 64 "точки" и произвести 4 этапа * 8 бабочек * 1 умножение = 32 операции умножения. При вычислении 4-х точечной бабочкой требует 2 этапа и, соответственно, нужно вычислить 2 этапа * 4 бабочки * 4 точки = 32 точки и произвести 2 этапа * 4 бабочки * 3 умножения = 24 операции умножения.

Понятие "последовательное вычисление" бабочки тоже не однозначно т.к. надо уточнять какие именно вычисления выполняются последовательно: для вычисления одной "выходной" точки 2-х точечной бабочки нужно сложить 2 комплексных числа, а для 4-х точечной бабочки нужно сложить 4 комплексных числа.

БПФ с бабочками не 2 в степени N. Это что то новенькое...

Так это для вас "это что-то новенькое"..

А для всех остальных это все отнюдь не ново: Radix-3,5, Radix-3,6,12.

Не говоря уж про классическое "БПФ с бабочками 4 и 8 в степени N": Radix-4,8.

Прошу помощи у знатоков! Возникла необходимость реализовать БПФ на плис Альтера. Сидеть разбираться и с нуля писать времени нет. Знаю про мега функцию FFT, хочу воспользоваться её. Кто пользовался, поделитесь опытом?
Может есть видео уроки или литература какая-нибудь. Блок создал, а какие сигналы и откуда их подключать не знаю. Подскажите!!!

ug_fft

спасибо. а примеров случайно нет?

Я работал лишь с Xilinx FFT core, но вот сейчас открыл альтеровский UG на их FFT ядро и вижу что там исчерпывающая информация, включая тайминги диаграммы, после которых никакие примеры больше не нужны.
Есть ли конкретные вопросы? Добавить компонент ведь труда не составляет, тогда может уже есть какие-то вопросы, которые я по аналогии смогу помочь прояснить?

Я новичок в этом деле, писал только простые алгоритмы, поэтому не судите строго.
Создать компонент не составило труда, но какие вх/ вых.сигналы от куда и куда подать тут загвоздка.
Если не трудно объясните НУБику))
Откуда взять вещественные и мнимые значения сигнала?
Как я понимаю должна быть память, где будут храниться значения, которые будет брать компонент?!
мне бы примерную блок-схему для начала.

Можно из космоса. Поймать антенной, снести на нужную частоту, оцифровать и подать в ПЛИС. А внутри уже - на БПФ.

ЭМмм, Остряк!

Можно по делу, прояви остроумие в помощи.

Это и было по делу. Если не устраивает такой ответ, то неплохо было бы расписать задачу поконкретнее. Реализовать БПФ? Ну так вставляете корку, собираете прошивку. Откуда взять входной сигнал? Так а что БПФить-то надо? Так то ноль это тоже входной сигнал. Не нравится ноль, можно счетчик подать.

Хорошо. Нужно с помощью плис Аltera реализовать БПФ. Есть аналоговый сигнал, который проходит через АЦП и поступает на ПЛИС, вот его как раз и нужно БПФить.
если еще конкретика нужна спрашивайте!
Я впервые имею дело с этим. Компонент вставить нет труда, а чем его "обвешать" не знаю. То есть как выделить мнимую и вещественную часть? Нужно ли организовывать доп. память, где будут храниться отсчеты перед выполнением компонентом БПФ или это уже встроено и достаточно только напрямую подавать данные, тогда для чего импульсы подавать для начала и конца кадра подачи данных?!

Может, кто сжалится надо мною и объяснит с низов, что делать и как работать со встроенной FFT, а то инет перерыл нигде нет инфы подробной, только теория об БПФ.

Что за аналоговый сигнал, каковы его параметры? Какой АЦП используется? Какая частота дискретизации?

Моделировать-то это дело вы будете, али сразу в железо загонять?

Для простоты, для начала можно забить на мнимую часть и подавать только действительную.
Что касается импульсов начала и конца кадра, то на входе есть только начало кадра - sink_sop. Поскольку БПФ вырабатывает пачку выходных частот (256, 512, 1024), то и на входе блоку нужна пачка. sink_sop - маркер начала этой пачки на входе.
Подали на вход 1024 отсчета АЦП, на выходе получили 1024 частоты.

Синусоидальный сигнал, частотой 1 МГц. АЦП еще не подбирал. Пока моделировать не планировал, а там как пойдет.
То есть я правильно понимаю, что должна быть память в которую будет записываться 1024 отсчета?

Память уже есть внутри FFT. Вам нужно разобраться с тем, как работает интерфейс Avalon.

Пропустить через sin/cos, либо подать на мнимые входы нули. Всё зависит от того, какой сигнал БПФить.
Обычно, когда берутся за такие задачи, уже есть устоявшаяся модель и подобных вопросов возникать уже не должно.

Почему бы для начала не сделать то же самое на Python или Matlab? Ну будет эта штука выдавать некие результаты - как это отлаживать? Я отлаживал сравнивая результаты обработки одного и того же сигнала мат моделью и работу IP-ядра FFT на HDL-симуляторе. Таких чудес насмотрелся, так что представляю какая будет боль при отладке FFT без этого.

из знакомых ни кто этим не занимался. А тут пришлось, упала задача. Я согласен, что моделировать надо, но для начала надо разобраться как слепить это все!

может у кого есть учебное пособие как подобное реализуется! Вы же познали это где-то?!

Ребята, Мужики!
Я благодарю вас всех, что откликнулись!
Вы люди с опытом в этом деле, поэтому не могли бы с самых низов расписать, с чего начать, чтобы решить данную задачку.

Начать с модели, с ней же и сравнивать. Вы пытаетесь создать сложную роботизированную лестницу чтобы сорвать яблоко, а достаточно лишь слегка потрясти яблоню. Не надо пытаться уйти от создания примитивной модели, это бессмысленно и контрпродуктивно.

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

А учебного пособия нет ровно по той причине, потому что учебное пособие на всё на свете писать не имеет смысла, ведь есть инструкции, да и те почти не читают, когда всё и так понятно. Вот альтеровский FFT UG содержит 100.0% необходимой информации, что после модели вообще не возникает вопросов что куда засовывать.

модель в матлабе создавать?

что-то совсем запутали!
как в матлабе делать БПФ я знаю.
Что вы подразумеваете под словом "модель"? Полное описание системы включая АЦП и ПЛИС в матлабе?

Если Вы выбираете допустим N=128 частоту дискретизации 2 МГц и разрядность 10 бит, то матлаб должен дать представление, какой результат ожидать на выходе после обработки первого сэмпла. Если значение первого же сэмпла будет отличаться от ожиданий, или выходить не в том порядке, или знак не такой, то это сразу поможет понять где проблема. Это ведь общие истины для любого алгоритма, разве нет?

Конечно, гении могут обходиться без такой ерунды как мат модели