正像這一章的概述中所提到的，我們使用的是surrus^[111]提出的術語，他將所有的快速傅立葉變換（fast fourier transform，fft）算法簡單地根據(jù)不同的（多維）輸入輸出序列的索引映射進行分類。這是建立在長度為n的dft（6．2）：

　　到多維n＝ii_lan_l的表達式的變換基礎之上的。—般情況下，只需要討論兩個因子的情形就足夠了，因為更高的維數(shù)可以通過簡單地反復迭代替換其中的一個因子就能夠?qū)崿F(xiàn)。為了簡化表達式，我們在此只在二維索引映射變換內(nèi)討論3種fet算法。

　　將（時域）索引n用：

　　進行交換，其中n＝n₁n₂，且a，b∈z是以后必須定義據(jù)下面的公式：

　　來構造數(shù)據(jù)的二維映射f∶cⁿ→c^{n₁ x n₂}。將另一個索引映射k應用到輸出（頻）域， 就得到：

　　其中c，d∈z是以后必須定義的常數(shù)。由于dft是雙映射，所以我們必須選擇a，b，c和d，這樣變換表達式才能仍然保持惟一，也就是惟一的雙映射投影。burrus^[111]已經(jīng)確定了如何為具體的n1和n2選擇a，b，c和d的一般情形，這樣映射就是雙映射了。

　　區(qū)別不同fft算法的重要一點就是是否允許n1和n2具有公因數(shù)的問題，也就是gcd（n₁，n₂）＞1（gcd，greatest common divisor，最大公約數(shù)），或者說ny和蠅必須是互質(zhì)的。通常，god（n₁，n₂）1的算法指的是公共因數(shù)算法（common factor algorithms，cfas），而gcd（n₁，n₂）＝1就稱為質(zhì)數(shù)因數(shù)算法（prlrne factor algorithms，pfas）。在接下來要討論的cfa算法是cooley-tukey fft，而good－thomas和winograd fft則是pfa類型的。應該強調(diào)的是cooley－tukey算法可以真正地用兩個因數(shù)n＝n1n2實現(xiàn)，彼此之間是互質(zhì)的，并且對于pfa，因子n₁和n₂必須是互質(zhì)的，也就是說它們自身不一定是質(zhì)數(shù)。例如：長度n＝12的變換因數(shù)分解成n₁＝4和n₂＝3，既可以用于cfa fft也可以用于pfa fft ！

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