5
$\begingroup$

I'm using python to learn about Discrete Fourier Analysis. What I want to understand is when does the technique fail to recover some frequency of the signal? I understand how this can occur via the phenomenon of aliasing, however, the following quote from the Wikipedia page for a Discrete Fourier Transform has let me to believe there are other reasons that the technique would fail.

The frequencies of the output sinusoids are integer multiples of a fundamental frequency, whose corresponding period is the length of the sampling interval.

Based on that quote, it is my understanding that the discrete Fourier transform can only recover the frequencies when they are integer multiples of the fundamental frequency (i.e. the sample rate). If this is true, then if I construct a signal based on a series whose frequencies are all co-prime with the sample rate, then the discrete fourier transform would fail to discover those frequencies in the signal.

Here is the test I have constructed using python:

The signal I am analyzing is a sum of $\sin(2\pi kt) + cos(2\pi kt)$ where $k$ is in $\{11, 13, 17, 19\}$ for any time $t$ measured in seconds. I have sampled this signal at a sample rate of $100$ samples per second over one second. Notice that none of the frequencies is an integer multiple of the sample rate.

I am not able to post the image of the plots I made, since I am a new member here, however, python's fft (I'm using the one included in numpy) is definitely able to detect each of the frequencies of the series.

Can anyone please explain where I have gone wrong? Why is the fft able to discover the frequencies and under what conditions does the fft fail to discover frequencies in a signal (besides aliasing).

$\endgroup$
6
  • 3
    $\begingroup$ You might want to change the spelling; "discreet" (instead of the correct "discrete") will sound comical to many ears. $\endgroup$
    – user43208
    Jul 30, 2013 at 19:39
  • 2
    $\begingroup$ Have I been using the Indiscreet Fourier Transform??? Rats... $\endgroup$
    – Igor Rivin
    Jul 30, 2013 at 19:57
  • $\begingroup$ I think you have a fundamental misunderstanding of what the DFT does. That quote from the Wiki page is referring to the frequencies of the orthonormal basis that comprises the DFT, viz. $\left\{e^{j2\pi / N \cdot f_s \cdot n }\right\}$ for $n=0,\dots,N-1$, where $f_s$ is the sampling frequency. The DFT samples the spectrum at those locations. That's it. The transform is an isomorphism, so it is not true that it can only recover those particular frequencies; it just expresses signals as a linear combination of those frequencies. $\endgroup$
    – AnonSubmitter85
    Jul 30, 2013 at 22:22
  • $\begingroup$ The DFT does not "discover" frequencies. It simply expresses a signal as a linear combination of complex sinusoids. These sinusoids are what are related by multiplies of the fundamental frequency. The transform is also bijective, so any set of DFT coefficients corresponds to one and only one signal in the time domain. There are principles and techniques for resolving frequency components, but, given your question, I don't think that is what you are after. $\endgroup$
    – AnonSubmitter85
    Jul 31, 2013 at 9:41
  • $\begingroup$ The transform is an isomorphism, so it is not true that it can only recover those particular frequencies; it just expresses signals as a linear combination of those frequencies. Thank you, that does answer my question. $\endgroup$
    – Harlequin144
    Jul 31, 2013 at 18:26

2 Answers 2

Reset to default
3
$\begingroup$

Hint: let me ask you something: How do the plots look when $k$ is an integer multiple of the fundamental frequency, compared to when it is not? Have you tried varying the sampling rate (say, 100 -> 50) to see what the effect on the plots is?

My guess is that you will see very sharp peaks when $k$ is an integer multiple; you will see slightly wider peaks when $k$ is not; and these peaks will increase in wideness as the sampling rate decreases.

Can you figure out what is going on?

$\endgroup$
5
  • $\begingroup$ I think the OP's confusion is more fundamental and that getting into resolution issues will only confuse him/her further. The statement that "the discrete Fourier transform can only recover the frequencies when they are integer multiples of the fundamental frequency" shows a misunderstanding of what the DFT is. I think the OP would be better served with a textbook in this case as the material would be much too verbose for SE. $\endgroup$
    – AnonSubmitter85
    Jul 31, 2013 at 9:34
  • $\begingroup$ @AnonSubmitter85 can you suggest a good text on the topic? Preferably one that is free and online. $\endgroup$
    – Harlequin144
    Jul 31, 2013 at 18:30
  • $\begingroup$ @Harlequin144 I started with Oppenheim and Schafer as my first DSP book and can highly recommend it. I just google'd it and found a pdf of the 2nd edition. I don't know if it's a legit copy though, so let your conscience guide you. Also, if you are familiar with linear algebra, it may help you to understand things better if you look at the matrix-vector-product implementation of the DFT. It's slow, but it shows explicitly how the DFT is nothing more than a change of basis. $\endgroup$
    – AnonSubmitter85
    Aug 1, 2013 at 1:17
  • $\begingroup$ Interesting. Much appreciated! $\endgroup$
    – Harlequin144
    Aug 5, 2013 at 17:51
  • $\begingroup$ Yes, I just made such an answer (which may be more fitting to this question): math.stackexchange.com/questions/1551498/… $\endgroup$
    – mathreadler
    Dec 5, 2015 at 22:33
0
$\begingroup$

Copying parts of my own answer from this question:

Yes you are correct, this is what happens (to the FFT magnitude) when a pure sine goes from one integer to a neighbouring (in steps of $\frac{1}{16}$). We can see that the main frequency gets notably dampened and that the resulting energy (which of course is preserved by the FFT being unitary) spreads out more or less all over the spectrum.

enter image description here

$\endgroup$
1
  • $\begingroup$ What, I was here 3 years ago already? $\endgroup$
    – mathreadler
    Apr 4, 2018 at 7:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .