Patgadget:
Oilburner could you post your working code?
Thanks
Patgadget
Montreal
This is the fix_fft.cpp file you can use in the library
#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 