I understand that the DFT (Discrete Fourier Transform) process produces the same number of outputs as there are inputs, and this is clear from the basic DFT expression
$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-i2\pi kn/N} \tag{1}$$
However, when computing the FFT (Fast Fourier Transform), the final output is the sum of two N/2 transforms (the even and odd DFTs).
$$X[k]=X_{even}[k]+W_{N}^{k}\cdot X_{odd}[k] \tag{2}$$
Suppose $N=16$. If I try to evaluate Equation (2) for $N=12$, it won't work, since $X_{even}[12]$ doesn't exist (since $X_{even}$ only has $N/2=8$ inputs in the first place).
This is normally solved, as in the case of Fat32's solution to a previous question of mine, by concatenating the outputs of each $N/2$ DFT with themselves to produce an output that is N long, which would result in an $X_{even}[12]$ which does exist. Alternatively, one could add a condition that if $k>N/2$, then substrat $N/2$ from each $X_{even}$ and $X_{odd}$ index.
I was wondering what the mathematical foundations of each of these work around are, since they aren't explicitly included in expression 2? Is it something that is basically common sense? Or does it really mean that only half of the outputs are actually valid?
I also have a hard time interpreting the output of the FFT since the second half of the outputs are mirrored and actually represent negative frequencies. So doesn't that mean that in order to really present an accurate output I must chop that second half off and move it to the negative frequency domain?
There seem to be several ways to present the output (some leave the negative frequencies mirrored and in the positive domain, and some do order them properly). Any advice about the best way to interpret and present the outputs of the FFT process is greatly appreciated!
even
orodd
(the same on both sides of the equality). $\endgroup$ – Dilip Sarwate Jan 24 '18 at 18:49