快速傅里葉變換程序設(shè)計1中文摘要數(shù)字信號處理(DigitalSignalProcessing，DSP)是一門應(yīng)用十分廣泛的學(xué)科。數(shù)字信號處理是指利用計算機技術(shù)，以數(shù)字形式對信號進行采樣、變換、濾波、估值、增強、壓縮、識別等處理，以得到人們需要的信號形式。數(shù)字信號處理器也稱DSP芯片，是一種用于進行數(shù)字信號處理運算的微處理器，其突出特點是采用多組總線技術(shù)實現(xiàn)并行機制，有獨立的家發(fā)起和乘法器，靈活的尋址方式，實時快速地實現(xiàn)各種數(shù)字信號處理算法及各種復(fù)雜運算。傅里葉變換是一種將時域信號變換為頻域信號的變換形式。在頻域分析中，信號的頻率及對應(yīng)的幅值、相位（統(tǒng)稱為頻譜）反映了系統(tǒng)的性能?？焖俑道锶~變換(FastFourierTransform)是實現(xiàn)離散傅里葉變換(DFT)的一種快速高效的運算方法，是數(shù)字信號處理中最為重要的算法之一。FFT算法的關(guān)鍵在于利用了蝶形因子的內(nèi)在對稱性和周期性，從而加快了運算的速度，使運算時間縮短1至2個數(shù)量級。此次快速傅里葉變換的DSP程序設(shè)計，根據(jù)書上提供的C編程序在相對應(yīng)的DSP工作環(huán)境下進行調(diào)試、圖形分析、輸入比較，來加深對程序的理解以及對所學(xué)內(nèi)容的融合和鞏固。程序設(shè)計所選擇的頭文件為，完成的是采樣次數(shù)N為128的FFT運算。為了更好的觀察到快速傅里葉運算的結(jié)果，還另外設(shè)計了一組為方波的輸入，從而得到設(shè)計要求的FFT運算結(jié)果圖形。關(guān)鍵詞：數(shù)字信號處理，DSP芯片，快速傅里葉變換FFT，C語言程序快速傅里葉變換程序設(shè)計21設(shè)計任務(wù)描述1.1設(shè)計題目：快速傅里葉變換程序設(shè)計1.2設(shè)計要求1.2.1設(shè)計目的1）理解FFT的算法以及利用DSP實現(xiàn)的方法。2）能熟練的調(diào)試程序并能觀察其結(jié)果。3）熟悉TMS320C54x系列DSP芯片的軟件設(shè)計方法。1.3基本要求1）研究FFT原理以及利用DSP實現(xiàn)的方法。2）編寫FFT程序。3）調(diào)試程序，觀察結(jié)果?？焖俑道锶~變換程序設(shè)計32設(shè)計思路根據(jù)此次課程設(shè)計的要求，采用的是C語言程序。本次快速傅里葉變換程序設(shè)計主要包括三大部分：初始化定義部分，主函數(shù)部分，子程序部分。其中調(diào)用的子程序由四個功能函數(shù)組成：FFT初始化函數(shù)、計算功率譜函數(shù)、波形發(fā)生函數(shù)、倒序運算函數(shù)。這四個調(diào)用函數(shù)在主函數(shù)運行到相應(yīng)位置時進入操作中，實現(xiàn)一個完整的快速傅里葉變換。由于在程序代碼中調(diào)用了pow、log、cos、sin函數(shù)，該函數(shù)所在的C文件應(yīng)包含頭文件math.h。初始化定義部分主要是對程序需要用到的函數(shù)或者數(shù)據(jù)進行定義，這就需要我們熟悉前面知識所學(xué)到的各種基本數(shù)據(jù)類型的格式，如數(shù)組、結(jié)構(gòu)、聯(lián)合等構(gòu)造類型數(shù)據(jù)。主函數(shù)部分就需要對FFT變換的整體過程有熟悉的了解，這樣才能夠知道應(yīng)該調(diào)用的子程序的順序。因為一旦程序開始運行，除了一開始的初始化階段，直接進入的就是主函數(shù)部分。函數(shù)調(diào)用部分是整個程序的重點部分，在這里實現(xiàn)了波形的輸入、FFT變換，可以通過CCS軟件調(diào)試該程序，并用其中ViewGraphTime/Frequency菜單功能，顯示變量INPUT與DATA圖形，觀察FFT的效果。在此次的程序設(shè)計中，我設(shè)計了正弦波和方波兩種輸入情況。對于不同的輸入，經(jīng)過FFT變換之后就會得到不同的頻譜圖，在整個程序中，F(xiàn)FT的變換過程是最大的難點，完成這部分需要對數(shù)字信號處理課程中的快速傅里葉變換的知識有很大程度的掌握，這樣才能知道函數(shù)中倒序產(chǎn)生的原理與方法，并且對蝶形圖中的運算也能相當了解，這樣才能理清思路，利用C語言的字符語句達到倒序處理的目的?？焖俑道锶~變換程序設(shè)計43設(shè)計方框圖設(shè)計方框圖顯現(xiàn)的是在設(shè)計時主要實現(xiàn)的功能和流程，簡單易懂，能清晰的體現(xiàn)整個設(shè)計的思路。圖3-1主程序流程結(jié)束程序初始化開始運行main()主函數(shù)調(diào)用InitForFFT初始化函數(shù)調(diào)用波形發(fā)生函數(shù)跳轉(zhuǎn)到FFT程序在128個采樣值內(nèi)否輸入波形是否在取點值范圍內(nèi)頻譜值輸出快速傅里葉變換程序設(shè)計54快速傅里葉變換的的算法實現(xiàn)4.1變換原理若給定由N個信號樣本x（0），x（1），x（N-1）組成的信號序列x（n），DFT可用式2-1給出：10()()NnkNnXkxnWk=0,1，N-1（2-1）式2-1中，nkNW稱為旋轉(zhuǎn)因子或蝶形因子，nkNW=2/jnkNe。從中可以看出：當信號樣本為復(fù)數(shù)時，計算單個()Xk需經(jīng)過N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法運算，相當于4N次實數(shù)乘法和2（2N-1）次實數(shù)加法。完成全部N點DFT共需2N次復(fù)數(shù)乘法和N（N-1）復(fù)數(shù)加法運算。可見，隨著N不斷增加，整個DFT運算量是相當龐大的，而FFT算法通過對計算過程的深入分析，利用旋轉(zhuǎn)因子nkNW具有的周期性與對稱性，實現(xiàn)了降低運算復(fù)雜度的目的。當序列長度N為偶數(shù)時，信號序列x（n）可被分解為奇、偶兩個子序列，相應(yīng)的N點DFT被分解為兩個N/2點的DFT：()()()kNXkGkWHkk=0,1,，N/2-1（2-2）(/2)()()kNXNkGkWHkk=0,1,，N/2-1（2-3）式（2-2）和（2-3）中，G(k)和()Hk分別表示x（n）分解后得到的N/2點偶序列點奇序列的DFT。式（2-2）和式（2-3）表明，只要求出G(k)和()Hk，x（n）前N/2點和后N/2點的DFT就得到了，整個序列的DFT也就得到了。這樣做的好處是計算N點DFT只需要約2N/2次復(fù)數(shù)乘法，總運算量約為直接DFT運算量的一半。同理，當N/2為偶數(shù)時，每個N/2點的DFT又可被分解成兩個N/4點的DFT，進一步減少了DFT運算的復(fù)雜度。依次類推，直到不能繼續(xù)分解為止。分解結(jié)束時，最小DFT的點數(shù)稱為稱為基數(shù)，當N=2L（L為正整數(shù)）時，經(jīng)過L-1次分解，N點DFT最終可被分解為N/2個兩點的DFT，即得到基數(shù)為2的FFT運算，使得DFT所需復(fù)數(shù)乘法次數(shù)降至2(/2)logNN?？焖俑道锶~變換程序設(shè)計64.2蝶形運算基于2FFT的蝶形運算流圖如下圖4-1所示，圖中以N=8為例。圖4-1蝶形運算采用的是原位運算原理和倒位序規(guī)律，其中原位運算指的是某一列的N個數(shù)據(jù)送到存儲器后，經(jīng)蝶形運算，其結(jié)果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲在這同一組存儲器中，直到最后輸出，中間無需其他存儲器。也就是蝶形的兩個輸出值仍放回蝶形的兩個輸入所在的存儲器中。每列的N/2個蝶形運算全部完成后，再開始下一列的蝶形運算。而倒位序規(guī)律則是根據(jù)二進制的自然順序和倒序得來的，其變換規(guī)律如圖4-2。自然順序（I）二進制數(shù)倒位序二進制數(shù)倒位序（J）0123456700000101001110010111011100010001011000110101111104261537圖4-2x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X(7)10NW0NW2NW110NW1NW2NW3NW1111快速傅里葉變換程序設(shè)計75各部分程序設(shè)計5.1初始化程序#includemath.h/數(shù)學(xué)函數(shù)頭文件#definePI3.1415926#defineN128/采樣次數(shù)NvoidInitForFFT()；/FFT初始化函數(shù)voidMakeWave()；/波形發(fā)生函數(shù)voidfinv(intN1,float*xr,float*xi)；/倒序運算函數(shù)，對輸入序倒序intINPUTN,DATAN；floatfWaveRN,fWaveIN,wN；floatsin_tabN,cos_tabN；/正余弦函數(shù)表intMum；/蝶形運算的級數(shù)這一段初始化程序是對需要用到數(shù)據(jù)和子程序段進行定義，其中包含了采樣的次數(shù)、蝶形運算的級數(shù)，倒序運算正余弦函數(shù)表。5.2FFT的蝶形運算在進行蝶形變換的時候，其中還引入了倒序運算函數(shù)，即運算完之后的FFT的輸出X(k)按正常順序排列在存儲單元中，即按X(0)，X(1)，X(7)的順序排列，但是這時輸入x(n)卻不是按自然順序存儲的，而是按x(0)，x(4)，x(7)的順序存入存儲單元，看起來好像是“混亂無序”的，實際上是根據(jù)倒序原理：倒序數(shù)的加1是在最高位加1，滿2向次高位進1，最高位變0，依次往下，從當前的倒序值求出下一