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

[Olegas]

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

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



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

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

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

[_pv]

FFT требует ~100 тактов на отсчёт, соответственно не жалко потратить ещё десяток тактов на отсчёт и сделать resampling, чтобы точек было всегда 512, ну или хотя бы просто нулями буфер дозабить по длине до 512 точек.
соответственно для 30 FFT * 512 точек * 100 тактов надо 1.5-2МГц, или 10мс при 168МГц.

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

будет несколько тысяч тактов на отсчёт, но если надо только несколько частот, а не весь спектр, может быть быстрее чем через FFT

Код

float SpecPowerGoertzel(float * y, int num, float dt, float w){
  const float K = 2.0 * cos(w * dt / num);
  float s1 = 0, s2 = 0;
  for (int i = 0; i < num; i++){
    float s0 = y[i] + K * s1 - s2;
    s2 = s1;
    s1 = s0;
  }
  return (s2*s2 + s1*s1 - K * s1 * s2) / ((float)num * num);
}

только корень еще навеное взять надо и почему оно на длину выборки делилось, причём дважды, уже не вспомню.