целочисленное БПФ в формате 1.15

Дмитрий К
Сообщения: 29
Зарегистрирован: 02 мар 2011, 09:48

целочисленное БПФ в формате 1.15

Сообщение Дмитрий К »

Здравствуйте!

Меня интересует вопрос относительно целочисленной арифметики.

Я принимаю данные с АЦП в формате 1.15
Мой процессор AT91SAM9260

Я совсем новичок, и пок ане совсем понятно как происходят элементарные операции над такими числами.
В итоге мне надо делать БПФ на этом процессоре.
Нуждаюсь в примерах элементарных операций (умножение, сложение...)
Интересны так же приёмы как избежать переполнения.
Желательны примеры на С (хотя бы короткие для наглядности)

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: целочисленное БПФ в формате 1.15

Сообщение Бахурин Сергей »

все целочисленные операции производятся в столбик например сложить два числа:
1001
0101
-----
1110

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

Дмитрий К
Сообщения: 29
Зарегистрирован: 02 мар 2011, 09:48

Re: целочисленное БПФ в формате 1.15

Сообщение Дмитрий К »

Я понимаю чтов столбик))))

Пример: фильтрация данных, принимаемых с АЦП.
Процессор 32-битный.

К примеру, принимаем с АЦП данные в виде 1.15.
Коэффиценты фильтра тоже должны быть 1.15?
Что нужно учесть при сложении(как учесть возможное появление доп разряда)?
Что нужно учесть при умножении (ведь результат умножения 32битное число, можно просто урезать до 16?)?
Как правильно делить (какие операции производить с делимым и делителем перед делением)?

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: целочисленное БПФ в формате 1.15

Сообщение Бахурин Сергей »

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

int a = 12345;
int b = 12345;
int c = a*b;

Представление чисел должно быть в одинаковым для данных с АЦП и данных в процессоре. АЦП ваш сколько бит? Фильтр какой БИХ или КИХ?

Дмитрий К
Сообщения: 29
Зарегистрирован: 02 мар 2011, 09:48

Re: целочисленное БПФ в формате 1.15

Сообщение Дмитрий К »

1)Фильтр КИХ, АЦП 16 бит.
Процессор AT91SAM9260 незнаю где смотреть как это реализовано в нём аппаратно...

2) да когда я пишу на си
int a = 12345;
int b = 12345;
int c = a*b;

Я не думаю. Потому что int c - 32 бита. и всё путём.
Но я начинаю думать когда:
int x = c*c;
...

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: целочисленное БПФ в формате 1.15

Сообщение Бахурин Сергей »

при 16 битных входных данных и 32 битных к-тах ких фильтра вы никогда не получите переполнения если сумма



где N - порядок КИХ фильтра, а h(n) его коэффициенты

Дмитрий К
Сообщения: 29
Зарегистрирован: 02 мар 2011, 09:48

Re: целочисленное БПФ в формате 1.15

Сообщение Дмитрий К »

Вот нашёл отрывок статьи

"Когда вычисления FFT осуществляются с фиксированой точкой, разрядность сигнала быстро растёт.
На один разряд на каждой ступени по максимуму (а статистически на пол-разряда). Для 16-разрядных вычислений это беда - разрядность быстро теряется. Например, если длина блока FFT 256, то не выходя за пределы 16 разрядов можно преобразовывать только входные 8-разрядные данные. Единственный выход из положения - это результаты бабочек каждой ступени блочно номализовать. Т.е. измерять блочную экспоненту и приводить фиксированую точку на место."

Хотелось бы подробнее узнать про "постановку запятой наместо" и "нормализуцию"

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: целочисленное БПФ в формате 1.15

Сообщение Бахурин Сергей »

я вообще не понимаю о чем речь. Вы хотите использовать целочисленную арифметику? Тогда причем тут приведение точки? Если мы говорим о точке, то имеются ввиду уже не целочисленные операции. Из приведенной цитаты я не понимаю что такое блочная экспонента и как ее надо нормализовать. Думаю по поводу fft вам стоит для начала почитать Блэйхута и к Нуссбаумера:
Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов: Пер. с англ. - М.: Мир, 1989. - 448 с.
Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток: Пер. с англ. - М.: Радио и связь, 1985. - 248 с.

Дмитрий К
Сообщения: 29
Зарегистрирован: 02 мар 2011, 09:48

Re: целочисленное БПФ в формате 1.15

Сообщение Дмитрий К »

Когда говорят о точке при целочисленных вычислениях имеют ввиду, то что точка мнимая. Оперируем с целыми числами, но некторое кол-во бит отводим под целую, некоторое кол-во бит под дробную часть.

Вот: http://microsin.ru/content/view/37/44/

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: целочисленное БПФ в формате 1.15

Сообщение Бахурин Сергей »

фиксированная точка не спасет вас от переполнения. От переполнения вас спасет плавающая точка . Переведите ваши 16 битные отсчеты во float и дальше обрабатывайте как float без головной боли

Ответить