cooley－tukey算法區(qū)別于其他fft算法的一個重要事實就是n的因子可以任意選取。這樣也就可以使用n＝r^s的radix－r算法了。最流行的算法都是以r＝2或r＝4為基的，最簡單的dft不需要任何乘法就可以實現(xiàn)。例如：在s級且r＝2的情形下，下列索引映射的結(jié)果是：

　　s＞2時的－個一般慣例是，在信號流程圖中2點dft是以蝶形圖的形式繪出的，圖1給出了8點變換的圖示。信號流程圖己經(jīng)簡化成用所有指向一個節(jié)點的箭頭都代表加法的形式了，而常系數(shù)乘法則是在箭頭上加一個因子表示。radix－r算法具有l(wèi)og_r（n）級，并且每組都有相同類型的旋轉(zhuǎn)因子。

　　圖1 radix－2的長度為8的頻率抽取算法

　　從圖的信號流程圖可以看出，計算可以“就地”完成，也就是蝶形所使用的存儲位置可以被重寫，因為數(shù)據(jù)在下一步的計算中已不再需要了。radix－2變換的旋轉(zhuǎn)因子乘法總數(shù)是：

因為每兩個箭頭僅有一個旋轉(zhuǎn)因子。

　　由于圖1中的算法在頻域中開始將最初的dft分成更短的dft，所以這種算法就叫作頻率抽�。╠ecimation－in－frequency，dif）算法。典型的輸入值是按順序出現(xiàn)的，而頻率值的索引是按位逆序的。表給出了dif radix－2算法的特征值。

　　表 頻率抽取的radix－2 fft

　　我們還可以用時間抽取（decimation h time，dit）構(gòu)造一種算法。在該情況下，首先將輸入序列分開，就會發(fā)現(xiàn)所有頻率值都是按順序出現(xiàn)的。

　　圖2給出了索引41的radix－2和radix－4算法的必要索引變換。radix－2算法需要位順序的反轉(zhuǎn)，也就是位逆序。而radix－4需要首先構(gòu)造一個2位的“數(shù)字”然后再反轉(zhuǎn)這些數(shù)字，這種操作就稱為數(shù)字逆序。

　　圖2 位逆序和數(shù)字逆序

　　歡迎轉(zhuǎn)載，信息來源維庫電子市場網(wǎng)（www.dzsc.com）