math - 计算任意频率的傅立叶变换

Question

我知道如果我们有一些数据代表一些波，例如图像线值，我们可以使用傅立叶变换来获得该波的频率函数。但是我们在点 x=0...N-1 处有 N 个值我们在输出端只得到 N 个频率。所以我想分析 [0, N-1] 范围内的所有波浪例如在点 u = 1.5。我该怎么做？

Answer 1

计算一组样本中任意频率的傅立叶变换值实际上非常简单:

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

代码方面，你做这样的事情:

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)

如果你有不规则的采样时间，你可以使用 time[] 向量/数组和你的 value[] 向量/数组，而不是从索引计算时间。 (但是，要小心，因为不规则间隔的样本并不一定就是你认为的那样!如果这个评论有任何神秘之处，请坚持使用常规样本...)

唯一的问题是，如果您想要基于规则样本生成 N 个规则间隔的频率，按上述方式执行将花费 O(N^2) 时间。 快速傅立叶变换是一种在 O(N log N) 时间内执行此操作的算法。