數(shù)字信號(hào)處理快速傅里葉變換(FFT)姚

1、第3章 快速(kui s)傅里葉變換(FFT) 共五十一頁3.5 引言(ynyn) DFT是信號(hào)分析與處理中的一種重要(zhngyo)變換。因直接計(jì)算DFT的計(jì)算量與變換區(qū)間長度N的平方成正比，當(dāng)N較大時(shí)，計(jì)算量太大，所以在快速傅里葉變換(簡稱FFT)出現(xiàn)以前，直接用DFT算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。直到1965年發(fā)現(xiàn)了DFT的一種快速算法以后，情況才發(fā)生了根本的變化。 共五十一頁3.5 基2FFT算法(sun f) 3.5.1 直接計(jì)算DFT的特點(diǎn)及減少(jinsho)運(yùn)算量的基本途徑 長度為N的有限長序列x(n)的DFT為 考慮x(n)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)k值，直

2、接按(4.2.1)式計(jì)算X(k)值需要N次復(fù)數(shù)乘法、(N-1)次復(fù)數(shù)加法。 (3.2.1) 共五十一頁 如前所述，N點(diǎn)DFT的復(fù)乘次數(shù)等于N2。顯然，把N點(diǎn)DFT分解為幾個(gè)較短的DFT，可使乘法次數(shù)大大減少。另外(ln wi)，旋轉(zhuǎn)因子WmN具有明顯的周期性和對(duì)稱性。其周期性表現(xiàn)為(3.2.2) 其對(duì)稱性表現(xiàn)(bioxin)為或者 共五十一頁 3.5.2 時(shí)域抽取(chu q)法基2FFT基本原理 FFT算法基本上分為兩大類：時(shí)域抽取法FFT(Decimation In Time FFT,簡稱DIT-FFT)和頻域抽取法FFT(Decimation In Frequency FFT,簡稱DIF

3、FFT)。下面先介紹DIFFFT算法。 設(shè)序列x(n)的長度為N，且滿足為自然數(shù) 按n的奇偶把x(n)分解(fnji)為兩個(gè)N/2點(diǎn)的子序列共五十一頁 則x(n)的DFT為由于(yuy)所以(suy) 共五十一頁 其中(qzhng)X1(k)和X2(k)分別為x1(r)和x2(r)的N/2點(diǎn)DFT，即 (3.2.5) (3.2.6) 由于X1(k)和X2(k)均以N/2為周期(zhuq)，且 ，所以X(k)又可表示為(3.2.7) (3.2.8) 共五十一頁圖4.2.1 蝶形運(yùn)算(yn sun)符號(hào) 共五十一頁圖4.2.2 N點(diǎn)DFT的一次時(shí)域抽取(chu q)分解圖(N=8) 共五十一頁 與

4、第一次分解相同，將x1(r)按奇偶分解成兩個(gè)(lin )N/4長的子序列x3(l)和x4(l)，即那么(n me)，X1(k)又可表示為 (3.2.9) 共五十一頁式中 同理，由X3(k)和X4(k)的周期性和Wm N/2的對(duì)稱(duchn)性 Wk+N/4 N/2=-Wk N/2 最后得到： (3.2.10) 共五十一頁 用同樣(tngyng)的方法可計(jì)算出(3.2.11)其中(qzhng) 共五十一頁圖3.2.3 N點(diǎn)DFT的第二次時(shí)域抽取(chu q)分解圖(N=8) 共五十一頁 圖3.2.4 N點(diǎn)DITFFT運(yùn)算(yn sun)流圖(N=8) 同址(原位)計(jì)算共五十一頁 3.5.3 D

5、ITFFT算法與直接計(jì)算DFT運(yùn)算量的比較1.蝶形運(yùn)算及運(yùn)算量的比較 每級(jí)由N/2個(gè)蝶形組成,每一級(jí)運(yùn)算都需要N/2次復(fù)數(shù)(fsh)乘和N次復(fù)數(shù)(fsh)加(每個(gè)蝶形需要兩次復(fù)數(shù)(fsh)加法)。所以，M級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為復(fù)數(shù)(fsh)加次數(shù)為 例如，N=210=1024時(shí)共五十一頁 2. 序列的倒序或變址計(jì)算 DITFFT算法的輸入序列的排序看起來似乎很亂，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于(yuy)N=2M，所以順序數(shù)可用M位二進(jìn)制數(shù)(nM-1nM-2n1n0)表示。 圖4.2.7 形成(xngchng)倒序的樹狀圖(N=23) 共五十一頁表4.2.1 順序(shnx)

6、和倒序二進(jìn)制數(shù)對(duì)照表 共五十一頁 圖4.2.8 倒序(do x)規(guī)律 共五十一頁 圖4.2.9 倒序(do x)程序框圖 共五十一頁 3.5.4 頻域抽取法FFT(DIFFFT) 在基2快速算法中，頻域抽取法FFT也是一種常用的快速算法，簡稱DIFFFT。 設(shè)序列x(n)長度為N=2M，首先(shuxin)將x(n)前后對(duì)半分開，得到兩個(gè)子序列，其DFT可表示為如下形式：共五十一頁偶數(shù)(u sh) 奇數(shù)(j sh) 將X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2r,r=0,1,N/2-1)時(shí) 共五十一頁當(dāng)k取奇數(shù)(j sh)(k=2r+1,r=0,1,N/2-1)時(shí)(3.2.15) 將x1

7、(n)和x2(n)分別(fnbi)代入(4.2.14)和(4.2.15)式，可得 (3.2.16) 共五十一頁圖3.2.10 DIFFFT蝶形運(yùn)算(yn sun)流圖符號(hào) 共五十一頁圖3.2.11 DIFFFT一次分解(fnji)運(yùn)算流圖(N=8) 共五十一頁圖3.2.12 DIFFFT二次分解(fnji)運(yùn)算流圖(N=8) 共五十一頁圖3.2.13 DIFFFT運(yùn)算(yn sun)流圖(N=8) 共五十一頁圖3.2.14 DITFFT的一種(y zhn)變形運(yùn)算流圖共五十一頁 3.5.6 IDFT的高效算法(sun f) 上述FFT算法流圖也可以用于離散傅里葉逆變換(Inverse Disc

8、rete Fourier Transform，簡稱IDFT)。比較DFT和IDFT的運(yùn)算公式： 共五十一頁圖4.2.16 DITIFFT運(yùn)算(yn sun)流圖 共五十一頁 如果希望直接調(diào)用FFT子程序計(jì)算IFFT，則可用下面的方法(fngf)： 由于 對(duì)上式兩邊(lingbin)同時(shí)取共軛，得共五十一頁 3.5.7 實(shí)序列的FFT算法 設(shè)x(n)為N點(diǎn)實(shí)序列，取x(n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分別(fnbi)作為新構(gòu)造序列y(n)的實(shí)部和虛部，即對(duì)y(n)進(jìn)行(jnxng)N/2點(diǎn)FFT，輸出Y(k)，則 根據(jù)DITFFT的思想及式(3.2.7)和(3.2.8)，可得到 共五十一頁 3.6 N為合數(shù)

9、(hsh)的FFT算法 P90共五十一頁3.7 FFT 的應(yīng)用(yngyng) DFT的快速算法FFT的出現(xiàn)， 使DFT在數(shù)字通信、 語言信號(hào)處理、 圖像處理、 功率譜估計(jì)、 仿真、 系統(tǒng)分析、 雷達(dá)理論、 光學(xué)、 醫(yī)學(xué)、 地震以及數(shù)值分析等各個(gè)領(lǐng)域都得到廣泛應(yīng)用。3.7.1 四種傅立葉變換1、非周期連續(xù)時(shí)間(shjin)信號(hào)的傅立葉變換（FT）共五十一頁 2、周期連續(xù)(linx)時(shí)間信號(hào)的傅立葉級(jí)數(shù)（FS）3、序列傅立葉變換共五十一頁 4、周期序列(xli)的傅立葉級(jí)數(shù)（DFS）注意周期性、離散性在時(shí)域和頻域中的對(duì)稱共五十一頁 3.7.2 用FFT對(duì)信號(hào)進(jìn)行譜分析 所謂信號(hào)的譜分析就是計(jì)算信

10、號(hào)的傅里葉變換。 連續(xù)信號(hào)與系統(tǒng)的傅里葉分析顯然不便于直接用計(jì)算機(jī)進(jìn)行計(jì)算， 使其應(yīng)用受到限制， 而DFT是一種時(shí)域和頻域均離散化的變換， 適合數(shù)值運(yùn)算， 成為分析離散信號(hào)和系統(tǒng)的有力工具。 1. 用DFT對(duì)連續(xù)信號(hào)進(jìn)行譜分析 工程(gngchng)實(shí)際中， 經(jīng)常遇到的連續(xù)信號(hào)xa(t)， 其頻譜函數(shù)Xa(j)也是連續(xù)函數(shù)。 共五十一頁 設(shè)連續(xù)(linx)信號(hào)xa(t)持續(xù)時(shí)間為tp， 最高頻率為fc， xa(t)的傅里葉變換為： 對(duì)xa(t)以采樣間隔T1/2fc(即fs=1/T2fc)采樣得 xa(nT)。 設(shè)共采樣N點(diǎn)， 并對(duì)Xa(jf)作零階近似(t=nT, dt=T)得共五十一頁 顯

11、然， Xa(jf)仍是f的連續(xù)周期函數(shù)(zhu q hn sh), xa(nT)和X (jf)如圖3.4.5(b)所示。 對(duì) X(jf)在區(qū)間0, fs上等間隔采樣N點(diǎn)， 采樣間隔為F，F(xiàn)也叫頻率分辨率 如圖3.4.5(c)所示。 參數(shù)fs 、 tp、 N和F滿足如下關(guān)系式： 由于NT=tp， tp為信號(hào)的觀測(cè)時(shí)間(shjin)，所以 N越大,F越小,分辨率越高共五十一頁 共五十一頁頻譜分析(fnx)的步驟1.數(shù)據(jù)(shj)準(zhǔn)備 已知2.用FFT計(jì)算頻譜共五十一頁 計(jì)算振幅譜 相位(xingwi)譜 功率譜例P93共五十一頁 3.7.3 用DFT計(jì)算(j sun)線性卷積 如果0kL-1則由時(shí)

12、域循環(huán)(xnhun)卷積定理有 Y(k)=DFTy(n)=X1(k)X2(k), 0kL-1共五十一頁 由此可見， 循環(huán)卷積既可在時(shí)域直接計(jì)算， 也可以按照?qǐng)D3.4.1所示的計(jì)算框圖， 在頻域計(jì)算。 由于DFT有快速(kui s)算法FFT， 當(dāng)N很大時(shí)， 在頻域計(jì)算的速度快得多， 因而常用DFT(FFT)計(jì)算循環(huán)卷積。 圖 3.4.1 用DFT計(jì)算(j sun)循環(huán)卷積 共五十一頁圖 3.4.3 用DFT計(jì)算(j sun)線性卷積框圖 共五十一頁計(jì)算(j sun)量的比較N=M81610244096r0.570.9429.2100共五十一頁 重疊(chngdi)相加法 當(dāng)N和M相差很大時(shí),則

13、用FFT計(jì)算時(shí),需要在長度較短的序列后面補(bǔ)很多零,這樣計(jì)算線性卷積效率并不高. 處理方法: 可將長度較長的序列分段處理,從而(cng r)不用補(bǔ)很多0,提高計(jì)算效率.共五十一頁 設(shè)序列h(n)長度(chngd)為N， x(n)為無限長序列。 將x(n)均勻分段， 每段長度(chngd)取M， 則于是(ysh)， h(n)與x(n)的線性卷積可表示為(3.4.4) 共五十一頁重疊相加法處理(chl)步驟共五十一頁圖 3.4.4 重疊(chngdi)相加法卷積示意圖 共五十一頁 重疊(chngdi)保留法 P97共五十一頁內(nèi)容摘要第3章 快速傅里葉變換(FFT)。直到1965年發(fā)現(xiàn)了DFT的一種快速算法以后，情況才發(fā)生了根本的變化。例如，