http://www.embeddedsignals.com/ARM.htm
там бенчмарки есть, для длины 4096 - сотня тактов на отсчёт.
32 bit FFT increases dynamic range by 90 dB , needs extra 20% to 50% cycles

нет.

Всем доброго времени суток!
Не балует гугл ответами на запрос о 1986ВЕ94Т. Эта тема - одна из трех (!) на весь инет ссылок! Миландр рулит!
У меня аналогичная задача как у топикстартера, и то же на этом МК. Только требования поскромнее. Надо посчитать БПФ для 4096 точек за 1 секунду. Чувствую, что МК справится. Хочу считать на float (32 бита), double не нужен, АЦП у меня 16 бит. В этой работе www.rf.unn.ru/NATO/1ws/SfP_Perov.pdf‎ люди посчитали, что для АЦП с разрядность от 11 до 23 float достаточно.

1986ВЕ94Т - это Cortex-M3, есть встроенный умножитель за 1 такт 32x32. Ответьте, пожалуйста, кто знает, сколько тактов занимает в таком МК умножение двух float ? Судя по http://habrahabr.ru/sandbox/58129/ даже целочисленные вычисления зависят от компилятора, поэтому если есть несколько результатов, приведите все. Спасибо.

Извиняюсь, правильная ссылка вот

как мне тут указали несколькими постами выше, что и 32 бит с фиксированной точкой должно хватить, и умножение у вас будет делаться за 1 такт, может попробовать так?

Я не понимаю, как можно реализовать целочисленное БПФ с 32 разрядными числами и получить хоть какую-нить приемлемую точность?

32 инт это
от +- 2 147 483 648
соответственно можно считать что это

+- 21474.83648

или
+- 214748.3648

в целом правда разрядов дофига... в той статье что вы приводили они использовали 16 битный инт, и посчитали его пригодным для рассчета 11 бит АЦП, а он +-32768. С 32 битным получается на порядок больше целых, и еще 4 десятичных знака.. Главное не потерять точность в вычислениях.

Вообще-то, 32 разряда дают динамический диапазон, который в реальной практике не встречается.
Ну, потеряются при БПФ несколько битов от 32-х, как это скажется на результате? Да никак. С 16-ю битами тоже не всё плохо.

В своё время приходилось делать оценку 16-бит версий БПФ с групповой плавающей точкой для 8К. Потеря точности (оценка по шуму) - примерно 1...2 бита.
При нормировании данных к 15-ти битам, шум от 8К 16-бит радикс-2 БПФ сопоставим с шумом 14-бит оцифровки.
Т.е. SNR преобразования что-то около 86дБ для шумоподобного сигнала. А вот 4-й радикс шумней на 6дБ из-за дополнительной потери 1-го бита при постадийном нормировании.

В том, что касается сабжа, на перемножителе 32*32 можно сделать вполне приемлимый вариант улучшенного 16-битного(16 данные+16 защита) БПФ на 64К с фикс. точкой. Лучше 90 дБ по шуму вполне достижимо. Потерь точности из-за нормирования данных ни на 2-м ни на 4-м радиксе не будет.

А вот со временем выполнения всё несколько сложнее. Эффективность кода по сравнению с сигнальниками будет существенно ниже.
8К 16-бит радикс-2 БПФ с групповой плавающей точкой на 533МГц блэкфине, со всем что можно в L1-памяти, выполняется за 1мс.
Грубая прикидка для 64К на 80МГц М3 даёт что-то около 350мс (1*10*7*5, где 5 - опять же, грубая оценка эффективности к блэкфину).

Так что, выбор 1986ВЕ94Е для данной задачи ТС несколько сомнителен.
Но что бы сказать наверняка, можно попробовать найти готовый радикс-4 и проверить на реальной железке или симуляторе.

Если искать что-нибудь другое, следует учитывать большой объём данных. Если не размещать данные и коэффициенты в памяти/кэше первого уровня, производительность может очень сильно упасть. На том же 533МГц блэкфине для 64к будет использоваться внешняя SDRAM. Результат будет на уровне 100мс вместо ожидаемых 10мс.


Фикс точка на 32 бита (20 данные + 12 защита) Вам более чем хватит. 1986ВЕ94Е сгодится.
float (32 бита) - 24 значащих бита и экспонента. Это явно избыточно и слишком затратно. Проще разобраться с фикс. точкой.

Сообщение отредактировал prig - Aug 21 2013, 17:23

533000 тактов на 8к отсчётов это 65тактов на отсчёт,
ftp://ftp.analog.com/pub/www/technology/d...kfin_FftDct.zip :

соответственно 1507505 для длины 65536 или 23 такта на отсчёт, только вот памяти под коэффициенты не напасёшся.
в ссылке выше fft для M3 получалось как раз в 5 раз больше около сотни тактов на отсчёт при 4096.

Вот здесь человек пишет буквально следующее
" Перед автором стояла задача написать преобразование Фурье на 2048 точек при разрядности исходных данных 16 бит. Из-за отсутствия арифметического сопроцессора пришлось делать целочисленное преобразование, что создало некоторые трудности. При разрядности исходных данных 16 бит разрядность коэффициентов должна быть не менее 16, чтобы не происходило потери точности. Их произведение содержит 32 разряда. 2048 точек дают еще 11 дополнительных разрядов, а это значит, что в 32-разрядное процессорное слово промежуточные данные не помещаются. Вычисление каждой “бабочки” ведется с точностью 64 разряда, а результат округляется до 32 разрядов. "

Как Вы тогда можете это прокомментировать ?

были данные 16 разрядов сделали преобразование Фурье, стало вдруг 32 разряда, если теперь обратное сделать чтобы исходные данные получить для результата уже 64 бита понадобится?
кто мешал по ходу округлять чтобы из 32 бит не вылезать.

это математическая оценка. Которая во всех случаях даст 100% точность без потери
в общем случае перемножение двух 16 битных чисел дает 32 битное число, если вы перемножите два максимальных числа, но если вы перемножите два числа в серединке, то получится бит 20-24...
этим и пользуются практики.

Я когда свое делал тоже оценивал по максимуму, потому в итоге решил не мучатся и даблами все сделать. Если же надо оптимизить, то может имеет смысл прикинуть реальные уровни сигнала.


Кстати у меня вопрос. Когда делаете 16 битное фурье на тучу точек, вычисления ведут в 20-32 битах, но время от времени округляют до 16? Потому что просто прям суммировать 16 бит точно переполнится, даже при 11 битах входных...
А процедура округления и нормировки не создает лишних тактов больше чем если бы сразу во флотах считать?

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

Я не понял, здесь люди что-нибудь в теме понимают, или, как часто на форумах бывает, дилетанты от нечего делать язык чешут. Чуток хоть надо в топике понимать.
Итак, имеем БПФ на 4096 точек. Используем целочисленную арифметику. Это 12 этапов (log2 4096) умножений в общем случае комплексных (это сейчас не принципиально) чисел. Если АЦП на 16 разрядов, то, чтобы не потерять точность при умножениях, коэффициенты должны быть не хуже по разрядности, пусть тоже будет 16 бит. Первый этап. Умножаем два таких числа. В худшем случае получается 32 битное число. А впереди еще 11 этапов. Чтобы не потерять точность при округлениях, результат надо разделить на 2 в 15, и мы получили промежуточный результат уже 17-ти разрядный. Умножаем его на коэффициент, который опять-таки 16-разрядный и получаем 33-разярядное число. К концу этапов, коих 12, имеем 44 разряда.

Если округлять на каждом этапе до 32 бит, это будет эквивалентно в итоге использованию 4-разрядных коэффициентов ! Круто, да ? И кому будет нужна такая точность ?

Ну и каша у Вас в голове. Результат рассуждений соответствующий.
Попробуйте разобратся с тем, что такое фикс. точка, и как её используют.




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




Я примерно так и оценивал, но это действительно грубая оценка.
Кто знает, сколько придётся обрабатывать эту заготовку напильником, и что из этого получится?

да это верно, и не верно одновременно...

4 разрядные коэффициенты это
0 1 2 3

хотим посчитать
1/2 + 1/2 + 1/2 + 1/2 = 0.5 + 0.5 + 0.5 + 0.5= 2;
в этих терминах 4 разрядных чисел
0.5 == 1
1/2 + 1/2 + 1/2 + 1/2 = 0.5 + 0.5 +0.5 + 0.5 = 1 + 1 + 1 + 1 = 4== 0;



если мы возьмем 3 разрядный
0 1 2 3 4 5 6 7
и будем считать что у нас младший разряд после точки, то получим
0 0.5 1 1.5 2 2.5 3 3.5

берем наш пример
1/2 + 1/2 + 1/2 + 1/2
переводим его в 3 разрядные числа
1/2 + 1/2 + 1/2 + 1/2 = 0.5 + 0.5 +0.5 + 0.5 = 1 + 1 + 1 + 1 = 4
переводим результат обратно в 2 разрядные
4 == 2 .

посчитано точно, причем в начале и конце 2 разрядные числа в середине 3 разрядные.

так что считать в 32 битных числах 16 битные значения, а потом нормировать обратно в 16 бит, это не тоже самое что сразу отрезать начало. Хотя я думаю вы тоже это знаете, это я так на всякий случай...


Теперь что происходит с флоат.

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

то есть это как
2 + 4 + 8 + 4 == 2*(1+2+4+2)

именно этим и пользуются при счете в целых, как я понимаю....

У меня PIC32 (ядро MIPS32, 40MHz) справлялся с FFT8192 за примерно 530 мс (оптимизация кода на минимуме, это отладка была). Все расчеты делаются в floaf, причем плавающей точки в процессоре нет (все программно, стандартными функциями компилятора). Это совершенно без ухищрений и допиливаний, сишные исходники FFT тоже стандартные из интернета. Скорость устраивает- значит не лезу улучшать.

Уверен, что ARM должен быть шустрее.