Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
You might want to change the spelling; "discreet" (instead of the correct "discrete") will sound comical to many ears. –  user43208 Jul 30 '13 at 19:39
2  
Have I been using the Indiscreet Fourier Transform??? Rats... –  Igor Rivin Jul 30 '13 at 19:57
    
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. –  AnonSubmitter85 Jul 30 '13 at 22:22
    
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. –  AnonSubmitter85 Jul 31 '13 at 9:41
    
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. –  Harlequin144 Jul 31 '13 at 18:26
add comment

migrated from mathoverflow.net Jul 30 '13 at 20:03

This question came from our site for professional mathematicians.

1 Answer

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?

share|improve this answer
    
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. –  AnonSubmitter85 Jul 31 '13 at 9:34
    
@AnonSubmitter85 can you suggest a good text on the topic? Preferably one that is free and online. –  Harlequin144 Jul 31 '13 at 18:30
    
@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. –  AnonSubmitter85 Aug 1 '13 at 1:17
    
Interesting. Much appreciated! –  Harlequin144 Aug 5 '13 at 17:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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