Go Down

Topic: 16-bit FFT on Arduino (Read 7300 times) previous topic - next topic

Magician

http://en.wikipedia.org/wiki/Discrete_Fourier_transform#Applications
IMHO, the most popular:
http://en.wikipedia.org/wiki/Spectrum_analyzer
Why do you need such analysis is another question.

Patgadget

Oilburner could you post your working code?
Thanks
Patgadget
Montreal
Patgadget
Montreal

AWOL

http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

oilburner

#18
Nov 27, 2011, 10:01 pm Last Edit: Nov 27, 2011, 10:04 pm by oilburner Reason: 1

Oilburner could you post your working code?
Thanks
Patgadget
Montreal



This is the fix_fft.cpp file you can use in the library
Code: [Select]

#include <avr/pgmspace.h>
#include "fix_fft.h"
#include <WProgram.h>


#define N_WAVE          256    /* full length of Sinewave[] */
#define LOG2_N_WAVE     8      /* log2(N_WAVE) */
/*
 Since we only use 3/4 of N_WAVE, we define only
 this many samples, in order to conserve data space.
*/

const prog_int16_t Sinewave[N_WAVE-N_WAVE/4] PROGMEM = {
   0,  402,  803, 1205, 1605, 2005, 2403, 2800, 3196, 3589, 3980,
4369, 4755, 5139, 5519, 5896, 6269, 6639, 7004, 7365, 7722, 8075,
8422, 8764, 9101, 9433, 9759,10079,10393,10700,11002,11296,11584,
11865,12139,12405,12664,12915,13158,13394,13621,13841,14052,14254,
14448,14633,14810,14977,15135,15285,15425,15556,15677,15789,15892,
15984,16068,16141,16205,16259,16304,16338,16363,16378,16383,16378,
16363,16338,16304,16259,16205,16141,16068,15984,15892,15789,15677,
15556,15425,15285,15135,14977,14810,14633,14448,14254,14052,13841,
13621,13394,13158,12915,12664,12405,12139,11865,11584,11296,11002,
10700,10393,10079, 9759, 9433, 9101, 8764, 8422, 8075, 7722, 7365,
7004, 6639, 6269, 5896, 5519, 5139, 4755, 4369, 3980, 3589, 3196,
2800, 2403, 2005, 1605, 1205,  803,  402,    0, -402, -803,-1205,
-1605,-2005,-2403,-2800,-3196,-3589,-3980,-4369,-4755,-5139,-5519,
-5896,-6269,-6639,-7004,-7365,-7722,-8075,-8422,-8764,-9101,-9433,
-9759,-10079,-10393,-10700,-11002,-11296,-11584,-11865,-12139,-12405,
-12664,-12915,-13158,-13394,-13621,-13841,-14052,-14254,-14448,-14633,
-14810,-14977,-15135,-15285,-15425,-15556,-15677,-15789,-15892,-15984,
-16068,-16141,-16205,-16259,-16304,-16338,-16363,-16378
};

/*
 fix_fft() - perform forward/inverse fast Fourier transform.
 fr[n],fi[n] are real and imaginary arrays, both INPUT AND
 RESULT (in-place FFT), with 0 <= n < 2**m; set inverse to
 0 for forward transform (FFT), or 1 for iFFT.
*/

inline int FIX_MPY(int a, int b)
{

   /* shift right one less bit (i.e. 15-1) */
   long c = ((long)a * (long)b) >> 14;
   /* last bit shifted out = rounding-bit */
   b = c & 0x01;
   /* last shift + rounding bit */
   a = (c >> 1) + b;

   return a;
}


int fix_fft(int fr[], int fi[], int m)
{
   int mr, nn, i, j, l, k, istep, n, scale, shift;
   int qr, qi, tr, ti, wr, wi;

   n = 1 << m;

   /* max FFT size = N_WAVE */
   if (n > N_WAVE)
 return -1;

   mr = 0;
   nn = n - 1;
   scale = 0;

   /* decimation in time - re-order data */
   for (m=1; m<=nn; ++m) {
 l = n;
 do
 {
l >>= 1;
 } while (mr+l > nn);
 mr = (mr & (l-1)) + l;
 if (mr <= m)
continue;

 tr = fr[m];
 fr[m] = fr[mr];
 fr[mr] = tr;
 ti = fi[m];
 fi[m] = fi[mr];
 fi[mr] = ti;
   }

   l = 1;
   k = LOG2_N_WAVE-1;
   while (l < n)
{
 /*
   it may not be obvious, but the shift will be
   performed on each data point exactly once,
   during this pass.
 */
 istep = l << 1;
 for (m=0; m<l; ++m)
 {
j = m << k;
/* 0 <= j < N_WAVE/2 */
wr =  pgm_read_word_near(Sinewave + j+N_WAVE/4);
wi = -pgm_read_word_near(Sinewave + j);
wr >>= 1;
wi >>= 1;
for (i=m; i<n; i+=istep)
{
   j = i + l;
//tr = ((long)wr*(long)fr[j] - (long)wi*(long)fi[j])>>15;
//ti = ((long)wr*(long)fi[j] + (long)wi*(long)fr[j])>>15;
tr = FIX_MPY(wr,fr[j]) - FIX_MPY(wi,fi[j]);
   ti = FIX_MPY(wr,fi[j]) + FIX_MPY(wi,fr[j]);
   qr = fr[i];
   qi = fi[i];
qr >>= 1;
qi >>= 1;
   fr[j] = qr - tr;
   fi[j] = qi - ti;
   fr[i] = qr + tr;
   fi[i] = qi + ti;
}
 }
 --k;
 l = istep;
   }
   return scale;
}




http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm


That's the algorithm behind the code I'm using :)

Go Up