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

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

2、某一個(gè)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) 共六十頁(yè) 如前所述，N點(diǎn)DFT的復(fù)乘次數(shù)等于N2。顯然，把N點(diǎn)DFT分解(fnji)為幾個(gè)較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子WmN具有明顯的周期性和對(duì)稱性。其周期性表現(xiàn)為(3.2.2) 其對(duì)稱性表現(xiàn)(bioxin)為或者 共六十頁(yè) 3.5.2 時(shí)域抽取法基2FFT基本原理 FFT算法基本上分為兩大類：時(shí)域抽取法FFT(Decimation In Time FFT,簡(jiǎn)稱DIT-FFT)和頻域抽取法FFT(Decimation In

3、 Frequency FFT,簡(jiǎn)稱DIFFFT)。下面先介紹DIFFFT算法。 設(shè)序列x(n)的長(zhǎng)度(chngd)為N，且滿足為自然數(shù) 按n的奇偶把x(n)分解(fnji)為兩個(gè)N/2點(diǎn)的子序列共六十頁(yè) 則x(n)的DFT為由于(yuy)所以(suy) 共六十頁(yè) 其中(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) 共六十頁(yè)圖4.2.1 蝶形運(yùn)算(yn sun)符號(hào) 共六十頁(yè)圖4.2.2 N點(diǎn)DFT的一次時(shí)域抽取(

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

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

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

7、)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)(k=2r,r=0,1,N/2-1)時(shí) 共六十頁(yè)當(dāng)k取奇數(shù)(j sh)(k=2r+1,r=0,1,N/2-1)時(shí) 將x1(n)和x2(n)分別(fnbi)代入上式，可得共六十頁(yè)圖3.2.10 DIFFFT蝶形運(yùn)算(yn sun)流圖符號(hào) 共六十頁(yè)圖3.2.11 DIFFFT一次分解(fnji)運(yùn)算流圖(N=8) 共六十頁(yè)圖3.2.12 DIFFFT二次分解(fnji)運(yùn)算流圖(N=8) 共六十頁(yè)圖3.2.13 DIFFFT運(yùn)算(yn sun)流圖(N=8) 共六十頁(yè)圖3.2.14 DITFFT的一種變形(bin xng)運(yùn)算流圖共六十頁(yè) 3.5.6 IDFT的

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

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

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

11、樣N點(diǎn)， 并對(duì)Xa(jf)作零階近似(t=nT, dt=T)得共六十頁(yè) 顯然， Xa(jf)仍是f的連續(xù)周期函數(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滿足(mnz)如下關(guān)系式： 由于NT=tp， tp為信號(hào)(xnho)的觀測(cè)時(shí)間，所以 N越大,F越小,分辨率越高共六十頁(yè) 共六十頁(yè)2.頻譜分析(fnx)的步驟(1).數(shù)據(jù)(shj)準(zhǔn)備 已知(2).用FFT計(jì)算頻譜共六十頁(yè) 計(jì)算振幅(zhnf)譜 相位譜 功率譜例P93共六十頁(yè) 共六十頁(yè) 3

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

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

14、 3.4.4 重疊(chngdi)相加法卷積示意圖 共六十頁(yè) 方法：(1) 將x(n)長(zhǎng)序列分段(fn dun)，每段長(zhǎng)度為L(zhǎng)； (2) 各段序列xk(n)與 M點(diǎn)短序列h(n)循環(huán)卷積；(3) 從各段循環(huán)卷積中提取線性卷積結(jié)果。重疊(chngdi)保留法前M-1個(gè)點(diǎn)不是線性卷積的點(diǎn)因 yk(n)=xk(n) L h(n)故分段時(shí)，每段與其前一段有M-1個(gè)點(diǎn)重疊。共六十頁(yè) -x (n(M1)M-1-L (M1)L-1x 0(n)x 1(n)2L-Mn第一段前需補(bǔ)M-1個(gè)零共六十頁(yè) 記 yk(n) =xk (n) L h(n)y0(n)ny1(n)n共六十頁(yè) 例 已知序列(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共六十頁(yè) 解: 重疊(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共六十頁(yè) 頻率(pnl)變量：角頻率復(fù)頻率s頻率(pnl)f連續(xù)信號(hào)離散信號(hào)角頻率復(fù)頻率z頻率k共六十頁(yè) 總結(jié)(zngji)s復(fù)頻域X(s)模擬時(shí)域x(t)模擬頻域X(j)z復(fù)頻域X(z)離散時(shí)域x(n)數(shù)字頻域X(ej)離散周期時(shí)域x(n)離散周期頻域X(k)離散頻域X(k)拉氏變換LTILT解析開拓=0傅氏變換 FTIFTz=esT=T對(duì)f歸一化且延拓取主值周期內(nèi)插采樣Z變換ZTIZT序列傅氏變換DTFTIDTFT內(nèi)插z=W-kNIDFT離散傅氏變換DFT周期延拓取主值區(qū)間內(nèi)插采樣=2k/N周期延拓取主值周期離散傅氏級(jí)數(shù)變換DFSIDFSZ=ej共六十頁(yè)內(nèi)容摘要3.5 快速傅里葉變換(FFT)。直到1965年發(fā)現(xiàn)了DFT的一種快速算法(sun f)以后