OouraFft should use forward transform

[borgne]

Had a look at the Aquila library mainly to get some understanding for how to use the Ooura FFT algortihms. I was eventually able to understand how to use them, but that also made me come to the conclusion that the algorithm used in Aquila is not the intended one.

If I have not misunderstood how the Ooura algorithms work, the line

    cdft(2*N, -1, a, ip, w);

should be replaced with

    cdft(2*N, 1, a, ip, w);

The current code performs the inverse transform, from spectrum to samples.

Also, the code returns a spectrum that has the same size as the input array. I believe that is also incorrect. The size of the spectrum is half the input plus one. I.e., the line

    SpectrumType spectrum(tmpPtr, tmpPtr + N);

should be replaced with

    SpectrumType spectrum(tmpPtr, tmpPtr + N / 2 + 1);

Finally, the code uses non-complex input, so it could use the rdft function instead of the cdft function. So, instead of this:

        // create a temporary storage array and copy input to even elements
        // of the array (real values), leaving imaginary components at 0
        double* a = new double[2 * N];
        for (std::size_t i = 0; i < N; ++i)
        {
            a[2 * i] = x[i];
            a[2 * i + 1] = 0.0;
        }

        // let's call the C function from Ooura's package
        cdft(2*N, -1, a, ip, w);

        // convert the array back to complex values and return as vector
        ComplexType* tmpPtr = reinterpret_cast<ComplexType*>(a);
        SpectrumType spectrum(tmpPtr, tmpPtr + N);

you could use this:

        // Create a copy of the input array to use for the FFT
        double *a = new double[N];
        for (std::size_t i = 0; i < N; ++i)
            a[i] = x[i];

        // Call the Ooura FFT function
        rdft(N, 1, a, ip, w);

        // The result is stored as complex numbers in a (where the last number's
        // real value is stored as the first number's complex value)
        ComplexType *tmpPtr = reinterpret_cast<ComplexType*>(a);
        SpectrumType spectrum(tmpPtr, tmpPtr + N / 2 + 1);
        spectrum[N / 2] = std::complex<double>(spectrum[0].imag(), 0);
        spectrum[0] = std::complex<double>(spectrum[0].real(), 0);

Since I am totally new to the world of DSP and FFT, I cannot guarantee that my conclusions are correct, but I'd say I'm at least 90% sure this is how it should be.

[zsiciarz]

Hi! Thanks for your comments. First - a forward Fourier Transform has minus sign in the exponent, so to my understanding the -1 in cdft call is correct (Ooura calls it case2). Regarding rdft instead of cdft and output size - good catch, I'll have a look at that.

[borgne]

It's possible that I have misunderstood the 1 / -1 values. For the CDFT case it is very unclear from the documentation (in fftg4.c) which case is the CDFT and which case is the inverse. But if you look at the RDFT, it is very clear that case1 (1) is the RDFT and that case2 (-1) is the Inverse RDFT. So I would kind of expect that to be true for the CDFT as well. And the tests I made to compare the CDFT to the RDFT also implicate that that is the case - the only way to get the same results was to use -1 for both.