Быстрое преобразование Фурье (FFT) на Arduino с высокой скоростью

Быстрое преобразование Фурье (Fast Fourier Transform, FFT) находит широкое применение в современной радиотехнике – с его помощью можно не только построить спектр анализируемого сигнала, но оно также необходимо в большинстве операций цифровой обработки сигналов (ЦОС).

Измерение частоты принимаемого сигнала является достаточно сложной задачей для платы Arduino вследствие ее ограниченной вычислительной мощности. Для этой цели частоты используются методы анализа перехода сигнала через ноль – то есть просто измеряется количество переходов сигналов через ноль за определенное время. Но эти методы не работают когда анализируемый сигнал является комбинацией нескольких частот.

Быстрое преобразование Фурье (FFT) на Arduino с высокой скоростьюВ данной статье предпринята попытка написания кода для платы Arduino, позволяющего производить анализ сигналов не вдаваясь глубоко в сущность математических процессов, лежащих в его основе. Этот проект не объясняет принципы быстрого преобразования Фурье (БПФ), но объясняет его использование в Arduino.

Ранее на нашем сайте мы уже рассматривали использование быстрого преобразования Фурье в плате Arduino в следующих проектах:

Но в этих проектах БПФ в Arduino реализовано с помощью специализированных библиотек, в этом же проекте оно реализовано “вручную”, без использования библиотек, и оно позволяет достичь более высоких скоростей БПФ по сравнению с использованием библиотек.

Дискретное преобразование Фурье с высокой скоростью

Чтобы сделать дискретное преобразование Фурье (ДПФ, DFT) более быстрым чем БПФ, James Cooley и John Tukey разработали специальный алгоритм. Некоторые эксперты считают, что этот алгоритм является одним из самых значимых научных прорывов XX века. Данный алгоритм разделяет сигнал на четную и нечетную части, что значительно уменьшает объем необходимых вычислений. При помощи ряда других операций данный алгоритм позволяет свести вычислительную сложность преобразования Фурье к величине NlogN. Обычное ДФП имеет сложность N*N, поэтому данный алгоритм обеспечивает существенное увеличение скорости работы по сравнению с обычным ДПФ при больших N. БПФ также обладает вычислительной сложностью порядка N*logN.

Объяснение данного “революционного” алгоритма ДПФ не является темой настоящей статьи. Посмотреть принципы данного алгоритма вы можете в следующих англоязычных источниках:

https://flylib.com/books/en/2.729.1/derivation_of_the_radix_2_fft_algorithm.html

https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/

https://cnx.org/contents/8D0YvnW1@7.1:zmcmahhR@7/Decimation-in-time-DIT-Radix-2-FFT

https://en.wikipedia.org/wiki/Fast_Fourier_transform#History

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

Общие принципы работы программы

Быстрое преобразование Фурье предполагает многократное вычисление синусов и косинусов. Встроенная в Arduino функция для данных операций не обладает хорошей скоростью работы и требует достаточно много времени для получения приемлемого результата. Чтобы преодолеть недостатки этой функции мы будем значение синуса от 0 до 90 градусов сохранять кратным числу 255, что избавит нас от необходимости использования вещественных чисел (float) и мы сможем хранить эти значения в переменных типа byte, что обеспечивает четырехкратную экономию памяти Arduino. Массив sine_data[ ], который мы будем использовать, необходимо объявить в самом верху программы как глобальный.

Также нам понадобится глобальный массив f_peaks[], который будет обновляться после каждого вызова функции расчета БПФ (FFT). Элемент f_peaks[0] содержит доминирующую (основную) частоту, остальные элементы массива содержат значения в убывающем порядке.

Поскольку мы храним в массиве все значения синуса от 0 до 90 градусов, то мы легко сможем рассчитать любое значение синуса или косинуса. Далее мы будем использовать функцию, которая будет округлять число до первого значения после запятой и возвращать значение из сохраненных данных. Для нашего метода необходима только одна операция с плавающей точкой. От этого недостатка метода тоже можно избавиться если хранить значения синуса, не кратные 255, но это съест много памяти Arduino.

Использованная нами процедура уменьшает точность вычислений, но зато увеличивает их скорость. Для 64 точек она обеспечивает увеличение скорости расчета на 8 мс по сравнению с традиционным подходом, а для 128 точек увеличение скорости расчета составит 20 мс.

Объяснение функции для вычисления БПФ

БПФ может выполняться только на числе отсчетов, кратных 2^n, то есть 4, 8, 16, 32, 64 и т.д. Если число отсчетов не будет равно 2^n, то будут приниматься во внимание только младшие отсчеты. То есть, к примеру, если число отсчетов будет равно 70, то мы будем принимать во внимание только первые 64 отсчета, а остальные отсчеты будут отбрасываться (не учитываться).

Таким образом, БПФ мы будем выполнять на числе отсчетов, равных 2^n, например:

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048,...

Две переменные вещественного типа out_r и out_im будут занимать достаточно большое количество памяти. Для платы Arduino Nano рассматриваемый алгоритм не будет работать при числе отсчетов большем 128 вследствие недостатка свободной памяти.

Итак, наш алгоритм вычисления БПФ для платы Arduino будет состоять из следующей последовательности действий:

  1. Код программы генерирует биты в обратном порядке для заданного размера выборки (подробнее о реверсировании битов в шаге 2).
  2. Входные данные упорядочиваются в соответствии с сгенерированным порядком.
  3. Выполняется БПФ (FFT).
  4. Вычисляется амплитуда комплексного числа.
  5. Обнаруженные максимумы упорядочиваются в убывающем порядке.
  6. Результаты записываются в массив f_peaks[].

Чтобы получить доступ к другим значениям, находящимся в стороне от пиковой частоты (частоты гармоники), код программы необходимо изменить таким образом, чтобы локальные переменные можно было копировать в некоторые заранее определенные глобальные переменные.

Схема проекта

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

Схема проекта

Тестирование работы проекта

Для теста написанной программы на ее вход было подано обычно колебание треугольной формы (треугольная волна) с частотой 1.25 Гц. Частота выборки отсчетов для этого колебания составила 10 Гц.

Как показано далее на видео, первоначальные выходные значения программы (raw output) представляют собой рассчитанные значения БПФ, но пока это не те значения, которые нам нужны – они с уменьшенной точностью.

В массиве выходных частот присутствуют частоты 1.25 и 3.75. При этом нет необходимости каждый раз получать точное значение этих частот. Часто эти числа называются элементами разрешения по частоте (frequency bins), то есть выходное значение должно находиться внутри указанных интервалов.

Скорость работы программы для платы Arduino Nano:

16 точек: 4ms

32 точек: 10ms

64 точек: 26ms

128 точек: 53ms

Итак, рассмотренный код программы для вычисления быстрого преобразования Фурье (FFT) можно использовать в приложениях реального времени. Для выполнения расчета необходимо около 30 мс времени. Разрешающая способность программы ограничена числом используемых отсчетов, число которых, в свою очередь, ограничено памятью платы Arduino. Число анализируемых отсчетов и, соответственно, точность работы алгоритма можно улучшить использую платы с большим объемом памяти чем у Arduino Nano - Arduino Mega и т.д.

Исходный код программы (скетча)

Видео, демонстрирующее работу проекта

Источник статьи

(Проголосуй первым!)
Загрузка...
50 просмотров


Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *