【文章內(nèi)容簡介】 )rr r rkx n k k x k k k??? ? ?? ?121 2 0 0( 2 2 )rrrrn n n kW ????? ? ?= 1 0 1 2 1 2 0 1 0 1 2 1 2 0( 0 ) ( 0 ) Pl r r r l r r rx n n n k k k x n n n k k k W? ? ? ? ? ? ? ?? （ 38） 式中 1 2 11 2 02 2 2r r rllP n n n? ? ???? ? ? ? （ 39） 根據(jù)式（ 38），第 L 個(gè)數(shù)組中每個(gè) 1 2 0 1 2 0( ) ( )l l r r r rx k x n n n k k k? ? ? ?? 的計(jì)算只依賴于上一個(gè)數(shù)組的兩個(gè)數(shù)據(jù)這兩個(gè)數(shù) 據(jù)的標(biāo)號(hào)相差 12 / 2YlN? ? ，即/2lj i n?? ，而且這兩個(gè)數(shù)據(jù)只用于計(jì)算第 L個(gè)數(shù)組中標(biāo)號(hào)的數(shù)據(jù)（等號(hào)右端為二進(jìn)制數(shù)）。當(dāng) 1ln? 分別取０和１時(shí)，分別有 , / 2 lk i k j i n? ? ? ?。因此，用上一組的兩個(gè)數(shù)據(jù)計(jì)算所得的兩個(gè)新數(shù)據(jù)仍可儲(chǔ)存在原來位置，計(jì)算過程中只需要 N個(gè)存儲(chǔ)器。將 ()lxi與 ( /2 )llx i n? 稱為第 L個(gè)數(shù)組中的對(duì)偶結(jié)點(diǎn)對(duì)。計(jì)算每個(gè)對(duì)偶結(jié)點(diǎn)對(duì)只需一次乘法，事實(shí)上由式（ 38）可得 11( ) ( ) [ ]2 pll lNx i x i i W?? ? ? 211( ) ( ) [ ]22 pl l lllNNx i x i x i W??? ? ? ? （ 310） 式中： lrlr nP ??? ??? 2...2 221 0n ； 0222 2...22 nnP lrlrlr ???? ???? 別為式（ 39）中 1?ln 取０，１時(shí)對(duì)應(yīng)的 P值。 因 2/2 1112 NPPP R ???? ? ，于是對(duì)偶結(jié)點(diǎn)的 pW 有如下關(guān)系： 1112 22 ][ PNPNNPP WeWW ???? ??? ??,因此式（ 38）可表示為 1111( ) ( ) [ ]2( ) ( ) [ ]22pl l l lpl l lllNx i x i x i WNNx i x i x i W????? ? ?? ? ? ? （ 311） 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 8 P 的求法：在 )(ixl中， i 寫成二進(jìn)制數(shù) kknnnlrl 01110 ?? ???右移 lr? 位，就成為 nnn l 11000 ??? 顛倒位序得 )2,1(00011 rlp nnn l ??? ?? ? 式（ 37）中，前面的 r 個(gè)等式，每個(gè)等式均對(duì)應(yīng)一組數(shù)據(jù)進(jìn)行計(jì)算，每組數(shù)據(jù)都有 N/２對(duì)結(jié)點(diǎn)，根據(jù)式（ 311），每對(duì)結(jié)點(diǎn)只需作１次乘法和２次加法，因此，每組數(shù)據(jù)只需 N/2次乘法和 N次加法，因而完成 r組數(shù)據(jù)的計(jì)算共需 Nr/2 次乘法和 Nr 次加法。 3. 2 CooleyTukey FFT 算法 FFT 的核心是將一層運(yùn)算映射為二層運(yùn)算。作 N 點(diǎn) FFT 時(shí)，若 N 不是素?cái)?shù)，則 N 可分解為 12N NN? ，那么由 []fn的 DFT 10[ ] [ ] 0 1N nkNnF k f n W k N??? ? ? ?? （ 312） 通過映射： 2 1 2 1 1 2 21 1 2 1 1 2 20 1 , 0 10 1 , 0 1n N n n n N n Nk k N k k N k N? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? （ 313） 可得到 2 1 2 1 1 2 2 1 1 1 2 1 2 2 1 1 2 2( ) ( ) ( )N n n k N k N n k N N n k n k N n knkN N NW W W? ? ? ? ??? 而 12N NN? ， 12NNNWW?， 21NNNWW?，可化簡為 1 1 2 1 2 212n k n k n knkN N N NW W W W? （ 314） 從而式（ 312）轉(zhuǎn)化為 212 2 2 1 1 121111 2 1 200[ , ] ( [ , ] )NNn k n k n kN N NnnF k k W W f n n W????? ?? （ 315） 其中 1 1 2 20 1 , 0 1k N k N? ? ? ? ? ?。 以 20 點(diǎn) FFT 為例， 1220, 5, 4N N N? ? ?，映射方式為： 124n n n??，125k k k?? ，則計(jì)算流圖如圖 31 所示。 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 9 圖 31 CooleyTukey 20 點(diǎn) FFT算法 3. 3 RaderBrenner FFT 算法 RaderBrenner 算法是類似于 CooleyTukey 算法，但是采用的旋轉(zhuǎn)因 子都是純虛數(shù)，以增加加法運(yùn)算和降低了數(shù)值穩(wěn)定性為代價(jià)減少了乘法運(yùn)算。這方法之后被 splitradix variant of CooleyTukey 所取代，與 RaderBrenner 算法相比，有一樣多的乘法量，卻有較少的加法量，且不犧牲數(shù)值的準(zhǔn)確性 [7]。 Bruun 以及 QFT 算法是不斷的把 DFT 分成許多較小的 DFT 運(yùn)算。(RaderBrenner 以及 QFT 算法是為了 2 的指數(shù)所設(shè)計(jì)的算法，但依然可以適用在可分解的整數(shù)上。 Bruun 算法則可以運(yùn)用在可被分成偶數(shù)個(gè)運(yùn)算的數(shù)字 )。尤其是 Bruun 算法，把 FFT 看成是 1?zN ，并把它分解成 1?zM 與 12 ?? zz MM a 的形式。 另一個(gè)從多項(xiàng)式觀點(diǎn)的快速傅立葉變換法是 Winograd 算法。此算法把n1 k2 f[0] 0 W0 0 F[0] f[4] 1 W0 1 F[5] f[8] 2 W0 2 F[10] f[12] 3 W0 3 F[15] f[16] 4 W0 0 F[1] f[1] 0 W1 1 F[6] f[5] 1 W2 2 F[11] f[9] 2 W3 3 F[16] f[13] 3 f[17] 4 W0 0 F[2] W2 1 F[7] f[2] 0 W4 2 F[12] f[6] 1 W6 3 F[17] f[10] 2 f[14] 3 W0 0 F[3] f[18] 4 W3 1 F[8] W6 2 F[13] f[3] 0 W9 3 F[18] f[7] 1 f[11] 2 W0 0 F[4] f[15] 3 W4 1 F[9] f[19] 4 W8 2 F[14] W12 3 F[19] k1=0 n2=0 n2=1 n2=2 n2=3 k1=1 k1=2 k1=3 k1=4 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說明書 10 1?zN 分 解成 cyclotomic 多項(xiàng)式，而這些多項(xiàng)式的系 數(shù)通常為 1， 0， 1。 這樣只需要很少的乘法量 (如果有需要的話 )，所以 winograd 是可以得到最少乘法量的快速傅立葉算法，對(duì)于較小的數(shù)字，可以找出有效率的算方式。更精確地說，winograd 算法讓 DFT 可以用 2K點(diǎn)的 DFT 來簡化，但減少乘法量的同時(shí)，也增加了非常多的加法量。 Winograd 也可以利用剩余值定理來簡化 DFT。 Rader 算法提出了利用點(diǎn)數(shù)為 N(N 為質(zhì)數(shù) )的 DFT 進(jìn)行長度為 N1的回旋折積來表示原本的 DFT，如此就可利用折積用一對(duì)基本的 FFT 來計(jì)算 DFT。另一個(gè)primesize 的 FFT 算法為 chirpZ 算法。此法也是將 DFT 用折積來表示，此法與 Rader 算法相比，能運(yùn)用在更一般的轉(zhuǎn)換 上，其轉(zhuǎn)換的基礎(chǔ)為 Z 轉(zhuǎn)換 [8]。 Goertsel 算法 如前所述 , N 點(diǎn)時(shí)域序列 )(nx 的離散付里葉變換式為 ?? ?? ?10 )()( Nn knNWnxkX ， 1,....,2,1,0 ?? Nk （ 316） 這 N 點(diǎn)頻域序列是同時(shí)被算出的，不可能只計(jì)算其中某一個(gè)或幾個(gè)指定點(diǎn)。Goetzel 算法是為了解決這個(gè)問題而提出的。這個(gè)算法把離散付里葉變換看作一組濾波器，將輸入端的時(shí)域序列與其中一個(gè)濾波器的沖激響應(yīng)序列進(jìn)行卷積運(yùn)算，求濾波器的輸出序列，即得 )(kX 序列的一點(diǎn)。這種算法利用旋轉(zhuǎn)因子 kNW 的周期性，使 DFT 運(yùn)算化為線性濾波運(yùn)算 [9]。 由于 1))(2( ?? ???? kNNjkNN eW 故式（ 316）可化為 )(1010 )()()( mNkNNmkmNNmkNN WmxWmxWkX ??????? ????1,....,2,1,0 ?? Nk （ 317） 定義序列 )(nyk 為 )(10 )()( mnkNNmk Wmxny ?????? （ 318） 可見 )(nyk 是由兩個(gè)序列卷積而得到的序列。 )()()( nhnxny kk ?? （ 319） 其中， )(nx 是輸入的 N 點(diǎn)序列，另