cooley－tukey fft是所有fft算法中最為通用的，因?yàn)棰た梢匀我獾剡M(jìn)行因數(shù)分解。最流行的cooley-tukey fft就是變換長(zhǎng)度n是r基的冪的形式，也就是n＝r^v。這些算法通常稱(chēng)作r基算法。

　　cooley和tukey（更早是gauss）提出的索引變換也是最簡(jiǎn)單的索引映射。令a＝n₂和b＝1就得到下面的映射結(jié)果：

　　從n₁和n₂的正確范圍可以得出結(jié)論。

　　cooley和tukey選擇c＝1和d＝n₁，就得到下面的映射結(jié)果：

　　在這種情況下也可以省略模計(jì)算。這時(shí)候如果根據(jù)（6．20）式和（6．21）式分別將n和k代入w^nk_n就會(huì)得到：

　　由于w是n＝n₁n₂階的。就可以得到wⁿ¹_n＝w_n2和wⁿ²_n＝w_n1，將（6．22）式簡(jiǎn)化成：

　　這時(shí)將就得到：

　　現(xiàn)在定義完整的cooley－tukey算法：

　　接下來(lái)用長(zhǎng)度為12的變換來(lái)說(shuō)明這些步驟。

　　例 n＝12的cooley－tukey fft

　　假設(shè)n1＝4和n2＝3。則有n＝3n1＋n2和k=k1＋4k2，為索引映射計(jì)算下面的表：

　　在這個(gè)變換的幫助之下，可以構(gòu)造如圖所示的信號(hào)流程圖�？梢钥吹剑紫缺仨氂�4個(gè)點(diǎn)計(jì)算3個(gè)dft中的每一個(gè)，然后乘以旋轉(zhuǎn)因子，最后計(jì)算4個(gè)dft，其中每個(gè)的長(zhǎng)度都是3。

　　圖 n12的cooley-tukey fft

　　要直接計(jì)算12點(diǎn)的dft，總共需要12²＝144次復(fù)數(shù)乘法和11²＝121次復(fù)數(shù)加法。要計(jì)算同樣長(zhǎng)度的cooley－tukey fft，旋轉(zhuǎn)因子需要12次復(fù)數(shù)乘法，其中8次是無(wú)關(guān)緊要的乘法（也就是±1或與）。用8次實(shí)數(shù)加法就可以計(jì)算長(zhǎng)度為4的dft，而且不需要乘法。要計(jì)算長(zhǎng)度為3的dft，則需要4次乘法和3次加法。如果要用3次加法和3次乘法實(shí)現(xiàn)（固定系數(shù)的）復(fù)數(shù)乘法，12點(diǎn)cooley－tukey fft的總工作量是：

　　而直接實(shí)現(xiàn)則需要2×11²＋12²×3＝674次實(shí)數(shù)加法和12²×3＝432次實(shí)數(shù)乘法�，F(xiàn)在就應(yīng)該非常清楚為什么將cooley-tukey算法叫作“快速傅立葉變換”（fast fourier transform，fft）的原因。

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