0

I have read in a lot of different places that an FFT algorithm needs to have an input array size that is a power of two, like 512 or 1024. I also found a lot of different algorithms that compute FFT, like Cooley-Tuckey and Bluestein (this one also works with numbers that follow prime factors like 2,3,5,7).

Well, I'm using KissFFT and inputting an array of length 200. Why is it working? Does someone know what is happening in this case? Is it truncating the size to 128 (2^7), or maybe using another algorithm? If it is using another algorithm, does it still give the right answer but just take longer to compute? (Time is not actually a problem for me in this case.)

4

2 回答 2

0

我终于找到了一些有用的信息，这里是：

  • 一、Cooley和Tukey算法 链接

  • 其次，MATLAB：“您可以使用 nextpow2 填充您传递给 fft 的信号。当信号长度不是 2 的精确幂时，这样做可以加快 FFT 的计算速度。” 关联

谢谢你们

于 2014-10-28T19:35:01.883 回答
0

如果您绝对必须有一个长度不是 2 的幂的 FFT，那么至少有两种方法可以合理有效地完成它：

(1) 如果您想要的长度是小数的乘积，您可以推广当长度是 2 的精确幂时使用的方法。

(2) 实际上，您可以使用比任意长度更长的向量进行卷积来构建具有任意长度的 FFT，并且这些较长向量的长度可以是 2 的幂，这意味着您可以通过幂次卷积来进行 FFT-两个 FFT。参见例如http://www.engineeringproductivitytools.com/stuff/T0001/PT11.HTM。这利用了 AB = (AB)^2 - A^2 - B^2 的恒等式。您希望得到一个看起来有点像 f(Xi) exp(ij) 的项的总和。使用卷积，您可以将看起来有点像 f(Xi)exp(-i^2) 的东西与 exp((ij)^2) 组合起来，这样指数相加就可以得到 exp(-2ij+j^2) 并且您可以在后处理中去掉 j^2 - 参考资料向您展示了如何正确执行此操作，因此指数实际上是正确的，当然。

于 2014-10-28T20:03:16.580 回答