N為合數(shù)的FFT算法

上面討論的以2為基(即N＝2M)的時間抽選和頻率抽選FFT算法，由于具有程序簡單、 計算效率高、對存儲量要求不很高等優(yōu)點，因而在實際中得到了最廣泛的應用。如果N不等于 2的冪2M，通常有兩種處理辦法：
(1)用補零的辦法將x(n)延長為2M。例如N=60，可在序列x(n)的末尾填補4個0，即 令x(60)=x(61) =x(62)=x(63)=0，使N達到26＝64，這樣就可使用基2FFT算法。有限長序列補零以后，只是頻譜的取樣點有所增加而不會影響它的頻譜X(ejω)的形狀。
(2)采用以任意數(shù)為基數(shù)的FFT算法。
設N等于兩個整數(shù)p和q 的乘積，即N=p·q，則可將N點DFT分解成p個q點DFT或q個p點DFT來計算。為此，首先將x(n) 分為p組，每組長為q，即

從而說明：一個N=p·q點的DFT可以用p個q點DFT來組成，如下圖所示。

在最一般的情況下，設
     N=p1p2···pm，其中p1～pm是m個素因子。首先把N分解為兩個因子，即N=p1q1，其中q1＝p2p3···pm，并用以上討論的方法將DFT分解為p1個q1點DFT； 然后，將q1分解為q1=p2q2，其中q2=p3p4···pm，即將每一個q1點DFT分解為p2個q2 點DFT；這樣，通過m次分解，最后達到pm點 DFT。這種算法可以使DFT的運算獲得最高效率。