Project tutorial
QuickFFT: High Speed (low accuracy) FFT for Arduino

QuickFFT: High Speed (low accuracy) FFT for Arduino © CC BY-NC

This project is performing a faster frequency transform (FFT).

  • 2,904 views
  • 0 comments
  • 4 respects

Components and supplies

About this project

Video explaining applicaion od the code

Typical Arduino has limited RAM and processing power, and FFT is a computationally-intensive process. For many real-time applications, the only requirement is to get frequency with maximum amplitude or required to detect frequency peaks.

In one of my tutorial, I prepared a code for FFT that can be found over here: EasyFFT

This code was able to perform FFT of up to 128 samples on Arduino nano. A higher sample number than this is not possible due to the limited memory of Arduino. I have modified the function a little bit to improve speed and reduce memory consumption. This modification allows Arduino to perform FFT five times faster and consumes almost half memory. This tutorial does not cover the Working of FFT, references for it can be found at EasyFFT.

Working

The typical FFT function is modified to improve the speed with lesser accuracy. As shown in the image a test signal needs to be multiplied by sine or cosine waveforms. These values can be between 0 to 1, so making floating multiplication is a must. in Arduino, Floating multiplication is slow compared to integer operations.

In this function, the sine/cosine wave is replaced by a square wave. As we have to multiply a test signal with a square wave which may have values 0, 1 or -1. Due to that, we can replace floating multiplication to simply integer addition or subtraction. For Arduino integer addition or subtraction is around 5 times faster. This makes solving around 5 times faster.

Due to this modification now frequency bin values can be stored as an integer (which was previously float) and we get another advantage of lower memory consumption. In Arduino Nano, int consumes 2 bytes of memory while float consumes 4 bytes of memory. Due to this advantage in the new code, we are able to perform FFT for almost 256 samples (previously 128 samples).

In Normal FFT we needed to store the sine value to make a solution faster. In new function, as we no more required sine/cosine values we can eliminate it and save some memory.

Implementation:

Implementing this function is straightforward. We can simply copy the function at the ens of the code. This function can be executed using the below command:

float f= Q_FFT(data,256,100);In function Q_FFT,

data: this term is an array having signal values, the recommended sample size are 2, 4, 8, 32, 64, 128, 256, 512,... onwards. if the sample size does not belong to these values it will be clipped to the nearest lower side of values. for example, if the sample size is 75 than FFT will be carried out for 64 numbers of samples. Max number of sample size is limited by available RAM on Arduino.

The second term specifies the number of samples in an array and the last term is sampling frequency in Hz.

Step 2: Code

This section explains the modification made in EasyFFT code that needs to be kept in mind while making modification in the code,

1. As explained before, here integers are used to do FFT. Int in Arduino is a 16-bit number and can contain values from -32768 to 32768. whenever the value of this int exceeds this range it causes the problem. to eliminate this problem after ever level calculation. if any of the value exceeds 15000 complete arrays will be divided by 100. this will prevent the int to overflow.

2. Amplitude calculation: To calculate amplitude, the real and imaginary part needs to be squared and the square root of the sum is required. squaring and the square root of the function is time taking. to make the process faster, this code will simply do some of the magnitudes of real and imaginary parts. This is surely less accurate and may lead to the wrong conclusion in some cases. you may choose to return to the Normal method for magnitude calculation but it will take more time and you also need to do some arrangement to store these numbers.

3. This code does not have a module for multiple peak detection. It will simply choose the value with max amplitude (excluding the first number which is DC offset). If you need multiple peaks you can refer EasyFFT code and do required modification over here. In that case, some array/variable also needs to be declared as a global variable.

4. The function contains the following line:

unsigned int Pow2[13]={1,2,4,8,16,32,64,128,256,512,1024,2048};

declaring the above variables as a global variable (pasting it at the start of code) will save somewhere 1 milliseconds time at every execution.

5. Unlike the EasyFFT function, where the top 5 peaks were stored in the predefined array. This function will return a float value. this value represents the frequency with maximum amplitude in Hz. So the representation of code will look something like this.

float f= Q_FFT(data,256,100);

6. Peak Detection: Once frequency with max amplitude is found this function uses an amplitude of frequency just before and after it to calculate the accurate results. Amplitude used in this calculation is also the sum of modulus (not the square root of the sum of squares)

if Fn is the frequency with max amplitude then the frequency can be calculated from below formula.

Actual F= (An-1 *Fn-1 + An-1 *Fn-1 + An-1 *Fn-1 ) / (An-1+An+An+1)

where An is amplitude of n the frequency and Fn-1 is frequency value.

Step 3: Results:

Solving time is shown in the above image comparison with EasyFFT. Speed of it shown with the comparison.

For sample data having 3 sinusoidal waves with different frequencies is shown. The result from QuickFFT is compared with Scilab output. As we can see in the image 3 peaks with max amplitude is matching with Scilab output. However, the output consists of lots of noise, which may be misleading for some applications. So it is advised to check code properly before applying to your application.

I hope you found this code useful for your project. In case of any query or suggestion please do comment.

Code

Code for QuickFFTArduino
This code is to perform FFT (low accuracy)
/*
//example data
int data[256]={10, 42, 47, 19, -20,  -39,  -26,  7,  30, 23, -10,  -42,  -47,  -19,  20,
39, 26, -7, -30,  -23,  10, 42, 47, 19, -19,  -39,  -26,  7,  30, 23, -9, -42,  -47,  -19,
19, 39, 26, -6, -30,  -24,  9,  42, 47, 20, -19,  -39,  -27,  6,  30, 24, -9, -42,  -47,
-20,  19, 39, 27, -6, -30,  -24,  9,  41, 47, 20, -19,  -39,  -27,  6,  30, 24, -9, -41,
-47,  -20,  18, 39, 27, -6, -30,  -24,  8,  41, 47, 20, -18,  -39,  -27,  6,  30, 24, -8,
-41,  -47,  -21,  18, 39, 27, -5, -30,  -24,  8,  41, 47, 21, -18,  -39,  -27,  5,  30, 24,
-8, -41,  -47,  -21,  18, 39, 27, -5, -30,  -24,  8,  41, 47, 21, -18,  -39,  -28,  5,  30,
25, -7, -41,  -47,  -21,  17, 39, 28, -5, -30,  -25,  7,  40, 47, 22, -17,  -39,  -28,  5,
30, 25, -7, -40,  -47,  -22,  17, 39, 28, -4, -30,  -25,  7,  40, 48, 22, -17,  -39,  -28,
4,  29, 25, -7, -40,  -48,  -22,  17, 39, 28, -4, -29,  -25,  7,  40, 48, 22, -17,  -39,  
-28,  4,  29, 25, -6, -40,  -48,  -22,  16, 39, 29, -4, -29,  -25,  6,  40, 48, 23, -16,  
-39,  -29,  4,  29, 25, -6, -40,  -48,  -23,  16, 39, 29, -3, -29,  -26,  6,  39, 48, 23,
-16,  -39,  -29,  3,  29, 26, -6, -39,  -48,  -23,  16, 39, 29, -3, -29,  -26,  5,  39, 48,
23, -15,  -39,  -29,  3,  29, 26, -5, -39,  -48,  -24,  15, 39};
*/

void setup() 
        {
    // Serial.begin(250000);
     
        }

        
void loop() {
/*
float f=Q_FFT(data,256,100);
Serial.println(f);
delay(1000000);
*/
       
            }



//-----------------------------FFT Function----------------------------------------------//
/*
Code to perform High speed (5-7 times faster) and low accuracy FFT on arduino,
This code compromises accuracy for speed,
setup:

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)

It will by default return frequency with max aplitude,

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 256 sample not possible due to mamory limitation 
Code by ABHILASH
Contact: abhilashpatel121@gmail.com 
Documentation & deatails: https://www.instructables.com/member/abhilash_patel/instructables/
*/


float Q_FFT(int in[],int N,float Frequency)
{ 

unsigned int Pow2[13]={1,2,4,8,16,32,64,128,256,512,1024,2048}; // declaring this as global array will save 1-2 ms of time


int a,c1,f,o,x;         
byte check=0;
a=N;  
                                 
      for(int i=0;i<12;i++)                 //calculating the levels
         { if(Pow2[i]<=a){o=i;} }
      
int out_r[Pow2[o]]={};   //real part of transform
int out_im[Pow2[o]]={};  //imaginory part of transform
           
x=0;  
      for(int b=0;b<o;b++)                     // bit reversal
         {
          c1=Pow2[b];
          f=Pow2[o]/(c1+c1);
                for(int j=0;j<c1;j++)
                    { 
                     x=x+1;
                     out_im[x]=out_im[j]+f;
                    }
         }

 
      for(int i=0;i<Pow2[o];i++)            // update input array as per bit reverse order
         {
          out_r[i]=in[out_im[i]]; 
          out_im[i]=0;
         }


int i10,i11,n1,tr,ti;
float e;
int c,s;
    for(int i=0;i<o;i++)                                    //fft
    {
     i10=Pow2[i];              // overall values of sine/cosine  
     i11=Pow2[o]/Pow2[i+1];    // loop with similar sine cosine
     e=360/Pow2[i+1];
     e=0-e;
     n1=0;

          for(int j=0;j<i10;j++)
          {
            c=e*j;
  while(c<0){c=c+360;}
  while(c>360){c=c-360;}

          n1=j;
          
          for(int k=0;k<i11;k++)
                 {

       if(c==0) { tr=out_r[i10+n1];
                  ti=out_im[i10+n1];}
  else if(c==90){ tr= -out_im[i10+n1];
                  ti=out_r[i10+n1];}
  else if(c==180){tr=-out_r[i10+n1];
                  ti=-out_im[i10+n1];}
  else if(c==270){tr=out_im[i10+n1];
                  ti=-out_r[i10+n1];}
  else if(c==360){tr=out_r[i10+n1];
                  ti=out_im[i10+n1];}
  else if(c>0  && c<90)   {tr=out_r[i10+n1]-out_im[i10+n1];
                           ti=out_im[i10+n1]+out_r[i10+n1];}
  else if(c>90  && c<180) {tr=-out_r[i10+n1]-out_im[i10+n1];
                           ti=-out_im[i10+n1]+out_r[i10+n1];}
  else if(c>180 && c<270) {tr=-out_r[i10+n1]+out_im[i10+n1];
                           ti=-out_im[i10+n1]-out_r[i10+n1];}
  else if(c>270 && c<360) {tr=out_r[i10+n1]+out_im[i10+n1];
                           ti=out_im[i10+n1]-out_r[i10+n1];}
          
                 out_r[n1+i10]=out_r[n1]-tr;
                 out_r[n1]=out_r[n1]+tr;
                 if(out_r[n1]>15000 || out_r[n1]<-15000){check=1;}
          
                 out_im[n1+i10]=out_im[n1]-ti;
                 out_im[n1]=out_im[n1]+ti;
                 if(out_im[n1]>15000 || out_im[n1]<-15000){check=1;}          
          
                 n1=n1+i10+i10;
                  }       
             }

    if(check==1){                                             // scale the matrics if value higher than 15000 to prevent varible from overloading
                for(int i=0;i<Pow2[o];i++)
                    {
                     out_r[i]=out_r[i]/100;
                     out_im[i]=out_im[i]/100;    
                    }
                     check=0;  
                }           

     }

/*
for(int i=0;i<Pow2[o];i++)
{
Serial.print(out_r[i]);
Serial.print("\t");                                     // un comment to print RAW o/p    
Serial.print(out_im[i]); Serial.println("i");      
}
*/

//---> here onward out_r contains amplitude and our_in conntains frequency (Hz)
int fout,fm,fstp;
float fstep;
fstep=Frequency/N;
fstp=fstep;
fout=0;fm=0;

    for(int i=1;i<Pow2[o-1];i++)               // getting amplitude from compex number
        {
        if((out_r[i]>=0) && (out_im[i]>=0)){out_r[i]=out_r[i]+out_im[i];}
   else if((out_r[i]<=0) && (out_im[i]<=0)){out_r[i]=-out_r[i]-out_im[i];}
   else if((out_r[i]>=0) && (out_im[i]<=0)){out_r[i]=out_r[i]-out_im[i];}
   else if((out_r[i]<=0) && (out_im[i]>=0)){out_r[i]=-out_r[i]+out_im[i];}
   // to find peak sum of mod of real and imaginery part are considered to increase speed
        
out_im[i]=out_im[i-1]+fstp;
if (fout<out_r[i]){fm=i; fout=out_r[i];}
         /*
         Serial.print(out_im[i]);Serial.print("Hz");
         Serial.print("\t");                            // un comment to print freuency bin    
         Serial.println(out_r[i]); 
          */
        }


float fa,fb,fc;
fa=out_r[fm-1];
fb=out_r[fm]; 
fc=out_r[fm+1];
fstep=(fa*(fm-1)+fb*fm+fc*(fm+1))/(fa+fb+fc);

return(fstep*Frequency/N);
}
    

//------------------------------------------------------------------------------------//
Quick_FFT.inoArduino
No preview (download only).

Schematics

Example connections diagram
Capture 5sraeqqq4j

Comments

Similar projects you might like

ApproxFFT: Fastest FFT Function for Arduino

Project tutorial by abhilash_patel

  • 7,258 views
  • 1 comment
  • 3 respects

High Speed Arduino RC car

by Aqib

  • 50,632 views
  • 18 comments
  • 37 respects

EasyFFT: Fast Fourier Transform (FFT) for Arduino

Project tutorial by abhilash_patel

  • 45,392 views
  • 13 comments
  • 23 respects

DIY FFT Audio Spectrum Analyzer

Project tutorial by Mirko Pavleski

  • 24,346 views
  • 2 comments
  • 24 respects

High Speed PWM on Arduino ATSAMD21

by JayV

  • 5,756 views
  • 1 comment
  • 5 respects
Add projectSign up / Login