ДПФ/БПФ/ДКП на Cortex-M3 (1986ВЕ94Т), Вычисление БПФ на ARM Опции

[uwboy]

Господа!
Есть необходимость решить задачу спектрального анализа квазипериодического сигнала. Частота дискретизации не менее 80 кГц (изначально 100 кГц, но возможно выбрать исходя из удобного числа отсчётов). Поступает сигнал непрерывно. Спектральный анализ проводится сначала приблизительный — на первой четверти выборки; затем точный — на всей выборке. Длина полной выборки 1 секунда. Для спектрального анализа следует выполнить одно из дискретных преобразований Фурье (как несведущий затрудняюсь определить).
Для ЦОС собираюсь использовать микросхему (1986ВЕ94Т, 1986ВЕ93Т или 1986ВЕ92Т). Предварительно планирую систему следующим образом. Буфер для исходных отсчётов собираюсь организовать на отдельных двух микросхемах (1645РУ4АУ): первая хранит первую четверть выборки и результаты ДПФ, вторая — остаток выборки. Перенаправлять вывод с внешнего АЦП собираюсь внешней же логикой. Сразу после захвата первой четверти отсчётов МК следует начать ДПФ на первой четверти выборки. Закончить следует быстрее, чем 250 мс (соответствует времени захвата четверти выборки), при этом должно остаться немного времени на анализ спектра (поиск пиков). По завершении захвата остатка выборки, МК выполняет ДПФ на первой четверти и остатке менее, чем за секунду.

Вопросы такие:

1. Успеет МК выполнить ДПФ?
2. Какой случай ДПФ более предпочтителен (вход — действительные целые, выход — амплитуды целые/дробные)?
3. Значительно ли повысит быстродействие количество отсчётов являющееся степенью числа 2?
4. Возможно ли использовать внутренний АЦП микросхемы 1986ВЕ94Т и единственную микросхему СОЗУ и копировать из внутреннего АЦП во внешнее СОЗУ отсчёты по прерываниям АЦП во время вычисления ДПФ? Не сильно ли это притормозит основную программу (ДПФ)?
5. Значительно ли вырастет производительность ДПФ при использовании внутренней СОЗУ микросхемы 1986ВЕ94Т для части операций?

Поправьте, если я неправильно задаю вопрос или не в тот раздел обращаюсь. Поиск использовал, но просветления не достиг. Заранее спасибо, джентльмены!

[Golikov A.]

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

[MSP430F]

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

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

[prig]

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

Вообще-то, 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мс.

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

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

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

[MSP430F]

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

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

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

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

[_pv]

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

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

[MSP430F]

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

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

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

[Golikov A.]

Я не понял, здесь люди что-нибудь в теме понимают, или, как часто на форумах бывает, дилетанты от нечего делать язык чешут. Чуток хоть надо в топике понимать.
Итак, имеем БПФ на 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)

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

[MSP430F]

Кто-нибудь может привести проверенный рабочий код на C (можно ссылку) целочисленного БПФ, использующего 32-разрядную (не выше) арифметику для 16-разрядных чисел ?

И чтобы без потери точности при вычислениях.

Сообщение отредактировал MSP430F - Aug 22 2013, 11:16

[prig]

И чтобы без потери точности при вычислениях.

Вообще без потери точности? Такого не найдёте, т.к. с точки зрения реальных задач это полный абсурд.

Сообщение отредактировал prig - Aug 22 2013, 13:19

[MSP430F]

Вообще без потери точности? Такого не найдёте, т.к. с точки зрения реальных задач это полный абсурд.

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

Все что я смог найти, лишь на 1024 точки. Думаю, что все-таки сделать БПФ на 4096 точки с честными 16 разрядами на целочисленной 32-битной орифметике невозможно в принципе, потому и прошу, покажите мне такой код, а то больше смахивает на троллинг.

Сообщение отредактировал MSP430F - Aug 22 2013, 14:01

[prig]

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

Все что я смог найти, лишь на 1024 точки. Думаю, что все-таки сделать БПФ на 4096 точки с честными 16 разрядами на целочисленной 32-битной орифметике невозможно в принципе, потому и прошу, покажите мне такой код, а то больше смахивает на троллинг.

Любой код с фикс. точкой 1.31 (нотация по ADI; с форматом и тем, как с ним работать, предлагаю разобраться самому).
Размещаете данные в младших 19-ти битах и знаковом разряде (не забыв правильно заполнить биты, куда не попали исходные данные). Коэффициенты 32 бита.
После преобразования данные нормализуются в нужный формат.

20 бит - это 122дБ. ДД преобразования будет примерно на уровне 110дБ.
Это эквиваленто снижению SNR исходного идеального 16-бит сигнала(98дБ) на величину менее 1 дБ.
Для сигнала на уровне 90дБ о привнесённом шуме можно будет вообще забыть.
Вы собираетесь работать со значениями SNR 98дБ? Сильно сомневаюсь.

Это моё понимание вопроса.
Могу несколько ошибаться в значениях (таки, лучше промоделировать для конкретной системы). Опустил некоторые детали.
Подход достаточно стандартный. Работает на 100%. Проверено на реальном железе.

А вот что Вы понимаете под "той же точностью" и чего хотите добиться, вопрос тёмный.

ПС Естественно, для 64К надо будет использовать 16 бит из 32 или прикручивать дополнительную нормализацию между стадиями, что и есть групповая плавающая точка.

Сообщение отредактировал prig - Aug 22 2013, 16:47