I have existing FFT code, and I'm trying to upgrade it to use the technique mentioned at http://processors.wiki.ti.com/index.php/Efficient_FFT_Computation_of_Real_Input
That is, since my incoming data is real, I can pack that real data into a complex array. Then I can perform an N/2-point FFT. Next, I can do some unpacking and trig, to come up with the result of what WOULD have been N-point FFT on my original real data. After that, I want the magnitude of the FFT result, which I consider the power of my signal at each bin frequency.
Well, I'm getting all confused trying to do the unpacking and trig. It mostly has to do with N vs N/2 and indices used and arguments to sin() or cos().
Looking at the wiki directly, it's ambiguous because it mentions Ar[k] and Ai[k], but later uses source code to define instead A[]. There's a disconnect here. It appears, however, that Ar[k] = A[2k] and Ai[k] = A[2k+1]. I'm not totally sure, however.
Furthermore, an indexing problem arises when you look closer. The wiki page defines Gr(k) in terms including Xr(N-k) with k varying from 0 to (N/2)-1. For the cases of k=0 and k=1 (as well as many others), this means we're accessing Xr(N) and Xr(N-1) (as well as many others). THE PROBLEM is that X is the result of an N/2 FFT and should only have N/2 entries, not N entries. So we've accessed DOUBLE the proper size of that array.
I try to reconcile this with the source code provided from the wiki page. Now it gets even more obtuse. The source code seems to pack EVERYTHING complex into a linear array where even-index entries are real and odd-index entries are imaginary. I believe the function FFT_Split() should correspond to the calculation I described above. In this source, the variable i varies from 0 to n-1. The data pIn[] is in one place indexed as pIn[2*n - 2*i]. Well, for i=0 and i=1 we find ourselves accessing pIn[2n] and pIn[2n - 2]. I believe that pIn, however, only has n valid entries, not 2n. SAME PROBLEM.
Finally, the wiki does not provide a direct definition of Ar[] and Ai[], as I have mentioned. Instead, it actually just copies the same code as one can find in the example code for the function split_gen(). In this function, i varies from 0 to n-1. When I compile and run this code, it generates what it looks like it should generate (of course). Most importantly, the parameter to the sin() and cos() functions is the same for all four coefficient calculations: 2 * PI / (2 * n) * i. Note that the last i is in the numerator, not the denominator. A little algebra reduces this parameter to i*PI/n. Therefore, we're calling sin(i*PI/n) and cos(i*PI/n) while i varies from 0 to n-1. So as i gets very close to n, we get very close to calling sin(PI) and cos(PI). Another way to say this is that for large n, when i=n-1 the expression i*PI/n gets close to PI. What I'm trying to get at here is that we run these trig functions through about 180 degrees: 0 through almost PI radians.
However, when I try to translate the complex storage into simple storage, I'm trying to convert 2*i to k, etc. I end up running the trig functions through only PI/2 radians, or 90 degrees. This means I've messed up by a factor of two.
I'm messed up all over the place by a factor of two! I need to get a good handle on this, if someone can help, please. Perhaps the BEST place and method to do this is in terms of the very simple wiki explanation. It references Ar() and Ai(), but doesn't define them. If someone can help me define them in terms consistent with the other wiki definitions, I would greatly appreciate it. We'll also have to address the Xr(N) and Xr(N-1) problem.
By the way, regarding the Xr(N) and Xr(N-1) problem, I did notice another tiny inconsistency between the wiki page and the source code. The wiki page mentions X(N/2) = X(0) on the same line as Gr(k) is defined. The indices of X used here are indeed within bounds, since X corresponds to an N/2 FFT. However, in the source code, I see an assignment "pIn[2 * n] = pIn[0];" and "pIn[2 * n + 1] = pIn[1];", which I think is trying to do the same thing. Here, however, the 2*n index ... I'm confused ... corresponds to what, exactly? Let me try again. if "2*n" is actually within range for the source code, where the source code is doing an FFT of size n... And if N/2 is indeed within range for the wiki equations, where the wiki equations are doing an N/2 point FFT... Then maybe we are consistent.
Maybe I can sleep on this and stop seeing the wrong 2's tomorrow! Otherwise, assistance in fixing up the wiki page would be greatly appreciated.
Thanks,
Helmut
