1、DFT and Its Fast Computation(part-1),問題的提出（1）,連續(xù)信號xa(t)，其傅氏變換為 xa(t)為時域連續(xù)信號， Xa() 為頻域連續(xù)信號。,問題的提出（2）,離散信號x(n) ，其傅氏變換為 x(n)是離散序列，但 仍然是連續(xù)的。,問題的提出（3）,數(shù)字系統(tǒng)的基本特征： 1、無法處理模擬量； 2、存儲能力總是有限的。,目標(biāo)： 相應(yīng)于數(shù)字系統(tǒng)的基本特征，針對有限長序列定義變換，并要求變換結(jié)果仍為有限長序列。,應(yīng)用： 1、無限長序列的分段處理； 2、基于數(shù)字系統(tǒng)的信號頻域特征分析。,DFS與DFT導(dǎo)出（1）,頻域取樣分析,基礎(chǔ),DFS與DFT導(dǎo)出（2）,頻

2、域取樣分析(contd),周期序列的DTFT,DFS與DFT導(dǎo)出（3）,頻域取樣分析(contd),周期序列的DTFT，離散譜,離散化了主值序列的頻譜 頻域采樣,DFS與DFT導(dǎo)出（4）,頻域取樣分析(contd),DFS與DFT導(dǎo)出（5）,頻域取樣分析(contd),DFS與DFT導(dǎo)出（6）,周期序列的離散付氏級數(shù)（DFS）,有限項復(fù)指數(shù)序列的加權(quán)和； 直流分量、基頻分量和各次諧波； 實周期序列DFS系數(shù)的特點。,DFS與DFT導(dǎo)出（7）,是x(n)的周期延拓，因此，可寫成 用符號(n)N 表示求n對N的余數(shù)， 上式又可寫為：,DFS與DFT導(dǎo)出（8）,通常把周期序列 的第一個周期 n=0到

3、N-1 定義為“主值區(qū)間”,x(n) 就是 的“主值序列” 利用矩形序列 ，上式可表示為：,DFS與DFT導(dǎo)出（9）,同理，有限長頻域序列X(k)就是周期序列 的主值序列，即 ：,DFS與DFT導(dǎo)出（10）,DFT的導(dǎo)出,目標(biāo)：為了便于表示和處理 的頻域特征，由 定義有限長序列,步驟：,頻域采樣與DFS,DFS與DFT導(dǎo)出（11）,DFT的導(dǎo)出, 隱含著周期性； 嚴(yán)格的數(shù)學(xué)定義，明確的物理含義；,Z變換與DFT的關(guān)系 （1）,Z變換在單位圓上的取樣 令x(n)為有限長序列,Z變換與DFT的關(guān)系（2）,Z變換的內(nèi)插表示,一個（N-1）階極點，z=0；,（N-1）個一階零點，如下：,Z變換與DFT

4、的關(guān)系（3）,DTFT的內(nèi)插表示,Z變換與DFT的關(guān)系（4）,內(nèi)插的物理含義,DFS與DFT的性質(zhì)（1）,DFS的性質(zhì) 線性,DFS與DFT的性質(zhì)（2）,DFS的性質(zhì) 序列的周期移位,序列周期移位特性的證明,DFS與DFT的性質(zhì)（3）,DFS的性質(zhì),DFS與DFT的性質(zhì)（4）,DFS的性質(zhì) 對于實序列:,DFS與DFT的性質(zhì)（5）,DFS的性質(zhì) 周期卷積,周期卷積證明,DFS與DFT的性質(zhì)（6）,DFT的性質(zhì) 線性關(guān)系,DFS與DFT的性質(zhì)（7）,DFT的性質(zhì) 反轉(zhuǎn)定理,序列的循環(huán)移位,DFS與DFT的性質(zhì)（8）,DFT的性質(zhì) 序列的循環(huán)移位,DFS與DFT的性質(zhì),DFS與DFT的性質(zhì)（9）,

5、DFT的性質(zhì) 對稱性 設(shè)x(n)的DFT為X(K），則,DFS與DFT的性質(zhì)（10）,DFT的性質(zhì) 帕斯瓦爾定理 設(shè)x(n)的DFT為X(K），則,循環(huán)卷積,1. 定義 設(shè) 是長度為N的有限長序列，定義循環(huán)卷積為：,循環(huán)卷積與周期卷積的關(guān)系,循環(huán)卷積,若 則,例 ： 設(shè) ，計 算 4 點循環(huán)卷積,循環(huán)卷積,解： 注意 為 3 點序列，進(jìn)行循環(huán)卷積之前 在其尾部填一個零，使其成為 4 點序列，我 們分別在時域和頻域中求解這個問題。,（1）時域方法 4 點循環(huán)卷積由下式給出 對每一個 n 產(chǎn)生一個循環(huán)移位序列，將它的樣本逐個與 相乘，然后求和，得此 n 值的循環(huán)卷值，在 0n 3 上重復(fù)此過程。考

6、慮,n = 0 時，,n = 3 時， 因此,n = 2 時，,n = 1 時，,（2）頻域方法： 首先計算 x1(n) 和 x2(n) 的 4 點 DFT，逐個樣本相乘，取逆 DFT， 得到循環(huán)卷積。 則,IDFT 后,循環(huán)卷積和線性卷積的關(guān)系,在實際問題中，碰到的問題大多數(shù)是求解線性卷積，例如，一個LSI系統(tǒng)，輸出y(n)為： 可用循環(huán)卷積代替線性卷積，在計算速度上可提高許多倍。,循環(huán)卷積和線性卷積的關(guān)系,線性卷積的長度： 設(shè)x(n)和h(n)均為有限長序列，長度同為N,的長度為 ，位于集合之上,循環(huán)卷積和線性卷積的關(guān)系,對 作周期為 頻域采樣，可得：,兩邊取IDFS，則有：,循環(huán)卷積和線性卷積的關(guān)系,設(shè)x(n)是長度為N1的有限長序列，h(n)是長度為 N2的有限長度序列，且 N1大于 N2,因此，循環(huán)卷積等于線性卷積的條件是：,用DFT求線性卷積,設(shè) 若 則 即時域循環(huán)卷積 頻域相乘 因此,用DFT求線性卷積,如果循環(huán)卷積的長度L滿足 ，則此循環(huán)卷積 就等于 ， 的線性卷積。用流程圖表示法求 的過程如下： 因為DFT，IDFT都是快速算法，因此，線性卷積也可以實現(xiàn)快速算法。,用DFT求有限長序列線性卷積,在許多實際問題中常需要計算線性卷