Calculating fourier transform at any frequency

Question

I know that if we have some data representing some wave, for example image line values, we can use fourier transform to get frequency function of that wave. But we have N values at points x=0...N-1 And we get only N frequencies at the output. So I want to analyze the wave everywhere in the range [0, N-1] For example at point u = 1.5. How can I do it?

Answer 1

It's been over 10 years since I've done any of these, but I think Matlab had some FT methods that would let you do what you wanted. At least that's what we used in our Linear Signals and DSP classes

Answer 2

You need to interpolate the data for those intermediate points.

Answer 3

Computing the Fourier transform value for any frequency from a set of samples is actually quite easy:

F(w)= sum[over all sample indices k] ( f(t_k) e^(i w t_k) )

Code-wise, you do something like this:

float Fourier(float omega) {
  Complex a(0.0); // think "a is for accumulator"
  for(int k=0; k<value.size(); ++k) {
    float time= t_start + k*dt;
    float theta= omega * time;  // this is (w t_k) from above
    a+= value[k] * Complex(cos(theta), sin(theta));
  }
  return a;
} // note, I have explicitly written out e^(i theta) = cos(theta) + i sin(theta)

If you have irregular sample times, you can use a time[] vector/array along with your value[] vector/array, instead of computing the time from the index. (However, be careful, since irregularly spaced samples don't necessarily mean what you think they do! If this comment is in any way mysterious, stick with regular samples...)

The only problem is that, if you want to generate N regularly spaced frequencies based on regular samples, doing it the above way will take O(N^2) time. The Fast Fourier Transform is an algorithm that does this in O(N log N) time.