N為合數的FFT算法

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

從而說(shuō)明：一個(gè)N=p·q點(diǎn)的DFT可以用p個(gè)q點(diǎn)DFT來(lái)組成，如下圖所示。

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