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

[Zelepuk]

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

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

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

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

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



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

[DASM]

Странно, дока говорит иное.Вы уверены, что это не проблемы компилятора/ассемблера / ключей?

[Corner]

Странно, дока говорит иное.Вы уверены, что это не проблемы компилятора/ассемблера / ключей?

Только умножение 32*32=32 - MULS


Сообщение отредактировал Corner - Sep 19 2013, 15:39

[AndrewN]

Только умножение 32*32=32 - MULS

Для пробразования размером 4К Х 16 этого хватит с избытком. N = 2¹² даёт рост 12 бит максимум.

[Corner]

Для пробразования размером 4К Х 16 этого хватит с избытком. N = 2¹² даёт рост 12 бит максимум.

16+16+12=44, как тут в 32 укладываться?

[AndrewN]

16+16+12=44, как тут в 32 укладываться?

А так и не делается, даже в флоатинг пойнт (24 Х 24 -> 48 но младшие биты округляются до 24. Даже Пентиум - и тот ошибается, потому что внутренне он свои 64 Х 64 -> 128, но потом таки округляет обратно до 64).

Так и тут, 16 Х 16 -> 32, и округляются до 16. Умножения роста не дают, сложение может дать рост в 1 бит на одну фазу БПФ. В итоге 16 + 12 -> 28, укладывается в 32.

Но на самом деле и так поступают довольно редко. Обычно фаза БПФ завершается сдвигом вправо на 1, т.е. масштабированием - с округлением, конечно. Соответственно, результат остаётся тем же Q16.15 что и исходные данные.

Наихудший (в смысле потери точности) метод, это когда вместо масштабирования после бабочек, исходные данные "т..о" сдвигают вправо на число фаз БПФ перед преобразованием (N=256 - на 8, 4096 - на 12...), зато скорость вычислений существенно растёт, так что и так делают.

Конечно, любое умножение делается с округлением, и сложение, если результат масштабируется, тоже. Жизнь несовершенна, но если знать в чём, то жить можно :)

Если есть много времени, то можно данные обрабатывать, например, как Q64.32 =~ плавать в "безошибочном" уютном озере :)

Сообщение отредактировал AndrewN - Sep 24 2013, 21:55

[Corner]

А так и не делается, даже в флоатинг пойнт (24 Х 24 -> 48 но младшие биты округляются до 24. Даже Пентиум - и тот ошибается, потому что внутренне он свои 64 Х 64 -> 128, но потом таки округляет обратно до 64).

Так и тут, 16 Х 16 -> 32, и округляются до 16. Умножения роста не дают, сложение может дать рост в 1 бит на одну фазу БПФ. В итоге 16 + 12 -> 28, укладывается в 32.

Но на самом деле и так поступают довольно редко. Обычно фаза БПФ завершается сдвигом вправо на 1, т.е. масштабированием - с округлением, конечно. Соответственно, результат остаётся тем же Q16.15 что и исходные данные.

Наихудший (в смысле потери точности) метод, это когда вместо масштабирования после бабочек, исходные данные "т..о" сдвигают вправо на число фаз БПФ перед преобразованием (N=256 - на 8, 4096 - на 12...), зато скорость вычислений существенно растёт, так что и так делают.

Конечно, любое умножение делается с округлением, и сложение, если результат масштабируется, тоже. Жизнь несовершенна, но если знать в чём, то жить можно

Если есть много времени, то можно данные обрабатывать, например, как Q64.32 =~ плавать в "безошибочном" уютном озере

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

Сообщение отредактировал Corner - Sep 29 2013, 09:19