Максимально возможное окно для FFT при 64МБ ОЗУ. Опции

[kolobochishe]

Посоветуйте алгоритм (точнее его реализацию на С или С++) для ARM9 (NXP LPC3250) с ОЗУ 64МБ.
Один рабочий нашел вот тут. "Прицепил" к своему проекту. Все работает, но до величины окна 65536. Больше - и программа виснет. Под "кучу" выделил 15МБ ОЗУ. В принципе если постараться, то можно еще 40МБ добавить.

Интересует вопрос - каковы требования к объему памяти разных алгоритмов?




Тему можно удалить. Проблема не в БПФ, а во мне массив для получения результата не того размера подготовил

[kolobochishe]

Хотя нет тему не стоит удалять. В общем у меня получилось примерно так.

тип double (8 байт) на реальную часть и тип double (8 байт) на мнимую часть. Если величина окна 2^20=1048576, то получается на исходный массив выборок - 16МБ, плюс 8МБ на массив WStore (пока не вник, не знаю точно можно от него избавится или нет). В итоге примерно 24МБ - вот такие требования. Мне пока не хватает примерно 4МБ, поэтому окно 2^19.

Считает это дело мое устройство примерно секунд 50 (100МГц тактовая, 64МБ 100МГц SDRAM). Есть у кого алгоритмы получше?



Где то вроде видел что-то такое: сделать много FFT последовательно накладывая окна, а потом эти результаты подвергнуть еще раз какому-то преобразованию. В итоге будет большое окно с маленькими требованиями к памяти. Такое возможно?

[blackfin]

Считает это дело мое устройство примерно секунд 50 (100МГц тактовая, 64МБ 100МГц SDRAM).

А сколько нужно? 49 секунд устроит?

И какая нужна точность по амплитуде на выходе?

Для целочисленных алгоритмов число "шумящих" разрядов растет примерно как 0.5*[log2(N)-2], так что для FFT на 65536 точек с фиксированной запятой Вы потеряете семь младших бит.

Точнее можно промоделировать в MATLAB'е.

PS. Кстати, для вещественных данных: Efficient_FFT_Computation_of_Real_Input

[kolobochishe]

А сколько нужно? 49 секунд устроит?

И какая нужна точность по амплитуде на выходе?

Для целочисленных алгоритмов число "шумящих" разрядов растет примерно как 0.5*[log2(N)-2], так что для FFT на 65536 точек с фиксированной запятой Вы потеряете семь младших бит.

Точнее можно промоделировать в MATLAB'е.

PS. Кстати, для вещественных данных: Efficient_FFT_Computation_of_Real_Input

нет. 49 тоже многовато до 5 секунд было бы хорошо.
АЦП 16 бит - поэтому очень жалко 7 бит терять. Или я неправильно понял?

...
Если использование длинного окна обусловлено требованиями к разрешению, кардинально ничего Вы не измените.
...
PS. Есть один такой чувак который лет 20 уже пишет книгу и библиотек про быстрые преобразования. Там посмотрите, может найдете "на месте". Там их столько, что огого. http://www.jjj.de/fxt/

Нет. Требование к разрешению примерно 100 Гц. 16384 элемента вполне хватает. Требование по времени, которое охватывает БПФ. Т.е. спектр за 1 секунду, например. Итого - 2млн элементов. Разрешение 1Гц мне не надо.

За ссылку спасибо

[blackfin]

АЦП 16 бит - поэтому очень жалко 7 бит терять. Или я неправильно понял?

Всё правильно. Если процессор целочисленный, можно посчитать FFT в целых числах - в формате "fract 24.8".

Сообщение отредактировал blackfin - Mar 26 2012, 09:36