有限長(zhǎng)離散變換Finite課件

第五章

有限長(zhǎng)離散變換

Finite-LengthdiscreteTransforms1第五章

有限長(zhǎng)離散變換

Finite-Lengthdi本章主要內(nèi)容離散傅立葉變換定義離散傅立葉變換性質(zhì)（與DTFT的關(guān)系，圓周移位和圓周卷積，DFT的對(duì)稱性，DFT定理）DFT的應(yīng)用（實(shí)序列的DFT計(jì)算，用DFT計(jì)算線性卷積）離散余弦變換2本章主要內(nèi)容離散傅立葉變換定義25.1正交變換對(duì)信號(hào)的分析思路是：找一個(gè)正交的函數(shù)集，從而將任意信號(hào)分解為該函數(shù)集上各個(gè)元素的線性組合。設(shè)是基本序列，長(zhǎng)度為N。則其滿足：稱為正交序列。35.1正交變換對(duì)信號(hào)的分析思路是：找一個(gè)正交的函數(shù)集5.1正交變換正交變換對(duì)的一般形式：綜合式分析式將要討論的離散傅立葉變換是正交變換的一種。45.1正交變換正交變換對(duì)的一般形式：綜合式分析式將要5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DTFT是離散時(shí)間信號(hào)的傅里葉變換，時(shí)域離散，頻域連續(xù)，周期為2。由于計(jì)算機(jī)只能處理數(shù)字信號(hào)，而不能處理連續(xù)信號(hào)，所以必須把信號(hào)連續(xù)的頻譜離散化。

55.2離散傅里葉變換

DiscreteFourier

時(shí)域

頻域連續(xù)，非周期

FT連續(xù)，非周期連續(xù)，周期FST離散，非周期離散，非周期

DTFT周期，連續(xù)離散周期DFS離散周期5.2離散傅里葉變換

DiscreteFourierTransform(DFT)補(bǔ)充DFS內(nèi)容6時(shí)域已知周期沖激函數(shù)的傅立葉變換：T2T-T-2TδT(t)t0ω02ω0-ω0-2ω0ω0δω0(ω)0ωω0=2π/T7已知周期沖激函數(shù)的傅立葉變換：T2T-T-2TδT(t)t0周期化，離散化信號(hào)x(t)X(jω)P(jω)ω0ω0=2π/Tsx[nT]X(jω)q(t)TFTDFSDTFTQ(jω)Ω0……Ω0=

2π/TQ(jω)Ω0……Ω0=

2π/TP(t)Ts……8周期化，離散化信號(hào)x(t)X(jω)P(jω)ω0ω0=2π5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的定義時(shí)域中N點(diǎn)的序列x[n]的DFT95.2離散傅里葉變換

DiscreteFourierDFT定義中引入一個(gè)常用的符號(hào)5.2離散傅里葉變換

DiscreteFourierTransform(DFT)證明IDFT表達(dá)式：證明：在兩邊同乘以WNln，從n=0到n=N-1作10DFT定義中引入一個(gè)常用的符號(hào)5.2離散傅里葉變換

Di5.2離散傅里葉變換

DiscreteFourierTransform(DFT)其中有：115.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長(zhǎng)單點(diǎn)非零樣本的DFT計(jì)算其N點(diǎn)的DFT：125.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長(zhǎng)單點(diǎn)非零樣本的DFT計(jì)算其N點(diǎn)DFT為：135.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長(zhǎng)正弦序列的DFT計(jì)算解：145.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長(zhǎng)正弦序列的DFT計(jì)算155.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系可以重寫(xiě)為：DFT的定義165.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系175.2離散傅里葉變換

DiscreteFourier類似的,IDFT關(guān)系也可以表示為：5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系18類似的,IDFT關(guān)系也可以表示為：5.2離散傅里葉5.2.3用Matlab計(jì)算DFT

DFTComputationUsingMATLAB在matlab中有四個(gè)用來(lái)計(jì)算DFT和IDFT的內(nèi)置函數(shù)：fft(x),fft(x,M),ifft(X),ifft(X,M)在matlab信號(hào)處理工具箱中的函數(shù)dftmtx(N)用來(lái)計(jì)算NN階DFT矩陣DN例5.3

用matlab計(jì)算如下N點(diǎn)序列的M點(diǎn)DFT195.2.3用Matlab計(jì)算DFT

DFTComput%Program5_1%IllustrationofDFTComputation%

ReadinthelengthNofsequenceandthe%desiredlengthMoftheDFTN=input('Typeinthelengthofthesequence=');M=input('TypeinthelengthoftheDFT=');%Generatethelength-Ntime-domainsequenceu=[ones(1,N)];%ComputeitsM-pointDFTU=fft(u,M);%Plotthetime-domainsequenceanditsDFTt=0:1:N-1;stem(t,u)20%Program5_120title('Originaltime-domainsequence')xlabel('Timeindexn');ylabel('Amplitude')pausesubplot(2,1,1)k=0:1:M-1;stem(k,abs(U))title('MagnitudeoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Magnitude')subplot(2,1,2)stem(k,angle(U))title('PhaseoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Phase')21title('Originaltime-domainse2222例5.4

用matlab計(jì)算IDFT%Program5_2%IllustrationofIDFTComputation%ReadinthelengthKoftheDFTandthedesired%lengthNoftheIDFTK=input('TypeinthelengthoftheDFT=');N=input('TypeinthelengthoftheIDFT=');%Generatethelength-KDFTsequencek=0:K-1;V=k/K;%ComputeitsN-pointIDFTv=ifft(V,N);23例5.4用matlab計(jì)算IDFT%Program5%PlottheDFTanditsIDFTstem(k,V)xlabel('Frequencyindexk');ylabel('Amplitude')title('OriginalDFTsamples')pausesubplot(2,1,1)n=0:N-1;stem(n,real(v))title('Realpartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')subplot(2,1,2)stem(n,imag(v))title('Imaginarypartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')24%PlottheDFTanditsIDFT2425255.3FT與DFT之間的關(guān)系一.DFT與DTFT之間的關(guān)系長(zhǎng)度為N的序列的DTFT為：在=[0，2]對(duì)X(ej

)進(jìn)行的N點(diǎn)等間隔采樣：265.3FT與DFT之間的關(guān)系一.DFT與DTFT之間說(shuō)明：x(n)的N點(diǎn)DFT是x(n)的Z變換在單位圓上的N點(diǎn)等間隔采樣。X(k)為x(n)的傅立葉變換X(ej)在區(qū)間[0，2]上的N點(diǎn)等間隔采樣。27說(shuō)明：275.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉變換的數(shù)值計(jì)算已知,其傅立葉變換為希望以頻率間隔來(lái)估計(jì)，其中解：定義新序列285.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉則：上式是M點(diǎn)序列xe[n]的M點(diǎn)DFT序列Xe[k]5.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉變換的數(shù)值計(jì)算29則：上式是M點(diǎn)序列xe[n]的M點(diǎn)DFT序列Xe[k]5.5.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉變換的數(shù)值計(jì)算例5.5使用matlab計(jì)算DTFT程序5_3.m%Program5_3%NumericalComputationofFouriertransformUsingDFTk=0:15;w=0:511;x=cos(2*pi*k*3/16);%Generatethelength-16sinusoidalsequence305.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉%Computeits16-pointDFTX=fft(x);

%Computeits512-pointDFTXE=fft(x,512);%Plotthefrequencyresponseandthe16-%pointDFTsamplesplot(k/16,abs(X),'o',w/512,abs(XE))xlabel('\omega/\pi');ylabel('Magnitude')例5.5使用matlab計(jì)算DTFT程序5_3.m31%Computeits16-pointDFT例5.例-5_3.m

如下所示：5.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉變換的數(shù)值計(jì)算32例-5_3.m如下所示：5.3FT與DFT之間5.3FT與DFT之間的關(guān)系三.通過(guò)插值由DFT獲得傅立葉變換給定，其N點(diǎn)DFT序列通過(guò)唯一地確定335.3FT與DFT之間的關(guān)系三.通過(guò)插值由DFT獲得所以：34所以：345.3FT與DFT之間的關(guān)系四.傅立葉變換的抽樣——頻域采樣定理為了便于計(jì)算機(jī)計(jì)算,一般采取在頻率域采樣的方法,來(lái)計(jì)算有限長(zhǎng)序列的傅立葉變換。那么,是否任何一個(gè)序列的頻譜（或任何一個(gè)頻率特性）都能用頻率抽樣的方法去逼近呢?其限制條件是什么?0355.3FT與DFT之間的關(guān)系四.傅立葉變換的抽樣——頻域采樣定理推導(dǎo)過(guò)程:設(shè)任意序列x[n]存在傅立葉變換問(wèn)題在于這樣采樣以后是否能恢復(fù)出原序列x[n]對(duì)在上的N個(gè)均分點(diǎn)采樣,則得到36頻域采樣定理推導(dǎo)過(guò)程:設(shè)任意序列x[n]存在傅立葉變換問(wèn)經(jīng)推導(dǎo)得說(shuō)明：

在的N點(diǎn)等間隔采樣

X[k]的IDFT為：原序列x[n]以N為周期的周期延拓序列的主值序列.頻域抽樣造成時(shí)域信號(hào)的周期延拓,其延拓周期為采樣點(diǎn)數(shù)N.若x[n]不是有限長(zhǎng)的,則延拓后必然造成混迭現(xiàn)象,若x[n]

是有限長(zhǎng)的,長(zhǎng)度為M,當(dāng)抽樣點(diǎn)數(shù)不夠密時(shí)(N<M),也會(huì)造成混迭現(xiàn)象.37經(jīng)推導(dǎo)得說(shuō)明：37頻域抽樣定理如果序列x[n]的長(zhǎng)度為M,則只有當(dāng)頻域抽樣點(diǎn)數(shù)N滿足即可由X[k]恢復(fù)出原序列x[n]才有38頻域抽樣定理如果序列x[n]的長(zhǎng)度為M,則只有當(dāng)頻域抽樣點(diǎn)數(shù)時(shí)域抽樣與頻域抽樣的比較造成頻域函數(shù)的周期延拓，周期為造成時(shí)域函數(shù)的周期延拓，周期為頻域抽樣時(shí)域抽樣39時(shí)域抽樣與頻域抽樣的比較造成頻域函數(shù)的周期延拓，周期為造成時(shí)長(zhǎng)為M序列x[n]的周期延拓:當(dāng)N>=Mn0n0n0n040長(zhǎng)為M序列x[n]的周期延拓:當(dāng)N>=Mn0n0n0n040當(dāng)N<=M0n0nn0-8n0n08n41當(dāng)N<=M0n0nn0-8n0n08n415.4有限長(zhǎng)序列的運(yùn)算5.4.1序列的圓周移位若希望對(duì)移位，該序列仍在區(qū)間

0≤n≤N-1內(nèi)。這種移位稱為圓周移位（或循環(huán)移位）。圓周移位可以通過(guò)模運(yùn)算實(shí)現(xiàn)。若令則其中使在[0,N-1]之間425.4有限長(zhǎng)序列的運(yùn)算5.4.1序列的圓周移位若希望5.4.1序列的圓周移位CircularShiftofaSequence圓周移位定義為:當(dāng)

n0>0(則它是一個(gè)右圓周移位),上式可以寫(xiě)為：435.4.1序列的圓周移位圓周移位定義為:當(dāng)n0>0(則5.4.1序列的圓周移位CircularShiftofaSequence一個(gè)有限長(zhǎng)序列的圓周移位圖示向右圓周移位n0

個(gè)抽樣周期等效于向左圓周移位N-n0

個(gè)抽樣周期445.4.1序列的圓周移位一個(gè)有限長(zhǎng)序列的圓周移位圖示向右圓x[n-1]x[n]沒(méi)圓周移位圓周移位5.4.1序列的圓周移位CircularShiftofaSequence45x[n-1]x[n]沒(méi)圓周移位圓周移位5.4.1序列的圓周循環(huán)移位的過(guò)程示意圖nnnnn46循環(huán)移位的過(guò)程示意圖nnnnn465.4.2圓周卷積CircularConvolution圓周卷積與線性卷積：考慮兩個(gè)長(zhǎng)度N的序列g(shù)[n]和h[n]它們的線性卷積是長(zhǎng)度為(2N-1)的序列yL[n]：g[n]和h[n]的圓周卷積是長(zhǎng)度為N的序列yc[n]475.4.2圓周卷積圓周卷積與線性卷積：考慮兩個(gè)長(zhǎng)度N的序列5.4.2圓周卷積CircularConvolution上面的運(yùn)算通常稱之為N點(diǎn)圓周卷積，表示為：N485.4.2圓周卷積上面的運(yùn)算通常稱之為N點(diǎn)圓周卷積，表示N計(jì)算圓周卷積5.4.2圓周卷積CircularConvolution49N計(jì)算圓周卷積5.4.2圓周卷積49圓周卷積的計(jì)算mmmm50圓周卷積的計(jì)算mmmm50mmmmmmm51mmmmmmm51nn5.4.2圓周卷積CircularConvolution4例5.7-確定兩個(gè)長(zhǎng)度為4的序列的圓周卷積:52nn5.4.2圓周卷積4例5.7-確定兩個(gè)長(zhǎng)度為4的序y[n]=6δ[n]+7δ[n-1]+6δ[n-2]+5δ[n-3]g[n]=δ[n]+2δ[n-1]+δ[n-3]h[n]=2δ[n]+2δ[n-1]+δ[n-2]+δ[n-3]h[m]g[m]g[m]g[m]g[m]g[m]y[0]6y[1]7y[2]6y[3]553y[n]=6δ[n]+7δ[n-1]+6δ[n-2]+5δ[4由上我們得到：5.4.2圓周卷積CircularConvolution結(jié)果為長(zhǎng)度為4的序列yC[n]：544由上我們得到：5.4.2圓周卷積結(jié)果為長(zhǎng)度為4的序列y同樣5.4.2圓周卷積CircularConvolution55同樣5.4.2圓周卷積555.4.2圓周卷積CircularConvolution565.4.2圓周卷積565.4.2圓周卷積CircularConvolution可用矩陣形式表示：矩陣中每一行的元素，都是將上一行元素向右圓周移位一位得到的。575.4.2圓周卷積可用矩陣形式表示：矩陣中每一行的元素，都5.5有限長(zhǎng)序列的分類5.5.1基于共軛對(duì)稱的分類當(dāng)N為偶數(shù)時(shí)，將上式中的n換成N/2-n,得有限長(zhǎng)共軛對(duì)稱序列和共軛反對(duì)稱序列585.5有限長(zhǎng)序列的分類5.5.1基于共軛對(duì)稱的分類當(dāng)Nnn0123456759nn0123456759任一有限長(zhǎng)序列x[n]可以表示如下其中，60任一有限長(zhǎng)序列x[n]可以表示如下其中，605.5有限長(zhǎng)序列的分類5.5.2幾何對(duì)稱分類對(duì)于長(zhǎng)度為N的實(shí)序列，對(duì)稱分為兩類：對(duì)稱序列：N=7（奇數(shù)）063nN=8（偶數(shù)）063n1型：奇長(zhǎng)度對(duì)稱序列2型：偶長(zhǎng)度對(duì)稱序列615.5有限長(zhǎng)序列的分類5.5.2幾何對(duì)稱分類對(duì)于長(zhǎng)度為5.5有限長(zhǎng)序列的分類5.5.2幾何對(duì)稱分類反對(duì)稱序列：N=8（偶數(shù)）N=7（奇數(shù)）063n073n3型：奇長(zhǎng)度反對(duì)稱序列4型：偶長(zhǎng)度反對(duì)稱序列625.5有限長(zhǎng)序列的分類5.5.2幾何對(duì)稱分類反對(duì)稱序列5.6DFT對(duì)稱關(guān)系設(shè)是x[n]的復(fù)共軛序列，長(zhǎng)度為N，且

則且同理一.復(fù)序列的DFT635.6DFT對(duì)稱關(guān)系設(shè)是x[n]的復(fù)共軛序5.6DFT對(duì)稱關(guān)系二.DFT的對(duì)稱性其中則（1）如果645.6DFT對(duì)稱關(guān)系二.DFT的對(duì)稱性其中則（1）如其中則（2）如果65其中則（2）如果65總結(jié)如果x[n]的DFT為X[k]，則X[n]的實(shí)部和虛部（包括j）的DFT分別為X[k]的共軛對(duì)稱分量和共軛反對(duì)稱分量；X[n]的共軛對(duì)稱分量和的共軛反對(duì)稱分量的DFT分別為X[k]的實(shí)部和虛部（包括j）DFT的共軛對(duì)稱性66總結(jié)DFT的共軛對(duì)稱性66復(fù)序列的離散傅立葉變換的對(duì)稱關(guān)系序列離散時(shí)間傅立葉變換

67復(fù)序列的離散傅立葉變換的對(duì)稱關(guān)系序列實(shí)序列的離散傅立葉變換的對(duì)稱關(guān)系序列離散時(shí)間傅立葉變換

對(duì)稱關(guān)系

68實(shí)序列的離散傅立葉變換的對(duì)稱關(guān)系序列性質(zhì)長(zhǎng)度為N的序列N點(diǎn)離散傅立葉變換

5.7離散傅立葉變換定理

線性

圓周時(shí)移圓周頻移圓周卷積相乘

帕斯瓦爾公式對(duì)偶性69性質(zhì)有限長(zhǎng)序列的圓周移位在頻域中只引入一個(gè)和頻率成正比的線性相移

對(duì)頻譜的幅度沒(méi)有影響。2.圓周時(shí)移定理DFT70有限長(zhǎng)序列的圓周移位在頻域中只引入對(duì)頻譜的幅度沒(méi)有影響。2.3.圓周頻移定理DFT時(shí)域序列的調(diào)制等效于頻域的圓周移位。即乘以，則離散傅立葉變換向右圓周移位位，相當(dāng)于將進(jìn)行復(fù)調(diào)制，其結(jié)果使整個(gè)頻譜產(chǎn)生搬移。713.圓周頻移定理DFT時(shí)域序列的調(diào)制等效于頻域的圓周移位。74.圓周卷積定理DFTN點(diǎn)DFTN點(diǎn)DFTIDFT可以利用DFT求圓周卷積，思路如圖：724.圓周卷積定理DFTN點(diǎn)DFTN點(diǎn)DFTIDFT可以利用Dnng[n]的DFTG[k]長(zhǎng)度為4，表達(dá)如下：例5.11用DFT計(jì)算圓周卷積73nng[n]的DFTG[k]長(zhǎng)度為4，表達(dá)如下：例5.因此同樣例5.11用DFT計(jì)算圓周卷積74因此同樣例5.11用DFT計(jì)算圓周卷積74因此,兩個(gè)4點(diǎn)長(zhǎng)的序列的DFT還可以通過(guò)矩陣運(yùn)算得到。例5.11用DFT計(jì)算圓周卷積75因此,兩個(gè)4點(diǎn)長(zhǎng)的序列的DFT還可以通過(guò)矩陣運(yùn)算得到。例D4是長(zhǎng)度為4的DFT矩陣?yán)镁仃囘\(yùn)算求兩個(gè)4點(diǎn)長(zhǎng)的序列的DFT例5.11用DFT計(jì)算圓周卷積76D4是長(zhǎng)度為4的DFT矩陣?yán)镁仃囘\(yùn)算求兩個(gè)4點(diǎn)長(zhǎng)的序若YC[k]是長(zhǎng)度為4的序列yC[n]的DFT，則：因此：

例5.11用DFT計(jì)算圓周卷積77若YC[k]是長(zhǎng)度為4的序列yC[n]的DFT，例5YC[k]的IDFT如下：例5.11用DFT計(jì)算圓周卷積Matlab中圓周卷積函數(shù)：circonv78YC[k]的IDFT如下：例5.11用DFT計(jì)算圓5.9實(shí)序列的DFT計(jì)算在絕大多數(shù)應(yīng)用中，我們感興趣的是實(shí)序列。利用DFT的性質(zhì)可以提高實(shí)序列DFT的計(jì)算效率。一.用N點(diǎn)DFT計(jì)算兩個(gè)實(shí)序列的DFT和為長(zhǎng)度為N的實(shí)序列，以下是高效算法：設(shè)：，則根據(jù)DFT的對(duì)稱性可知：795.9實(shí)序列的DFT計(jì)算在絕大多數(shù)應(yīng)用中，我們感興趣的5.9實(shí)序列的DFT計(jì)算所以：805.9實(shí)序列的DFT計(jì)算所以：80二.用N點(diǎn)DFT計(jì)算2N點(diǎn)實(shí)序列的DFT5.9實(shí)序列的DFT計(jì)算設(shè)81二.用N點(diǎn)DFT計(jì)算2N點(diǎn)實(shí)序列的DFT5.9實(shí)序列的5.10用DFT實(shí)現(xiàn)線性卷積LinearConvolutionUsingtheDFT在絕大多數(shù)信號(hào)處理領(lǐng)域中，線性卷積都是很重要的一種運(yùn)算。因而運(yùn)用DFT實(shí)現(xiàn)線性卷積的方法就變得很有研究意義。825.10用DFT實(shí)現(xiàn)線性卷積在絕大多數(shù)信號(hào)處理領(lǐng)域中，例5.12nn求：83例5.12nn求：83有限長(zhǎng)序列存在兩種形式的卷積線性卷積：實(shí)際系統(tǒng)的輸出y[n]=x[n]*h[n]循環(huán)卷積：與DFT相對(duì)應(yīng)，有快速算法問(wèn)題：如何用循環(huán)卷積代替線性卷積？設(shè)h(n)和x(n)都是有限長(zhǎng)序列，長(zhǎng)度分別為N和M長(zhǎng)度為N+M

-1的有限長(zhǎng)序列將h[n]和x

[n]均視為長(zhǎng)度為L(zhǎng)的有限長(zhǎng)序列L>=max[N,M]84有限長(zhǎng)序列存在兩種形式的卷積線性卷積：實(shí)際系統(tǒng)的輸出y[n]循環(huán)卷積和線性卷積的關(guān)系設(shè)h(n)和x(n)都是有限長(zhǎng)序列，長(zhǎng)度分別為N和M其中，L>=max[N,M],所以，85循環(huán)卷積和線性卷積的關(guān)系設(shè)h(n)和x(n)都是有限對(duì)照式可知，即86對(duì)照式可知，即86經(jīng)推導(dǎo)可得可見(jiàn)是以L為周期，進(jìn)行延拓后，在0~L-1范圍內(nèi)所取的主值序列。若則循環(huán)卷積和線性卷積的關(guān)系87經(jīng)推導(dǎo)可得可見(jiàn)是5.10用DFT實(shí)現(xiàn)線性卷積

LinearConvolutionUsingtheDFT令g[n]和h[n]為長(zhǎng)度為N和M的有限長(zhǎng)序列其中L=N+M-1定義兩個(gè)長(zhǎng)度為L(zhǎng)的序列：885.10用DFT實(shí)現(xiàn)線性卷積

LinearConvolut5.10用DFT實(shí)現(xiàn)線性卷積

LinearConvolutionUsingtheDFT因此，yL[n]=g[n]*h[n]=yC[n]=ge[n]*he[n]圖示如下：895.10用DFT實(shí)現(xiàn)線性卷積

LinearConvolut5.10.2有限長(zhǎng)序列和無(wú)限長(zhǎng)序列的線性卷積LinearConvolutionofaFinite-LengthSequencewithanInfinite-LengthSequence建立一種基于DFT的方法：*h[n]是一個(gè)長(zhǎng)度為

M的有限長(zhǎng)序列，x[n]是一個(gè)無(wú)限長(zhǎng)序列(或者是長(zhǎng)度遠(yuǎn)大于M的有限長(zhǎng)序列)905.10.2有限長(zhǎng)序列和無(wú)限長(zhǎng)序列的線性卷積LinearC重疊相加法

Overlap-AddMethod其中首先分割

x[n],（假設(shè)是因果序列），得到一組長(zhǎng)度為

N的連續(xù)有限長(zhǎng)子序列xm[n]:91重疊相加法

Overlap-AddMethod其中首先分割分割

x[n],

例如N=792分割x[n],例如N=792*其中*因?yàn)?/p>

h[n]的長(zhǎng)度是

M，

xm[n]的長(zhǎng)度是N,所以線性卷積的長(zhǎng)度是

N+M-1重疊相加法

Overlap-AddMethod因此，93*其中*因?yàn)閔[n]的長(zhǎng)度是M，xm[n]的長(zhǎng)度是

結(jié)果是，y[n]被分成了無(wú)限個(gè)長(zhǎng)度為N+M-1的短長(zhǎng)度的線性卷積的和。每個(gè)短卷積ym[n]都可利用DFT求得，其中DFT（和IDFT）在N+M-1個(gè)點(diǎn)的基礎(chǔ)上進(jìn)行計(jì)算。

*重疊相加法

Overlap-AddMethod*94結(jié)果是，y[n]被分成了無(wú)限個(gè)長(zhǎng)度為N+M-1*重疊長(zhǎng)度是

N+M-1，定義在區(qū)間

0≤n≤N+M-2**重疊相加法

Overlap-AddMethod中的第一個(gè)短卷積:95長(zhǎng)度是N+M-1，**重疊相加法

Overlap-Add長(zhǎng)度是

N+M-1，疊加區(qū)間

N

≤n≤N+M-2**重疊相加法

Overlap-AddMethod中的第二個(gè)短卷積:96長(zhǎng)度是N+M-1，**重疊相加法

Overlap-Add重疊相加法

Overlap-AddMethod這表明這兩個(gè)短線性卷積之間有M-1個(gè)樣本是重疊的。

同樣,第三個(gè)短卷積是

長(zhǎng)度是N+M-1

疊加區(qū)間2N≤n≤2N+M-2**97重疊相加法

Overlap-AddMethod這表明這兩個(gè)重疊相加法

Overlap-AddMethod通常,在短卷積和疊加時(shí)，會(huì)有M-1個(gè)樣本的重疊，重疊的范圍為

rN≤n≤rN+M-2**98重疊相加法

Overlap-AddMethod通常,在短例如M=5和N=799例如M=5和N=799AddAdd例如M=5和N=7100AddAdd例如M=5和N=7100因此，通過(guò)x[n]和h[n]的線性卷積得到的期望序列y[n]：重疊相加法

Overlap-AddMethod101因此，通過(guò)x[n]和h[n]的線性卷積得到的期望序列y[由于短線性卷積的結(jié)果重疊，且需要將重疊部分加起來(lái)得到正確的最后結(jié)果，所以上面的實(shí)現(xiàn)過(guò)程稱為重疊相加法M文件fftfilt可以用來(lái)實(shí)現(xiàn)上面的方法。重疊相加法

Overlap-AddMethod102由于短線性卷積的結(jié)果重疊，且需要將重疊部分加起來(lái)得到正確的最快速傅立葉變換(FFT)1.FFT是DFT的一種快速算法2.提出與發(fā)展由庫(kù)利(J.K.Cooly)和圖基(J.KTuky)相繼出現(xiàn)了桑得(G.Sand)-圖基等快速算法3.價(jià)值使運(yùn)算效率提高了1~2個(gè)數(shù)量級(jí)推動(dòng)了數(shù)字信號(hào)處理技術(shù)的應(yīng)用和發(fā)展103快速傅立葉變換(FFT)1.FFT是DFT的一種快速算法2直接計(jì)算DFT的問(wèn)題及改進(jìn)的方法DFT的定義兩者形式類似，差別只在于的指數(shù)符號(hào)不同，及常數(shù)因子。運(yùn)算量是相同的104直接計(jì)算DFT的問(wèn)題及改進(jìn)的方法DFT的定義兩者形式類似，差（1）正變換的運(yùn)算量每計(jì)算一個(gè)點(diǎn)的X[k]需要N次復(fù)數(shù)乘法,(N-1)次復(fù)數(shù)加法計(jì)算N點(diǎn)X[k],則需要N2次復(fù)數(shù)乘法，N(N-1)次復(fù)數(shù)加法因?yàn)榫鶠閺?fù)數(shù)105（1）正變換的運(yùn)算量每計(jì)算一個(gè)點(diǎn)的X[k]需要N次復(fù)數(shù)乘法,（2）減少運(yùn)算量的途徑對(duì)稱性周期性具有如下特性：利用這些特性：1.使DFT運(yùn)算中的有些項(xiàng)可以合并。2.可將長(zhǎng)序列的DFT分解為短序列的DFT。106（2）減少運(yùn)算量的途徑對(duì)稱性周期性具有如下特性：利用這些特性FFT的基本思想在于：將原有的N點(diǎn)序列分成兩個(gè)較短的序列;兩個(gè)序列的DFT組合起來(lái),得出原序列的DFT。基2FFT基本原理FFT算法分為兩大類:時(shí)域抽取法(DIT)頻域抽取法(DIF)107FFT的基本思想在于：基2FFT基本原理FFT算法分為兩大設(shè)M為自然數(shù)將長(zhǎng)度為N的序列x[n]按n的奇偶分成兩組則x[n]的DFT為時(shí)域抽取法基本原理108設(shè)M為自然數(shù)將長(zhǎng)度為N的序列x[n]按n的奇偶分成兩組則x[由于所以時(shí)域抽取法基本原理式中，是x[2r]與x[2r+1]的N/2點(diǎn)DFT。109由于所以時(shí)域抽取法基本原理式中，是x[2r]與x[2r+1]上式可見(jiàn):一個(gè)N點(diǎn)DFT已分解為兩個(gè)N/2點(diǎn)的DFTX0[k]與X1[k]的組合。但得到的是X

[k]的前一半項(xiàng)。要用X0[k]，X1[k]表達(dá)全部的X[k]，必須應(yīng)用旋轉(zhuǎn)因子的周期性時(shí)域抽取法基本原理110上式可見(jiàn):一個(gè)N點(diǎn)DFT已分解為兩個(gè)N/2點(diǎn)的DFTX0[由于將下式自變量k變?yōu)閗+N/2得時(shí)域抽取法基本原理111由于將下式自變量k變?yōu)閗+N/2得時(shí)域抽取法基本原理111X

[k]的后半部分為：再考慮到旋轉(zhuǎn)因子的對(duì)稱性所以只要求出0～N/2-1區(qū)間上X0[k]與X1[k]的值，即可得到0～N-1區(qū)間內(nèi)所有X

[k]的值。時(shí)域抽取法基本原理112X[k]的后半部分為：再考慮到旋轉(zhuǎn)因子的對(duì)稱性所以只要求出時(shí)域抽取法基本原理用0～N/2-1區(qū)間上X0[k]與X1[k]的值，表示0～N-1區(qū)間內(nèi)所有X

[k]的值：另外的描述方法：113時(shí)域抽取法基本原理用0～N/2-1區(qū)間上X0[k]與X1[k時(shí)域抽取法的框圖解釋N/2-pointDFTN/2-pointDFT22z2x[n]x0[n]=x[2n]2x[n]x1[n]=x[2n+1]zx[n+1]時(shí)域抽取法基本原理114時(shí)域抽取法的框圖解釋N/2-pointN/2-point2X

[k]的運(yùn)算可用蝶形信號(hào)流圖表示時(shí)域抽取法基本原理115X[k]的運(yùn)算可用蝶形信號(hào)流圖表示時(shí)域抽取法基本原理1153時(shí)域抽取法基本原理1163時(shí)域抽取法基本原理116計(jì)算一個(gè)蝶形，需要1次復(fù)乘，2次復(fù)加每個(gè)N/2點(diǎn)的DFT需要（N/2)2次復(fù)數(shù)乘，N/2(N/2-1)次復(fù)數(shù)加兩個(gè)N/2點(diǎn)的DFT需要N2/2次復(fù)數(shù)乘，N(N/2-1)次復(fù)數(shù)加將兩個(gè)N/2點(diǎn)的DFT合并成N點(diǎn)DFT，有N/2個(gè)蝶形運(yùn)算，還需要N/2次復(fù)數(shù)乘及N次復(fù)數(shù)加計(jì)算N點(diǎn)DFT共需要N2/2＋N/2N2/2次復(fù)數(shù)乘

N(N/2-1)＋NN2/2次復(fù)數(shù)加只分解一次運(yùn)算量就減少一半這種分解方法可一直進(jìn)行到左側(cè)為兩點(diǎn)DFT為止時(shí)域抽取法基本原理117計(jì)算一個(gè)蝶形，需要1次復(fù)乘，2次復(fù)加時(shí)域抽取法基本原理117其中X00[k]和X01[k]分別是由序列x0[n]的偶數(shù)和奇數(shù)序號(hào)樣本產(chǎn)生的長(zhǎng)為(N/4)的序列x00[n]和x01[n]的(N/4)點(diǎn)DFT：

x00[n]=x0[2n],x01[n]=x0[2n+1]時(shí)域抽取法基本原理設(shè)N/2是偶數(shù)。我們將上面的兩個(gè)(N/2)點(diǎn)離散傅里葉變換X0[k]和X1[k]，表示成兩個(gè)(N/4)點(diǎn)的DFT加權(quán)和，例如將X0[k]表示為：118其中X00[k]和X01[k]分別是由序列x0[n]的偶與第一次分解相同，將x0[n]按n的奇偶分成兩個(gè)長(zhǎng)為N/4的子序列：且119與第一次分解相同，將x0[n]按n的奇偶分成兩個(gè)長(zhǎng)為N/4的其中

X10[k]和X11[k]分別由序列x1[n]的偶數(shù)和奇數(shù)序號(hào)樣本產(chǎn)生的長(zhǎng)為(N/4)的序列x10[n]和x11[n]的(N/4)點(diǎn)DFT：

x10[n]=x1[2n],x11[n]=x1[2n+1]時(shí)域抽取法基本原理同樣120其中X10[k]和X11[k]分別由序列x1[n]其中，將旋轉(zhuǎn)因子統(tǒng)一為，則一個(gè)N點(diǎn)DFT就可分解為4個(gè)N/4點(diǎn)的DFT.也可以進(jìn)行同樣的處理，得到X1[k]121其中，將旋轉(zhuǎn)因子統(tǒng)一為按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm方塊圖所示：222222zzz122按時(shí)間抽取FFT算法

Decimation-in-Time下面圖形表示FFT在時(shí)域所作的分解（1）8點(diǎn)長(zhǎng)時(shí)間信號(hào)（2）4點(diǎn)長(zhǎng)信號(hào)（3）2點(diǎn)長(zhǎng)信號(hào)012345670246135704261537按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm123下面圖形表示FFT在時(shí)域所作的分解（1）8點(diǎn)長(zhǎng)時(shí)間信號(hào)（2兩次抽取的蝶形圖按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm124兩次抽取的蝶形圖按時(shí)間抽取FFT算法

Decimation-在上圖所示的流圖中，N=8從而，(N/4)-點(diǎn)DFT即為2-點(diǎn)DFT并且不可能再進(jìn)一步分解；這四個(gè)2-點(diǎn)DFT—Xij[k],i,j=0,1很容易計(jì)算。例如：按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm125在上圖所示的流圖中，N=8按時(shí)間抽取FFT算法

Deci利用下面的恒等式，可以獲得2-點(diǎn)DFT的流圖：按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm126利用下面的恒等式，可以獲得2-點(diǎn)DFT的流圖：按時(shí)間抽取F按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithmN=8時(shí)按時(shí)間抽取FFT算法的完整流圖127按時(shí)間抽取FFT算法

Decimation-in-Time 這些性質(zhì)可用來(lái)進(jìn)一步降低計(jì)算的復(fù)雜度。在得出該總數(shù)的過(guò)程中,考慮:和的相乘也為復(fù)數(shù)對(duì)稱性按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm128 這些性質(zhì)可用來(lái)進(jìn)一步降低計(jì)算的復(fù)雜度。在得出該總數(shù)的過(guò)改進(jìn)的蝶形，減少?gòu)?fù)數(shù)乘129改進(jìn)的蝶形，減少?gòu)?fù)數(shù)乘129改進(jìn)的按時(shí)間抽取FFT算法流圖（書(shū)圖11.24）130改進(jìn)的按時(shí)間抽取FFT算法流圖（書(shū)圖11.24）130當(dāng)時(shí)，可分解為M級(jí)蝶形，每級(jí)都有N/2個(gè)蝶形運(yùn)算。每一級(jí)N/2次復(fù)數(shù)乘；N次復(fù)數(shù)加。則M級(jí)次復(fù)數(shù)乘次復(fù)數(shù)加與直接計(jì)算DFT的運(yùn)算量之比DIT-FFT算法運(yùn)算量131當(dāng)時(shí)，可分解為M級(jí)蝶形，每級(jí)都有N/2個(gè)蝶形運(yùn)算。每一級(jí)NDIT-FFT算法運(yùn)算量132DIT-FFT算法運(yùn)算量132按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm上述改進(jìn)的FFT算法的另一個(gè)吸引人的特性是存儲(chǔ)要求。這種類型的存儲(chǔ)位置共享特性通常稱之為同址計(jì)算，結(jié)果明顯節(jié)省了整個(gè)算法的存儲(chǔ)要求。133按時(shí)間抽取FFT算法

Decimation-in-Time按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm當(dāng)DFT樣本X[k]在輸出端順序排列時(shí)，輸入時(shí)域樣本x[n]則以一個(gè)不同的順序排列。134按時(shí)間抽取FFT算法

Decimation-in-Time按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm因此,在開(kāi)始用上面描述的FFT算法運(yùn)算以前，必須重新排列順序結(jié)構(gòu)輸入的x[n]

用二進(jìn)制形式表示輸入樣本點(diǎn)x[n]和它們順序重新排列后的樣本點(diǎn)，則可得到m和n之間有如下關(guān)系：135按時(shí)間抽取FFT算法

Decimation-in-Time按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithmm:000001010011100101110111n:000100010110001101011111設(shè)(b2b1b0)代表輸入序列x[n]于二進(jìn)制的序號(hào)n。

則在開(kāi)始進(jìn)行DFT計(jì)算之前，樣本x[b2b1b0]在位置m=b0b1b2輸出是原輸入序列的倒序列。136按時(shí)間抽取FFT算法

Decimation-in-Time1、原位計(jì)算（就地算法）DIT-FFT的運(yùn)算規(guī)律及編程思想3、蝶形運(yùn)算規(guī)律及編程思想2、旋轉(zhuǎn)因子的變化規(guī)律4、倒位序規(guī)律5、倒位序?qū)崿F(xiàn)1371、原位計(jì)算（就地算法）DIT-FFT的運(yùn)算規(guī)律及編程思想3DIT-FFT的運(yùn)算規(guī)律及編程思想1.原位計(jì)算（就地算法）用同一地址既存輸入序列又存輸出序列的算法。如圖11.24，每級(jí)運(yùn)算由N/2個(gè)蝶形構(gòu)成，每個(gè)蝶形完成下述基本運(yùn)算：式中L代表第L級(jí)蝶形運(yùn)算。J、J+B代表數(shù)據(jù)所在行。B表示蝶形運(yùn)算的兩個(gè)輸入相距B個(gè)點(diǎn)。138DIT-FFT的運(yùn)算規(guī)律及編程思想1.原位計(jì)算（就地算法）運(yùn)算規(guī)律DIT-FFT的運(yùn)算規(guī)律及編程思想每個(gè)蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)又在同一水平線上。這樣，蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸入所在的存儲(chǔ)器中。每列的N/2個(gè)蝶形運(yùn)算全部完成后，再開(kāi)始下一列的蝶形運(yùn)算。下一列仍采用原位運(yùn)算，只是進(jìn)入蝶形的組合關(guān)系有所不同。139運(yùn)算規(guī)律DIT-FFT的運(yùn)算規(guī)律及編程思想每個(gè)蝶形運(yùn)算的兩個(gè)DIT-FFT的運(yùn)算規(guī)律及編程思想2.旋轉(zhuǎn)因子的變化規(guī)律觀察圖11.24，第L級(jí)共有2L-1個(gè)不同的旋轉(zhuǎn)因子。稱為旋轉(zhuǎn)因子，p稱為旋轉(zhuǎn)因子的指數(shù)。級(jí)(L):從左到右的運(yùn)算級(jí)數(shù)。(L=1,2,…M)140DIT-FFT的運(yùn)算規(guī)律及編程思想2.旋轉(zhuǎn)因子旋轉(zhuǎn)因子與級(jí)數(shù)（L）的關(guān)系更一般地第L級(jí)的旋轉(zhuǎn)因子為DIT-FFT的運(yùn)算規(guī)律及編程思想141旋轉(zhuǎn)因子與級(jí)數(shù)（L）的關(guān)系更一般地第L級(jí)的旋轉(zhuǎn)因子為DI蝶形運(yùn)算兩輸入點(diǎn)間距離為：第1級(jí)：1第2級(jí)：2第3級(jí)：4第L級(jí)：2L-1

每一級(jí)的兩個(gè)輸入節(jié)點(diǎn)進(jìn)行蝶形運(yùn)算后，得到下一級(jí)的相同序號(hào)的兩個(gè)輸出節(jié)點(diǎn)。DIT-FFT的運(yùn)算規(guī)律及編程思想3.蝶形運(yùn)算規(guī)律142蝶形運(yùn)算兩輸入點(diǎn)間距離為：第1級(jí)：1第2級(jí)：2對(duì)于每個(gè)旋轉(zhuǎn)因子，有2M-L個(gè)蝶形運(yùn)算。第一個(gè)蝶形的第一個(gè)輸入所在行為J，第二個(gè)蝶形的第一個(gè)輸入所在行為J+2L，相鄰兩個(gè)蝶形運(yùn)算第一個(gè)輸入相距2L。DIT-FFT的運(yùn)算規(guī)律及編程思想143對(duì)于每個(gè)旋轉(zhuǎn)因子，有2M-L個(gè)蝶形運(yùn)算。DIT-FFT的運(yùn)算編程思想先從輸入端開(kāi)始，逐級(jí)進(jìn)行計(jì)算，共進(jìn)行M級(jí)運(yùn)算。在進(jìn)行第L級(jí)運(yùn)算時(shí)，依次求出2L-1個(gè)不同的旋轉(zhuǎn)因子，每求一個(gè)旋轉(zhuǎn)因子，就計(jì)算完它對(duì)應(yīng)的所有2M-L個(gè)蝶形。DIT-FFT的運(yùn)算規(guī)律及編程思想144編程思想先從輸入端開(kāi)始，逐級(jí)進(jìn)行計(jì)算，共進(jìn)行M級(jí)運(yùn)算。DIT開(kāi)始輸入x(n),MN=2M倒序L=1,MB2L-1J=0,B-1P=2M-L.Jk=J,N-1,2L輸出結(jié)束L表示運(yùn)算級(jí)數(shù)旋轉(zhuǎn)因子個(gè)數(shù)對(duì)旋轉(zhuǎn)因子計(jì)數(shù)計(jì)算旋轉(zhuǎn)因子指數(shù)每個(gè)旋轉(zhuǎn)因子對(duì)應(yīng)2M-L個(gè)蝶形運(yùn)算。兩個(gè)蝶形運(yùn)算第一個(gè)輸入點(diǎn)‘距離’是2L145開(kāi)始輸入x(n),MN=2M倒序L=1,MB2L4.倒位序規(guī)律若是三位二進(jìn)制數(shù)，則就是它的倒位序。按原位計(jì)算時(shí)，F(xiàn)FT的輸出X(k)是按自然順序存儲(chǔ)的，但這時(shí)輸入序列卻不是按自然順序存儲(chǔ)的。輸入序列初看起來(lái)，好象沒(méi)有規(guī)律，實(shí)際是按倒位序存儲(chǔ)的。DIT-FFT的運(yùn)算規(guī)律及編程思想1464.倒位序規(guī)律若是三位二進(jìn)制數(shù)，則就是它的倒位序。按原位計(jì)DIT-FFT的運(yùn)算規(guī)律及編程思想倒位序的形成00100011010111x(111)=x(7)x(000)=x(0)x(010)=x(2)x(110)=x(6)x(001)=x(1)x(101)=x(5)x(100)=x(4)造成倒位序的原因是輸入序列x(n)，按標(biāo)號(hào)n的奇偶不斷地分組造成的。x(011)=x(3)147DIT-FFT的運(yùn)算規(guī)律及編程思想倒位序的形成00100015.倒位序的實(shí)現(xiàn)DIT-FFT的運(yùn)算規(guī)律及編程思想（1）只要將順序二進(jìn)制數(shù)（n2n1n0）的二進(jìn)制位倒置，得（n0n1n2）。根據(jù)這種規(guī)律，容易用硬件電路和匯編語(yǔ)言產(chǎn)生倒位序數(shù)。（2）用高級(jí)語(yǔ)言程序?qū)崿F(xiàn)時(shí)，必須找出產(chǎn)生倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律。1485.倒位序的實(shí)現(xiàn)DIT-FFT的運(yùn)算規(guī)律及編程思想（1DIT-FFT的運(yùn)算規(guī)律及編程思想000000001

001

4

100201020103

011

6

1104

100

1

001510151016

110

3

01171117111左邊為按自然順序排列的二進(jìn)制數(shù)，下面的一個(gè)數(shù)是上面一個(gè)數(shù)的最低位上加上1，且向高位進(jìn)位。右邊為倒位序數(shù)，下面的一個(gè)數(shù)是上面一個(gè)數(shù)的最高位上加上1，且由高位向低位進(jìn)位。稱為反向進(jìn)位加法順序與倒序二進(jìn)制對(duì)照表可由當(dāng)前任一倒序值求得下一個(gè)倒序值149DIT-FFT的運(yùn)算規(guī)律及編程思想0000反向進(jìn)位加法的實(shí)現(xiàn)若已知某個(gè)倒位序數(shù)J，求下一個(gè)倒位序數(shù)，判斷J的最高位是否為“0”,讓J與N/2比較，因?yàn)镹/2總是100……,如果J<N/2,則J

的最高位為零,只需把該位變?yōu)?(J+N/2),就得到下一個(gè)倒位序數(shù),否則,把最高位變?yōu)?(J-N/2)判斷J的次高位是否為“0”,讓J與N/4比較，如果J

的次高位為零,只需把該位變?yōu)?(J+N/4),其它位不變,就得到下一個(gè)倒位序數(shù),否則,還需判斷下一位(與N/8比較),如此依次進(jìn)行下去,總會(huì)碰到某位為0,將此位改為1即可.DIT-FFT的運(yùn)算規(guī)律及編程思想150反向進(jìn)位加法的實(shí)現(xiàn)若已知某個(gè)倒位序數(shù)J，求下一個(gè)倒位序數(shù)，判按時(shí)間抽取FFT算法

Decimation-in-TimeFFTAlgorithm若對(duì)每一級(jí)序列以因子R抽取，則得到的FFT算法稱為基R快速傅立葉變換算法。如圖11.24為基2按時(shí)間抽取FFT算法圖11.25基4按時(shí)間抽取FFT算法第一級(jí)使用不同的抽取因子，稱為混合基快速傅立葉變換算法。151按時(shí)間抽取FFT算法

Decimation-in-Time與DIT相對(duì)應(yīng)，DIF算法是將頻域X[k]的序號(hào)k按奇偶分開(kāi)。推導(dǎo)過(guò)程:設(shè)M為自然數(shù)則x(n)的DFT為按頻域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm152與DIT相對(duì)應(yīng)，DIF算法是將頻域X[k]的序號(hào)k按奇偶分開(kāi)按頻域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm式中分別令k=2r,k=2r+1,r=0.1……,N/2-1153按頻域抽取FFT算法

Decimation-in-Frequ令則按頻域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm154令則按頻域抽取FFT算法

Decimation-in-Fre按頻域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithm由于N=2M，N/2仍然是偶數(shù)，繼續(xù)將N/2點(diǎn)的DFT分成偶數(shù)組和奇數(shù)組。這樣每個(gè)N/2點(diǎn)DFT可由兩個(gè)N/4點(diǎn)DFT形成。其輸入序列分別是x0(n)和x1(n)按上下對(duì)半分開(kāi)形成的四個(gè)子序列。該過(guò)程可以繼續(xù)，直到最小的DFT為2點(diǎn)DFT155按頻域抽取FFT算法

Decimation-in-Frequ按頻域抽取FFT算法

Decimation-in-FrequencyFFTAlgorithmN=8時(shí)頻率抽取FFT算法的完整流圖。156按頻域抽取FFT算法

Decimation-in-FrequIDFT算法

InverseDFTComputation計(jì)算DFT樣本的FFT算法，也可以有效地計(jì)算離散傅里葉逆變換(IDFT)考慮一個(gè)N點(diǎn)DFT為X[k]的N點(diǎn)序列

x[n]上式同時(shí)乘以

N并對(duì)其取復(fù)共軛157IDFT算法

InverseDFTComputatio所求的離散傅里葉逆變換x[n]為：{X[k]}ReRe{x[n]}Im{x[n]}Im{X[k]}N-pointDFTIDFT的計(jì)算過(guò)程如圖:IDFT算法

InverseDFTComputation158所求的離散傅里葉逆變換x[n]為：{X[k]}ReRe{作業(yè)閱讀教材p.234to264習(xí)題5.8,5.11,5.20,5.21,5.26,5.28,5.41M3.2,M3.8,M3.9159作業(yè)閱讀教材p.234to264159補(bǔ)充：周期序列的離散傅立葉級(jí)數(shù)及傅立葉變換一、周期序列的離散傅立葉級(jí)數(shù)式中是傅立葉級(jí)數(shù)的系數(shù)。設(shè)是以N為周期的周期序列，將其展成傅立葉級(jí)數(shù)，得為求ak,將上式兩邊乘以,并對(duì)n在一個(gè)周期N中求和。160補(bǔ)充：周期序列的離散傅立葉級(jí)數(shù)及傅立葉變換一、周期序列的離散正交函數(shù)集的條件推導(dǎo)過(guò)程：周期序列的離散傅立葉級(jí)數(shù)所以161正交函數(shù)集的條件推導(dǎo)過(guò)程：周期序列的離散傅立葉級(jí)數(shù)所以161因?yàn)槭侵芷跒镹的周期函數(shù)，所以也是周期為N的周期函數(shù)。周期序列的離散傅立葉級(jí)數(shù)設(shè)則將上式兩邊乘以,并對(duì)k在一個(gè)周期N中求和:162因?yàn)槭侵芷跒镹的周期函數(shù)，所以也是周期為N的周期函數(shù)。周期序周期序列的離散傅立葉級(jí)數(shù)所以163周期序列的離散傅立葉級(jí)數(shù)所以163周期序列的離散傅立葉級(jí)數(shù)DFS

在時(shí)域和頻域都是周期的且是離散的。只要知道周期序列的一個(gè)周期的內(nèi)容，則該序列的全部?jī)?nèi)容也就都知道了。離散周期序列的傅立葉級(jí)數(shù)

DFS164周期序列的離散傅立葉級(jí)數(shù)DFS在時(shí)域和頻域都是周期的且是周期序列的離散傅立葉級(jí)數(shù)連續(xù)傅立葉級(jí)數(shù)的基波成分為

k次諧波成分有無(wú)窮多個(gè)離散傅立葉級(jí)數(shù)的基波成分為k次諧波成分只有N個(gè)獨(dú)立分量連續(xù)傅立葉級(jí)數(shù)與離散傅立葉級(jí)數(shù)的比較返回165周期序列的離散傅立葉級(jí)數(shù)連續(xù)傅立葉級(jí)數(shù)的基波成分為k次諧166166167167第五章

有限長(zhǎng)離散變換

Finite-LengthdiscreteTransforms168第五章

有限長(zhǎng)離散變換

Finite-Lengthdi本章主要內(nèi)容離散傅立葉變換定義離散傅立葉變換性質(zhì)（與DTFT的關(guān)系，圓周移位和圓周卷積，DFT的對(duì)稱性，DFT定理）DFT的應(yīng)用（實(shí)序列的DFT計(jì)算，用DFT計(jì)算線性卷積）離散余弦變換169本章主要內(nèi)容離散傅立葉變換定義25.1正交變換對(duì)信號(hào)的分析思路是：找一個(gè)正交的函數(shù)集，從而將任意信號(hào)分解為該函數(shù)集上各個(gè)元素的線性組合。設(shè)是基本序列，長(zhǎng)度為N。則其滿足：稱為正交序列。1705.1正交變換對(duì)信號(hào)的分析思路是：找一個(gè)正交的函數(shù)集5.1正交變換正交變換對(duì)的一般形式：綜合式分析式將要討論的離散傅立葉變換是正交變換的一種。1715.1正交變換正交變換對(duì)的一般形式：綜合式分析式將要5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DTFT是離散時(shí)間信號(hào)的傅里葉變換，時(shí)域離散，頻域連續(xù)，周期為2。由于計(jì)算機(jī)只能處理數(shù)字信號(hào)，而不能處理連續(xù)信號(hào)，所以必須把信號(hào)連續(xù)的頻譜離散化。

1725.2離散傅里葉變換

DiscreteFourier

時(shí)域

頻域連續(xù)，非周期

FT連續(xù)，非周期連續(xù)，周期FST離散，非周期離散，非周期

DTFT周期，連續(xù)離散周期DFS離散周期5.2離散傅里葉變換

DiscreteFourierTransform(DFT)補(bǔ)充DFS內(nèi)容173時(shí)域已知周期沖激函數(shù)的傅立葉變換：T2T-T-2TδT(t)t0ω02ω0-ω0-2ω0ω0δω0(ω)0ωω0=2π/T174已知周期沖激函數(shù)的傅立葉變換：T2T-T-2TδT(t)t0周期化，離散化信號(hào)x(t)X(jω)P(jω)ω0ω0=2π/Tsx[nT]X(jω)q(t)TFTDFSDTFTQ(jω)Ω0……Ω0=

2π/TQ(jω)Ω0……Ω0=

2π/TP(t)Ts……175周期化，離散化信號(hào)x(t)X(jω)P(jω)ω0ω0=2π5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的定義時(shí)域中N點(diǎn)的序列x[n]的DFT1765.2離散傅里葉變換

DiscreteFourierDFT定義中引入一個(gè)常用的符號(hào)5.2離散傅里葉變換

DiscreteFourierTransform(DFT)證明IDFT表達(dá)式：證明：在兩邊同乘以WNln，從n=0到n=N-1作177DFT定義中引入一個(gè)常用的符號(hào)5.2離散傅里葉變換

Di5.2離散傅里葉變換

DiscreteFourierTransform(DFT)其中有：1785.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長(zhǎng)單點(diǎn)非零樣本的DFT計(jì)算其N點(diǎn)的DFT：1795.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長(zhǎng)單點(diǎn)非零樣本的DFT計(jì)算其N點(diǎn)DFT為：1805.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長(zhǎng)正弦序列的DFT計(jì)算解：1815.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長(zhǎng)正弦序列的DFT計(jì)算1825.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系可以重寫(xiě)為：DFT的定義1835.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系1845.2離散傅里葉變換

DiscreteFourier類似的,IDFT關(guān)系也可以表示為：5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系185類似的,IDFT關(guān)系也可以表示為：5.2離散傅里葉5.2.3用Matlab計(jì)算DFT

DFTComputationUsingMATLAB在matlab中有四個(gè)用來(lái)計(jì)算DFT和IDFT的內(nèi)置函數(shù)：fft(x),fft(x,M),ifft(X),ifft(X,M)在matlab信號(hào)處理工具箱中的函數(shù)dftmtx(N)用來(lái)計(jì)算NN階DFT矩陣DN例5.3

用matlab計(jì)算如下N點(diǎn)序列的M點(diǎn)DFT1865.2.3用Matlab計(jì)算DFT

DFTComput%Program5_1%IllustrationofDFTComputation%

ReadinthelengthNofsequenceandthe%desiredlengthMoftheDFTN=input('Typeinthelengthofthesequence=');M=input('TypeinthelengthoftheDFT=');%Generatethelength-Ntime-domainsequenceu=[ones(1,N)];%ComputeitsM-pointDFTU=fft(u,M);%Plotthetime-domainsequenceanditsDFTt=0:1:N-1;stem(t,u)187%Program5_120title('Originaltime-domainsequence')xlabel('Timeindexn');ylabel('Amplitude')pausesubplot(2,1,1)k=0:1:M-1;stem(k,abs(U))title('MagnitudeoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Magnitude')subplot(2,1,2)stem(k,angle(U))title('PhaseoftheDFTsamples')xlabel('Frequencyindexk');ylabel('Phase')188title('Originaltime-domainse18922例5.4

用matlab計(jì)算IDFT%Program5_2%IllustrationofIDFTComputation%ReadinthelengthKoftheDFTandthedesired%lengthNoftheIDFTK=input('TypeinthelengthoftheDFT=');N=input('TypeinthelengthoftheIDFT=');%Generatethelength-KDFTsequencek=0:K-1;V=k/K;%ComputeitsN-pointIDFTv=ifft(V,N);190例5.4用matlab計(jì)算IDFT%Program5%PlottheDFTanditsIDFTstem(k,V)xlabel('Frequencyindexk');ylabel('Amplitude')title('OriginalDFTsamples')pausesubplot(2,1,1)n=0:N-1;stem(n,real(v))title('Realpartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')subplot(2,1,2)stem(n,imag(v))title('Imaginarypartofthetime-domainsamples')xlabel('Timeindexn');ylabel('Amplitude')191%PlottheDFTanditsIDFT24192255.3FT與DFT之間的關(guān)系一.DFT與DTFT之間的關(guān)系長(zhǎng)度為N的序列的DTFT為：在=[0，2]對(duì)X(ej

)進(jìn)行的N點(diǎn)等間隔采樣：1935.3FT與DFT之間的關(guān)系一.DFT與DTFT之間說(shuō)明：x(n)的N點(diǎn)DFT是x(n)的Z變換在單位圓上的N點(diǎn)等間隔采樣。X(k)為x(n)的傅立葉變換X(ej)在區(qū)間[0，2]上的N點(diǎn)等間隔采樣。194說(shuō)明：275.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉變換的數(shù)值計(jì)算已知,其傅立葉變換為希望以頻率間隔來(lái)估計(jì)，其中解：定義新序列1955.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉則：上式是M點(diǎn)序列xe[n]的M點(diǎn)DFT序列Xe[k]5.3FT與DFT之間的關(guān)系二.使用DFT進(jìn)行傅立葉變換的數(shù)值計(jì)算196則：上式是M點(diǎn)序列xe[n]的M點(diǎn)DFT序列Xe[k]5.