【正文】 用如下運(yùn)算方法進(jìn)行DITFFT運(yùn)算。第L級(jí)共有個(gè)不同指數(shù)的旋轉(zhuǎn)因子，用R表示這些不同指數(shù)旋轉(zhuǎn)因子從上到下的順序(R=0，1，…，B1)。蝶形運(yùn)算是分級(jí)進(jìn)行的；每級(jí)的蝶形運(yùn)算可以按旋轉(zhuǎn)因子的指數(shù)大小排序進(jìn)行；如果指數(shù)大小一樣則可從上往下依次蝶算。在同一級(jí)中，每個(gè)蝶的輸入數(shù)據(jù)只對(duì)本蝶有用，且輸出節(jié)點(diǎn)與輸入節(jié)點(diǎn)在同一水平線上，這就意味著每算完一個(gè)蝶后，所得數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的數(shù)組元素(存儲(chǔ)單元)，這種原位(址)計(jì)算的方法可節(jié)省大量?jī)?nèi)存。 DITFFT算法的運(yùn)算規(guī)律及編程思想為了編寫DITFFT算法的運(yùn)算程序，首先要分析其運(yùn)算規(guī)律，總結(jié)編程思想并繪出程序框圖。M級(jí)運(yùn)算共需要復(fù)數(shù)乘法次數(shù)為C=N/2*M,復(fù)數(shù)加法次數(shù)為C=N*M。FFT對(duì)DFT的數(shù)學(xué)運(yùn)算量改進(jìn)：直接采用DFT進(jìn)行計(jì)算，運(yùn)算量為N2次復(fù)數(shù)乘法和N*(N1)次復(fù)數(shù)乘法。按時(shí)間下標(biāo)的奇偶將N點(diǎn)x(n)分別抽取組成兩個(gè)N/2點(diǎn)序列，分別記為x1(n)和x2(n)，將x(n)的DFT轉(zhuǎn)化為x1(n)和x2(n)的DFT的計(jì)算。若N不能滿足上述關(guān)系，可以將序列x(n)補(bǔ)零實(shí)現(xiàn)。利用這兩個(gè)途徑實(shí)現(xiàn)DFT的快速傅里葉變換（FFT），F(xiàn)FT算法基本上可分為按時(shí)間抽取的FFT算法（DITFFT）和按頻率抽取的FFT算法（DIFFFT）。隨著N的增加，運(yùn)算量將急劇增加，而在實(shí)際問題中，N往往是較大的，如當(dāng)N=1024時(shí)，完成復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)分別為百萬以上，無論是用通用計(jì)算機(jī)還是用DSP芯片，都需要消耗大量的時(shí)間，不能滿足實(shí)時(shí)的要求,，不適合于對(duì)實(shí)時(shí)處理要求高的場(chǎng)合。 DITFFT算法的基本原理快速傅里葉變換（FFT）是為提高DFT運(yùn)算速度而采用的一種算法。向量x則就代表了一個(gè)信號(hào)（也即一個(gè)復(fù)雜的“函數(shù)表達(dá)式”）也就是說可以像處理一個(gè)信號(hào)表達(dá)式一樣處理這個(gè)聲音信號(hào)。sound(x,fs,nb)。 用于讀取語音，采樣值放在向量x中，fs表示采樣頻率(Hz)，nb表示采樣位數(shù)。)。,39。在MATLAB中，fn=input(39。所以得到系統(tǒng)總體流程圖如圖1所示。本課程設(shè)計(jì)主要是對(duì)數(shù)字信號(hào)的分析。如果有能力可以選做系統(tǒng)人機(jī)對(duì)話界面。基于本學(xué)期所學(xué)的DITFFT的運(yùn)算規(guī)律和編程思想以及Matlab的學(xué)習(xí)和使用，本課設(shè)要求在Matlab環(huán)境下編寫基2 DITFFT算法實(shí)現(xiàn)對(duì)離散信號(hào)的快速傅里葉變換，再與Matlab軟件自帶的FFT函數(shù)實(shí)現(xiàn)對(duì)離散信號(hào)的傅里葉變換進(jìn)行比較，如果得到的頻譜相同，那么我們編寫的程序就是正確的。因此，DFT的這種運(yùn)算只能進(jìn)行理論上的計(jì)算，不適合對(duì)實(shí)時(shí)處理要求高的場(chǎng)合。對(duì)于有限長(zhǎng)序列x(n),若要求其N點(diǎn)的傅里葉變換（DFT）需要經(jīng)過次復(fù)數(shù)乘法運(yùn)算和N*(N1)次復(fù)數(shù)加法運(yùn)算。它可以將聲音文件變換為離散的數(shù)據(jù)文件，然后利用其強(qiáng)大的矩陣運(yùn)算能力處理數(shù)據(jù)，如數(shù)據(jù)濾波、傅立葉變換、時(shí)域和頻域分析、聲音回放以及各種圖的呈現(xiàn)等，它的信號(hào)處理與分析工具箱位語音信號(hào)分析提供了十分豐富的功能函數(shù)，利用這些功能函數(shù)可以快捷而又方便的完成語音信號(hào)的處理和分析以及信號(hào)的可視化。附加的工具箱（單獨(dú)提供的專用 MATLAB 函數(shù)集）擴(kuò)展了 MATLAB 環(huán)境，以解決這些應(yīng)用領(lǐng)域內(nèi)特定類型的問題。課程設(shè)計(jì)說明書目 錄1 引言 12 基于MATLAB的FFT算法實(shí)現(xiàn) 2 2 FFT運(yùn)算規(guī)律及編程思想 3 3 DITFFT算法的基本原理 3 DITFFT算法的運(yùn)算規(guī)律及編程思想 53 Matlab程序?qū)崿F(xiàn) 104 系統(tǒng)人機(jī)對(duì)話界面 13 GUI簡(jiǎn)介 13 界面設(shè)計(jì) 13 運(yùn)行調(diào)試 145 心得體會(huì) 16參考文獻(xiàn) 17附錄Ⅰ 18附錄Ⅱ 21281 引言MATLAB是矩陣實(shí)驗(yàn)室（Matrix Laboratory）的簡(jiǎn)稱，是美國(guó)MathWorks公司出品的商數(shù)學(xué)軟件，用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算的高級(jí)技術(shù)計(jì)算語言和交互式環(huán)境，主要包括MATLAB和Simulink兩大部分。MATLAB 的應(yīng)用范圍非常廣，包括信號(hào)和圖像處理、通訊、控制系統(tǒng)設(shè)計(jì)、測(cè)試和測(cè)量、財(cái)務(wù)建模和分析以及計(jì)算生物學(xué)等眾多應(yīng)用領(lǐng)域。它以矩陣運(yùn)算為基礎(chǔ)，把計(jì)算、可視化、程序設(shè)計(jì)融合在一個(gè)簡(jiǎn)單易用的交互式工作環(huán)境中，是一款數(shù)據(jù)分析和處理功能都非常強(qiáng)大的工程適用軟件。數(shù)字信號(hào)處理是MATLAB重要應(yīng)用的領(lǐng)域之一。隨著N的增加，運(yùn)算量將急劇增加，而在實(shí)際問題中，N往往是較大的，如當(dāng)N=1024時(shí)，完成復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)分別為百萬以上，無論是用通用計(jì)算機(jī)還是用DSP芯片，都需要消耗大量的時(shí)間和機(jī)器內(nèi)存，不能滿足實(shí)時(shí)的要求。因此，研究作為DSP的快速算法的FFT是相當(dāng)必要的，快速傅里葉變換（FFT）是為提高DFT運(yùn)算速度而采用的一種算法，快速算法的種類很多，而且目前仍在改進(jìn)和提高，它是根據(jù)離散傅里葉變換的奇、偶、虛、實(shí)等特性，對(duì)離散傅立葉變換的算法進(jìn)行改進(jìn)獲得的。其中離散信號(hào)是通過PC自帶的錄音機(jī)錄制一段wav語音信號(hào)，用Matlab采樣得到離散序列x1。用GUI界面完成人機(jī)交互方便使用的。2 基于MATLAB的FFT算法實(shí)現(xiàn)本設(shè)計(jì)要求錄制一段個(gè)人自己的語音信號(hào)，并對(duì)錄制的信號(hào)進(jìn)行采樣；畫出采樣后語音信號(hào)的時(shí)域波形和頻譜圖；在Matlab環(huán)境下編寫基2 DITFFT算法；利用自己編寫的算法對(duì)已采集的語音信號(hào)進(jìn)行頻譜分析，并畫出語音信號(hào)的時(shí)域與頻譜圖，并與Matlab數(shù)字信號(hào)處理工具箱中的fft函數(shù)進(jìn)行對(duì)比研究，驗(yàn)證自編算法的正確性。語音信號(hào)采集完成信號(hào)時(shí)域圖完成信號(hào)頻率響應(yīng)編寫fft程序，畫出信號(hào)頻譜圖實(shí)現(xiàn)輸入信號(hào)的倒序?qū)崿F(xiàn)一級(jí)中不同種蝶形算運(yùn)實(shí)現(xiàn)一級(jí)中相同種蝶形運(yùn)算與Matlab自帶的FFT比較圖1 系統(tǒng)總體流程圖 FFT運(yùn)算規(guī)律及編程思想利用PC機(jī)自帶的錄音機(jī)，錄制一段語音信號(hào)，保存格式為wave的文件，并將其保存在電腦中。 Enter WAV filename:39。s39。 [x,fs,nb]=wavread(fn,[n1 n2])。[n1 n2]表示讀取從n1點(diǎn)到n2點(diǎn)的值（若只有一個(gè)n的點(diǎn)則表示讀取前n點(diǎn)的采樣值）。 用于對(duì)聲音的回放。采集到語音信號(hào)之后，需要對(duì)語音信號(hào)進(jìn)行分析，如語音信號(hào)的時(shí)域分析、頻譜分析、譜圖分析。對(duì)一個(gè)有限長(zhǎng)度序列x(n)的N點(diǎn)的DFT為：所以，要求N點(diǎn)的DFT,需要N2次的復(fù)數(shù)乘法運(yùn)算,N*(N1)次復(fù)數(shù)乘法運(yùn)算算。為了能實(shí)時(shí)處理DFT,要想減少DFT的運(yùn)算量可以有兩個(gè)途徑：第一是降N，N的值減小了，運(yùn)算量就減少了；第二是利用旋轉(zhuǎn)因子的周期性，對(duì)稱性和可約性。旋轉(zhuǎn)因子的性質(zhì)：（1）周期性（2）共軛對(duì)稱性（3）可約性本次課設(shè)要求用用基2的按時(shí)間抽取的FFT算法（DITFFT）實(shí)現(xiàn)FFT功能，設(shè)序列x(n)的長(zhǎng)度為N，且N滿足N=2M,M為正整數(shù)。按時(shí)間抽取基2FFT算法的基本思路是將N點(diǎn)序列按時(shí)間下標(biāo)的奇偶分為兩個(gè)N/2點(diǎn)序列，計(jì)算這兩個(gè)N/2點(diǎn)序列的N/2點(diǎn)DFT，計(jì)算量可減小約一半；每一個(gè)N/2點(diǎn)序列按照同樣的劃分原則，可以劃分為兩個(gè)N/4點(diǎn)序列，最后，將原序列劃分為多個(gè)2點(diǎn)序列，將計(jì)算量大大降低。利用旋轉(zhuǎn)因子的可約性，即：用蝶形運(yùn)算可表示為如圖2所示：圖2 DITFFT蝶形運(yùn)算流圖符號(hào)以此類推，還可以把x1(n)和x2(n)按n值得奇偶分為兩個(gè)序列，這樣就達(dá)到了降N得目的，從而減少了運(yùn)算量。當(dāng)采用M次FFT時(shí)，由N=2M求得M=logN，運(yùn)算流圖有M級(jí)蝶形，每一級(jí)都由N/2個(gè)蝶形運(yùn)算構(gòu)成，這樣每一級(jí)蝶形運(yùn)算都需要N/2次復(fù)數(shù)乘法和N次復(fù)數(shù)加法。當(dāng)N值較大時(shí)，F(xiàn)FT減少運(yùn)算量的特點(diǎn)表現(xiàn)的越明顯。1. 原位計(jì)算對(duì)點(diǎn)的FFT共進(jìn)行M級(jí)運(yùn)算，每級(jí)由N/2個(gè)蝶形運(yùn)算組成。2. 蝶形運(yùn)算實(shí)現(xiàn)FFT運(yùn)算的核心是蝶形運(yùn)算，找出蝶形運(yùn)算的規(guī)律是編程的基礎(chǔ)。對(duì)點(diǎn)的FFT共有M級(jí)運(yùn)算，用L表示從左到右的運(yùn)算級(jí)數(shù)(L=1，2，…，M )。第R個(gè)旋轉(zhuǎn)因子的指數(shù)，旋轉(zhuǎn)因子指數(shù)為P的第一個(gè)蝶的第一節(jié)點(diǎn)標(biāo)號(hào)k從R開始，由于本級(jí)中旋轉(zhuǎn)因子指數(shù)相同的蝶共有個(gè)，且這些蝶的相鄰間距為，故旋轉(zhuǎn)因子指數(shù)為P的最后一個(gè)蝶的第一節(jié)點(diǎn)標(biāo)號(hào)k為：，本級(jí)中各蝶的第二個(gè)節(jié)點(diǎn)與第一個(gè)節(jié)點(diǎn)都相距B點(diǎn)。首先讀入數(shù)據(jù)，根據(jù)數(shù)據(jù)長(zhǎng)度確定運(yùn)算級(jí)數(shù)M，運(yùn)算總點(diǎn)數(shù)，不足補(bǔ)0處理。數(shù)據(jù)倒序后從第1級(jí)開始逐級(jí)進(jìn)行，共進(jìn)行M級(jí)運(yùn)算。每個(gè)R對(duì)應(yīng)的旋轉(zhuǎn)因子指數(shù)，旋轉(zhuǎn)因子指數(shù)相同的蝶從上往下依次逐個(gè)運(yùn)算，各個(gè)蝶的第一節(jié)點(diǎn)標(biāo)號(hào)k都是從R開始，以為步長(zhǎng)，到(可簡(jiǎn)取極值N2)結(jié)束。這樣數(shù)據(jù)倒序后的運(yùn)算可用三重循環(huán)程序?qū)崿F(xiàn)。