有限長離散變換Finite課件

第五章

有限長離散變換

Finite-LengthdiscreteTransforms1第五章

有限長離散變換

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

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

55.2離散傅里葉變換

DiscreteFourier

時域

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

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

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

DiscreteFourierTransform(DFT)補充DFS內(nèi)容6時域已知周期沖激函數(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周期化，離散化信號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周期化，離散化信號x(t)X(jω)P(jω)ω0ω0=2π5.2離散傅里葉變換

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

DiscreteFourierDFT定義中引入一個常用的符號5.2離散傅里葉變換

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

Di5.2離散傅里葉變換

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

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長單點非零樣本的DFT計算其N點的DFT：125.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長單點非零樣本的DFT計算其N點DFT為：135.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長正弦序列的DFT計算解：145.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長正弦序列的DFT計算155.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系可以重寫為：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計算DFT

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

用matlab計算如下N點序列的M點DFT195.2.3用Matlab計算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計算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計算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)系長度為N的序列的DTFT為：在=[0，2]對X(ej

)進行的N點等間隔采樣：265.3FT與DFT之間的關(guān)系一.DFT與DTFT之間說明：x(n)的N點DFT是x(n)的Z變換在單位圓上的N點等間隔采樣。X(k)為x(n)的傅立葉變換X(ej)在區(qū)間[0，2]上的N點等間隔采樣。27說明：275.3FT與DFT之間的關(guān)系二.使用DFT進行傅立葉變換的數(shù)值計算已知,其傅立葉變換為希望以頻率間隔來估計，其中解：定義新序列285.3FT與DFT之間的關(guān)系二.使用DFT進行傅立葉則：上式是M點序列xe[n]的M點DFT序列Xe[k]5.3FT與DFT之間的關(guān)系二.使用DFT進行傅立葉變換的數(shù)值計算29則：上式是M點序列xe[n]的M點DFT序列Xe[k]5.5.3FT與DFT之間的關(guān)系二.使用DFT進行傅立葉變換的數(shù)值計算例5.5使用matlab計算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進行傅立葉%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計算DTFT程序5_3.m31%Computeits16-pointDFT例5.例-5_3.m

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

在的N點等間隔采樣

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

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

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

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

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

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

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

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

對稱關(guān)系

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

5.7離散傅立葉變換定理

線性

圓周時移圓周頻移圓周卷積相乘

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

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

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

-1的有限長序列將h[n]和x

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

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

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

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

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

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

Overlap-AddMethod其中首先分割

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

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

Overlap-AddMethod其中首先分割分割

x[n],

例如N=792分割x[n],例如N=792*其中*因為

h[n]的長度是

M，

xm[n]的長度是N,所以線性卷積的長度是

N+M-1重疊相加法

Overlap-AddMethod因此，93*其中*因為h[n]的長度是M，xm[n]的長度是

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

*重疊相加法

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

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

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

Overlap-AddMethod中的第一個短卷積:95長度是N+M-1，**重疊相加法

Overlap-Add長度是

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

N

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

Overlap-AddMethod中的第二個短卷積:96長度是N+M-1，**重疊相加法

Overlap-Add重疊相加法

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

同樣,第三個短卷積是

長度是N+M-1

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

Overlap-AddMethod這表明這兩個重疊相加法

Overlap-AddMethod通常,在短卷積和疊加時，會有M-1個樣本的重疊，重疊的范圍為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Decimation-in-Time下面圖形表示FFT在時域所作的分解（1）8點長時間信號（2）4點長信號（3）2點長信號012345670246135704261537按時間抽取FFT算法

Decimation-in-TimeFFTAlgorithm123下面圖形表示FFT在時域所作的分解（1）8點長時間信號（2兩次抽取的蝶形圖按時間抽取FFT算法

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

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

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

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

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

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

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

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

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

Decimation-in-Time按時間抽取FFT算法

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

Decimation-in-Time按時間抽取FFT算法

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

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

Decimation-in-Time按時間抽取FFT算法

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

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

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

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

001

4

100201020103

011

6

1104

100

1

001510151016

110

3

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

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

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

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

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

Decimation-in-FrequencyFFTAlgorithm152與DIT相對應(yīng)，DIF算法是將頻域X[k]的序號k按奇偶分開按頻域抽取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點的DFT分成偶數(shù)組和奇數(shù)組。這樣每個N/2點DFT可由兩個N/4點DFT形成。其輸入序列分別是x0(n)和x1(n)按上下對半分開形成的四個子序列。該過程可以繼續(xù)，直到最小的DFT為2點DFT155按頻域抽取FFT算法

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

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

Decimation-in-FrequIDFT算法

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

x[n]上式同時乘以

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

InverseDFTComputatio所求的離散傅里葉逆變換x[n]為：{X[k]}ReRe{x[n]}Im{x[n]}Im{X[k]}N-pointDFTIDFT的計算過程如圖: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補充：周期序列的離散傅立葉級數(shù)及傅立葉變換一、周期序列的離散傅立葉級數(shù)式中是傅立葉級數(shù)的系數(shù)。設(shè)是以N為周期的周期序列，將其展成傅立葉級數(shù)，得為求ak,將上式兩邊乘以,并對n在一個周期N中求和。160補充：周期序列的離散傅立葉級數(shù)及傅立葉變換一、周期序列的離散正交函數(shù)集的條件推導(dǎo)過程：周期序列的離散傅立葉級數(shù)所以161正交函數(shù)集的條件推導(dǎo)過程：周期序列的離散傅立葉級數(shù)所以161因為是周期為N的周期函數(shù)，所以也是周期為N的周期函數(shù)。周期序列的離散傅立葉級數(shù)設(shè)則將上式兩邊乘以,并對k在一個周期N中求和:162因為是周期為N的周期函數(shù)，所以也是周期為N的周期函數(shù)。周期序周期序列的離散傅立葉級數(shù)所以163周期序列的離散傅立葉級數(shù)所以163周期序列的離散傅立葉級數(shù)DFS

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

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

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

有限長離散變換

Finite-LengthdiscreteTransforms168第五章

有限長離散變換

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

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

1725.2離散傅里葉變換

DiscreteFourier

時域

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

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

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

DiscreteFourierTransform(DFT)補充DFS內(nèi)容173時域已知周期沖激函數(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周期化，離散化信號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周期化，離散化信號x(t)X(jω)P(jω)ω0ω0=2π5.2離散傅里葉變換

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

DiscreteFourierDFT定義中引入一個常用的符號5.2離散傅里葉變換

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

Di5.2離散傅里葉變換

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

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長單點非零樣本的DFT計算其N點的DFT：1795.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.1

有限長單點非零樣本的DFT計算其N點DFT為：1805.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長正弦序列的DFT計算解：1815.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)例5.2

有限長正弦序列的DFT計算1825.2離散傅里葉變換

DiscreteFourier5.2離散傅里葉變換

DiscreteFourierTransform(DFT)DFT的矩陣關(guān)系可以重寫為：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計算DFT

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

用matlab計算如下N點序列的M點DFT1865.2.3用Matlab計算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計算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計算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)系長度為N的序列的DTFT為：在=[0，2]對X(ej

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