【正文】 ，因此比CooleyTukey算法的乘法運算次數(shù)要少得多，而加法次數(shù)與之相當。WFTA算法有兩個主要思想：一是用Rader提出的方法將小N點DFT轉(zhuǎn)換為循環(huán)卷積，利用多項式理論使卷積計算具有盡可能少的乘法次數(shù)；二是將小N點DFT運算進行嵌套來完成大N點的DFT運算。但WFTA算法也有一些突出的問題，如算法不能采用原位運算，需要占用較大的存儲空間，更重要的是，隨著變換點數(shù)N的不同，為使運算所需的加法次數(shù)最少，要求采用不同的運算次序，這導致運算過程的規(guī)則性較差，且控制過程復雜。但后來發(fā)現(xiàn)它們在實際應用中并不理想，盡管在理論上仍是有意義的進展。分裂基算法的特點是將基2分解與基4分解揉和在一起，對序列的不同部分分別實施基2算法和基4算法。乘法：加法：對于具體實現(xiàn)而言，算法的運算量只是一個方面，而算法的復雜性、規(guī)則性、模塊性往往是更重要的。這一算法相對簡單、規(guī)則，且所有的運算單元均相同，具有良好的模塊性，易于實現(xiàn)。為使運算所需的加法次數(shù)最少，隨著變換點數(shù)N的不同，要求采用不同的運算次序，這導致運算過程的規(guī)則性較差，控制過程復雜。對于PFA算法，由于沒有與旋轉(zhuǎn)因子相乘的運算，因此避免了對旋轉(zhuǎn)因子的求取，但由于指標映射造成的地址表達式中具有乘、加及求模運算，而這些運算又不易采用簡單的方法實現(xiàn)，因此PFA算法的控制單元要比CooleyTukey算法的復雜。雖然不同長度的短點數(shù)DFT運算單元可以采用統(tǒng)一的通用結(jié)構(gòu)，但這不僅降低硬件的效率，同時影響運算單元的速度。對于分裂基算法，由于不同地址中的數(shù)據(jù)分別輸入到2點、4點DFT運算模塊以及與旋轉(zhuǎn)因子相乘的單元進行運算，模塊性同樣較差，對于程序控制來說比較困難。對于變換點數(shù)N為2的整數(shù)次幕的情況，分裂基算法的乘法次數(shù)比基基4算法更少。二者都是通過指標映射，將一維DFT轉(zhuǎn)化為多維DFT，同時避免了與旋轉(zhuǎn)因子相乘的運算，因此都有更少的運算次數(shù)?？偟膩碚f，快速傅里葉變換（Fast Fourier Transform，F(xiàn)FT）并不是與離散傅里葉變換不同的另一種變換，而是為了減少DFT計算次數(shù)的一種快速有效的算法。它對傅氏變換的理論并沒有新的發(fā)現(xiàn)，但是對于在計算機系統(tǒng)或者說數(shù)字系統(tǒng)中應用離散傅里葉變換，可以說是進了一大步。當N=1024點甚至更多的時候，需要次運算，在FFT中，利用的周期性和對稱性，把一個N項序列（設(shè)N=2k，k為正整數(shù)），分為兩個項的子序列，每個點DFT變換需要次運算，再N次運算把兩個點的DFT變換組合成一個N點的DFT變換。繼續(xù)上面的例子，N=1024時，總的運算次數(shù)就變成了525312次，節(jié)省了大約50%的運算量。 快速傅里葉變換算法FFT的基本思想：將大點數(shù)的DFT分解為若干個小點數(shù)DFT的組合，從而減少運算量。算法分類如圖21所示：FFT算法基2FFT算法基4FFT算法混合基算法分裂基算法線性調(diào)頻Z變換算法按時間抽取按頻率抽取圖21 FFT的幾種算法在這次設(shè)計中，采用最基礎(chǔ)的按時間抽取的基2FFT算法來實現(xiàn)快速傅里葉變換。該情況下的變換稱為基2FFT算法。先將序列x(n)按奇偶項分解為兩組： （21）將DFT運算也相應分為兩組: （22）其中分別是的點的DFT （23）至此，一個點DFT被分解為兩個點的DFT。要求出全部點的，需要找出、和的關(guān)系，其中。1圖22 蝶形運算符號通過這樣的分解以后，每一個點的DFT只需要次復數(shù)乘法，兩個點的DFT需要次復乘，再加上將兩個點DFT合并成N點的DFT時，有次與因子相乘，一共需要次復乘。因為，仍然是偶數(shù)，因此可以對兩個點的DFT分別作進一步的分解，將兩個的DFT分解成兩個點的DFT。一直分解下去，最后是2點的DFT，2點的DTF的運算也可以用蝶形符號來表示。a)8點DFTX[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]b)X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]4點DFTX[0]X[2]X[4]X[6]X[1]X[3]X[5]X[7]11 4點DFT11X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]2點DFT2點DFT2點DFT2點DFT11111111X[0]X[4]X[2]X[6]X[1]X[5]X[3]X[7]c)d)X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]X[0]X[4]X[2]X[6]X[1]X[5]X[3]X[7]X[0]X[4]X[2]X[6]X[1]X[5]X[3]X[7]11111 1111111圖23 時間抽取分解過程這種方法，由于每一步分解都是按輸入序列在時域上的次序是屬于偶數(shù)還是奇數(shù)來抽取的，故稱為“時間抽取法”。每一級運算都是由個蝶形運算構(gòu)成，因此每一級運算都需要次復乘和M次復加，則按時間抽取的M級運算后總用需要：復數(shù)乘法次數(shù)： 復數(shù)加法次數(shù)： 根據(jù)上面的流圖，分析FFT算法的兩個特點，它們對FFT的軟硬件構(gòu)成產(chǎn)生很大的影響。根據(jù)運算流圖分析原位運算是如何進行的。（2） 變址：分析運算流圖中的輸入輸出序列的順序，輸出按順序，輸入是“碼位倒置”的順序，見表21所示。變址的功能如圖24所示。盡管變址運算所占運算量的比例很小，但對某些高要求的應用（尤其在實時信號處理中），也可設(shè)法用適當?shù)碾娐方Y(jié)構(gòu)直接實現(xiàn)變址。圖24 碼位倒置的變址處理01234567X（0）X（4）X（2）X（6）X（1）X（5）X（3）X（7）在這里，我想簡單的介紹一下其他的算法，為了開發(fā)創(chuàng)新思維，開創(chuàng)改進新算法等。當?shù)那闆r一般可有以下兩種處理方法：（1）將用補零的方法延長，使N增長到最鄰近的一個數(shù)值。如果計算FFT的目的是為了解整個頻譜，而不是特定頻率點，則此法可行。（2）如果要求特定頻率點的頻譜，則N不能改變。快速傅里葉變換的基本思想就是要將DFT的運算盡量分小。 本章小結(jié)在學習離散傅里葉變換的基礎(chǔ)上，研究快速傅里葉變換的原理，掌握了快速傅里葉變換的幾種算法，并深入學習了以基2FFT算法為主結(jié)合混合基的算法，為下面的程序編寫和研究奠定了基礎(chǔ)。可以繪出編程用的程序框圖[4]如圖31所示：程序說明：：①序列倒序程序；②第一級蝶形運算；③第二級蝶形運算；④第三級至第級的蝶形運算；⑤求功率譜及輸出程序。為了追求代碼的高效性,以前大都用匯編語言來編DSP的應用軟件。C語言以其獨特的可讀性、可修改性和可重用性，使DSP的運算速度大幅提高。鑒于DSP應用復雜性，用C語言進行軟件開發(fā)時，一般先在PC上對算法進行仿真，然后將程序移植到DSP平臺中。整個程序的編寫過程[5]如下：（1）首先定義一個復數(shù)結(jié)構(gòu)。（2）定義一個輸入數(shù)據(jù)序列。（3）定義兩個復數(shù)相乘。=**。Return(b3)。{....nv2=N/2。i=nm1。xin[j]=xin[i]。}k=nv2。K=k/2。}（5）定義FFT變換的函數(shù)。l=m。Lei=le/2。=。=cos(pi/lei)。For(j=1。j++){for(i=j。i=i+le){ip=i+lei。Xin[ip].real=xin[i].real=。Xin[i].real=xin[i].real+。}V=EE()。許多工具都是TI的實時ExpressDSP?軟件和開發(fā)工具策略的一部分，這對設(shè)計過程中快速起步及節(jié)省寶貴時間非常有幫助。Code Composer Studio IDE是強大的DSP集成開發(fā)工具，利用CCS開發(fā)環(huán)境可以實現(xiàn)對設(shè)計的軟件仿真。在進入CCS開發(fā)環(huán)境前，必須選擇一個合適的配置環(huán)境。使用標準配置文件產(chǎn)生一個系統(tǒng)配置： （1）雙擊桌面上的Setup Code Composer Sutdio圖標，出現(xiàn)系統(tǒng)配置配置對話框。確定可用配置中是否存在與系統(tǒng)匹配的配置，如圖32所示圖32 CCS配置環(huán)境圖（3）單擊選擇的配置，然后單擊ADD按鈕將選擇的配置添加到system configuration中。如果你的配置包含多于一個的目標板，重復以上步驟直到你為每一個目標板選擇了一個配置。 Quit按鈕保存配置。現(xiàn)在可以打開一個工程。按照以下步驟創(chuàng)建一個新工程：（1）如果CCS安裝在C:\，在C:\\myprogects文件下新建一個practice文件夾。目標與當前CCS的配置有關(guān)。（3）選擇ProjectNew。（5）在Location框里輸入或者瀏覽第一步創(chuàng)建的文件夾。（7）點擊Finish。（8）選擇ProjectAdd files to Project，把文件加到工程里。（9），(映射內(nèi)存的連接命令文件)。（10）不必手工添加包含文件到工程里，因為編譯程序的時候，程序會自動找到它們。創(chuàng)建工程后，打開C語言程序，顯示沒有錯誤后構(gòu)建程序。當構(gòu)建完成后，輸出窗口將會顯示Build plete 0 errors，0 warnings。程序成功構(gòu)建后，執(zhí)行FileLoad Program加載程序。默認情況下，CCS集成開發(fā)環(huán)境將會在你的工程路徑下創(chuàng)建一個Debug子目錄。加載完成后，完成一些基本調(diào)試以便在實踐中體會CCS的功能強大的調(diào)試器（debugger）。執(zhí)行到Main函數(shù)出暫停，此時程序指針（黃色箭頭）停在Main函數(shù)的左邊空白處?？梢栽谶@個區(qū)域設(shè)置斷點（break point），探針(probe)等。此外，你還可以通過選擇Toggle Breakpoint工具條按鈕創(chuàng)建斷點。再按F9或Toggle Breakpoint按鈕將除去斷點。一旦程序運行到斷點出，程序?qū)炱稹．敵绦蛟跀帱c處掛起后，便可以單步執(zhí)行程序。多次單步執(zhí)行觀察執(zhí)行結(jié)果。同樣也可以使用匯編單步。在調(diào)試過程中，你應該查看變量的值以確保程序正常的執(zhí)行。通過選擇ViewWatch Window可以打開watch窗口。當你連續(xù)單步執(zhí)行整個循環(huán)時，變量的值會隨之改變。 CCS軟件仿真CCS IDE可以通過各種方法把程序處理到的數(shù)據(jù)畫出來，包括時間/頻率，星座圖，眼圖和圖像。這時候可以在圖屬性（graph property）的對話框中指定圖的屬性選項。圖33 視圖屬性對話框一旦屬性被設(shè)定了，選擇OK按鈕，開啟圖窗口，就會畫出指定的數(shù)據(jù)點。Display type分別是single time和FFT magnitude。三個仿真的start address分別為INPUT、DATA和INPUT。display data size、acquisitio