Целочисленные алгоритмы ЦОС, надо сформулировать правила Опции

[Zelepuk]

Существует рабочий алгоритм(несколько фильтров и БПФ). Код работает на плавучке на обычном десктопе.
Стоит задача портировать алгоритм на процессор с фиксированой точкой.
Отсчёты, над которыми производятся преобразования, поступают в формате 1.15.
Понимаю что тупое преобразование float в int ни к чему хорошему не приведёт.
Тогда стоит вопрос: какие требования к оперрациям нужно предъявить?

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

(лучше если примеры коротенькие на С будут)

Используется 32-битный процессор на ARM9E ядре

Заранее спасибо.



Сообщение отредактировал Zelepuk - Mar 6 2011, 07:48

[Ruslan1]

еще может интересно будет, насчет целочисленной реализации БПФ посмотрите вот это

Вроде нареканий не было и чистый си, хоть куда лепится И очень экономно подходит к используемой памяти, как RAM так и ROM.
Используются 16-битные знаковые числа. Очень удобно напрямую данные с АЦП подсовывать, ну или после нормирования, чтобы максимально использовать все биты.

[MSP430F]

еще может интересно будет, насчет целочисленной реализации БПФ посмотрите вот это

Вроде нареканий не было и чистый си, хоть куда лепится И очень экономно подходит к используемой памяти, как RAM так и ROM.
Используются 16-битные знаковые числа. Очень удобно напрямую данные с АЦП подсовывать, ну или после нормирования, чтобы максимально использовать все биты.

Скажите, а можно этот код переделать на 4096 точек (там сейчас 1024) ? Ответьте, пожалуйста. Очень надо.

[Zelepuk]

Скажите, а можно этот код переделать на 4096 точек (там сейчас 1024) ? Ответьте, пожалуйста. Очень надо.

конечно можно! За отдельную плату готов предоставить готовую реализацию на 4096 точек

P.S. Протестировано на MSP430F47197 в проекте счётчика электроэнергии.

Сообщение отредактировал Zelepuk - Aug 23 2013, 07:57

[MSP430F]

конечно можно! За отдельную плату готов предоставить готовую реализацию на 4096 точек

P.S. Протестировано на MSP430F47197 в проекте счётчика электроэнергии.

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

[Zelepuk]

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

почему недостатачно? как вы считаете? у меня всё было достатачно точно, единственное что: нужно данные масштабировать в нужных местах.

Сообщение отредактировал Zelepuk - Aug 23 2013, 09:03

[MSP430F]

почему недостатачно? как вы считаете? у меня всё было достатачно точно, единственное что: нужно данные масштабировать в нужных местах.

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

И как же можно тогда все посчитать в 32 разрядах без потери точности ?

[Corner]

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

И как же можно тогда все посчитать в 32 разрядах без потери точности ?

С учетом Cortex-M3 можно использовать 32 битное умножение со знаком и 64 бит накопление - SMLAL инструкция. Для signed long long компилер сам подставит.
Вот если нет 64 бит аккумулятора, то можно использовать отдельно знаковое умножение с арифметическим сдвигом на 32 (взятие старшей части от умножения), тогда коэффициенты придется обрезать по модулю (считать за 1), чтобы они не превышали ((64 - Х)/2) бит, где Х - log N по основанию 2, а N - число точек (максимум 16384 точки). Это лишь вопрос к правильной табличке синусов. Уровень шума не вырастет больше чем на 1 дБ. При этом использовать максимальное отрицательное число для выбранного размера нельзя. Например, для 24 бит синус должен лежать в диапазоне от -8388607 до +8388607.
Обрезать результат сильнее нельзя, так как если, к примеру, использовать 16 бит знаковые данные и 16 бит знаковый синус, то динамический диапазон уже ни при каком числе точек не превысит 87 дБ (3 дБ "съедает" формат синусов), даже если результат накапливать в 64 битном аккумуляторе без потерь.