EasyFFT: Fast Fourier Transform (FFT) for Arduino

Measurement of frequency from the captured signal can be a difficult task, especially on Arduino as it has lower computational power. There are methods available to capture zero-crossing where the frequency is captured by checked how many times the signal crosses zero lines within the given time. Such a method may not work when the signal is a combination of various frequencies.

This is somehow difficult to code if you are not from such a background. But being a tinkerer this code may be highly useful for various projects related to music, signal analysis. The motive of this project was to prepare a code that is easy to implement on Arduino without getting into the background of it.

This project does not explain the Working of FFT but explains the application of the FFT function. The same process is also explained in the attached video.

If you are only interested in the application of code and not into an explanation of it. You may skip directly to step no 3.

Any signal can be composed of a combination of various sinusoidal waves. So any time-based signal can be also shown as a combination of the various sine of different amplitudes.

I tried to explain the working of DFT(discrete Fourier transform)in one of the previous instructable (https://www.instructables.com/id/Arduino-Frequency...). These methods are extremely slow for any real-time application. which makes it almost useless.

In the image, a signal is shown which is a combination of two frequencies f2 and f5. This signal is multiplied by test sine waves of values f1 to f5.

It can be shown mathematically that -summation of multiplication of two harmonic data-set having different frequency tends to zero(higher number of data can lead to batter result). In our case, If these two multiplication frequency has the same (or very close) frequency that sum of multiplication is the nonzero number.

So if our signal is multiplied by f1 summation of multiplication will be zero (near to zero for real application). similar is the case for f3, f4. However for the value, f2 and f5 output won't be zero, but significantly higher than the rest of the values.

Here a signal is tested with 5 frequencies, so signal needs to be multiplied by five frequencies. Such intense calculation takes a higher time. Mathematically it is shown that for N number of samples it takes N*N complex multiplication.

To make the computation of DFT faster FFT algorithm was developed by James Cooley and John Tukey. This algorithm is also considered as one of the most important algorithms of the 20th century. It divides a signal into an odd and even sequenced part which makes a number of required calculations lower. By using it total required complex multiplication can be reduced to NlogN. which is a significant improvement.

You may refer below references that I referred to while writing the code for a detailed understanding of the mathematics behind FFT:

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...

1. Fast sine and Cosine:

Calculation FFT takes the value of various sine and cosine multiple times. The inbuilt function of Arduino is not fast enough and takes a good amount of time to provide the required value. Which makes code significantly slower (doubles time for 64 samples). To counter this issue value of sine for 0 to 90 degrees is stored as multiple of 255. Doing so will eliminate the need of using storing numbers as float and we can store it as byte which takes 1/4th space on Arduino. The sine_data[ ] needs to paste at top of code to declare it as a global variable.

Apart from sine_data, an array called f_peaks[] declared as a global variable. After every run of FFT function this array updates. Where f_peaks[0] is the most dominant frequency and further values in descending order.

byte sine_data [91]=<br> {
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];

As we have stored value of sine for 0 to 90 degree any value of sine or cosine can be calculated. Below function the first round of the number to zero decimal point and return value from stored data. this method needs only one floating division. This can be further reduced by directly storing sine values (not 255 multiple). but that eats up high memory on Arduino.

Using the above procedure reduces accuracy but improves speed. For 64 points, it gives the advantage of 8ms and for 128 points it gives an advantage of 20ms.

FFT can only be performed for the sample size of 2,4,8,16,32,64 and so on. if the value is not 2^n, than it will take the lower side of value. For example, if we choose the sample size of 70 then it will only consider the first 64 samples and omit rest.

It is always recommended to have a sample size of 2^n. which can be:

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

Two floats out_r and out_im will take a high amount of memory. for Arduino nano won't work for samples higher than 128 (and in some cases 128) due to lack of available memory.

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

Further flow is as follow:

1. Code generates a bit reversed the order for the given sample size (details on bit reversing on references: step 2)

2. Input data ordered as per generated order,

3. FFT performed

4. The amplitude of the complex number calculated,

5. Peaks are detected and ordered in descending order

6. results can be accessed from f_peaks[].

[to access other data (apart from peak frequency) code should be modified, so that local variable can be copied to some predefined global variable]

A sample triangle wave is given as input. for this wave sampling frequency is 10 Hz and the frequency of wave itself is 1.25 Hz.

As can be shown from the raw output, value is matching with the FFT calculated by Scilab. however, these values are not exactly the same as we low accuracy but faster sine wave.

In output frequency array frequency are 1.25 and 3.75. it is not necessary to get the exact value every time. typically these numbers are called frequency bins. so output value might be anywhere within specified bins.

Speed:

for Arduino nano it takes:

16 Points : 4ms
32 Points : 10ms
64 Points : 26ms
128 Points: 53ms

This FFT code can be used in real-time applications. As it takes around 30 ms to complete the calculation. However, its resolution limited by a number of samples. The number of the sample is limited by Arduino memory. By using Arduino Mega or other higher performance board accuracy can be improved.

if you have any queries, suggestions, or corrections feel free to comment.

Update (2/5/21)

Updates://-----------------------------FFT Function----------------------------------------------//
float FFT(int in[],int N,float Frequency)

The data type of N changed to Integer (existing Byte) to support >255 sample size. If the sample size is <=128, byte data type should be used.