LINUX.ORG.RU

Посоветуйте целочисленный FFT для эмбедов

 , , ,


0

2

Надо делать FFT на 512 точек, для fixed point Q15 / Q31 (еще не определился)

С удивлением обнаружил, что CMSIS DSP генерит немеряные таблицы, которые не влазят в 32К флеша. И это после обрезки лишних.

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

★★★★★

Можно попробовать kissfft

Аллокация памяти там есть, но она относительно легко отпиливается руками. https://github.com/mborgerding/kissfft/blob/8f47a67f595a6641c566087bf5277034b... - эта вот функция аллоцирует память и заполняет синусы. Можно эту функцию посчитать заранее и подставить инициализированный массив туда.

Fixed-point есть, вот https://github.com/mborgerding/kissfft/blob/8f47a67f595a6641c566087bf5277034b...

SZT ★★★★★ ()
Ответ на: комментарий от SZT

Дык я гуглил, вариантов есть немало. Хочется чтобы кто-то сказал что-то вроде «я юзал в эмбедах <URL>, работает, выходит XXX циклов на отсчет»

IMHO FFT не та задача, где надо до сих пор что-то руками писать.

Vit ★★★★★ ()
Последнее исправление: Vit (всего исправлений: 1)
Ответ на: комментарий от SZT

https://github.com/stg/SYLT-FFT можешь вот это глянуть? Глаза разбегаются, что там дергать для прямого преобразования (сэмплы в спектр)

  • Почему-то автор бенчмаркает fft_inverse
  • https://github.com/stg/SYLT-FFT/blob/master/fft.h#L251 тут почему-то написано «This allows us to output N*2 point of real data using a N point complex (I)FFT». Непонятно откуда возьмется в 2 раза больше точек.
  • В ридми указано «Minimal twiddle tables (512 bytes for max N=512 FFT)», а я этой тиблицы вообще не нашел.
Vit ★★★★★ ()
Ответ на: комментарий от Vit

Сразу скажу, что я не специалист в FFT. Когда мне надо было считать на контроллере FFT, я просто взял kissfft, отпилил там аллокации памяти, вбив статический масссив из синусов, и меня это устроило. Каких-то сложных замеров на конкретном контроллере я не делал

Глаза разбегаются, что там дергать для прямого преобразования (сэмплы в спектр)

Думаю, это void fft_fft(fft_complex_t *complex, unsigned bits) : https://github.com/stg/SYLT-FFT/blob/c6f58caa8d3d01c622768b5c66a0be1d7953235b... «Спектр» оно пишет туда же, откуда читает сэмплы. Это конечно не спектр, для спектра надо sqrt(Re^2+Im^2) еще. Применение FFTW для рисования спектрограммы (комментарий) - тут я FFTW когда-то разбирался, функция convert()

В ридми указано «Minimal twiddle tables (512 bytes for max N=512 FFT)», а я этой тиблицы вообще не нашел.

Под «twiddle tables» понимается предвычисленные синусы. В CMSIS это вот тут https://arm-software.github.io/CMSIS_5/DSP/html/group__CFFT__CIFFT.html#ga3f7...

Там эта таблица тут https://github.com/stg/SYLT-FFT/blob/c6f58caa8d3d01c622768b5c66a0be1d7953235b...

SZT ★★★★★ ()
Последнее исправление: SZT (всего исправлений: 2)
Ответ на: комментарий от SZT

Спасибо. Успел списаться с автором SYLT-FFT. В тикетах обсудили, как отрефакторить для юзабельности. Скоро всем будет щщастье.

Vit ★★★★★ ()
Ограничение на отправку комментариев: только для зарегистрированных пользователей