Go Down

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

#### Magician

#15
##### Nov 23, 2011, 05:13 am
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.

#16
##### Nov 23, 2011, 05:55 am
Oilburner could you post your working code?
Thanks
Montreal
Montreal

#### AWOL

#17
##### Nov 23, 2011, 01:40 pm
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 pmLast Edit: Nov 27, 2011, 10:04 pm by oilburner Reason: 1

Oilburner could you post your working code?
Thanks
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

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