1
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ Why don't you just try it? If you don't want to install a library, there are lots of online FFT calculators. $\endgroup$ – joriki Jul 23 '18 at 4:19
  • $\begingroup$ @joriki I want to understand DFT, not use a black box. I also don't want to type in 2048 values. $\endgroup$ – CJ Dennis Jul 23 '18 at 4:25
  • $\begingroup$ You don't have to type them, you can generate them automatically. And it will help you understand them. You're asking us "What do the result data look like (the $2048$ transformed values)?" How are we less of a black box than the online FFT calculator? $\endgroup$ – joriki Jul 23 '18 at 4:30
  • $\begingroup$ @joriki Because a human will say "The reason why we see X at Y is because of Z". A black box can't teach me why. $\endgroup$ – CJ Dennis Jul 23 '18 at 4:32
  • $\begingroup$ Please take a look at this guide on how to ask a good question, especially the section "Include your work". In this case, I think showing your own effort would include first taking a look at what the result looks like and then describing what you don't understand about it (e.g. "I don't understand why the result seems to have a sinusoidal form"), rather than asking us to describe something to you that you could easily see for yourself. $\endgroup$ – joriki Jul 23 '18 at 4:37
1
$\begingroup$

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:

30.322000,0.000000
30.391603,-0.332305
30.619103,-0.635705
30.983132,-0.983397
31.541176,-1.314554
32.258933,-1.685996
33.213385,-2.076468
34.383753,-2.509669
35.850294,-2.989665
37.679693,-3.538320
39.950279,-4.172808
42.781442,-4.897551
46.400390,-5.801462
51.088228,-6.910079
57.343876,-8.338977
66.017176,-10.282208
78.721064,-13.088380
98.974578,-17.487260
136.068697,-25.448952
225.318492,-44.421047
727.024048,-150.774758
-543.414483,118.240910
-191.999756,43.727082
-114.594042,27.275221
-80.661116,20.008091
-61.661208,15.918785
-49.536603,13.289953
-41.141647,11.459233
-35.002598,10.087933
-30.321248,9.041060
-26.630074,8.216618
-23.664950,7.534937
-21.230810,6.967688
-19.199079,6.488785
-17.492157,6.083581
-16.004951,5.723743
-14.733225,5.416510
-13.616822,5.138707
-12.640339,4.905611
-11.768659,4.665358

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.

$\endgroup$
  • $\begingroup$ How do you get from "727.024048,-150.774758", "-543.414483,118.240910" to 440 Hz? As I guessed, there are two results with an error of +/-12 Hz, with the true answer somewhere in between. $\endgroup$ – CJ Dennis Jul 23 '18 at 5:36
  • $\begingroup$ @CJDennis: You could interpolate the three greatest magnitudes with a quadratic polynomial to estimate the maximum in the magnitude. $\endgroup$ – joriki Jul 23 '18 at 5:45
  • $\begingroup$ @CJDennis: Doing that with Wolfram|Alpha yields a maximum around $20.34$, corresponding to $20.34\cdot44100\text{Hz}/2048\approx438\text{Hz}$. $\endgroup$ – joriki Jul 23 '18 at 5:52
  • $\begingroup$ @CJDennis: Or you could perform the calculation I suggested in the last paragraph of the answer to get the functional form of the result depending on the input frequency, and then try to use that for a more specific method to estimate the frequency. $\endgroup$ – joriki Jul 23 '18 at 5:54
  • $\begingroup$ Possibly, if I understood the last paragraph... $\endgroup$ – CJ Dennis Jul 23 '18 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.