'Get Fourier an and bn coefficients from fft

I have a signal which is periodic (think force acting on a specific point of a disc while rotating, for each angle the force is different, but over time the force at each angle does not change).

For the ease of data exchange I want to provide "the essence" of this signal as Fourier-Coefficients an and bn. Instead of 360 values (one for each degree of rotation) e.g. 10 pairs of an and bn should suffice without too much loss of accuracy.

Wikipedia gives an algorithm for an FFT in pseudocode which I implemented in C# (never mind faster libraries for the moment, there is a satisfying element to learning something new and writing things yourself) and which returns results I would expect.

static IList<Complex> FFT(IList<Complex> f)
{
    if (f.Count == 1)
        return f;
    else
    {
        int n2 = f.Count / 2;
        IList<Complex> g = FFT(GetEvenElements(f));
        IList<Complex> u = FFT(GetOddElements(f));
        Complex[] c = new Complex[n2*2];

        for (int k = 0; k < n2; k++)
        {
            c[k] = g[k] + u[k] * new Complex(Math.Cos(-2 * Math.PI * k / (n2 * 2)), Math.Sin(-2 * Math.PI * k / (n2 * 2)));
            c[k+n2] = g[k] - u[k] * new Complex(Math.Cos(-2 * Math.PI * k / (n2 * 2)), Math.Sin(-2 * Math.PI * k / (n2 * 2)));
        }
        return c;
    }
}

static IList<Complex> GetEvenElements(IList<Complex> data)
{
    List<Complex> res = new List<Complex>(data.Count / 2);

    for (int i = 0; i < data.Count; i += 2)
        res.Add(data[i]);
    return res;
}

static IList<Complex> GetOddElements(IList<Complex> data)
{
    List<Complex> res = new List<Complex>(data.Count / 2);

    for (int i = 1; i < data.Count; i += 2)
        res.Add(data[i]);
    return res;
}

The intended usage of this code is thus:

int FFTSize = 262144; //Power of 2
IList<Complex> Fx = FFT(Enumerable.Range(0, 1024).SelectMany(y=>ForceSignalList.Select(x => new Complex(x.ForceValue, 0))).Take(FFTSize).ToArray());
//Signal gets duplicated 1024 times to give the algorithm enough periodicity to chew on and then the nearest (smaller) power of 2 of the sampling points is taken
for(int i=0;i<Fx.Count;i++)
{
    Fx[i] /= (double)FFTSize; //normalise the values
}
double a0 = Fx[0].Real;
IList<double> a_n = Fx.Skip(1).Take(10).Select(x => -2 * x.Real).ToArray();
IList<double> bn = Fx.Skip(1).Take(10).Select(x => -2 * x.Imaginary).ToArray();

Reconstruction should be as simple as double f_at_target_Degrees = a0/2d + Enumerable.Range(0, a_n.Count).Select(x=> a_n[x] * Math.Cos(x * at_target_Degrees_In_Radians)).Sum() + Enumerbale.Range(0, b_n.Count).Select(x => b_n[x] * Math.Sin(x * at_target_Degrees_In_Radians)).Sum(), but it is not. The result shows little to no variation over the target angle at all.

Does this have to do with the rather high sample count and thus very small frequency increments in my FFT?

Did I get something obvious spectacularly wrong conceptually?

This post probably could also go on math.stackexchange, but I figured that I would get more valuable hints for the concrete implementation here.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source