KissFFT和两个功率

我已经读了很多不同的地方，FFT算法需要有一个输入数组大小是2的幂，如512或1024.我还发现了很多不同的算法，计算FFT，就像Cooley-Tuckey和Bluestein一样（这个也适用于2,3,5,7等主要因素）。KissFFT和两个功率

那么，我使用KissFFT并输入长度为200的数组。为什么它工作？有人知道在这种情况下发生了什么？是截断大小为128（2^7），或者可能使用其他算法？如果它正在使用另一种算法，它是否仍然给出正确的答案，但只需花费更长的时间来计算？（时间实际上不是一个问题，我在这种情况下）。

来源

2014-10-28 Will

前段时间当我实现FFT时，我一直在调整数据长度为2^n（并用零填充“新单元格”），它的工作原理可以用这种方式实现 – fex 2014-10-28 17:33:23

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

首先，库利和基算法 link
第二，MATLAB： “你可以使用nextpow2来填充你传递给fft的信号，这样做可以在信号长度不是2的精确幂时加快FFT的计算。” link

谢谢大家

来源

2014-10-28 19:35:01 Will

如果你绝对必须有长度的FFT不是2的幂，至少有两种方法可以合理有效地做到这一点：

（1）你想要的长度是小数的乘积，当长度是2的精确幂时，可以推广使用的方法。（2）实际上你可以用长度超过任意长度的矢量来构建一个任意长度的FFT，这些较长的矢量的长度可以是2的幂，这意味着你可以做FFT由两个幂的FFT进行卷积。例如参见http://www.engineeringproductivitytools.com/stuff/T0001/PT11.HTM。这使用了AB =（A-B）^ 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-28 20:03:16 mcdowella

KissFFT和两个功率

回答

相关问题