Search code examples
cfftcomplex-numbers

What is the significance of the output of this FFT function?

I have the following periodic data which has a period of ~2000:Periodic Data

I am trying to discover the period of the data and the offset of the first peak. I have the following FFT function to perform a Fourier Transform:

typedef double _Complex cplx;

void _fft(cplx buf[], cplx out[], int n, int step){
    if (step < n) {
        _fft(out, buf, n, step*2);
        _fft(out+step, buf+step, n, step*2);

        for(int i=0; i<n; i+=step*2) {
            cplx t = cexp(-I * M_PI * i / n) * out[i + step];
            buf[i / 2]     = (out[i] + t);
            buf[(i + n)/2] = (out[i] - t);
        }
    }
}

void fft(cplx* buf, int n){
    cplx* out = (cplx*)malloc(sizeof(cplx) * n);
    memcpy(out, buf, sizeof(cplx)*n);
    _fft(buf, out, n, 1);

    for(int i=0; i<n; i++){ buf[i] /= n; }

    free(out);
}

Which has been adapted from here: Fast Fourier Transformation (C) (link contains a full running example with main function and example data)

I understand that a Fourier Transform converts time series data into frequency data. Each frequency has a amplitude and a phase. However, I am having a hard time understanding the output given by this function. Graphing the output gives me this:FFT Graphical Output

I have tried graphing the real component, the imaginary component, and the magnitude of both components. Each attempt gives a very similar-looking graph.

Am I wrong to assume there should be a spike at ~2000? Am I miss-interpreting the output of this function?

Solution

  • Am I wrong to assume there should be a spike at ~2000?

    Yes, because 2000 is the period you're interested in, not the frequency. It looks like you're running a 32,768-point FFT, so you should expect to find a peak in bin #16 (16 cycles per 32k = periods of approximately 2048 samples), not bin #2000.

    If you want something that reports directly in terms of number of samples, instead of frequency, you may want an autocorrelation, instead of an FFT. Your signal would have autocorrelation peaks at lags of 2000, 4000, etc.