數(shù)字信號處理快速傅里葉變換(FFT)本

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

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

3、 Frequency FFT,簡稱DIFFFT)。下面先介紹DIFFFT算法。 設(shè)序列x(n)的長度(chngd)為N，且滿足為自然數(shù) 按n的奇偶把x(n)分解(fnji)為兩個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) 由于(yuy)X1(k)和X2(k)均以N/2為周期，且 ，所以X(k)又可表示為(3.2.7) (3.2.8) 共六十頁圖4.2.1 蝶形運(yùn)算(yn sun)符號 共六十頁圖4.2.2 N點(diǎn)DFT的一次時域抽取(

4、chu q)分解圖(N=8) 共六十頁 與第一次分解相同，將x1(r)按奇偶分解成兩個(lin )N/4長的子序列x3(l)和x4(l)，即那么(n me)，X1(k)又可表示為 (3.2.9) 共六十頁式中 同理，由X3(k)和X4(k)的周期性和Wm N/2的對稱(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的第二次時域抽取(chu q)分解圖(N=8) 共六十頁 圖3.2.4 N點(diǎn)DITFFT運(yùn)算(yn sun)流圖(N=8) 同址(原

5、位)計(jì)算共六十頁 3.5.3 DITFFT算法與直接計(jì)算DFT運(yùn)算量的比較1.蝶形運(yùn)算及運(yùn)算量的比較 每級由N/2個蝶形組成,每一級運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個蝶形需要兩次復(fù)數(shù)加法)。所以(suy)，M級運(yùn)算總共需要的.復(fù)數(shù)乘次數(shù)為復(fù)數(shù)(fsh)加次數(shù)為 例如，N=210=1024時P84共六十頁 2.同址計(jì)算(原位) 每一級的蝶形的輸入(shr)與輸出在運(yùn)算前后可以存儲在同一地址的存儲單元中,這種同址運(yùn)算的優(yōu)點(diǎn)是可以節(jié)省存儲單元,減低對硬件的要求.共六十頁 3. 序列的倒序(do x)或變址計(jì)算 DITFFT算法的輸入序列的排序看起來似乎很亂，但仔細(xì)分析就會發(fā)現(xiàn)這種倒序是很有規(guī)

6、律的。由于N=2M，所以順序數(shù)可用M位二進(jìn)制數(shù)(nM-1nM-2n1n0)表示。 圖4.2.7 形成(xngchng)倒序的樹狀圖(N=23) 共六十頁表4.2.1 順序(shnx)和倒序二進(jìn)制數(shù)對照表 共六十頁 圖4.2.8 倒序(do x)規(guī)律 共六十頁 圖4.2.9 倒序(do x)程序框圖 IJ共六十頁 3.5.4 頻域抽取法FFT(DIFFFT) 在基2快速算法中，頻域抽取法FFT也是一種常用的快速算法，簡稱DIFFFT。 設(shè)序列(xli)x(n)長度為N=2M，首先將x(n)前后對半分開，得到兩個子序列，其DFT可表示為如下形式：共六十頁偶數(shù)(u sh) 奇數(shù)(j sh) 將X(k

7、)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2r,r=0,1,N/2-1)時 共六十頁當(dāng)k取奇數(shù)(j sh)(k=2r+1,r=0,1,N/2-1)時 將x1(n)和x2(n)分別(fnbi)代入上式，可得共六十頁圖3.2.10 DIFFFT蝶形運(yùn)算(yn sun)流圖符號 共六十頁圖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的一種變形(bin xng)運(yùn)算流圖共六十頁 3.5.6 IDFT的

8、高效算法 上述(shngsh)FFT算法流圖也可以用于離散傅里葉逆變換(Inverse Discrete Fourier Transform，簡稱IDFT)。比較DFT和IDFT的運(yùn)算公式： 共六十頁圖4.2.16 DITIFFT運(yùn)算(yn sun)流圖 共六十頁 另一種方法, 如果希望直接調(diào)用FFT子程序計(jì)算(j sun)IFFT，則可用下面的方法： 由于 對上式兩邊(lingbin)同時取共軛，得共六十頁 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í)部和虛部，即對y(n)進(jìn)行(jnxng)N/2點(diǎn)FFT，輸出Y

9、(k)，則 根據(jù)DITFFT的思想及式(3.2.7)和(3.2.8)，可得到 共六十頁 3.6 N為合數(shù)(hsh)的FFT算法 P90共六十頁3.7 FFT 的應(yīng)用(yngyng) DFT的快速算法FFT的出現(xiàn)， 使DFT在數(shù)字通信、 語言信號處理、 圖像處理、 功率譜估計(jì)、 仿真、 系統(tǒng)分析、 雷達(dá)理論、 光學(xué)、 醫(yī)學(xué)、 地震以及數(shù)值分析等各個領(lǐng)域都得到(d do)廣泛應(yīng)用。3.7.1 四種傅立葉變換1、非周期連續(xù)時間信號的傅立葉變換（FT）共六十頁 2、周期連續(xù)時間信號的傅立葉級數(shù)（FS）3、序列(xli)傅立葉變換共六十頁 4、周期(zhuq)序列的傅立葉級數(shù)（DFS）注意周期性、離散性

10、在時域和頻域中的對稱共六十頁 3.7.2 用FFT對信號進(jìn)行譜分析 所謂信號的譜分析就是計(jì)算信號的傅里葉變換。 連續(xù)信號與系統(tǒng)的傅里葉分析顯然不便于直接用計(jì)算機(jī)進(jìn)行計(jì)算， 使其應(yīng)用受到限制， 而DFT是一種時域和頻域均離散化的變換， 適合(shh)數(shù)值運(yùn)算， 成為分析離散信號和系統(tǒng)的有力工具。 1. 譜分析中參數(shù)的選擇 工程實(shí)際中， 經(jīng)常遇到的連續(xù)信號xa(t)， 其頻譜函數(shù)Xa(j)也是連續(xù)函數(shù)。 共六十頁 設(shè)連續(xù)信號xa(t)持續(xù)時間為tp， 最高頻率為fo， xa(t)的傅里葉變換為： 對xa(t)以采樣間隔(jin g)T1/2fo(即fs=1/T2fo)采樣得 xa(nT)。 設(shè)共采

11、樣N點(diǎn)， 并對Xa(jf)作零階近似(t=nT, dt=T)得共六十頁 顯然， Xa(jf)仍是f的連續(xù)周期函數(shù), xa(nT)和X (jf)如圖3.4.5(b)所示。 對 X(jf)在區(qū)間0, fs上等間隔采樣N點(diǎn)， 采樣間隔為F，F(xiàn)也叫頻率分辨率 如圖3.4.5(c)所示。 參數(shù)fs 、 tp、 N和F滿足(mnz)如下關(guān)系式： 由于NT=tp， tp為信號(xnho)的觀測時間，所以 N越大,F越小,分辨率越高共六十頁 共六十頁2.頻譜分析(fnx)的步驟(1).數(shù)據(jù)(shj)準(zhǔn)備 已知(2).用FFT計(jì)算頻譜共六十頁 計(jì)算振幅(zhnf)譜 相位譜 功率譜例P93共六十頁 共六十頁 3

12、.7.3 用DFT計(jì)算(j sun)線性卷積 如果0kL-1則由時域循環(huán)(xnhun)卷積定理有 Y(k)=FFTy(n)=X1(k)X2(k), 0kL-1共六十頁 由此可見， 循環(huán)(xnhun)卷積既可在時域直接計(jì)算， 也可以按照圖3.4.1所示的計(jì)算框圖， 在頻域計(jì)算。 由于DFT有快速算法FFT， 當(dāng)N很大時， 在頻域計(jì)算的速度快得多， 因而常用DFT(FFT)計(jì)算循環(huán)(xnhun)卷積。 圖 3.4.1 用FFT計(jì)算(j sun)循環(huán)卷積 FFTFFTIFFT共六十頁圖 3.4.3 用FFT計(jì)算(j sun)線性卷積框圖 補(bǔ)L- N個零點(diǎn)L點(diǎn)FFT補(bǔ)L- M個零點(diǎn)L點(diǎn)FFTL點(diǎn)IFF

13、Ty(n)h(n)x(n)共六十頁計(jì)算(j sun)量的比較N=M81610244096r0.570.9429.2100例:P95共六十頁 長序列(xli)和短序列(xli)的線性卷積直接利用(lyng)DFT計(jì)算的缺點(diǎn)：(1) 信號要全部輸入后才能進(jìn)行計(jì)算，延遲太多(2) 內(nèi)存要求大(3) 算法效率不高解決問題方法：采用分段卷積分段卷積可采用重疊相加法 和 重疊保留法共六十頁 設(shè)序列h(n)長度為N， x(n)為無限長序列。 將x(n)均勻(jnyn)分段， 每段長度取M， 則于是(ysh)， h(n)與x(n)的線性卷積可表示為(3.4.4) 共六十頁重疊相加法處理(chl)步驟共六十頁圖

14、 3.4.4 重疊(chngdi)相加法卷積示意圖 共六十頁 方法：(1) 將x(n)長序列分段(fn dun)，每段長度為L； (2) 各段序列xk(n)與 M點(diǎn)短序列h(n)循環(huán)卷積；(3) 從各段循環(huán)卷積中提取線性卷積結(jié)果。重疊(chngdi)保留法前M-1個點(diǎn)不是線性卷積的點(diǎn)因 yk(n)=xk(n) L h(n)故分段時，每段與其前一段有M-1個點(diǎn)重疊。共六十頁 -x (n(M1)M-1-L (M1)L-1x 0(n)x 1(n)2L-Mn第一段前需補(bǔ)M-1個零共六十頁 記 yk(n) =xk (n) L h(n)y0(n)ny1(n)n共六十頁 例 已知序列(xli)x(n)=n+

15、2,0n12, h(n)=1,2,1試分別利用重疊相加和保留法計(jì)算線性卷積, 取L=5 。y(n)=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14解: 重疊(chngdi)相加法x1(n)=2, 3, 4, 5, 6x2(n)=7, 8, 9, 10, 11x3(n)=12,13, 14y1(n)=2, 7, 12, 16, 20, 17, 6y2(n)= 7, 22, 32, 36, 40, 32, 11y3(n)=12, 37, 52, 41, 14共六十頁 解: 重疊(chngdi)保留法y(n)=2, 7, 12, 16

16、, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14x1(n)=0, 0, 2, 3, 4x2(n)=3, 4, 5, 6 ,7x3(n)=6 ,7 , 8, 9, 10y1(n)= x1(n) 5 h(n)= 11, 4, 2, 7, 12x4(n)=9, 10 , 11, 12,13y2(n)= x2(n) 5 h(n)=23, 17, 16, 20, 24y3(n)= x3(n) 5 h(n)=35, 29, 28, 32, 36y4(n)= x4(n) 5 h(n)= 47, 41, 40, 44, 48x5(n)=12,13, 14, 0, 0y5

17、(n)= x5(n) 5 h(n)=12, 37, 52, 41, 14共六十頁 頻率(pnl)變量：角頻率復(fù)頻率s頻率(pnl)f連續(xù)信號離散信號角頻率復(fù)頻率z頻率k共六十頁 總結(jié)(zngji)s復(fù)頻域X(s)模擬時域x(t)模擬頻域X(j)z復(fù)頻域X(z)離散時域x(n)數(shù)字頻域X(ej)離散周期時域x(n)離散周期頻域X(k)離散頻域X(k)拉氏變換LTILT解析開拓=0傅氏變換 FTIFTz=esT=T對f歸一化且延拓取主值周期內(nèi)插采樣Z變換ZTIZT序列傅氏變換DTFTIDTFT內(nèi)插z=W-kNIDFT離散傅氏變換DFT周期延拓取主值區(qū)間內(nèi)插采樣=2k/N周期延拓取主值周期離散傅氏級數(shù)變換DFSIDFSZ=ej共六十頁內(nèi)容摘要3.5 快速傅里葉變換(FFT)。直到1965年發(fā)現(xiàn)了DFT的一種快速算法(sun f)以后