EasyFFT: Fast Fourier Transform (FFT) for Arduino

This code performs FFT with good accuracy.

Jul 11, 2020

•

133364 views

•

15 respects

fft

spectrum

frequency

Components and supplies

Arduino Nano R3

Apps and platforms

Arduino IDE

Project description

Code

EasyFFT

arduino

This code performs FFT and updates the F_peasks array with top 5 most dominent frequencies.

1/*
2//Example data:
3int data[64]={14, 30, 35, 34, 34, 40, 46, 45,  30, 4,  -26,  -48,  -55,  -49,  -37,
4-28,  -24,  -22,  -13,  6,  32, 55, 65,  57, 38, 17, 1,  -6, -11,  -19,  -34, 
5-51,  -61,  -56,  -35,  -7, 18, 32, 35,  34, 35, 41, 46, 43, 26, -2, -31,  -50,
6-55,  -47,  -35,  -27,  -24,  -21,  -10,  11, 37, 58, 64, 55, 34, 13, -1, -7};
7*/
8
9
10//---------------------------------------------------------------------------//
11byte  sine_data [91]=
12 {
130,  
144,    9,    13,   18,   22,   27,   31,   35,   40,   44, 
1549,   53,   57,   62,   66,   70,   75,   79,   83,   87, 
1691,   96,   100,  104,  108,  112,  116,  120,  124,  127,  
17131,  135,  139,  143,  146,  150,  153,  157,  160,  164,  
18167,  171,  174,  177,  180,  183,  186,  189,  192,  195,       //Paste this at top of program
19198,  201,  204,  206,  209,  211,  214,  216,  219,  221,  
20223,  225,  227,  229,  231,  233,  235,  236,  238,  240,  
21241,  243,  244,  245,  246,  247,  248,  249,  250,  251,  
22252,  253,  253,  254,  254,  254,  255,  255,  255,  255
23  };
24float f_peaks[5];  // top 5 frequencies peaks in descending order
25//---------------------------------------------------------------------------//
26
27
28void  setup() 
29        {
30        Serial.begin(250000);           
31        }
32
33        
34void loop() {
35
36/*
37//example
38FFT(data,64,100);        //to  get top five value of frequencies of X having 64 sample at 100Hz sampling
39Serial.println(f_peaks[0]);
40Serial.println(f_peaks[1]);
41delay(99999);
42*/
43
44
45/*  
46after ruing above FFT(), frequencies available at f_peaks[0],f_peaks[1],f_peaks[2],f_peaks[3],f_peaks[4],
47*/           
48            }
49
50
51
52//-----------------------------FFT Function----------------------------------------------//
53
54float  FFT(int in[],int N,float Frequency)
55{
56/*
57Code to perform FFT on arduino,
58setup:
59paste  sine_data [91] at top of program [global variable], paste FFT function at end of  program
60Term:
611. in[]     : Data array, 
622. N        : Number of sample  (recommended sample size 2,4,8,16,32,64,128...)
633. Frequency: sampling frequency  required as input (Hz)
64
65If sample size is not in power of 2 it will be clipped  to lower side of number. 
66i.e, for 150 number of samples, code will consider  first 128 sample, remaining sample  will be omitted.
67For Arduino nano, FFT of  more than 128 sample not possible due to mamory limitation (64 recomended)
68For  higher Number of sample may arise Mamory related issue,
69Code by ABHILASH
70Contact:  abhilashpatel121@gmail.com 
71Documentation:https://www.instructables.com/member/abhilash_patel/instructables/
722/3/2021:  change data type of N from float to int for >=256 samples
73*/
74
75unsigned  int data[13]={1,2,4,8,16,32,64,128,256,512,1024,2048};
76int a,c1,f,o,x;
77a=N;  
78                                 
79      for(int i=0;i<12;i++)                 //calculating  the levels
80         { if(data[i]<=a){o=i;} }
81      
82int in_ps[data[o]]={};     //input for sequencing
83float out_r[data[o]]={};   //real part of transform
84float  out_im[data[o]]={};  //imaginory part of transform
85           
86x=0;  
87      for(int b=0;b<o;b++)                     // bit reversal
88         {
89          c1=data[b];
90          f=data[o]/(c1+c1);
91                for(int  j=0;j<c1;j++)
92                    { 
93                     x=x+1;
94                     in_ps[x]=in_ps[j]+f;
95                    }
96         }
97
98 
99      for(int i=0;i<data[o];i++)            // update input array as per bit reverse order
100         {
101          if(in_ps[i]<a)
102          {out_r[i]=in[in_ps[i]];}
103          if(in_ps[i]>a)
104          {out_r[i]=in[in_ps[i]-a];}      
105         }
106
107
108int i10,i11,n1;
109float e,c,s,tr,ti;
110
111    for(int  i=0;i<o;i++)                                    //fft
112    {
113     i10=data[i];              // overall values of sine/cosine  :
114     i11=data[o]/data[i+1];    // loop with similar sine cosine:
115     e=360/data[i+1];
116     e=0-e;
117     n1=0;
118
119          for(int j=0;j<i10;j++)
120          {
121          c=cosine(e*j);
122          s=sine(e*j);    
123          n1=j;
124          
125                for(int  k=0;k<i11;k++)
126                 {
127                 tr=c*out_r[i10+n1]-s*out_im[i10+n1];
128                 ti=s*out_r[i10+n1]+c*out_im[i10+n1];
129          
130                 out_r[n1+i10]=out_r[n1]-tr;
131                 out_r[n1]=out_r[n1]+tr;
132          
133                 out_im[n1+i10]=out_im[n1]-ti;
134                 out_im[n1]=out_im[n1]+ti;          
135          
136                 n1=n1+i10+i10;
137                  }       
138             }
139     }
140
141/*
142for(int i=0;i<data[o];i++)
143{
144Serial.print(out_r[i]);
145Serial.print("\	");                                     // un comment to print RAW o/p    
146Serial.print(out_im[i]);  Serial.println("i");      
147}
148*/
149
150
151//---> here onward out_r contains  amplitude and our_in conntains frequency (Hz)
152    for(int i=0;i<data[o-1];i++)               // getting amplitude from compex number
153        {
154         out_r[i]=sqrt(out_r[i]*out_r[i]+out_im[i]*out_im[i]);  // to  increase the speed delete sqrt
155         out_im[i]=i*Frequency/N;
156         /*
157         Serial.print(out_im[i]); Serial.print("Hz");
158         Serial.print("\	");                            // un comment to print freuency bin    
159         Serial.println(out_r[i]);  
160         */    
161        }
162
163
164
165
166x=0;       // peak detection
167   for(int i=1;i<data[o-1]-1;i++)
168      {
169      if(out_r[i]>out_r[i-1] &&  out_r[i]>out_r[i+1]) 
170      {in_ps[x]=i;    //in_ps array used for storage of  peak number
171      x=x+1;}    
172      }
173
174
175s=0;
176c=0;
177    for(int  i=0;i<x;i++)             // re arraange as per magnitude
178    {
179        for(int  j=c;j<x;j++)
180        {
181            if(out_r[in_ps[i]]<out_r[in_ps[j]]) 
182                {s=in_ps[i];
183                in_ps[i]=in_ps[j];
184                in_ps[j]=s;}
185        }
186    c=c+1;
187    }
188
189
190
191    for(int i=0;i<5;i++)     //  updating f_peak array (global variable)with descending order
192    {
193    f_peaks[i]=out_im[in_ps[i]];
194    }
195
196
197
198}
199    
200
201float sine(int i)
202{
203  int j=i;
204  float  out;
205  while(j<0){j=j+360;}
206  while(j>360){j=j-360;}
207  if(j>-1   && j<91){out=  sine_data[j];}
208  else if(j>90  && j<181){out= sine_data[180-j];}
209  else if(j>180  && j<271){out= -sine_data[j-180];}
210  else if(j>270 && j<361){out= -sine_data[360-j];}
211  return (out/255);
212}
213
214float cosine(int i)
215{
216  int j=i;
217  float  out;
218  while(j<0){j=j+360;}
219  while(j>360){j=j-360;}
220  if(j>-1   && j<91){out=  sine_data[90-j];}
221  else if(j>90  && j<181){out= -sine_data[j-90];}
222  else  if(j>180 && j<271){out= -sine_data[270-j];}
223  else if(j>270 && j<361){out= sine_data[j-270];}
224  return (out/255);
225}
226
227//------------------------------------------------------------------------------------//

/*
//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;b<o;b++)                     // bit reversal
         {
          c1=data[b];
          f=data[o]/(c1+c1);
                for(int  j=0;j<c1;j++)
                    { 
                     x=x+1;
                     in_ps[x]=in_ps[j]+f;
                    }
         }

 
      for(int i=0;i<data[o];i++)            // update input array as per bit reverse order
         {
          if(in_ps[i]<a)
          {out_r[i]=in[in_ps[i]];}
          if(in_ps[i]>a)
          {out_r[i]=in[in_ps[i]-a];}      
         }


int i10,i11,n1;
float e,c,s,tr,ti;

    for(int  i=0;i<o;i++)                                    //fft
    {
     i10=data[i];              // overall values of sine/cosine  :
     i11=data[o]/data[i+1];    // loop with similar sine cosine:
     e=360/data[i+1];
     e=0-e;
     n1=0;

          for(int j=0;j<i10;j++)
          {
          c=cosine(e*j);
          s=sine(e*j);    
          n1=j;
          
                for(int  k=0;k<i11;k++)
                 {
                 tr=c*out_r[i10+n1]-s*out_im[i10+n1];
                 ti=s*out_r[i10+n1]+c*out_im[i10+n1];
          
                 out_r[n1+i10]=out_r[n1]-tr;
                 out_r[n1]=out_r[n1]+tr;
          
                 out_im[n1+i10]=out_im[n1]-ti;
                 out_im[n1]=out_im[n1]+ti;          
          
                 n1=n1+i10+i10;
                  }       
             }
     }

/*
for(int i=0;i<data[o];i++)
{
Serial.print(out_r[i]);
Serial.print("\	");                                     // 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)
    for(int i=0;i<data[o-1];i++)               // getting amplitude from compex number
        {
         out_r[i]=sqrt(out_r[i]*out_r[i]+out_im[i]*out_im[i]);  // to  increase the speed delete sqrt
         out_im[i]=i*Frequency/N;
         /*
         Serial.print(out_im[i]); Serial.print("Hz");
         Serial.print("\	");                            // un comment to print freuency bin    
         Serial.println(out_r[i]);  
         */    
        }




x=0;       // peak detection
   for(int i=1;i<data[o-1]-1;i++)
      {
      if(out_r[i]>out_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;i<x;i++)             // re arraange as per magnitude
    {
        for(int  j=c;j<x;j++)
        {
            if(out_r[in_ps[i]]<out_r[in_ps[j]]) 
                {s=in_ps[i];
                in_ps[i]=in_ps[j];
                in_ps[j]=s;}
        }
    c=c+1;
    }



    for(int i=0;i<5;i++)     //  updating f_peak array (global variable)with descending order
    {
    f_peaks[i]=out_im[in_ps[i]];
    }



}
    

float sine(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[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);
}

//------------------------------------------------------------------------------------//

Downloadable files

Example connections for Audio analysis

Comments

Only logged in users can leave comments

abhilashpatel121

0 Followers

•

0 Projects

Intro

Components and supplies

Apps and platforms

Project description

Code

Downloadable files