I have been working on understanding the innards of the Discrete Fourier Transform, and I’ve stumbled on what I believe to be the heart of the algorithm. Since then I have been trying to understand why it works. Let’s take a look at this heart:
These two functions will extract the amplitude and phase of the selected frequency c from the function f. With some experimentation, I have found the following to be true:
What this means is that if we have a sine wave at frequency b, amplitude a and phase d, we can extract phase and amplitude for some test frequency c. Anytime that b and c are equal, we get a non-zero value relating to phase and amplitude. If they are not equal, the answer is simply zero. This is precisely what is needed in a discrete Fourier transform, and why I call it the heart. In a DFT, the function checks the data for each possible integer frequency for the data set, and gets either it’s amplitude and phase, or zero.
First, the discrete Fourier transform in standard notation:
Use Euler's formula:
Now, assume x is real and break this into the real and imaginary parts and all frequencies:
Let’s try this on a set of data.
Here we have a (b) of frequency of 5 Hz with an amplitude (a) of 1 and phase angle (d) of 45°, and a check frequency (c) of 5 Hz. The sum of the real and imaginary parts is non-zero.
Now let’s try a check frequency of 6 Hz.
Here, the sum of the check frequencies for both real and imaginary are zero. It is more obvious when the check frequency is higher, say 50:
Here it is more obvious both the real and imaginary parts spend the same amount of time above and below 0, so overall summing to 0. It also doesn’t matter how many frequencies are in the signal. In the above examples there is just a single frequency, but it will extract amplitude and phase for the check frequency regardless of how many other frequencies are present in the signal.
I haven’t yet figured out why this is the case, but it makes perfect sense why this makes a DFT work.