Properly interpreting FFT output

Question

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!

Answer 1

First of all, the view that the $N$-point DFT $X[k]$ can be decomposed into the sum of two half length $N/2$-point DFTs $X_e[k]$ and $X_o[k]$ is a helpful interpretation for the development of fast algorithms (FFT) to compute the DFT $X[k]$, but not required for a solid understanding of the theory of DFT otherwise.

A direct for-loop computation of the whole $N$-point sequence $X[k]$ $$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N} nk} ~~~,~~~\text{ for } k=0,1,...,N-1$$ will have about $N^2$ complex MACs (multiply accumulate), where as the fast algorithms will approach to $N \log_2(N)$ complex MACs; a pretty huge improvement for large $N$.

The reduction is visible through the binary-tree wise decomposition of the original $N$-point DFT $X[k]$ into half sized parts, recursively down to the root size of 2-point DFTs which are explicitly computed. In the butterfly interpretation of the $N$-point FFT, the number of steps (levels) will be $\log_2(N)$ and each step will be have the same $N$ many MAC's with twiddle factors, hence yielding a total of $N \times $\log_s(N)$ complex MAC's.

That being said, one of the fundamental concepts behind the DFT is that its inputs and outputs are assumed to be periodic sequences of length $N$ by the definition of $N$-point DFT. This is called inherent periodicity assumption of DFT. And it's a direct consequence of its ancestor being DFS (discrete Fourier series) which is by definition a periodic sequence of period $N$. Therefore $N$-point DFT $X[k]$ is inherently (always, without conditions) a periodic sequence with $N$ and thus $X[k+rN] = X[k]$ for all $k,r$ integers.

Apply this to $N/2$ point seqeunces, and the sum $$X[k] = X_e[k] + W_N^k X_o[k] ~~~,~~~\text{ for} k=0,1,...,N-1$$ can be computed for all $k$ by the periodicity of $X_e[k]$ and $X_o[k]$.

Indeed in the defining sum of $X_e[k]$ you can see that, $$X_e[k] = \sum_{m=0}^{N/2-1} x_e[m] e^{-j \frac{2\pi}{N/2} m k }~~~,~~~\text{for} k=0,1,...,N/2-1$$

for $k = N/2 + r$ you will have $X_e[N/2 + r] = X_e[r]$ due to the periodicity of $W_{N/2}$ as follows: $$X_e[N/2+r] = \sum_{m=0}^{N/2-1} x_e[m] e^{-j \frac{2\pi}{N/2} m(N/2+r)} = \sum_{m=0}^{N/2-1} x_e[m] e^{-j \frac{2\pi}{N/2}mr } e^{-j \frac{2\pi}{N/2} m(N/2) } = X_e[r]$$

Answer 2

The upper half of the DFT being the conjugate mirror of the lower half is only true for real valued signals.

For an alternative understanding of what the DFT means you can read my blog article DFT Graphical Interpretation: Centroids of Weighted Roots of Unity. I also recommend your read my first article "The Exponential Nature of the Complex Unit Circle" for an understanding of the foundation of the DFT, in particular, the significance of the Roots of Unity.

Hope this helps.

Ced