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

[kolobochishe]

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

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




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

[kolobochishe]

Вот сейчас в голову пришла такая "идея". Если разрешение по частоте допустимо порядка 100Гц, то брать последовательно по шкале времени участки (N штук) по 16384 элементов, вычислить для каждого FFT, просуммировать коэффициенты одинаковых частот и поделить на количество участков N. Получим спектральную характеристику продолжительного участка, но с небольшими требованиями к памяти и небольшим размером файла результата.

Как идея?

Одно "НО". Как суммировать коэффициенты? векторно (как комплексные числа) или по модулю?

По сути это вариант "скользящего" окна, но с суммированием.

[fontp]

Вот сейчас в голову пришла такая "идея". Если разрешение по частоте допустимо порядка 100Гц, то брать последовательно по шкале времени участки (N штук) по 16384 элементов, вычислить для каждого FFT, просуммировать коэффициенты одинаковых частот и поделить на количество участков N. Получим спектральную характеристику продолжительного участка, но с небольшими требованиями к памяти и небольшим размером файла результата.

Как идея?

Одно "НО". Как суммировать коэффициенты? векторно (как комплексные числа) или по модулю?

По сути это вариант "скользящего" окна, но с суммированием.

Идея так себе. Перидиограммы так и считают, но там ставится цель не обеспечить разрешение, а усреднить случайные флуктуации. Однако разрешение при некогерентном складывании "многих окон" не возрастет вообще, а определяется размером преобразования.

Если же складывать когерентно, но с пропусками, то шаг между бинами Фурье конечно уменьшится и будет определяться максимальным расстоянием между отсчетами. Но частотная функция окна (преобразование Фурье от временной) будет очень широко размазана и убьет всё разрешение. Т.е. значения соседних бинов будут очень сильно размазаны.

Хочется готовое 100% работающее решение. Имел ввиду что-то, что кардинально изменит требования к памяти и скорость, а не использование других типов. Ну и чтобы кто-нибудь поделился своим мнением и опытом по поводу различных реализаций БПФ.

Если использование длинного окна обусловлено требованиями к разрешению, кардинально ничего Вы не измените.
Скорость немного можно подправить использованием целых типов, а требование по памяти немного можно уменьшить как сказано выше, если считать синусы/косинусы итеративно, а не держать таблицу. Короткий целый тип тоже даст экономию в двое.
Кроме того можно найти реализации без всяких больших рабочих массивов WSTORE, в том числе и "на месте", т.е. такие чтобы входной массив совпадал с выходным. Теретически можно избавиться от всех таблиц (синусных и инверсной адресации) и провести преобразование "на месте". Тогда получите N/2 от ОЗУ


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