第九章離散傅里葉變換

前言：引入DFT的原因計算機應(yīng)用于信號處理的基本條件：1.連續(xù)函數(shù)轉(zhuǎn)變?yōu)殡x散數(shù)據(jù)(時域與頻域)；2.計算范圍從無限寬收縮到一個有限區(qū)間。離散傅里葉變換研究內(nèi)容：1.如何在頻域進行離散化？2.時域上的樣本與頻域上的樣本之間的數(shù)學(xué)關(guān)系是怎樣的？現(xiàn)在是1頁\一共有82頁\編輯于星期四現(xiàn)在是2頁\一共有82頁\編輯于星期四主要內(nèi)容離散傅里葉級數(shù)（DFS）離散傅里葉變換（DFT）快速傅里葉變換（FFT）現(xiàn)在是3頁\一共有82頁\編輯于星期四一.DFT是重要的變換

1.分析有限長序列的有用工具。

2.在信號處理的理論上有重要意義。

3.在運算方法上起核心作用，譜分析、卷積、相關(guān)都可以通DFT在計算機上實現(xiàn)?！?-1 引言現(xiàn)在是4頁\一共有82頁\編輯于星期四二.DFT是現(xiàn)代信號處理橋梁

DFT要解決兩個問題： 一是離散與量化， 二是快速運算。信號處理DFT(FFT)傅氏變換離散量化現(xiàn)在是5頁\一共有82頁\編輯于星期四

FT傅立葉變換t00時域：連續(xù)、非周期，頻域：非周期、連續(xù)§9.2傅里葉變換的幾種可能形式現(xiàn)在是6頁\一共有82頁\編輯于星期四FS

傅立葉級數(shù)時域：連續(xù)、周期，頻域：非周期、離散0t------01111111111現(xiàn)在是7頁\一共有82頁\編輯于星期四DTFTx(nT)T-T0T2Tt0------時域：離散、非周期頻域：周期、連續(xù)現(xiàn)在是8頁\一共有82頁\編輯于星期四

時域

頻域連續(xù)非周期非周期連續(xù)傅里葉變換連續(xù)周期

非周期離散 傅里葉級數(shù)離散非周期周期連續(xù)

序列的傅里葉變換離散周期周期離散離散傅里葉級數(shù)傅里葉變換形式傅里葉變換的4種形式現(xiàn)在是9頁\一共有82頁\編輯于星期四

但是，前三種傅里葉變換對都不適于計算機上運算，因為它們至少在一個域（時域或頻域）中函數(shù)是連續(xù)的。 因此，我們感興趣的是時域和頻域都是離散的情況?，F(xiàn)在是10頁\一共有82頁\編輯于星期四時域：離散、周期，頻域：周期、離散現(xiàn)在是11頁\一共有82頁\編輯于星期四§9.3DFS與DFT連續(xù)周期信號:抽樣（抽樣周期為T，一個周期內(nèi)抽樣N個點）得周期序列

一、離散傅里葉級數(shù)是周期為N的周期序列1、DFS的引入現(xiàn)在是12頁\一共有82頁\編輯于星期四

將兩端乘

再從n=0到N-1求和，則：2、的求取現(xiàn)在是13頁\一共有82頁\編輯于星期四現(xiàn)在是14頁\一共有82頁\編輯于星期四3、將定標(biāo)因子1/N移到表達式中。保持與Z變換相同的形式？現(xiàn)在是15頁\一共有82頁\編輯于星期四設(shè)則離散傅氏級數(shù)表示為：正變換：反變換：4、離散傅氏級數(shù)的表示：現(xiàn)在是16頁\一共有82頁\編輯于星期四DFS的圖示說明n0N-N......k0N-N現(xiàn)在是17頁\一共有82頁\編輯于星期四5、函數(shù)的幾個性質(zhì)：1.共軛對稱性：2.周期性：i為整數(shù)3.可約性：4.正交性：i為整數(shù)現(xiàn)在是18頁\一共有82頁\編輯于星期四二、離散傅里葉變換在進行DFS分析時，時域、頻域序列都是無限長的周期序列周期序列實際上只有有限個序列值有意義長度為N的有限長序列可以看成周期為N的周期序列的一個周期（主值序列）借助DFS變換對，取時域、頻域的主值序列可以得到一個新的變換—DFT，即有限長序列的離散傅里葉變換現(xiàn)在是19頁\一共有82頁\編輯于星期四另一種表示其中表示對n取模N運算(或模N的余數(shù))。則若1、周期序列與主值序列的關(guān)系現(xiàn)在是20頁\一共有82頁\編輯于星期四舉例：設(shè)周期為N=6。則有周期序列和求余運算：

這是因為：(19=3×6+1)

同理這是因為：(-2=-1×6+4)

同樣：X(k)也是一個N點的有限長序列現(xiàn)在是21頁\一共有82頁\編輯于星期四2、DFT的定義現(xiàn)在是22頁\一共有82頁\編輯于星期四3、DFT的矩陣形式其中：現(xiàn)在是23頁\一共有82頁\編輯于星期四4、離散傅里葉變換(DFT)的特點序列x(n)在時域是有限長的(長度為N)，它的離散傅里葉變換X(k)也是離散、有限長的(長度也為N)。n為時域變量，k為頻域變量。離散傅里葉變換與離散傅里葉級數(shù)沒有本質(zhì)區(qū)別，DFT實際上是離散傅里葉級數(shù)的主值，DFT也隱含有周期性。離散傅里葉變換(DFT)具有唯一性?，F(xiàn)在是24頁\一共有82頁\編輯于星期四例1、計算(N=12)的N點DFT.解：

現(xiàn)在是25頁\一共有82頁\編輯于星期四現(xiàn)在是26頁\一共有82頁\編輯于星期四§9.4離散傅里葉變換的性質(zhì)1、線性這里，序列長度及DFT點數(shù)均為N若不等，分別為N1，N2，則需補零使兩序列長度相等，均為N，且若則現(xiàn)在是27頁\一共有82頁\編輯于星期四

有限長序列的圓周移位導(dǎo)致頻譜線性相移，而對頻譜幅度無影響。(1)圓周移位2、時移特性(2)時移特性現(xiàn)在是28頁\一共有82頁\編輯于星期四從圖中兩虛線之間的主值序列的移位情況可以看出：當(dāng)主值序列左移m個樣本時，從右邊會同時移進m個樣本好像是剛向左邊移出的那些樣本又從右邊循環(huán)移了進來因此取名“循環(huán)移位”。顯然，循環(huán)移位不同于線性移位現(xiàn)在是29頁\一共有82頁\編輯于星期四3、頻移特性時域序列的調(diào)制等效于頻域的圓周移位現(xiàn)在是30頁\一共有82頁\編輯于星期四eg：現(xiàn)在是31頁\一共有82頁\編輯于星期四4、時域圓周卷積設(shè)則(1)定理現(xiàn)在是32頁\一共有82頁\編輯于星期四圓周卷積步驟：1）翻褶2）圓周移位3）相乘4）相加(2)圓周卷積的計算現(xiàn)在是33頁\一共有82頁\編輯于星期四Eg1.N-10nN-10n現(xiàn)在是34頁\一共有82頁\編輯于星期四0m0m0m0m現(xiàn)在是35頁\一共有82頁\編輯于星期四現(xiàn)在是36頁\一共有82頁\編輯于星期四0233211N-1n最后結(jié)果：現(xiàn)在是37頁\一共有82頁\編輯于星期四1）.線性卷積的長度為的長度為2）圓周卷積（3）線性卷積與圓周卷積的關(guān)系現(xiàn)在是38頁\一共有82頁\編輯于星期四3)關(guān)系補‘0’加長現(xiàn)在是39頁\一共有82頁\編輯于星期四x(n)的N點DFT是

x(n)的z變換在單位圓上的N點等間隔抽樣；

x(n)的DTFT在區(qū)間[0,2π]上的N點等間隔抽樣。§9-5現(xiàn)在是40頁\一共有82頁\編輯于星期四一.DFT的計算工作量

兩者的差別僅在指數(shù)的符號和因子1/N.

§9-6FFT的應(yīng)用現(xiàn)在是41頁\一共有82頁\編輯于星期四DFT與IDFT運算特點復(fù)數(shù)乘法復(fù)數(shù)加法一個X(k)NN–1N個X(k)(N點DFT)N2N(N–1)當(dāng)N很大時,運算量將是驚人的,如N=1024,要完成1048576次(一百多萬次)運算.這樣,難以做到實時處理.現(xiàn)在是42頁\一共有82頁\編輯于星期四二.改進的途徑

1.的對稱性和周期性對稱性:周期性:2、N點DFT2個N/2點DFT現(xiàn)在是43頁\一共有82頁\編輯于星期四

利用上述特性,可以將有些項合并,并將DFT分解為短序列,從而降低運算次數(shù),提高運算速度.1965年,庫利(cooley)和圖基(Tukey)首先提出FFT算法.對于N點DFT,僅需(N/2)log2N

次復(fù)數(shù)乘法運算.例如N=1024=210

時，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍現(xiàn)在是44頁\一共有82頁\編輯于星期四三、基2FFT算法的思路把一個序列分為長度減半的偶序列和奇序列,原序列的DFT就由這兩個N/2序列求得.進一步把N/2序列分解成兩個N/4序列,一直分解到2點序列.現(xiàn)在是45頁\一共有82頁\編輯于星期四Eg.N=8的FFT1,3,5,70,2,4,60,42,61,53,7x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第一級第二級第三級現(xiàn)在是46頁\一共有82頁\編輯于星期四四.算法原理(基2FFT)1.先將按n的奇偶分為兩組N/2點作DFT,設(shè)N=2M,不足時,可補些零。

n為偶數(shù)時:n為奇數(shù)時:現(xiàn)在是47頁\一共有82頁\編輯于星期四因此現(xiàn)在是48頁\一共有82頁\編輯于星期四

其中,2.兩點結(jié)論:(1)G(k),H

(k)均為N/2點的DFT。

(2)X(k)=G(k)+W

H

(k)只能確定出

X(k)的k=0,1,…(N/2-1)時的值；即前N/2點的結(jié)果。kN現(xiàn)在是49頁\一共有82頁\編輯于星期四同理,3.X(k)后N/2個點的確定*X(k)的后N/2個點，也完全由G(k),H(k)確定*N點的DFT可由兩個N/2點的DFT來計算?，F(xiàn)在是50頁\一共有82頁\編輯于星期四實現(xiàn)上式運算的流圖稱作蝶形運算

k=0,1,…(N/2-1)4.蝶形運算（N/2個蝶形)11-1由X1(k)、X2(k)表示X(k)的運算是一種特殊的運算-碟形運算

k=0,1,…(N/2-1)現(xiàn)在是51頁\一共有82頁\編輯于星期四

例N=8時的FFT:

1、2個N/2點DFT（1）將分成奇偶序列，并計算X(k)現(xiàn)在是52頁\一共有82頁\編輯于星期四其中現(xiàn)在是53頁\一共有82頁\編輯于星期四

g(0)=x(0)

g(1)=x(2)

N/2點

g(2)=x(4)DFT

g(3)=x(6)

h(0)=x(1)

h(1)=x(3)

N/2點

h(2)=x(5)

DFT

h(3)=x(7)

12G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（2）對X

(k)和X

(k)進行蝶形運算如下圖所示:現(xiàn)在是54頁\一共有82頁\編輯于星期四2、

4個N/4點DFT（1）將分成奇偶序列，并進行DFT現(xiàn)在是55頁\一共有82頁\編輯于星期四其中現(xiàn)在是56頁\一共有82頁\編輯于星期四（2）將分成奇偶序列,并進行DFT現(xiàn)在是57頁\一共有82頁\編輯于星期四現(xiàn)在是58頁\一共有82頁\編輯于星期四WN0WN0WN0W0N-1-1-1-1P(0)P(1)Q(0)Q(1)Y(0)Y(1)Z(0)Z(1)WN0WN2WN0WN2-1-1-1-1G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)8點DFT的FFT的運算流圖如下現(xiàn)在是59頁\一共有82頁\編輯于星期四1.蝶形運算蝶形單元蝶距:2m-1（第m級蝶形運算）

五.FFT算法的特點現(xiàn)在是60頁\一共有82頁\編輯于星期四輸入數(shù)據(jù)、中間運算結(jié)果和最后輸出均用同一存儲器。

2.原位運算WN0WN0WN0W0N-1-1-1-1P(0)P(1)Q(0)Q(1)Y(0)Y(1)Z(0)Z(1)WN0WN2WN0WN2-1-1-1-1G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)現(xiàn)在是61頁\一共有82頁\編輯于星期四

3

倒位序運算FFT運算流程中，輸出X(k)按正常順序排列在存儲單元,而輸入是按順序:

這種順序稱作倒位序,即二進制數(shù)倒位?，F(xiàn)在是62頁\一共有82頁\編輯于星期四是由奇偶分組造成的,以N=8為例說明如下:現(xiàn)在是63頁\一共有82頁\編輯于星期四倒位序的實現(xiàn)

輸入序列先按自然順序存入存儲單元,然后經(jīng)變址運算來實現(xiàn)倒位序排列。

設(shè)輸入序列的序號為n,二進制為

(n2n1n0)2,倒位序順序用

表示,其倒位序二進制為(n0n1n2)2

?，F(xiàn)在是64頁\一共有82頁\編輯于星期四

00

0

00

0

00

10

0

11

0

04

20

1

00

1

02

30

1

11

1

06

41

0

00

0

11

51

0

11

0

15

61

1

00

1

13

71

1

11

1

17自然順序n二進制nnn倒位序二進制nnn倒位順序n^210012碼位倒序（N=8）現(xiàn)在是65頁\一共有82頁\編輯于星期四碼位倒序（N=16）現(xiàn)在是66頁\一共有82頁\編輯于星期四A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)倒位序的變址處理方法存儲單元自然順序變址倒位序現(xiàn)在是67頁\一共有82頁\編輯于星期四蝶距為1蝶距為2WN0WN0WN0W0N-1-1-1-1P(0)P(1)Q(0)Q(1)Y(0)Y(1)Z(0)Z(1)WN0WN2WN0WN2-1-1-1-1G(0)G(1)G(2)G(3)H(0)H(1)H(2)H(3)WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)現(xiàn)在是68頁\一共有82頁\編輯于星期四4.WNr

的分布規(guī)律第1級：第2級：……第i級:……第L級:現(xiàn)在是69頁\一共有82頁\編輯于星期四

5.存儲單元

存輸入序列

(n),n=0,1,,N-1,計N

個單元;

存放系數(shù)

,r=0,1,,N/2-1,

需N/2個存儲單元；共計(N+N/2)個存儲單元?，F(xiàn)在是70頁\一共有82頁\編輯于星期四三、FFT運算量1．N=2時，共有L=logN級蝶形運算；每一級有N/2個蝶形單元。2．每一級有N個輸入中間數(shù)據(jù)，且每級只用到本級的輸入中間數(shù)據(jù)，適合于迭代運算。3．計算量：每級N/2次復(fù)乘法，N次復(fù)加。（每蝶形只乘一次，加減各一次）。共有L*N/2=N/2log2N次復(fù)乘法；復(fù)加法L*N=Nlog2N

次。與直接DFT定義式運算量相比(倍數(shù))N2/(Nlog2N)

。當(dāng)N大時，此倍數(shù)很大。2L現(xiàn)在是71頁\一共有82頁\編輯于星期四§9-7DFT的應(yīng)用一、利用FFT計算線卷積1、

時