數(shù)字信號處理課程設計FFT快速傅里葉變換程序設計

1、中文摘要數(shù)字信號處理 (digital signal processing，dsp)是一門應用十分廣泛的學科。數(shù)字信號處理是指利用計算機技術，以數(shù)字形式對信號進行采樣、變換、濾波、估值、增強、壓縮、識別等處理，以得到人們需要的信號形式。數(shù)字信號處理器也稱dsp芯片，是一種用于進行數(shù)字信號處理運算的微處理器，其突出特點是采用多組總線技術實現(xiàn)并行機制，有獨立的家發(fā)起和乘法器，靈活的尋址方式，實時快速地實現(xiàn)各種數(shù)字信號處理算法及各種復雜運算。傅里葉變換是一種將時域信號變換為頻域信號的變換形式。在頻域分析中，信號的頻率及對應的幅值、相位（統(tǒng)稱為頻譜）反映了系統(tǒng)的性能。快速傅里葉變換(fast four

2、ier transform)是實現(xiàn)離散傅里葉變換(dft)的一種快速高效的運算方法，是數(shù)字信號處理中最為重要的算法之一。fft算法的關鍵在于利用了蝶形因子的內(nèi)在對稱性和周期性，從而加快了運算的速度，使運算時間縮短1至2個數(shù)量級。此次快速傅里葉變換的dsp程序設計，根據(jù)書上提供的c編程序在相對應的dsp工作環(huán)境下進行調(diào)試、圖形分析、輸入比較，來加深對程序的理解以及對所學內(nèi)容的融合和鞏固。程序設計所選擇的頭文件為，完成的是采樣次數(shù)n為128的fft運算。為了更好的觀察到快速傅里葉運算的結果，還另外設計了一組為方波的輸入，從而得到設計要求的fft運算結果圖形。關鍵詞： 數(shù)字信號處理，dsp芯片，快速

3、傅里葉變換fft，c語言程序1 設計任務描述1.1 設計題目：快速傅里葉變換程序設計1.2 設計要求1.2.1 設計目的1）理解fft的算法以及利用dsp實現(xiàn)的方法。2）能熟練的調(diào)試程序并能觀察其結果。3）熟悉tms320c54x系列dsp芯片的軟件設計方法。1.3 基本要求 1）研究fft原理以及利用dsp實現(xiàn)的方法。2）編寫fft程序。3）調(diào)試程序，觀察結果。2 設計思路根據(jù)此次課程設計的要求，采用的是c語言程序。本次快速傅里葉變換程序設計主要包括三大部分：初始化定義部分，主函數(shù)部分，子程序部分。其中調(diào)用的子程序由四個功能函數(shù)組成：fft初始化函數(shù)、計算功率譜函數(shù)、波形發(fā)生函數(shù)、倒序運算函

4、數(shù)。這四個調(diào)用函數(shù)在主函數(shù)運行到相應位置時進入操作中，實現(xiàn)一個完整的快速傅里葉變換。由于在程序代碼中調(diào)用了pow、log、cos、sin函數(shù)，該函數(shù)所在的c文件應包含頭文件math.h。初始化定義部分主要是對程序需要用到的函數(shù)或者數(shù)據(jù)進行定義，這就需要我們熟悉前面知識所學到的各種基本數(shù)據(jù)類型的格式，如數(shù)組、結構、聯(lián)合等構造類型數(shù)據(jù)。主函數(shù)部分就需要對fft變換的整體過程有熟悉的了解，這樣才能夠知道應該調(diào)用的子程序的順序。因為一旦程序開始運行，除了一開始的初始化階段，直接進入的就是主函數(shù)部分。函數(shù)調(diào)用部分是整個程序的重點部分，在這里實現(xiàn)了波形的輸入、fft變換，可以通過ccs軟件調(diào)試該程序，并用

5、其中viewgraphtime/frequency菜單功能，顯示變量input與data圖形，觀察fft的效果。在此次的程序設計中，我設計了正弦波和方波兩種輸入情況。對于不同的輸入，經(jīng)過fft變換之后就會得到不同的頻譜圖，在整個程序中，fft的變換過程是最大的難點，完成這部分需要對數(shù)字信號處理課程中的快速傅里葉變換的知識有很大程度的掌握，這樣才能知道函數(shù)中倒序產(chǎn)生的原理與方法，并且對蝶形圖中的運算也能相當了解，這樣才能理清思路，利用c語言的字符語句達到倒序處理的目的。3設計方框圖設計方框圖顯現(xiàn)的是在設計時主要實現(xiàn)的功能和流程，簡單易懂，能清晰的體現(xiàn)整個設計的思路。結束程序初始化開始運行main

6、()主函數(shù)調(diào)用initforfft初始化函數(shù)調(diào)用波形發(fā)生函數(shù)跳轉到fft程序在128個采樣值內(nèi)否輸入波形是否在取點值范圍內(nèi)頻譜值輸出圖 3-1 主程序流程 4 快速傅里葉變換的的算法實現(xiàn)4.1變換原理 若給定由個信號樣本（0），（1），（-1）組成的信號序列（），dft可用式2-1給出： =0,1，-1 （2-1）式2-1中，稱為旋轉因子或蝶形因子，=。從中可以看出：當信號樣本為復數(shù)時，計算單個需經(jīng)過次復數(shù)乘法和-1次復數(shù)加法運算，相當于4次實數(shù)乘法和2（2-1）次實數(shù)加法。完成全部點dft共需次復數(shù)乘法和（-1）復數(shù)加法運算?？梢?，隨著不斷增加，整個dft運算量是相當龐大的，而fft算法通過

7、對計算過程的深入分析，利用旋轉因子具有的周期性與對稱性，實現(xiàn)了降低運算復雜度的目的。當序列長度為偶數(shù)時，信號序列（）可被分解為奇、偶兩個子序列，相應的點dft被分解為兩個/2點的dft： =0,1, ，/2-1 （2-2） =0,1, ，/2-1 （2-3）式（2-2）和（2-3）中，和分別表示（）分解后得到的/2點偶序列點奇序列的dft。式（2-2）和式（2-3）表明，只要求出和，（）前/2點和后/2點的dft就得到了，整個序列的dft也就得到了。這樣做的好處是計算點dft只需要約/2次復數(shù)乘法，總運算量約為直接dft運算量的一半。同理，當/2為偶數(shù)時，每個/2點的dft又可被分解成兩個/4

8、點的dft，進一步減少了dft運算的復雜度。依次類推，直到不能繼續(xù)分解為止。分解結束時，最小dft的點數(shù)稱為稱為基數(shù)，當=（為正整數(shù)）時，經(jīng)過-1次分解，點dft最終可被分解為/2個兩點的dft，即得到基數(shù)為2的fft運算，使得dft所需復數(shù)乘法次數(shù)降至。4.2蝶形運算 基于2fft的蝶形運算流圖如下圖4-1所示，圖中以n=8為例。圖4-1 蝶形運算采用的是原位運算原理和倒位序規(guī)律，其中原位運算指的是某一列的n個數(shù)據(jù)送到存儲器后，經(jīng)蝶形運算，其結果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲在這同一組存儲器中，直到最后輸出，中間無需其他存儲器。也就是蝶形的兩個輸出值仍放回蝶形的兩個輸入所在的存儲器中。

9、 每列的n/2 個蝶形運算全部完成后， 再開始下一列的蝶形運算。而倒位序規(guī)律則是根據(jù)二進制的自然順序和倒序得來的，其變換規(guī)律如圖4-2。 自然順序（i） 二進制數(shù) 倒位序二進制數(shù) 倒位序（j） 0123456700000101001110010111011100010001011000110101111104261537 圖4-25 各部分程序設計5.1初始化程序 #includemath.h /數(shù)學函數(shù)頭文件#define pi 3.1415926#define n 128 /采樣次數(shù)n void initforfft(); /fft初始化函數(shù)void makewave(); /波形發(fā)生函數(shù)

10、void finv(int n1,float *xr,float *xi); /倒序運算函數(shù)，對輸入序倒序int inputn,datan; float fwavern,fwavein,wn;float sin_tabn,cos_tabn; /正余弦函數(shù)表 int mum; /蝶形運算的級數(shù)這一段初始化程序是對需要用到數(shù)據(jù)和子程序段進行定義，其中包含了采樣的次數(shù)、蝶形運算的級數(shù)，倒序運算正余弦函數(shù)表。5.2 fft的蝶形運算 在進行蝶形變換的時候，其中還引入了倒序運算函數(shù)，即運算完之后的fft的輸出x(k)按正常順序排列在存儲單元中，即按x(0)，x(1)，x(7)的順序排列，但是這時輸入x(

11、n)卻不是按自然順序存儲的，而是按x(0)，x(4)， ， x(7)的順序存入存儲單元，看起來好像是“混亂無序”的，實際上是根據(jù)倒序原理：倒序數(shù)的加1是在最高位加1，滿2向次高位進1，最高位變0，依次往下，從當前的倒序值求出下一個倒序值。其蝶形變換的主要程序如下： for(k=j;k=n-1;k+=(int)(pow(2,m)+0.5) x=xrk+b*cos_tabs+xik+b*sin_tabs; y=xik+b*cos_tabs-xrk+b*sin_tabs; xrk+b=xrk -x; /運算結果的實部和虛部分別存儲在原 xik+b=xik-y; /實部和虛部的位置 xrk=xrk+x

12、; xik=xik+y; 蝶形運算展開采用的是原位運算，即某一列的n個數(shù)據(jù)送到存儲器后，經(jīng)蝶形運算，其結果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲在這同一組存儲器中，直到最后輸出，中間無需其他存儲器。也就是蝶形的兩個輸出值仍放回蝶形的兩個輸入所在的存儲器中。 每列的n/2 個蝶形運算全部完成后， 再開始下一列的蝶形運算。 這樣存儲器數(shù)據(jù)只需n個存儲單元。 下一級的運算仍采用這種原位方式，只不過進入蝶形結的組合關系有所不同。 5.3 旋轉因子 旋轉因子是復數(shù)，可表示為： （4-1） 由式（4-1）可以看出旋轉因子的實部為余弦函數(shù)，虛部為正弦函數(shù)。為了獲得fft運算中需要的全部旋轉因子，需要分別存儲正

13、弦表和余弦表，且每個表長度為，對應于0180，同時，采用循環(huán)尋址方式對正弦表和余弦表進行尋址。5.4 實現(xiàn)n點的fft變換實現(xiàn)n點的fft變換需要知道采樣的次數(shù)n值，且n為2的整數(shù)冪次方；同時還需要旋轉因子的冪數(shù)，蝶形運算輸入數(shù)據(jù)的距離，即各級旋轉因子的個數(shù)；然后再進行蝶形運算，展開結果的實部和虛部分別存儲在原實部和虛部位置。fft變換的程序如下： void fft(float xrn,float xin)int s,b;int m,j,k;float x,y;finv(n,xr,xi);for(m=1;m=mum;m+) b=(int)(pow(2,m-1)+0.5); for(j=0;jb

14、;j+) s=j*(int)(pow(2,mum-m)+0.5); for(k=j;k=n-1;k+=(int)(pow(2,m)+0.5) x=xrk+b*cos_tabs+xik+b*sin_tabs; y=xik+b*cos_tabs-xrk+b*sin_tabs; xrk+b=xrk-x; xik+b=xik-y; xrk=xrk+x; xik=xik+y; for(m=0;m=n/2;m+) wm=sqrt(xrm*xrm+xim*xim); /功率譜計算在fft變換的后，經(jīng)過功率譜計算公式得到頻率域的頻譜，根據(jù)輸入信號的不同，得到不同的頻譜圖，當輸入信號為正弦波時，輸出的data數(shù)

15、據(jù)如圖5-1，當輸入的信號為方波時，輸出的data數(shù)據(jù)序列見圖5-2。 圖5-1 圖5-25.5 倒序運算部分的設計 倒序運算是在fft變換的蝶形運算開始之前調(diào)用的，其作用是不斷的從當前的倒序值算出下一個倒序值，同時把輸入序列的實部和虛部按順序調(diào)換，是程序中需要仔細去理解的部分，其函數(shù)代碼如下： void finv(int n1,float *xr,float *xi) int m,n,n2,k; float t; n2=n1/2; n=n2; for(m=1;m=n1-2;m+) if(m=k) n=n-k; k=(int)(k/2+0.5); n=n+k; 5.6正余弦函數(shù)表與波形發(fā)生部分

16、的設計 正余弦函數(shù)表的建立的目的是為蝶形變換公式中的正余弦序列提供原始數(shù)據(jù)依據(jù)，而波形發(fā)生器的作用則是為整個程序提供一個輸入序列，使系統(tǒng)根據(jù)輸入的波形來得到與之相對應的頻譜。正余弦函數(shù)表的程序代碼為： void initforfft() int i; for(i=0;in;i+) sin_tabi=sin(pi*2*i/n); cos_tabi=cos(pi*2*i/n); 至于波形發(fā)生的輸入，我用了正弦波和方波兩種波形作為互相對比的輸入，正弦波為f=3hz的序列： void makewave() int i; for(i=0;in;i+) inputi=sin(pi*2*i/n*3)*102

17、4; 與之相對應的正弦波序列的地址為0x3f90c0，波形圖如圖5-3所示。 圖5-3若以方波作為輸入，除了多定義兩個變量之外則是把for循環(huán)里的語句變?yōu)閖=(int)i/20; l=j%2; if(l=0)inputi=1024; else inputi=0;即可。其方波的波形圖見圖5-4 圖5-45.7主函數(shù)部分的設計 主函數(shù)main()是每一個c語言程序中有且僅有的一個重要部分，是一個程序的入口點，可以根據(jù)自己的愛好把它放在程序的某個地方。有些程序員把它放在最前面，而另一些程序員把它放在最后面, 無論放在哪個地方。本次程序的主函數(shù)main()為： main()int i;initforf

18、ft();makewave();for(i=0;in;i+) fwaveri=inputi; fwaveii=0.0;wi=0.0; mum=(int)(0.5+log(n)/log(2);fft(fwaver,fwavei); for(i=0;in;i+)datai=wi;while(1);5 工作過程分析 根據(jù)此次課程設計的要求，為了實現(xiàn)快速傅里葉變換的目的，首先要做的就是讓程序有相應的輸入信號，為此，在程序中，我用了正弦波和方波兩種波形作為輸入以形成對比。再然后就是調(diào)用程序各部分分支以實現(xiàn)相應功能，最終達到fft變換的目的。首先，需要對程序用到的函數(shù)進行定義，這部分就是程序是初始化階段。

19、由于傅里葉變換是一種數(shù)學運算，所以對文件類型進行定義為數(shù)學函數(shù)頭文件，再來就是程序用了不少的函數(shù)，就定義了波形發(fā)生函數(shù)、倒序運算函數(shù)、fft初始化函數(shù)和正余弦函數(shù)表等變量。然后，進行main()主函數(shù)部分，這是程序的主干、入口，主函數(shù)內(nèi)調(diào)用子程序的順序決定了各部分子程序運行的順序，所以這部分是很重要的，要根據(jù)實際fft變換的順序來編寫。再來，就是對各個子程序的編寫，這些程序分支就包含fft初始化函數(shù)，順利建立正余弦函數(shù)表，倒序運算函數(shù)，波形發(fā)生及蝶形運算展開并計算功率譜。最后，就是根據(jù)輸入輸出程序代碼段的地址，通過ccs軟件調(diào)試該程序，并用其中viewgraphtime/frequency菜單

20、功能，改變相應的起始地址和顯示方式顯示輸入變量input與輸出結果data圖形，觀察fft的效果。 其中，輸入變量input的起始地址為0x3f90c0，輸出結果data的地址為0x3f9040，這樣就能顯示輸入輸出圖形，順利觀察fft的效果。小 結通過本次的dsp課程設計,讓我對這個工作原理以及它編程的調(diào)試方法都類似于單片機的學科有了更好的掌握與理解。與次同時，通過此次的課程設計也讓我充分地認識到了我在學習這門課程中存在的不足之處。當剛知道有dsp這門學科的程序設計時，首先闖入我腦中的信息便是這次的課設肯定不好做，但是，在真正的知道了我要設計的題目在樹上能找到類似的程序時，我就知道我把問題給

21、想復雜了。在整個的設計過程中，我需要做的就是把書上的程序看明白，然后再對其中的某些部分進行小小的修改，算起來，我做的設計算是三組里最簡單的一個了，程序調(diào)試很快，波形除了一些瑕疵之外算得上是不錯了。這其中出現(xiàn)的主要問題便是對主函數(shù)調(diào)用的子程序內(nèi)容，特別是蝶形運算那部分，是這次設計的瓶頸 ，經(jīng)過幾天的研究與討論，讓我對以前學的懵懵懂懂的fft變換有了更深層次的了解，特別是蝶形圖展開及倒序運算部分。 通過這次的課程設計讓我學到了很多平時課上學不到的東西，讓我知道了哪些方面是自己的薄弱環(huán)節(jié)，自己需要在哪些方面下一些功夫。更重要的是能過這次的實驗我熟練地掌握了程序的調(diào)試，知道如果一個程序運進的時候出現(xiàn)了

22、問題應該怎樣找到錯誤并改正，也知道了該如何去利用圖書館和網(wǎng)絡上的資源，這對我們以后的課程設計和學習是有很大幫助的?？傊n程設計對我們的幫助是非常大的，在提高我們的動手能力和開發(fā)邏輯思維之于也能在一定的程度上激發(fā)我們對dsp這門課學習的興趣。讓我們的學習從單一的理論升華到實踐的高度。 很慶幸能有這樣一次課設的機會，讓我學嘗試了理論與實際的結合，讓我學到了很多知識，讓我認識到了自己的不足，知道光是掌握了理論知識并不代表什么，必須還要與實際結合才能更好的理解這些知道，使之掌握得更牢靠。在以后的學習生涯中我會不斷的完善自己，用更多知識來豐富和充實自己，為自己以后的人生道路打下堅實的基礎！致謝短短一周的

23、dsp課程設計就這樣結束了，很感謝呂老師和雷老師在這一周里給我?guī)淼膸椭椭笇?。還要感謝在這一周時間里與我共同討論和交流的同學，感謝他們的細心指導和他們提出的疑點。呂老師在軟件方面很厲害，只要遇到跟程序里遇到的問題就可以找他，老師肯定會盡責為我們講解，而雷老師因為本來就是數(shù)字信號處理的任課老師，在傅里葉變換這個設計中，必然會有很多請教雷老師的時候，他都會細心地為我們一一解惑，知道我們聽懂為止。還要感謝為我提供課設資料的學校圖書館，圖書館的大量書籍為我提供了廣闊的資源，讓我熟悉掌握了定時器、外部中斷的工作原理，由其是液晶顯示器的原理開啟方法，對我的幫助非常大。僅僅運用課堂所學的知識，靠自己的力量

24、要在兩周之內(nèi)完成設計的題目是難以想象的。所以這兩周我能夠順利地完成課設任務有很大一部分原因是大家的幫助和圖書的資源。再次，我要感謝指導老師和與我同一個課設題目的同學，因為一個人的思路是有限的，感謝大家的集思成就了我們的妙想。最后感謝學校給我們提供這種獨立自主研究性學習的機會，充分開發(fā)了我們的創(chuàng)新能力。每個學期的課程設計都讓我學會了很多，讓我對學習充滿濃厚的興趣! 參考文獻1 姜沫岐，許涵，俞鵬，段國強 . dsp原理與應用從入門到提高. 北京: 機械工業(yè)出版社， 20072 李行一. 數(shù)字信號處理.重慶大學出版社，20023 張東亮. dsp控制器原理與應用.機械工業(yè)出版社，20114 李哲英

25、. dsp基本理論與應用系統(tǒng)設計.北京航空航天大學出版社，20025 俞卞章. 數(shù)字信號處理. 西安: 西北工業(yè)大學出版社， 20026 王安國. 數(shù)字信號處理基礎.北京: 電子工業(yè)出版社， 20037 何蘇秦，王忠勇. tms320c2000dsp原理及實用技術.電子工業(yè)出版社，2003附錄a1 程序清單#includemath.h#define pi 3.1415926#define n 128void initforfft();void makewave();void finv(int n1,float *xr,float *xi);int inputn,datan;float fwavern,fwavein,wn;float sin_tabn,cos_tabn;int mum;void fft(float xrn,float xin)int s,b;int m,j,k;float x,y;finv(n,xr,xi);for(m=1;m=mum;m+)b=(int)(pow(2,m-1)+0.5); for(j=0;jb;j+) s=j*(int)(pow(2,mum-m)+0.5); for(k=j;k=n-1;k+=(int)(pow(2,m)+0.