Pages: 1 [2]   Go Down
Author Topic: 16-bit FFT on Arduino  (Read 6735 times)
0 Members and 1 Guest are viewing this topic.
Montreal
Offline Offline
Faraday Member
**
Karma: 30
Posts: 2602
Per aspera ad astra.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

Montreal
Offline Offline
Full Member
***
Karma: 0
Posts: 185
Arduino rocks
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

Patgadget
Montreal

Global Moderator
UK
Offline Offline
Brattain Member
*****
Karma: 309
Posts: 26515
I don't think you connected the grounds, Dave.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

"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.

Offline Offline
Newbie
*
Karma: 0
Posts: 12
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Oilburner could you post your working code?
Thanks
Patgadget
Montreal


This is the fix_fft.cpp file you can use in the library
Code:
#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;
}



That's the algorithm behind the code I'm using smiley
« Last Edit: November 27, 2011, 04:04:14 pm by oilburner » Logged

Pages: 1 [2]   Go Up
Jump to: