數(shù)字信號處理 - DFT及其快速計算方法

數(shù)字信號處理若序列x(n)的非零值點僅分布在有限整數(shù)集合上，則稱此序列為有限長序列，即

x(n)=0n<N1

orn>N2

周期延拓(PeriodicExtension)有限長序列（FiniteLengthSequence）由于計算機系統(tǒng)存儲空間的限制，對序列分析時只能存儲其中一段信息，因此有限長序列是數(shù)字信號處理的主要對象；可以證明，對確定性的信號，完全可以用有限長序列反映信號所包含的頻率信息；式中為n對N取余數(shù)。若有限長序列x(n)不是周期序列，以正整數(shù)N對它進行周期延拓，獲得無限長的周期序列，記為如果m和r均為整數(shù)則n對N取余數(shù)就等于r：例如：周期延拓(PeriodicExtension)Tuesday,October15,20244x(n)N-1n0......n0N-1定義周期序列從n=0到(N-1)的第一個周期為主值序列或區(qū)間周期延拓(PeriodicExtension)描述系統(tǒng)特性的工具Tuesday,October15,20245連續(xù)時間系統(tǒng)時域分析工具：系統(tǒng)沖擊響應(yīng)，微分方程頻域分析工具：頻率響應(yīng)，拉氏變換（傳遞函數(shù)）離散時間系統(tǒng)時域分析工具：系統(tǒng)沖擊響應(yīng)，差分方程頻域分析工具：頻率響應(yīng)，z變換（傳遞函數(shù)）Tuesday,October15,20246DTFT是分析離散時間信號和系統(tǒng)的有力工具DTFT的局限性信號離散、非周期DTFT具有周期性、連續(xù)曲線Tuesday,October15,20247DTFT是分析離散時間信號和系統(tǒng)的有力工具DTFT的局限性信號離散、非周期DTFT連續(xù)曲線、具有周期性兩個局限性：如果序列無限長，則需要為無限個時間點計算DTFT；DTFT輸出為關(guān)于數(shù)字頻率的連續(xù)函數(shù)，需要為無限多個頻率點計算頻譜；Tuesday,October15,20248DTFT的局限性解決方案：對無限長序列加窗截斷，生成有限長序列；把頻域內(nèi)的DTFT頻譜曲線看做是一個連續(xù)頻率函數(shù)，仿照對連續(xù)時間信號采樣，對DTFT曲線X(ejω)進行等頻率間隔采樣，得到離散的DTFT序列離散傅里葉變換(DFT)對有限長離散序列x(n)的離散時間傅里葉變換（DTFT）按照等頻率間隔在一個頻率周期(0≤ω<2π)內(nèi)進行N點采樣，得到一個長度為N的頻域離散序列，該序列為x(n)的離散傅里葉變換Tuesday,October15,20249對有限長離散序列x(n)的離散傅里葉變換(DiscreteFourierTransformation,DFT)定義如下：DFT：DTFT：Tuesday,October15,202410離散傅里葉變換DFT：引入旋轉(zhuǎn)因子：DFT定義簡化為：DTFT是單位圓上的z變換DFT是DTFT的抽樣序列DFT在單位圓上，且具有周期性Tuesday,October15,202411離散傅里葉變換旋轉(zhuǎn)因子的性質(zhì)：Tuesday,October15,202412離散傅里葉逆變換DFT：等式兩邊同時乘以旋轉(zhuǎn)因子，并對k求和：=NTuesday,October15,202413離散傅里葉逆變換DFT：等式兩邊同時乘以旋轉(zhuǎn)因子，并對k求和：=N上式為離散傅里葉逆變換（IDFT）定義；Tuesday,October15,202414DFT的計算觀察上述和式的結(jié)構(gòu)，可以把計算寫成如下矩陣與向量相乘的形式：kn由于N值確定后，旋轉(zhuǎn)因子WN可以被視為常數(shù)，因此該式可以簡化計算的工作量。Tuesday,October15,202415DFT的計算觀察上述和式的結(jié)構(gòu)，可以把計算寫成如下矩陣與向量相乘的形式：Tuesday,October15,202416DFT的計算觀察上述和式的結(jié)構(gòu)，可以把計算寫成如下矩陣與向量相乘的形式：Tuesday,October15,202417例5.1求序列的DFT：Solution:W=

=不同傅里葉變換比較傅里葉變換，F(xiàn)T離散時間傅里葉變換，DTFT傅里葉級數(shù)，F(xiàn)S離散傅里葉級數(shù)，DFS？離散傅里葉變換，DFT？Tuesday,October15,202418變換的目的都是時域內(nèi)的信號變成頻域內(nèi)信號，利用頻域內(nèi)的性質(zhì)分析原有信號的特征；不同傅里葉變換比較Tuesday,October15,202419連續(xù)、非周期時域信號←映射→非周期、連續(xù)頻域信號1.傅里葉變換（FourierTransformation）0t00------x(nTs)-Ts0Ts2Tst離散、非周期時域信號←映射→周期、連續(xù)頻域信號2.離散時間傅里葉變換（Discrete-timeFourierTransformation）不同傅里葉變換比較連續(xù)、周期時域信號←映射→非周期、離散頻域信號3.傅里葉級數(shù)（FourierSeriesExpansion）不同傅里葉變換比較0t------0

不同傅里葉變換比較聯(lián)想：對于離散序列，是否存在傅里葉級數(shù)展開？周期為T的連續(xù)函數(shù)可以展開成基波頻率Ω0整數(shù)倍頻率上復(fù)指數(shù)函數(shù)加權(quán)和，即傅里葉級數(shù)

離散傅里葉級數(shù)與連續(xù)函數(shù)傅里葉級數(shù)展開相類似，如果一個序列具有周期N，可以展開成基波頻率ω0整數(shù)倍頻率上復(fù)指數(shù)函數(shù)的加權(quán)和，即存在下面的和式：等式成立的關(guān)鍵在于能否找到滿足上式的一組系數(shù)可以先假設(shè)級數(shù)存在，再求解Xp(k)表達(dá)式Tuesday,October15,202424離散傅里葉級數(shù)等式兩邊同時乘以旋轉(zhuǎn)因子，并對n求和：假設(shè)級數(shù)存在：當(dāng)且僅當(dāng)n=r時，方括弧中的和式取非零值：系數(shù)Xp(k)存在，因此離散周期序列可展開為傅里葉級數(shù)Tuesday,October15,202425離散傅里葉級數(shù)離散傅里葉級數(shù)表達(dá)式：傅里葉級數(shù)系數(shù)表達(dá)式：Note:習(xí)慣上，把因子1/N放進X

(k)表達(dá)式的和式里面，因此x(n)表達(dá)式前面需要加一個1/N；從Xp(k)表達(dá)式可以看出，Xp(k)是周期序列，只在N個獨立的分量上有值；x(nT)=x(n)t0T2T12N

nNT離散、周期時域信號←映射→周期、離散頻域信號4.離散傅里葉級數(shù)（Discrete-timeFourierSeries，DFS）不同傅里葉變換比較00123k27x(nT)=x(n)t0T2T12N

nNT4.離散傅里葉級數(shù)（Discrete-timeFourierSeries，DFS）Tuesday,October15,202428離散、有限長時域信號←映射→非周期、離散頻域信號5.離散傅里葉變換（Discrete-timeFourierTransformation，DFT）不同傅里葉變換比較把有限長序列進行周期延拓，即可以展開為DFS取DFS的主值序列，即可得到DFT對DFT進行周期延拓，即可得到DFSTuesday,October15,202429離散、有限長時域信號←映射→非周期、離散頻域信號5.離散傅里葉變換（Discrete-timeFourierTransformation，DFT）不同傅里葉變換比較x(nTs)-Ts0Ts2Tst01234…Nk不同傅里葉變換比較Tuesday,October15,202431Tuesday,October15,202432序列重構(gòu)-頻域抽樣理論由DFT重構(gòu)時域序列由DFT重構(gòu)z變換由DFT重構(gòu)DTFT為什么要研究重構(gòu)？時域抽樣(先抽樣，再DTFT):對一個頻帶有限的信號，根據(jù)抽樣定理對其進行抽樣，所得抽樣信號的頻譜是原帶限信號頻譜的周期延拓，因此完全可以由抽樣信號恢復(fù)原信號。33重構(gòu)序列-頻域抽樣理論頻域抽樣（先DTFT，再抽樣）:對一有限長序列進行DFT所得X(k)就是序列DTFT的采樣，所以DFT是頻域抽樣。34重構(gòu)序列已知序列x(n)的DTFT：通過對DTFT一個周期進行采樣得到N點有限長序列計算IDFT，得到一個長度為N的有限長序列35重構(gòu)序列如果用DFT還原時域信號，該信號是原序列無限多個移位序列的疊加;如果原序列的長度L≤N，則由N點DFT重構(gòu)的序列取0≤n≤N-1的主值部分就是原序列；如果L>N，則由N點DFT重構(gòu)的序列將產(chǎn)生混疊失真；Tuesday,October15,202436例5.2已知系統(tǒng)的單位沖擊響應(yīng)為：，(1)求DTFT；（2）由N點頻域采樣得到DFT；（3）由DFT數(shù)據(jù)重構(gòu)時域序列；Solution:(1)頻域抽樣造成時域混疊!(2)Tuesday,October15,202437混疊無法避免，但通過增大頻域采樣點值N可以降低這種影響。Tuesday,October15,202438N=8N=1639重構(gòu)Z變換已知z變換的定義和IDFT的定義分別如下：把x(n)表達(dá)式帶入z變換定義：此式就是由X(k)重構(gòu)X(z)的內(nèi)插公式，Pk(z)稱作內(nèi)插函數(shù)40單位圓上的z變換即DTFT,代入內(nèi)插函數(shù)重構(gòu)DTFTTuesday,October15,202441結(jié)論：DFT在采樣點上的值與DTFT在相同頻率點上的值相等，因此在這些點上可以真實反映DTFT，在其他頻率點的值是內(nèi)插函數(shù)的加權(quán)和因此，DTFT可由DFT還原為如下表達(dá)式：在采樣頻率上Tuesday,October15,202442P123，Ex3-4：求寬度為L的矩形序列DTFT和N點DFT：（1）若N=L，能根據(jù)DFT重構(gòu)DTFT嗎？（2）比較N=8，32及64時，DTFT和DFT的頻譜圖。Solution：DTFT（1）把N=L帶入上式盡管有L個點的值，但只在零頻率點上非零，無法復(fù)現(xiàn)其它頻率點的值Tuesday,October15,202443Solution：（2）把L=8帶入DTFT表達(dá)式P123，Ex3-4：求寬度為L的矩形序列DTFT和N點DFT：（1）若N=L，能根據(jù)DFT重構(gòu)DTFT嗎？（2）比較N=8，32及64時，DTFT和DFT的頻譜圖。Tuesday,October15,202444Solution：（2）把N=32和64分別帶入DFT表達(dá)式P123，Ex3-4：求寬度為L的矩形序列DTFT和N點DFT：（1）若N=L，能根據(jù)DFT重構(gòu)DTFT嗎？（2）比較N=8，32及64時，DTFT和DFT的頻譜圖。Tuesday,October15,202445Assignment分析簡單聲音信號，利用樂器生成包含若干頻率的聲音信號，利用電腦聲卡和matlab及采集分析信號；可參考利用附錄中的matlab（2013版）程序；使用不同的采樣分析參數(shù)，說明這些參數(shù)的影響；Tuesday,October15,202446%samplerateSampleRate=4000;%num