Go Down

Topic: 16-bit FFT on Arduino (Read 8195 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
 


Please enter a valid email to subscribe

Confirm your email address

We need to confirm your email address.
To complete the subscription, please click the link in the email we just sent you.

Thank you for subscribing!

Arduino
via Egeo 16
Torino, 10131
Italy