Оптимизация дискретного преобразования Фурье, Как уменьшить время вычисления ДПФ? Опции

[Olegas]

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

Сейчас вычисляю ДПФ формулами по определению (формулы ниже, плюс ещё вычисление амплитуды). При обработке одного слова требуется выполнить 30 преобразований Фурье. Число отсчётов лежит в пределах 200 - 500 (конкретное значение заранее неизвестно), но одинаковое для всех тридцати преобразований.



В результате при реализации такого алгоритма на stm32f417 при частоте 168 МГц и арифметике с 32-битными float эти 30 преобразований (анализ одного произнесённого слова) вычисляются четыре-пять секунд, что составляет большую часть времени всех вычислений (80%).

Для вычисления коэффициентов ДПФ и квадратных корней использую функции DSP-ядра этого микроконтроллера (синус, косинус, квадратный корень). И большую часть времени (68%) занимает как раз вычисление этих самых коэффициентов.

Как ещё можно ускорить вычисление ДПФ?

[=GM=]

Для вычисления коэффициентов ДПФ и квадратных корней использую функции DSP-ядра этого микроконтроллера (синус, косинус, квадратный корень). И большую часть времени (68%) занимает как раз вычисление этих самых коэффициентов. Как ещё можно ускорить вычисление ДПФ?

Ну так, заранее вычислите эти коэффициенты и разместите их в таблице.

У меня на 100 МГц ДСП двойной МАК для преобразования Фурье вычисляется за 10 нс. Т.о., для 200-500 точек время счёта Re/Im одной палки составит порядка 2-5 мкс. Для 30 частот время счета составит 60-150 мкс. Но это прикид для 100 МГц тактовой, а у вас 168 МГц тактовая, так что о каких секундах может идти речь?

[Olegas]

Ну так, заранее вычислите эти коэффициенты и разместите их в таблице.

Я, наверное, неоптимально представляю, но для N отсчётов ДПФ требуется матрица размером N^2. Взяв по максимуму N=500 получим: 4*N^2=4*500^2/1024=976 КБ. Многовато.

[=GM=]

Я, наверное, неоптимально представляю, но для N отсчётов ДПФ требуется матрица размером N^2. Взяв по максимуму N=500 получим: 4*N^2=4*500^2/1024=976 КБ

Ну прямо в лоб-то считать не надо. Ваша таблица по рядам (и по столбцам) будет многократно повторяться.

Лучше составьте таблицу одного периода синуса на N=500 точек (для двоичного ЦПУ практичнее брать число N степени двойки, например N=512).
Для первой палки считаете МАКи, беря синусы: 0,1,2,..,499 (всего 500), для второй палки берете каждый второй: 0,2,4,..,498,0,2,4,..,498 (всего 500).
Для третьей палки берете каждый третий:0,3,6,.. (всего 500) и так далее.

Ну и не надо считать компоненты спектра (пресловутые "палки") выше частоты Найквиста, поскольку амплитудный спектр симметричен.