快速傅里叶变换FFT为什么必须是2^n呢?

郭先抢

进行FFT的时候要求点必须是2^n个,这是为什么呢?
我很好奇,虽能告诉我简单的容易明白的理由呢?

Lwins_G

不一定，亦存在不需指定为$2^n$的FFT。
之所以通常的FFT需要指定为$2^n$个点，大概是因为这些原因：
1. 最简单的FFT实现基于一个折半（$n \to \frac{n}{2}$）的递归。如此，我们当然需要点的个数为$2$的幂。
2. 在以上基础上，一般需要使用FFT的场合，对点数并没有强制限定。即，即使点数不是$2$的幂，可以增加一些平凡（一般是值为$0$的）点凑出一个$2$的幂，然后进行运算，如此不影响算法的执行。（当然，有一些场合下，因为某些外部的要求，并不能使用该方法）
3. $2$的幂对于计算机而言是“喜欢的”。

郭先抢

这个答案不算是让我太满意

Lwins_G

这个答案不算是让我太满意
郭先抢 发表于 2012-12-15 18:30

已尽力而为。

liangbch

任何正整数数都可以表示为几个质数的乘积，这几个质数称为这个数的素因子。如果一个数的素因子仅包含2(即变换长度为2^k)，这样的FFT变换是最简单，
也最容易实现一个高效的算法。如果一个数的素因子包含多个小质数，如30，48，80，这样的FFT也可以实现，不过实现比较复杂，性能也不如变换长度
为2^k的FFT。FFTW是目前公认的性能最好的FFT的实现，它给出的性能测试页，就包括变换长度为2^k和变换长度包含小的素因子两种情况，前者包括变换
长度为 2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144的性能数据，后者包含变换长度为6,9,12,15,18,24,36,
80,108,210,504,1000,1960,4725,10368,27000,756000,165375的性能数据。详情请见http://www.fftw.org/speed/Pentium4-2.4GHz-icc/。

FFT的长度包含多个素因子的变换叫做混合基FFT. 我在csdn发的一个帖子《征集FFT算法的代码和算法》 http://bbs.csdn.net/topics/80425676
有对FFT的讨论，我还给出《7种FFT代码和测试程序》资源，可在: http://download.csdn.net/detail/liangbch/2025284 下载

郭先抢

任何正整数数都可以表示为几个质数的乘积，这几个质数称为这个数的素因子。如果一个数的素因子仅包含2(即变换长度为2^k)，这样的FFT变换是最简单，
也最容易实现一个高效的算法。如果一个数的素因子包含多个小质数， ...
liangbch 发表于 2012-12-17 11:51

版主果然很有水平呀