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

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

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

在最一般的情況下，設(shè)
     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；這樣，通過m次分解，最后達(dá)到pm點(diǎn) DFT。這種算法可以使DFT的運(yùn)算獲得最高效率。