EasyFFT — надежная библиотека БПФ для проектов на Arduino

Компоненты и материалы

Arduino Nano R3

×

1

Приложения и сервисы

Arduino IDE

О проекте

Измерение частоты по захваченному сигналу — сложная задача, особенно на Arduino с ограниченной вычислительной мощностью. Существуют методы перехода через ноль, но они не работают для сигналов, состоящих из нескольких частот.

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

Проект не объясняет теорию БПФ, а фокусируется на практическом применении. Процесс также показан в прилагаемом видео.

Если интересует только применение — переходите сразу к шагу 3.

Для БПФ с высшей скоростью (в 3 раза) при небольшой потере точности (~5%) см. мою статью ApproxFFT: https://create.arduino.cc/projecthub/abhilashpatel121/approxfft-fastest-fft-function-for-arduino-fd4917

Шаг 1: Быстрое преобразование Фурье

Алгоритм БПФ был разработан Джеймсом Кули и Джоном Тьюки для ускорения ДПФ. Он считается одним из самых важных алгоритмов XX века. БПФ разделяет сигнал на четные и нечетные части, снижая количество вычислений. Обычное ДПФ требует N² комплексных умножений, БПФ — только N·logN, что критично при большом числе отсчетов.

Ссылки для изучения математики БПФ:

1. https://flylib.com/books/en/2.729.1/derivation_of_...
2. https://jakevdp.github.io/blog/2013/08/28/understa...
3. https://cnx.org/contents/8D0YvnW1@7.1:zmcmahhR@7/D...
4. https://en.wikipedia.org/wiki/Fast_Fourier_transfo...

Шаг 2: Пояснение кода — быстрые синус и косинус

БПФ многократно вычисляет синусы/косинусы. Стандартные функции Arduino медленные (удваивают время для 64 отсчетов). Решение: храним значения синуса для 0–90° как кратные 255 в массиве byte sine_data[91]. Это позволяет хранить данные в байтах (в 4 раза меньше памяти), а не во float.

Массив sine_data[] нужно разместить в начале программы как глобальную переменную.

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

byte sine_data[91] = { 0, 4, 9, 13, 18, 22, 27, 31, 35, 40, 44, 49, 53, 57, 62, 66, 70, 75, 79, 83, 87, 91, 96, 100, 104, 108, 112, 116, 120, 124, 127, 131, 135, 139, 143, 146, 150, 153, 157, 160, 164, 167, 171, 174, 177, 180, 183, 186, 189, 192, 195, 198, 201, 204, 206, 209, 211, 214, 216, 219, 221, 223, 225, 227, 229, 231, 233, 235, 236, 238, 240, 241, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 253, 254, 254, 254, 255, 255, 255, 255 };
float f_peaks[5];

Функции sine() и cosine() округляют угол до целого и берут значение из таблицы. Требуется одно деление с плавающей точкой. Это снижает точность, но ускоряет работу: для 64 точек +8 мс, для 128 — +20 мс.

Шаг 3: Функция БПФ

БПФ работает только для размеров выборки 2ⁿ: 2, 4, 8, 16, 32, 64, 128, 256... Если размер не степень двойки, берется ближайшее меньшее значение (например, 70 → 64). Рекомендуется использовать 2ⁿ.

Массивы out_r и out_im (вещественная и мнимая части) потребляют много памяти. На Arduino Nano БПФ больше 128 отсчетов не помещается (рекомендуется 64).

unsigned int data[13] = {1,2,4,8,16,32,64,128,256,512,1024,2048};
int a, c1, f, o, x;
a = N;
for(int i=0; i<12; i++) //расчет уровней
    if(data[i] <= a) o = i;
int in_ps[data[o]] = {}; //вход для перестановки
float out_r[data[o]] = {}; //вещественная часть
float out_im[data[o]] = {}; //мнимая часть

Алгоритм:

1. Генерация бит-реверсного порядка для заданного размера.
2. Упорядочивание входных данных.
3. Выполнение БПФ.
4. Вычисление амплитуды комплексных чисел.
5. Поиск пиков и сортировка по убыванию.
6. Результаты в f_peaks[].

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

Шаг 4: Тестирование кода

На входе треугольный сигнал: частота дискретизации 10 Гц, частота сигнала 1.25 Гц. Результаты совпадают с расчетами в Scilab (небольшие расхождения из-за упрощенного синуса). Выдаются частотные корзины (frequency bins) — точное значение не гарантируется.

Скорость на Arduino Nano:

• 16 точек: 4 мс
• 32 точки: 10 мс
• 64 точки: 26 мс
• 128 точек: 53 мс

Шаг 5: Заключение

Код подходит для реального времени (~30 мс на расчет). Разрешение ограничено числом отсчетов, а оно — памятью Arduino. На Arduino Mega или более мощных платах точность выше.

Вопросы, предложения, исправления — в комментариях.

Код

EasyFFT (Arduino)

/* //Example data: int data[64]={14, 30, 35, 34, 34, 40, 46, 45, 30, 4, -26, -48, -55, -49, -37, -28, -24, -22, -13, 6, 32, 55, 65, 57, 38, 17, 1, -6, -11, -19, -34, -51, -61, -56, -35, -7, 18, 32, 35, 34, 35, 41, 46, 43, 26, -2, -31, -50, -55, -47, -35, -27, -24, -21, -10, 11, 37, 58, 64, 55, 34, 13, -1, -7}; */ //---------------------------------------------------------------------------// byte sine_data [91]= { 0, 4, 9, 13, 18, 22, 27, 31, 35, 40, 44, 49, 53, 57, 62, 66, 70, 75, 79, 83, 87, 91, 96, 100, 104, 108, 112, 116, 120, 124, 127, 131, 135, 139, 143, 146, 150, 153, 157, 160, 164, 167, 171, 174, 177, 180, 183, 186, 189, 192, 195, //Paste this at top of program 198, 201, 204, 206, 209, 211, 214, 216, 219, 221, 223, 225, 227, 229, 231, 233, 235, 236, 238, 240, 241, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 253, 254, 254, 254, 255, 255, 255, 255 }; float f_peaks[5]; // top 5 frequencies peaks in descending order //---------------------------------------------------------------------------// void setup() { Serial.begin(250000); } void loop() { /* //example FFT(data,64,100); //to get top five value of frequencies of X having 64 sample at 100Hz sampling Serial.println(f_peaks[0]); Serial.println(f_peaks[1]); delay(99999); */ /* after ruing above FFT(), frequencies available at f_peaks[0],f_peaks[1],f_peaks[2],f_peaks[3],f_peaks[4], */ } //-----------------------------FFT Function----------------------------------------------// float FFT(int in[],int N,float Frequency) { /* Code to perform FFT on arduino, setup: paste sine_data [91] at top of program [global variable], paste FFT function at end of program Term: 1. in[] : Data array, 2. N : Number of sample (recommended sample size 2,4,8,16,32,64,128...) 3. Frequency: sampling frequency required as input (Hz) If sample size is not in power of 2 it will be clipped to lower side of number. i.e, for 150 number of samples, code will consider first 128 sample, remaining sample will be omitted. For Arduino nano, FFT of more than 128 sample not possible due to mamory limitation (64 recomended) For higher Number of sample may arise Mamory related issue, Code by ABHILASH Contact: abhilashpatel121@gmail.com Documentation:https://www.instructables.com/member/abhilash_patel/instructables/ 2/3/2021: change data type of N from float to int for >=256 samples */ unsigned int data[13]={1,2,4,8,16,32,64,128,256,512,1024,2048}; int a,c1,f,o,x; a=N; for(int i=0;i<12;i++) //calculating the levels { if(data[i]<=a){o=i;} } int in_ps[data[o]]={}; //input for sequencing float out_r[data[o]]={}; //real part of transform float out_im[data[o]]={}; //imaginory part of transform x=0; for(int b=0;ba) {out_r[i]=in[in_ps[i]-a];} } int i10,i11,n1; float e,c,s,tr,ti; for(int i=0;i here onward out_r contains amplitude and our_in conntains frequency (Hz) for(int i=0;iout_r[i-1] && out_r[i]>out_r[i+1]) {in_ps[x]=i; //in_ps array used for storage of peak number x=x+1;} } s=0; c=0; for(int i=0;i360){j=j-360;} if(j>-1 && j<91){out= sine_data[j];} else if(j>90 && j<181){out= sine_data[180-j];} else if(j>180 && j<271){out= -sine_data[j-180];} else if(j>270 && j<361){out= -sine_data[360-j];} return (out/255); } float cosine(int i) { int j=i; float out; while(j<0){j=j+360;} while(j>360){j=j-360;} if(j>-1 && j<91){out= sine_data[90-j];} else if(j>90 && j<181){out= -sine_data[j-90];} else if(j>180 && j<271){out= -sine_data[270-j];} else if(j>270 && j<361){out= sine_data[j-270];} return (out/255); } //------------------------------------------------------------------------------------//

Схемы