【導(dǎo)讀】采用高級(jí)C語(yǔ)言實(shí)現(xiàn)FFT算法。利用DSP芯片特有的哈佛結(jié)構(gòu)和專門的FFT指令。從而促進(jìn)DSP芯片的發(fā)展，同時(shí)加快基于DSP數(shù)字信號(hào)處理的速度。通過對(duì)FFT的算法進(jìn)行研究，從基礎(chǔ)深入研究和學(xué)習(xí)，掌握FFT算法的關(guān)鍵。研究DSP芯片如何加快蝶形計(jì)算以及如何有效地碼位倒置的輸出顛倒過來(lái)。熟悉旋轉(zhuǎn)因子的生成。通過對(duì)DSP開發(fā)環(huán)境的學(xué)習(xí)，掌握CCS的簡(jiǎn)單調(diào)試和軟件仿真。比較仿真圖，驗(yàn)證設(shè)計(jì)和程序的正確性。表明利用DSP控制器特有的反序間接尋址使FFT的實(shí)現(xiàn)更加方便。它不僅適用于數(shù)字信號(hào)處理，而且在圖像處理、語(yǔ)音處理、通信等領(lǐng)域得到廣泛的應(yīng)用。由于多數(shù)的DSP芯片都能在一個(gè)指令周期內(nèi)完成一次乘法和加法，而且提供了專門的FFT指令。FFT技術(shù)應(yīng)用DSP芯片，從而可以提供使調(diào)制、解調(diào)、壓縮、解壓縮和數(shù)據(jù)傳輸更為高效的信號(hào)處理解決方案，因而廣泛應(yīng)用于雷達(dá)、通信、圖像處理、聲納和生物醫(yī)學(xué)領(lǐng)域。本文主要介紹基于DSP的快速傅里葉變換的算法的實(shí)現(xiàn)。

　　

【正文】 的乘法，結(jié)果為32位。乘法器由三部分組成，分別是乘法器陣列、PREG（乘積寄存器）、TREG0（臨時(shí)寄存器）。16位的TREG0存儲(chǔ)乘數(shù)，PREG保存32位的乘積結(jié)果。乘法器中的數(shù)值來(lái)自數(shù)據(jù)存儲(chǔ)器，當(dāng)使用MAC/MACD/MADS/MADD指令時(shí)來(lái)自程序存儲(chǔ)器，或者來(lái)自乘立即數(shù)指令（MPY ）。片內(nèi)快速乘法器對(duì)執(zhí)行諸如卷積、相關(guān)和濾波等基本的DSP操作十分有效。TMS320C5416的定標(biāo)移位器有一個(gè)16位的輸入來(lái)自數(shù)據(jù)總線，32位的輸出連接到ALU。定標(biāo)移位器依照指令的編程使輸入數(shù)據(jù)產(chǎn)生0到16位的左移。移位量取決于指令或移位計(jì)數(shù)寄存器（TREG1）中的定義值。輸出的最低有效位（LSB）補(bǔ)零，最高有效位補(bǔ)0或符號(hào)擴(kuò)展（取決于狀態(tài)寄存器ST1的符號(hào)擴(kuò)展模式位SXM）。附加的移位能力使處理器能執(zhí)行數(shù)值定標(biāo)、二進(jìn)制位提取、符號(hào)擴(kuò)展運(yùn)算和溢出防止等功能。8級(jí)硬件堆棧用于在中斷及子程序調(diào)用時(shí)保存程序計(jì)數(shù)器的內(nèi)容。中斷發(fā)生時(shí)，重要寄存器（ACC、ACCB、ARCR、INDX、PMST、PREG、ST0、ST1和TREG）壓入堆棧，中斷返回時(shí)彈出，實(shí)現(xiàn)了無(wú)開銷的中斷文本切換。 FFT算法在DSP上的實(shí)現(xiàn)DIT—FFT的運(yùn)算規(guī)律及編程思想[13](1) 旋轉(zhuǎn)因子的生成在FFT運(yùn)算中，旋轉(zhuǎn)因子，正弦和余弦函數(shù)的計(jì)算量很大，所以編程時(shí)，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運(yùn)算速度。一種方法是在每級(jí)運(yùn)算中直接生成，另一種方法是在FFT程序開始前預(yù)先計(jì)算出旋轉(zhuǎn)因子，存放在數(shù)組中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過程中，直接查表得到所需的旋轉(zhuǎn)因子值，這樣使運(yùn)算速度大大提高，其不足之處是占用內(nèi)存較多。權(quán)衡比較后，采用第二種方法。(2) 序列的倒序DIT—FFT算法的輸入序列的排序看起來(lái)似乎很亂，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的，由于，所以順序數(shù)可以用二進(jìn)制數(shù)表示，M次奇偶時(shí)域抽選過程中倒序規(guī)律，第1次按最低位的0和1將x(n)按奇偶分解為兩組，第2次又按次低位的0和1分別在分組，以此類推，第M次按位分解，最后所得二進(jìn)制倒序數(shù)圖41所示。可以看出，只要將二進(jìn)制數(shù)倒序則得到對(duì)應(yīng)的倒序值，按這一規(guī)律，用硬件電路和匯編語(yǔ)言程序產(chǎn)生倒序數(shù)很容易。1000010001011000110101111104261537010011010101圖41 倒序規(guī)律（3） 蝶形運(yùn)算規(guī)律設(shè)序列經(jīng)時(shí)域抽選(倒序)后存人數(shù)組中，如果蝶形運(yùn)算的兩個(gè)輸人數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算見式（41）。 （41）式中下標(biāo)L表示第L級(jí)的運(yùn)算，則表示第L級(jí)運(yùn)算后數(shù)組元素的值。 本章小結(jié)本章首先介紹了DSP的概況，接著從DSP的硬件結(jié)構(gòu)和芯片特點(diǎn)上進(jìn)行闡述，針對(duì)設(shè)計(jì)題目對(duì)芯片TMS320C5416進(jìn)行了學(xué)習(xí)。通過快速傅里葉變換算法的學(xué)習(xí)，在DSP上明確了FFT算法的實(shí)現(xiàn)方法。東北石油大學(xué)本科生畢業(yè)設(shè)計(jì)（論文）結(jié) 論本論文學(xué)習(xí)和研究了按時(shí)間抽取的基2FFT算法。通過查找資料了解DSP芯片TMS320C5416的結(jié)構(gòu)、功能和特點(diǎn)，掌握了DSP芯片的原理。明確FFT在DSP實(shí)現(xiàn)的關(guān)鍵，研究了DSP芯片如何加快蝶形計(jì)算以及如何有效地把碼位倒置的輸出顛倒過來(lái)。掌握了旋轉(zhuǎn)因子的生成和序列的倒序。熟練的運(yùn)行CCS開發(fā)環(huán)境，用C語(yǔ)言編寫了程序，并利用CCS開發(fā)環(huán)境仿真，比較仿真圖驗(yàn)證程序的正確性。通過這次畢業(yè)設(shè)計(jì)加深了理論知識(shí)的學(xué)習(xí)和動(dòng)手實(shí)踐能力的鍛煉。獨(dú)立自主的完成設(shè)計(jì)是對(duì)自己能力的鍛煉和肯定。本設(shè)計(jì)驗(yàn)證了利用DSP能夠有效快速的實(shí)現(xiàn)快速傅里葉變換，從而加快數(shù)字信號(hào)處理的速度。在數(shù)字信號(hào)處理的實(shí)際應(yīng)用中做出決定性的突破。東北石油大學(xué)本科生畢業(yè)設(shè)計(jì)（論文）參考文獻(xiàn)[1] 陳鵬,[J].,28(2):146151.[2] 呂武,申萍,[J].(3):7477.[3] 王軍寧,[M].北京：高等教育出版社,.[4] 趙桂芳,劉興云,[J].,23(5):2730.[5] 汪安民,[M].北京人民郵電出版社,.[6] 劉艷萍,[M].北京：北京航空航天大學(xué)出版社,.[7] 何羚,張欣,[J].,35(2):145150.[8] Ahnoff M. ExtendedPrecision Complex Radix2 FFT/IFFT Implemented on TMS320C54. Literature Number: SPRA696A. Copyright@2001. Texas Instruments Application Report[Z]. 2001.[9] Texas Instruments. TMS320C54 DSP Library Programmer’s Reference. Literature Number: SPRU402A. Copyright@2002. Texas Instruments Incorporated[Z]. 2002.[10] 李楓,[M].北京：國(guó)防工業(yè)出版社,.[11] [M].北京：國(guó)防工業(yè)出版社,.[12] BanerjeeAyan, Sundar, Anindya. FPGA Realization of a CORDICbased FFT processor for Bomedical signal processing[J]. Microprocessors and Microsystems, 2001.[13] 萬(wàn)佑紅,[J].,29:8489.東北石油大學(xué)本科生畢業(yè)設(shè)計(jì)（論文）致 謝畢業(yè)設(shè)計(jì)轉(zhuǎn)眼間就要接近尾聲了，經(jīng)過這三個(gè)多月的畢業(yè)設(shè)計(jì)。很大程度的提高了自己的動(dòng)手實(shí)踐能力，并使我對(duì)專業(yè)理論有了深一步的了解和學(xué)習(xí)。在有理論知識(shí)的基礎(chǔ)后，把理論和實(shí)踐相結(jié)合。通過這整個(gè)的設(shè)計(jì)過程，我學(xué)會(huì)了設(shè)計(jì)一個(gè)項(xiàng)目要進(jìn)行方案論證、芯片的選擇等，尤其是牟海維老師嚴(yán)謹(jǐn)?shù)慕虒W(xué)態(tài)度使我受益匪淺。這些都對(duì)我今后的工作和學(xué)習(xí)有很大的幫助。在此，要特別感謝在實(shí)驗(yàn)室和我一起進(jìn)步的同學(xué)們，是你們的行動(dòng)給了我鼓勵(lì)和支持。最后，再次感謝指導(dǎo)老師給我的指導(dǎo)。這次設(shè)計(jì)是我一次寶貴的人生經(jīng)歷，是人生歷程中一次寶貴的財(cái)富。附錄include define PI define SAMPLENUMBER 128void InitForFFT()。void MakeWave()。int INPUT[SAMPLENUMBER],DATA[SAMPLENUMBER]。float fWaveR[SAMPLENUMBER],fWaveI[SAMPLENUMBER],w[SAMPLENUMBER]。float sin_tab[SAMPLENUMBER],cos_tab[SAMPLENUMBER]。void FFT(float dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER])。main(){ int i。 InitForFFT()。 MakeWave()。 for ( i=0。iSAMPLENUMBER。i++ ) { fWaveR[i]=INPUT[i]。 fWaveI[i]=。 w[i]=。 } FFT(fWaveR,fWaveI)。 for ( i=0。iSAMPLENUMBER。i++ ) { DATA[i]=w[i]。 } while ( 1 )。 // break point}void FFT(float dataR[SAMPLENUMBER],float dataI[SAMPLENUMBER]){ int x0,x1,x2,x3,x4,x5,x6,xx。 int i,j,k,b,p,L。 float TR,TI,temp。 /********** following code invert sequence ************/ for ( i=0。iSAMPLENUMBER。i++ ) { x0=x1=x2=x3=x4=x5=x6=0。 x0=iamp。0x01。 x1=(i/2)amp。0x01。 x2=(i/4)amp。0x01。 x3=(i/8)amp。0x01。x4=(i/16)amp。0x01。 x5=(i/32)amp。0x01。 x6=(i/64)amp。0x01。 xx=x0*64+x1*32+x2*16+x3*8+x4*4+x5*2+x6。 dataI[xx]=dataR[i]。 } for ( i=0。iSAMPLENUMBER。i++ ) { dataR[i]=dataI[i]。 dataI[i]=0。 } /************** following code FFT *******************/ for ( L=1。L=7。L++ ) { /* for(1) */ b=1。 i=L1。 while ( i0 ) { b=b*2。 i。 } /* b= 2^(L1) */ for ( j=0。j=b1。j++ ) /* for (2) */ { p=1。 i=7L。 while ( i0 ) /* p=pow(2,7L)*j。 */ { p=p*2。 i。 } p=p*j。 for ( k=j。k128。k=k+2*b ) /* for (3) */ { TR=dataR[k]。 TI=dataI[k]。 temp=dataR[k+b]。 dataR[k]=dataR[k]+dataR[k+b]*cos_tab[p]+dataI[k+b]*sin_tab[p]。 dataI[k]=dataI[k]dataR[k+b]*sin_tab[p]+dataI[k+b]*cos_tab[p]。 dataR[k+b]=TRdataR[k+b]*cos_tab[p]dataI[k+b]*sin_tab[p]。 dataI[k+b]=TI+temp*sin_tab[p]dataI[k+b]*cos_tab[p]。 } /* END for (3) */ } /* END for (2) */ } /* END for (1) */ for ( i=0。iSAMPLENUMBER/2。i++ ) { w[i]=sqrt(dataR[i]*dataR[i]+dataI[i]*dataI[i])。 }} /* END FFT */void InitForFFT(){ int i。 for ( i=0。iSAMPLENUMBER。i++ ) { sin_tab[i]=sin(PI*2*i/SAMPLENUMBER)。 cos_tab[i]=cos(PI*2*i/SAMPLENUMBER)。 }}void MakeWave(){ int i。 for ( i=0。iSAMPLENUMBER。i++ ) { INPUT[i]=sin(PI*2*i/SAMPLENUMBER*3)*1024。 }}40