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

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

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

Прямо с Википедии, или адресок подскажете?

Попробуйте поискать гуглом с ключевым словом fix-fft.

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

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

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

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

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

все настолько просто, что влезет прямо сюда. Копирайт не мой, ну может что-то под себя чуть поменял, но точно не алгоритм Где на просторах интернета взял- уж и не найду теперь.
там два файла, хедер и си

Кстати, что любопытно: я даже от таблицы отказался, синусы-косинусы на ходу считаю. Сначала была таблица, но снес (большая и, как я говорил уже, рекорды скорости не ставил).
Сравнивал алгоритм с результатами Матлабовской функции: разница не превышает рассчетную из-за разной битности данных.

Любой код с фикс. точкой 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

По поводу дополнительной обработки спектра после Фурье. 1. Перед расчетом нужно использовать окно, отличное от прямоугольного. В зависимости от выбранной функции можно оптимизировать различные параметры. Мы использовали окно Гаусса, т.к. требовалось получить максимально точные значения амплитуд. В любом случае форма линии в спектре повторяет форму оконной функции. Если пик одиночный, то можно расчитать его положение по 3 - 5 точкам у вершины гораздо точнее одного бина, используя метод наименьших квадратов. Вы получаете параметры функции - положение и амплитуду. В
Вашем случае, когда может быть непредсказуемая модуляция, она может вносить ошибку, но, полагаю, незначительную по частоте. В случае наложения двух пиков в пределах ширины ответ будет произвольным и разрешить эти линии не удасться.

Вы наверное очень в теме, а мы совсем не в теме. Мне на данный момент БПФ с фикс точкой не нужно, но для общего развития интересно. Не могли бы вы немного спуститься до нашего уровня и разъяснить что есть:

фикс.точка 1.31, да еще и в нотации ADI.
какие данные надо разместить в младших 19 битах, и чем правильно заполнить биты? Какой формат нужный?
И сколько бит вы предлагали использовать для 4К точек, 19? тогда для 64К почему 16?

Вы написали много текста, но пропустив некоторые для вас "очевидные" вещи, сделали для нас простых смертных его полностью не читаемым...

хотя может я один такой, не понимающий.

А я о чем говорю? Если коэффиценты у Вас 32 бита (очень хорошие, кстати, коэффициенты), то как Вы собираетесь реализовывать арифметику в 32 разрядах ? Я же не спорю о том, что целочисленные вычисления - это круто. Я только говорю, что если у меня данные честные 16-битные и я хочу получить на выходе спектр с диапазоном тоже в 90 дБ, то целочисленных вычислений в 32 разрядов для этого не достаточно. Для этого-то человек ЗДЕСЬ и использует вычисления с точностью 64 разряда.

Знаете, сильно лень. И так мого букв, и так много времени потрачено. Разве что, из чисто альтруистических соображений.
Так что, считайте это только подсказками, когда будете разбираться.

- ADI я упомянул сознательно, и именно потому, что у них всё это хозяйство с фикс. точкой описано достаточно хорошо и подробно.
Полистайте их доки на сигнальники, статьи и книжки по DSP. У TI всё то же самое, но описано несколько хуже.
А в длинных и умных книжках могут так запутать простые вещи, что без пол-банки...

Если вкратце и грубо:
1.31 - запись вещественных чисел со знаком (фактически - целое число). Диапазон типа +-0.9999... Умножение в этом формате (фактически, это целочисленное со знаком 32*32 с дополнительным сдвигом влево на один бит и округлением результата до 32-битного числа) даёт результат в этом же формате. Т.е., если умножается 0.0999.. на 0.9999.., должно получаться 0.0999... С точностью до младшего бита, есстественно.

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

- Результат вычисления бабочки радикс-2 может вырасти на один бит (в два раза) по сравнению с исходными значениями. Если использовать 1.31 без постадийного нормирования, то для 4К приходится оставлять 12 "запасных" бит, а для 64К - 16. Т.о. получается, что в первом случае округление будет вестись по фактическим 20-ти разрядам, а во втором - по 16-ти.

Если использовать постадийное нормирование (групповую плавающую точку), требуется 1 "запасной" бит для радикс-2 и 2 бита для радикс-4. Производительность упадёт, но всё-равно будет лучше, чем для 32-битного числа с плавающей точкой. А точность выше оного.

П.С. Поймите меня правильно. Я не пытаюсь устроить здесь ликбез или что-то кому-то показать. Время это занимает много, толку для меня самого почти никакого.
Так что, ещё раз повторюсь, считайте это только подсказками для желающих изучить вопрос. Не более.


О, теперь понял, о чем это Вы.
Оказывается, Вы не в курсе, что при целочисленном умножении 32*32 получается 64-битный результат, который может благополучно округляться.

Пишите много, но не емко...
и того.



ADI означает фирму, и надо обращаться к их программным кодам



1.31 означает 1 бит знака, 31 бит - значащие



наверное все таки влево, иначе вы просто обнулите число или я чего то не понимаю? Да и вообще сдвигая 32 бита на 32 бита вы получите либо 0 либо 64 бита, тут хотелось бы определенности. Потому что если 0, то это глупо, а если 64, то откуда у нас 32 битная арифметика?



Почему опять у вас 4К БПФ стало 20 разрядным, а 64К - 16 разрядным? Или вы считаете число отбрасываемых разрядов?



Ну вас трудно понять, потому и времени занимает много. Были бы ближе к народу, было бы быстрее, может в этом для вас был бы толк? Много раз убеждался объясняя самые простые вещи всегда и для себя что-то новое понимаешь...


П.С. кстати все время упускаются процы с арифм модулем которые флоты за 1 такт перемножают, а таких не мало...












естественно если у вас 32 битные операнды, то все их виды без потерь перемножить можно только в 64 битном числе

Но если у вас коэффициенты 32 битные, но со значениями от -2^15 .. +2^15, то у вас они фактически 16 битные, и их можно перемножить в 32 битах без потерь. Игра идет на том что реальный сигнал и реальные коэффициенты никогда не занимают весь диапазон иначе бы не помогли ни флоты ни даблы.

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

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

посмотри это

-Обращаться к программным кодам ADI не обязательно. Достаточно разобраться с с форматами и арифметикой.

- 1.31(нотация ADI) означает вещественное, 1 бит знака, 31 бит - дробная часть в дополнительном коде

- Для правильной работы БПФ в формате с фиксированной точкой 1.X и произвольными данными, исходные данные арифметически сдвигаются вправо на необходимое количество "защитных" бит N, где N - двоичный логарифм размерности БПФ.

- "Фактической" разрядностью БПФ в формате с фиксированной точкой можно считать разрядность арифметики минус количество "защитных" бит N.

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

Так там на ASM, к тому же 32-бита не под Cortex M3, а только для ARM 9E.



То есть для 16-разрядных данных в 4096 точках "фактическая" разрядность БПФ = 16 - 12 = 4. Так по Вашему ?