为什么FFT要求N为2的幂数

问题描述

精选答案

不一定，亦存在不需指定为$2^n$的FFT。之所以通常的FFT需要指定为$2^n$个点，大概是因为这些原因：

1.最简单的FFT实现基于一个折半（$n

o

frac{n}{2}$）的递归。如此，我们当然需要点的个数为$2$的幂。

2.在以上基础上，一般需要使用FFT的场合，对点数并没有强制限定。即，即使点数不是$2$的幂，可以增加一些平凡（一般是值为$0$的）点凑出一个$2$的幂，然后进行运算，如此不影响算法的执行。（当然，有一些场合下，因为某些外部的要求，并不能使用该方法）3.$2$的幂对于计算机而言是“喜欢的”。