I'm trying to understand the Discrete Fourier Transform so that I can understand the Fast Fourier Transform so that I can write a program to calculate it. I know that there are existing libraries that already do this, but if I use one of them I won't understand the maths behind the DFT.
I understand the general theory that you run different frequencies through the DFT and when the frequency matches a frequency in the signal, you get a spike in the amplitude and that the phase of the signal frequency can also be measured.
What I don't understand is which frequencies are represented in the results, and if the amplitude is normalised.
I've been mucking around with signals with only 8 data points. It seems that the wavelengths measured are $8/1$, $8/2$, $8/3$, etc. and the amplitudes seem to be multiplied by 8. I don't understand the usefulness of frequency 0, because it just sums all the data points.
I am wondering, if I have a signal that only is a sine wave at Concert A (440 Hz) with an amplitude of 1, sampled 44100 times per second (CD sample rate), and I do a DFT on the first 2048 samples, how do I detect the frequency at 440 Hz? The wavelength is 100.23 data points, which repeats 20.43 times in my sample. If I understand the measurable frequencies, they must be integer fractions of the sample size, so $2048/20=430.66$ or $2048/21=452.20$. Do I get a partial match for both close frequencies? If this is the case, how do I recognise that the true frequency is 440 Hz? What do the result data look like (the 2048 transformed values)?
Best Answer
The discrete Fourier transform implicitly regards the input data as periodic. The length of the input data is an integer multiple of the frequencies that the output data correspond to. If you generate the input data from a sinusoidal that has a different period that doesn't evenly divide the length of the data, then you're effectively creating a jump at the point where the first data point follows the last in the periodic continuation. A jump has appreciable Fourier components at all frequencies, and this is superimposed on your signal.
Nevertheless, you do get a signal with a clear maximum around the input frequency. I tried this using this online FFT calculator. In your case, as you calculated, we'd expect the maximum to be around the $21$st and $22$nd output data point (with the first data point corresponding to frequency $0$), and indeed, the first $40$ output values are:
So it seems you must have been doing something wrong when you got spikes all over the place at roughly the same amplitude.
You can actually calculate the output in closed form in this case by writing the sinusoidals in terms of complex exponentials and summing the resulting partial geometric series.
Edit:
Here's that last suggestion written out.
You have the time-domain signal $\sin2\pi\nu t$ with $\nu=440\text{Hz}$, and you sample it at the frequency $f=44100\text{Hz}$, so you have the samples
$$ s_k=\sin\frac{2\pi\nu k}f=\frac1{2\mathrm i}\left(\exp\left(\frac{2\pi\mathrm i\nu k}f\right)-\exp\left(-\frac{2\pi\mathrm i\nu k}f\right)\right) $$
for $0\le k\lt n$, with $n=2048$. Performing a discrete Fourier transform on these samples yields
\begin{eqnarray*} \tilde s_j &=& \sum_{k=0}^{n-1}s_k\exp\left(\frac{2\pi\mathrm i jk}n\right) \\ &=& \sum_{k=0}^{n-1}\frac1{2\mathrm i}\left(\exp\left(\frac{2\pi\mathrm i\nu k}f\right)-\exp\left(-\frac{2\pi\mathrm i\nu k}f\right)\right)\exp\left(\frac{2\pi\mathrm i jk}n\right) \\ &=& \frac1{2\mathrm i}\sum_{k=0}^{n-1}\left(\exp\left(2\pi\mathrm i\left(\frac jn+\frac\nu f\right)k\right)-\exp\left(2\pi\mathrm i\left(\frac jn-\frac\nu f\right)k\right)\right) \\ &=& \frac1{2\mathrm i}\sum_{k=0}^{n-1}\left(\omega_{j+}^k-\omega_{j-}^k\right) \\ &=& \frac1{2\mathrm i}\left(\frac{1-\omega_{j+}^n}{1-\omega_{j+}}-\frac{1-\omega_{j-}^n}{1-\omega_{j-}}\right)\end{eqnarray*}
with $\omega_{j\pm}=2\pi\mathrm i\left(\frac jn\pm\frac\nu f\right)$. The second term dominates and is maximal at $\frac jn=\frac\nu f$ (which in your case is at the fractional value $j=\frac{n\nu}f$). It's a phase factor times
$$ \frac{\sin n\pi\left(\frac jn-\frac\nu f\right)}{\sin\pi\left(\frac jn-\frac\nu f\right)}\;, $$
which is a discrete periodic analogue of the $\operatorname{sinc}$ function. Fitting to this functional form might improve your estimate of the frequency from the output data of the Fourier transform.