Быстрое преобразование Фурье (БПФ, или Fast Fourier Transform, FFT) это эффективный алгоритм для вычисления дискретного преобразования Фурье (Discrete Fourier Transform, DFT). FFT может быть на порядок быстрее, чем DFT, особенно на буферах большой длины. Алгоритмы, описанные в этой статье (перевод документации [1]), работают с комплексными данными (Complex FFT, CFFT). Имеется также отдельный набор функций, посвященный обработке реальных последовательностей чисел [2].

В библиотеке CMSIS DSP для обработки разных типов данных (float, Q15 и Q31) используются раздельные алгоритмы.

Функции FFT работают с данными "по месту". Это значит, что в массив, где находятся входные данные, также используется для сохранения соответствующего результата обработки. Входные (и выходные) комплексные данные хранятся в массиве как чередующиеся значения реальное/мнимое (действительная длина массива получается в 2 раза больше, чем количество выборок, 2*fftLen):

{real[0], imag[0], real[1], imag[1], ...}

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

[Обработка выборок с плавающей запятой (float32)]

FFT для комплексных данных float использует алгоритм смешанного основания (mixed-radix). Несколько стадий radix-8 выполняются с одной стадией radix-2 или radix-4, по мере необходимости. Алгоритм поддерживает определенные длины буфера [16, 32, 64, ..., 4096], и для каждой длины используется своя таблица коэффициентов вращения (twiddle factor table).

Функция использует стандартное определение БПФ, и при вычислении прямого преобразования выходные значения могут расти в соответствии с коэффициентом fftLen (длина FFT). Обратное преобразование как часть вычислений масштабирует значения в пропорции 1/fftLen, и это соответствует каноническому описанию обратного преобразования БПФ частотный домен - временной домен (inverse FFT, IFFT).

Предварительно инициализированные структуры данных, содержащие данные таблиц коэффициентов вращения и таблиц реверсирования бит, предоставлены и определены в заголовочном файле arm_const_structs.h. Подключите этот заголовок в свою функцию и затем передайте указатель на таблицу коэффициентов а качестве аргумента функции arm_cfft_f32. Пример вычисления 64-точечного комплексного FFT, включая реверсирование бит:

arm_cfft_f32(&arm_cfft_sR_f32_len64, pBuffer, 1, 1);

Структуры данных, описывающих преобразование (в этом примере это таблица коэффициентов вращения arm_cfft_sR_f32_len64), обрабатываются как данные констант, и во время вычислений не модифицируются. Одна и та же структура данных может быть использована повторно для нескольких преобразований, включая смешанное использование прямого и обратного преобразований.

Ранние релизы библиотеки предоставляли отдельные алгоритмы radix-2 и radix-4, которые работали с данными float. Эти функции считаются устаревшими, однако все еще предоставляются для совместимости. Старые функции работают медленнее, и не имеют такой же удобный и обобщенный интерфейс для использования, как новые функции.

Пример инициализации констант для функции arm_cfft_f32:

   const static arm_cfft_instance_f32 *S;
   ...
   switch (length)
   {
   case 16:
      S = &arm_cfft_sR_f32_len16;
      break;
   case 32:
      S = &arm_cfft_sR_f32_len32;
      break;
   case 64:
      S = &arm_cfft_sR_f32_len64;
      break;
   case 128:
      S = &arm_cfft_sR_f32_len128;
      break;
   case 256:
      S = &arm_cfft_sR_f32_len256;
      break;
   case 512:
      S = &arm_cfft_sR_f32_len512;
      break;
   case 1024:
      S = &arm_cfft_sR_f32_len1024;
      break;
   case 2048:
      S = &arm_cfft_sR_f32_len2048;
      break;
   case 4096:
      S = &arm_cfft_sR_f32_len4096;
      break;
   }

[Обработка выборок с фиксированной запятой (Q15 и Q31)]

Интерфейс вызова функций FFT для обработки данных с фиксированной запятой Q15 и Q31 аналогичен интерфейсу функций float. Просто используется другие имена функций:

arm_cfft_q15         // для CFFT-обработки типов Q15
arm_cfft_q31         // для CFFT-обработки типов Q31

Аналогично используются другие таблицы коэффициентов вращения, с измененными именами. Пример инициализации констант для функции arm_cfft_q31:

   const static arm_cfft_instance_q31 *S;
   ...
   switch (length)
   {
   case 16:
      S = &arm_cfft_sR_q31_len16;
      break;
   case 32:
      S = &arm_cfft_sR_q31_len32;
      break;
   case 64:
      S = &arm_cfft_sR_q31_len64;
      break;
   case 128:
      S = &arm_cfft_sR_q31_len128;
      break;
   case 256:
      S = &arm_cfft_sR_q31_len256;
      break;
   case 512:
      S = &arm_cfft_sR_q31_len512;
      break;
   case 1024:
      S = &arm_cfft_sR_q31_len1024;
      break;
   case 2048:
      S = &arm_cfft_sR_q31_len2048;
      break;
   case 4096:
      S = &arm_cfft_sR_q31_len4096;
      break;
   }

[Сравнение скорости работы]

Процессор STM32F429, рабочая частота 168 МГц, буфер обработки находится в SDRAM, таблица коэффициентов вращения во FLASH. Время обработки буфера из 2048 комплексных выборок показано в таблице ниже.

Результат немного обескураживает, но факт — обработка для float работает ощутимо быстрее. Вероятно это из-за аппаратной поддержки вычислений с плавающей точкой на STM32F4.

[Ссылки]

1. Complex FFT Functions site:keil.com.
2. CMSIS DSP: функции БПФ для обработки действительных чисел.