【正文】 kk ?? （ 319） 其中， )(nx 是輸入的 N 點(diǎn)序列，另一個(gè)序列被看作濾波器的沖激響應(yīng)序列 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 11 )()( nuWnh knNk ?? 。這種算法利用旋轉(zhuǎn)因子 kNW 的周期性，使 DFT 運(yùn)算化為線性濾波運(yùn)算 [9]。Goetzel 算法是為了解決這個(gè)問(wèn)題而提出的。此法也是將 DFT 用折積來(lái)表示，此法與 Rader 算法相比，能運(yùn)用在更一般的轉(zhuǎn)換 上，其轉(zhuǎn)換的基礎(chǔ)為 Z 轉(zhuǎn)換 [8]。 Rader 算法提出了利用點(diǎn)數(shù)為 N(N 為質(zhì)數(shù) )的 DFT 進(jìn)行長(zhǎng)度為 N1的回旋折積來(lái)表示原本的 DFT，如此就可利用折積用一對(duì)基本的 FFT 來(lái)計(jì)算 DFT。更精確地說(shuō)，winograd 算法讓 DFT 可以用 2K點(diǎn)的 DFT 來(lái)簡(jiǎn)化，但減少乘法量的同時(shí)，也增加了非常多的加法量。此算法把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ì) (論文 )說(shuō)明書 10 1?zN 分 解成 cyclotomic 多項(xiàng)式，而這些多項(xiàng)式的系 數(shù)通常為 1， 0， 1。尤其是 Bruun 算法，把 FFT 看成是 1?zN ，并把它分解成 1?zM 與 12 ?? zz MM a 的形式。(RaderBrenner 以及 QFT 算法是為了 2 的指數(shù)所設(shè)計(jì)的算法，但依然可以適用在可分解的整數(shù)上。這方法之后被 splitradix variant of CooleyTukey 所取代，與 RaderBrenner 算法相比，有一樣多的乘法量，卻有較少的加法量，且不犧牲數(shù)值的準(zhǔn)確性 [7]。 以 20 點(diǎn) FFT 為例， 1220, 5, 4N N N? ? ?，映射方式為： 124n n n??，125k k k?? ，則計(jì)算流圖如圖 31 所示。 3. 2 CooleyTukey FFT 算法 FFT 的核心是將一層運(yùn)算映射為二層運(yùn)算。計(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 ?。埃睍r(shí)對(duì)應(yīng)的 P值。因此，用上一組的兩個(gè)數(shù)據(jù)計(jì)算所得的兩個(gè)新數(shù)據(jù)仍可儲(chǔ)存在原來(lái)位置，計(jì)算過(guò)程中只需要 N個(gè)存儲(chǔ)器。將初始數(shù)據(jù)代入式（ 37）的第一個(gè)等式，可得每一組計(jì)算數(shù)據(jù)，一般將痗 L1 組計(jì)算數(shù)據(jù)代入式（ 37）的第 L個(gè)等式，計(jì)算后可得第 L 組計(jì)算數(shù)據(jù)（ L＝１，２，?，γ），計(jì)算公式也可表示為 1011 0 2 0 0 1 2 0( ) ( )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) 2rN? 時(shí)， n 和 k 可用二進(jìn)制數(shù)表示： 121 2 0 1 2 022rrr r r rn n n n n n n??? ? ? ?? ? ? ? ?錯(cuò)誤 ! 未 找 到 引 用 源 。 次乘法及 N(N1)次復(fù)數(shù)加法。12,1,0。 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 6 3. 快速傅里葉變換的算法 快速傅里 葉變換算法 快速傅里葉變換 FFT 是離散傅里葉變換 DFT 的一種快速算法，只有 FFT 才能在現(xiàn)實(shí)中有實(shí)際應(yīng)用的意義。5. 著名的卷積定理指出 :傅立葉變換可以化復(fù)變換可以利用數(shù)字計(jì)算機(jī)快速的算出 (其算法稱為快速傅立葉變換算法 (FFT))。3. 正弦基函數(shù)是微分運(yùn)算的本征函數(shù) ,從而使得線性微分方程的求解可以轉(zhuǎn)化為常系數(shù)的代數(shù)方程的求解 .在線性時(shí)不變雜的卷積運(yùn)算為簡(jiǎn)單的乘積運(yùn)算 ,從而提供了計(jì)算卷積的一種簡(jiǎn)單手段 。 任意 的函數(shù)通過(guò)一定的分解，都能夠表示為正弦函數(shù)的線性組合的形式，而正弦函數(shù)在物理上是被充分研究而相對(duì)簡(jiǎn)單的函數(shù)類： 1. 傅立葉變換是線性算子 ,若賦予適當(dāng)?shù)姆稊?shù) ,它還是酉算子 。在不同的研究領(lǐng)域里，傅里葉變 換具有多種形式各異的變體形式，如連續(xù)傅里葉變換和離散傅里葉變換。 從現(xiàn)代數(shù)學(xué)的眼光來(lái)看，傅里葉變換其實(shí)就是一種特殊的積分變換。因此，也可以說(shuō)，傅立葉變換將原來(lái)難以處理的時(shí)域信號(hào)轉(zhuǎn)換成了易于分析的頻域信號(hào)（信號(hào)的頻譜），我們可以利用一些專業(yè)工具對(duì)這些頻域信號(hào)進(jìn)行加工、處理。 與傅立葉變換算法對(duì)應(yīng)的是反傅立葉變換算法。傅立葉變換原理表明：任何連續(xù)測(cè)量的時(shí)序或信號(hào)，都能夠表示成為不同頻率的正弦波信號(hào)的無(wú)限疊加。 2. 3 快速傅里葉變換的意義 傅立葉變換的物理意義：傅立葉變換是數(shù)字信號(hào)處理技術(shù)領(lǐng)域一項(xiàng)很重要的算法。承接上面的例子，當(dāng) 1024?時(shí)，總的運(yùn)算次數(shù)就變成了 525312 次，這樣看來(lái)，節(jié)省了大約 50%的運(yùn)算量。在 FFT 中，利用 WN 的對(duì)稱性和周期性，把一個(gè) N 項(xiàng)序列（設(shè)k2?,k為正整數(shù)），分為兩個(gè) /項(xiàng)的子序列，而且每個(gè) 2/點(diǎn)的 DFT 變換需要? ?2/N次運(yùn)算，再運(yùn)用 N次運(yùn)算把兩個(gè) 2/N點(diǎn)的DFT 變換重新組合成一個(gè) N點(diǎn)的 DFT 變換。 其中：快速傅里葉變換分為兩種，分為基 2時(shí)間抽取算法和基 2 頻率抽取算法 基 2時(shí)間抽取 (Decimation in time)FFT 算法 ??? ?? ]12[ ]2[][ rx rxkx其中 :r=0,1,2? 12?N （ 21） 基 2頻率抽取 (Decimation in frequency)FFT 算法 ??? ?? ]12[ ]2[][ mX mXmX （ 22） 武漢工程大學(xué)畢業(yè)設(shè)計(jì) (論文 )說(shuō)明書 4 2. 2 快速傅里葉變換的優(yōu)越性 設(shè)nx為N項(xiàng)的復(fù)數(shù)序列，依據(jù) DFT 變換，任一)(mx的計(jì)算都需要有N次復(fù)數(shù)乘法和（1?）次復(fù)數(shù)加法，而且一次復(fù)數(shù)乘法等同于四次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法，同樣的，一次復(fù)數(shù)加法等同于兩次實(shí)數(shù)加法，即使我們把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運(yùn)算”（四次實(shí)數(shù)乘法和四次實(shí)數(shù)加法），那么求出N項(xiàng)復(fù)數(shù)序列的)(mx, 即 N 點(diǎn) DFT 變換大約就需要2N次運(yùn)算。 2. 1 快速傅里葉變換原理 快速傅里葉變換原理： 1. 將長(zhǎng)序列 DFT分解為短序列的 DFT 2. 利用旋轉(zhuǎn)因子的對(duì)稱性、周期性、可約性。 1965 年 , 和 發(fā)現(xiàn)了 DFT 的一種快速算法 ,經(jīng)過(guò)后來(lái)學(xué)者的進(jìn)一步改進(jìn) , 很快便形成了一套高效的運(yùn)算方法 ,即現(xiàn)在通用的快速傅里葉變換 , 簡(jiǎn)稱 FFT( The Fast Fourier Transform)。 DFT 存在的缺點(diǎn)就是計(jì)算量太大 ,不易進(jìn)行實(shí)時(shí)處理。 FFT技術(shù)應(yīng)用 DSP芯片，從而可以提供使調(diào)制、解調(diào)、壓縮、解壓縮的數(shù)據(jù)傳輸更為高效的信號(hào)處理解決方案，因而廣泛應(yīng)用于雷達(dá)、圖像處理、通信、生物醫(yī)學(xué)和聲納領(lǐng)域。多數(shù)的 DSP芯片都能夠在一個(gè)指令周期內(nèi)完成一次乘法和加法，并且提供了專門的 FFT指令，完成一次指令的周期只需 10ns，使得 FFT算法在 DSP芯片上實(shí)現(xiàn)的速度更加快速。 1. 2 課題研究的意義 如上所述，基于對(duì) DSP的快速傅里葉變換算法的研究，從而使 FFT算法能夠有效地在 DSP芯片上實(shí)現(xiàn)。數(shù)字信號(hào)處理區(qū)別于普通的科學(xué)計(jì)算與分析，它強(qiáng)調(diào)運(yùn)算的實(shí)時(shí)性。之前通用的 微處理器在運(yùn)算速度上已經(jīng)很難適應(yīng)信號(hào)實(shí)時(shí)處理的高要求。 數(shù)字信號(hào)處理器（ DSP），是一種可編程的高性能處理器。應(yīng)當(dāng)指出的是，也是因?yàn)楫?dāng)時(shí)電子數(shù)字計(jì)算機(jī)的“落后”條件也促成了這個(gè)算法的提出。繼庫(kù)利和圖基算法出來(lái)之后，桑德（ ）