離散傅里葉變換dft及其快速算法fft

1、第3章　離散傅里葉變換(DFT) 及其快速算法(FFT),,3.1　學(xué)習(xí)要點(diǎn)與重要公式3.2　頻率域采樣3.3　循環(huán)卷積和線性卷積的快速計(jì)算以及信號的頻譜分析3.4　例題3.5　教材第3章習(xí)題與上機(jī)題解答3.6　教材第4章習(xí)題與上機(jī)題解答,3.1 學(xué)習(xí)要點(diǎn)與重要公式3.1.1 學(xué)習(xí)要點(diǎn)　　 （1） DFT的定義和物理意義， DFT和FT、 ZT之間的關(guān)系；　　 （2） DFT

2、的重要性質(zhì)和定理： 隱含周期性、 循環(huán)移位性質(zhì)、 共軛對稱性、 實(shí)序列DFT的特點(diǎn)、 循環(huán)卷積定理、 離散巴塞伐爾定理；　　 （3） 頻率域采樣定理；　　 （4） FFT的基本原理及其應(yīng)用。,3.1.2 重要公式　　1） 定義,,k=0, 1, …, N－1,,k=0, 1, …, N－1,2） 隱含周期性,,3） 線性性質(zhì)若,，則,,4） 時域循環(huán)移位性質(zhì),,,5) 頻域循環(huán)移位性質(zhì),,,6） 循環(huán)卷積定

3、理　　 循環(huán)卷積：,,,L x(n),,循環(huán)卷積的矩陣表示：,,循環(huán)卷積定理： 若　　　　　　　yc(n)=h(n) L x(n)則 Yc(k)=DFT［yc(n)］L=H(k)X(k) k=0, 1, 2, …, L－1其中 H(k)=DFT［h(n)］L, X(k)=DFT［x(n)］L　　6) 離散巴塞伐爾定理,,,7） 共軛對稱性質(zhì)　　(1) 長度為N的共軛對稱

4、序列xep(n)與反共軛對稱序列xop(n):,,,序列x(n)的共軛對稱分量與共軛反對稱分量：,,,（2） 如果　　x(n)=xr(n)+jxi(n)且　　　　　　　　X(k)=Xep(k)+Xop(k)則　　　　Xep(k)=DFT［xr(n)］, Xop(k)=DFT［jxi(n)］ （3） 如果x(n)=xep(n)+xop(n)且　　　　X(k)=Xr(k)+jXi(k)則　　　　Xr(k)=

5、DFT［xep(n)］, jXi(k)=DFT［xop(n)］ （4） 實(shí)序列DFT及FT的特點(diǎn): 假設(shè)x(n)是實(shí)序列， X(k)=DFT［x(n)］， 則　　　　　X(k)=X*(N－k)　　　　　|X(k)|=|X(N－k)|, θ(k)=－θ(N－k),,3.2 頻 率 域 采 樣　　我們知道， 時域采樣和頻域采樣各有相應(yīng)的采樣定理。 頻域采樣定理包含以下內(nèi)容:　?。?） 設(shè)

6、x(n)是任意序列， X(ejω)=FT［x(n)］，對X(ejω)等間隔采樣得到,,,k=0，1，2，3，…，N－1,則,,,(2) 如果x(n)的長度為M， 只有當(dāng)頻域采樣點(diǎn)數(shù)N≥M時， xN(n)=x(n)， 否則,,會發(fā)生時域混疊， xN(n)≠x(n)。,通過頻率域采樣得到頻域離散序列xN(k)， 再對xN(k)進(jìn)行IDFT得到的序列xN(n)應(yīng)是原序列x(n)以采樣點(diǎn)數(shù)N為周期進(jìn)行周期化后的主值區(qū)序列， 這一

7、概念非常重要。,(3) 如果在頻率域采樣的點(diǎn)數(shù)滿足頻率域采樣定理， 即采樣點(diǎn)數(shù)N大于等于序列的長度M， 則可以用頻率采樣得到的離散函數(shù)X(k)恢復(fù)原序列的Z變換X(z)， 公式為,,式中,,上面第一式稱為z域內(nèi)插公式， 第二式稱為內(nèi)插函數(shù)。,,3.3 循環(huán)卷積和線性卷積的快速計(jì)算 　　　　以及信號的頻譜分析3.3.1 循環(huán)卷積的快速計(jì)算　　如果兩個序列的長度均不很長， 可以直接采用循環(huán)卷積的矩陣乘法計(jì)算其

8、循環(huán)卷積； 如果序列較長， 可以采用快速算法。 快速算法的理論基礎(chǔ)是循環(huán)卷積定理。 設(shè)h(n)的長度為N， x(n)的長度為M, 計(jì)算yc(n)=h(n) L x(n)的快速算法如下：,,,（1） 計(jì)算,,,k=0,1,2,3,…，L－1，L=max［N, M］,（2） 計(jì)算 　　　　Yc(k)=H(k)X(k) k=0, 1, 2, …, L－1　?。?） 計(jì)算

9、 　　　　yc(n)=IDFT［Yc(k)］L n=0, 1, 2, …, L－1　　說明： 如上計(jì)算過程中的DFT和IDFT均采用FFT算法時， 才稱為快速算法， 否則比直接在時域計(jì)算循環(huán)卷積的運(yùn)算量大3倍以上。,3.3.2 線性卷積的快速計(jì)算——快速卷積法 序列h(n)和x(n)的長度分別為N和M， L=N+M－1， 求y(n)=h(n)*x(n)的方法如下： 　?。?）

10、在h(n)的尾部加L－N個零點(diǎn)， 在x(n)的尾部加L－M個零點(diǎn)；　?。?）計(jì)算L點(diǎn)的H(k)=FFT［h(n)］和L點(diǎn)的X(k)=FFT［x(n)］;　?。?） 計(jì)算Y(k)=H(k)X(k)；　?。?） 計(jì)算Y(n)=IFFT［Y(k)］， n=0，1，2，3，…，L-1?！　〉?dāng)h(n)和x(n)中任一個的長度很長或者無限長時， 需用書上介紹的重疊相加法和重疊保留法。,3.3.3 用DFT/FFT進(jìn)行頻譜分

11、析　　對序列進(jìn)行N點(diǎn)的DFT/FFT就是對序列頻域的N點(diǎn)離散采樣， 采樣點(diǎn)的頻率為ωk=2πk/N, k=0, 1, 2, …, N－1。 　　對信號進(jìn)行頻譜分析要關(guān)心三個問題： 頻譜分辨率、 頻譜分析范圍和分析誤差。 　　DFT的分辨率指的是頻域采樣間隔2π/N， 用DFT/FFT進(jìn)行頻譜分析時， 在相鄰采點(diǎn)之間的頻譜是不知道的， 因此頻率分辨率是一個重要指標(biāo)， 希望分辨率高， 即2π/N要小， DFT的變換

12、區(qū)間N要大。,,當(dāng)然， 截取信號的長度要足夠長。 但如果截取的長度不夠長， 而依靠在所截取的序列尾部加零點(diǎn)， 增加變換區(qū)間長度， 也不會提高分辨率。 例如， 分析周期序列的頻譜， 只觀察了一個周期的1/4長度， 用這些數(shù)據(jù)進(jìn)行DFT， 再通過尾部增加零點(diǎn)， 加大DFT的變換區(qū)間N， 也不能分辨出是周期序列， 更不能得到周期序列的精確頻率。  用DFT/FFT對序列進(jìn)行頻譜分析， 頻譜分析范圍為π;

13、 用DFT/FFT對模擬信號進(jìn)行頻譜分析， 頻譜分析范圍為采樣頻率的一半， 即0.5Fs。  用DFT/FFT對信號進(jìn)行譜分析的誤差表現(xiàn)在三個方面， 即混疊現(xiàn)象、 柵欄效應(yīng)和截?cái)嘈?yīng)。 截?cái)嘈?yīng)包括泄漏和譜間干擾。,,3.4 例 題　?。劾?.4.1］ 設(shè)x(n)為存在傅里葉變換的任意序列， 其Z變換為X(z)，X(k)是對X(z)在單位圓上的N點(diǎn)等間隔采樣， 即,,求X(k

14、)的N點(diǎn)離散傅里葉逆變換（記為xN(n)）與x(n)的關(guān)系式。 　　解: 由題意知,,,,即X(k)是對X(ejω)在［0, 2π］上的N點(diǎn)等間隔采樣。 由于X(ejω)是以2π為周期的， 所以采樣序列,即　　　以N為周期。 所以它必然與一周期序列　　　相對應(yīng)， 　　為　　　的DFS系數(shù)。,,,,為了導(dǎo)出　　　與x(n)之間的關(guān)系， 應(yīng)將上式中的用x(n)表示：,,所以,,因?yàn)?,所以,,即　　　是x(n)的周期延拓序列

15、， 由DFT與DFS的關(guān)系可得出,,,,xN(n)=IDFT［X(k)］為x(n)的周期延拓序列（以N為延拓周期）的主值序列。 以后這一結(jié)論可以直接引用。 　?。劾?.4.2］ 已知　　　　　　x(n)=R8(n), X(ejω)=FT［x(n)］對X(ejω)采樣得到X(k)，,,求,,解：直接根據(jù)頻域采樣概念得到,,［例3.4.3］ 令X(k)表示x(n)的N點(diǎn)DFT， 分別證明： ?。?） 如果x(n)滿足關(guān)

16、系式　　　　　　　　x(n)=－x(N－1－n)則　　　　　　　　　X(0)=0 （2） 當(dāng)N為偶數(shù)時， 如果　　　　　　　　　x(n)=x(N－1－n)則,,證 （1） 直接按DFT定義即可得證。 因?yàn)?,所以,,①,令n=N－1－m， 則,②,①式+②式得,,所以　　　　　　　　　　　X(0)=0 （2） 因?yàn)閤(n)=x(N－1－n)， 所以,,令m=N－1－n， 則上式

17、可寫成,,,當(dāng)　　　時（N為偶數(shù)），,,,因?yàn)?,所以,,因此證得,,［例3.4.4］　有限時寬序列的N點(diǎn)離散傅里葉變換相當(dāng)于其Z變換在單位圓上的N點(diǎn)等間隔采樣。 我們希望求出X(z)在半徑為r的圓上的N點(diǎn)等間隔采樣， 即,,試給出一種用DFT計(jì)算得到　　　的算法。 　　解: 因?yàn)?,,,所以,,,,由此可見， 先對x(n)乘以指數(shù)序列r－n， 然后再進(jìn)行N點(diǎn)DFT， 即可得到題中所要求的復(fù)頻域采樣　　　。,,［例3.4.5］

18、 長度為N的一個有限長序列x(n)的N點(diǎn)DFT為X(k)。 另一個長度為2N的序列y(n)定義為,,試用X(k)表示y(n)的2N點(diǎn)離散傅里葉變換Y(k)。　　解: 該題可以直接按DFT定義求解。,,,,,,上面最后一步采用的是X(k)以N為周期的概念。,［例3.4.6］ 用DFT對模擬信號進(jìn)行譜分析， 設(shè)模擬信號xa(t)的最高頻率為200 Hz， 以奈奎斯特頻率采樣得到時域離散序列x(n)=xa(nT)， 要求

19、頻率分辨率為10 Hz。 假設(shè)模擬信號頻譜Xa(jΩ)如圖3.4.1所示， 試畫出X(ejω)=FT［x(n)］和X(k)=DFT［x(n)］的譜線圖， 并標(biāo)出每個k值對應(yīng)的數(shù)字頻率ωk和模擬頻率fk的取值。,圖3.4.1,解: 因?yàn)樽罡哳l率fmax=200 Hz， 頻率分辨率F=10 Hz， 所以采樣頻率fs為,,觀察時間,,采樣點(diǎn)數(shù)　　　　　　N=Tρfs=0.1×400=40個所以， 對xa(t)進(jìn)行采

20、樣得　　　　　　x(n)=xa(nT) n=0, 1, …, 39,,,Xa(jf)、 X(ejω)及X((k))N分別如圖3.4.2（a）、 （b）、 （c）所示。,圖3.4.2,當(dāng)fs=2fmax時， f=fmax 對應(yīng)　　　　　　　　　　　　， 由　　　 　 可求得　　　 ； 當(dāng)fs>2fmax時，fmax對應(yīng)的數(shù)字頻率ω=2πfmaxT<π。 Xa(if)與X(k

21、)的對應(yīng)關(guān)系（由圖3.4.2（a）、 （c）可看出）為,,,,,,該例題主要說明了模擬信號xa(t)的時域采樣序列x(n)的N點(diǎn)離散傅里葉變換X(k)與xa(t)的頻譜Xa(jf)之間的對應(yīng)關(guān)系。 只有搞清該關(guān)系， 才能由X(k)看出Xa(jf)的頻譜特征。 否則， 即使計(jì)算出X(k)， 也搞不清X(k)的第k條譜線對應(yīng)于Xa(jf)的哪個頻率點(diǎn)的采樣， 這樣就達(dá)不到譜分析的目的。 實(shí)際中， X(k)求出后， 也可以將橫坐

22、標(biāo)換算成模擬頻率， 換算公式為fk=kF=k/(NT)。 直接作Xa(kF)=Xa(fk)=TX(k)譜線圖。,,［例3.4.7］ 已知x(n)長度為N， X(z)=ZT［x(n)］。 要求計(jì)算X(z)在單位圓上的M個等間隔采樣。 假定M<N， 試設(shè)計(jì)一種計(jì)算M個采樣值的方法， 它只需計(jì)算一次M點(diǎn)DFT。 　解: 這是一個典型的頻域采樣理論應(yīng)用問題。 根據(jù)頻域采樣、 時域周期延拓以及DFT的惟一性概念， 容易解答

23、該題。 　　由頻域采樣理論知道， 如果,,即X(k)是X(z)在單位圓上的M點(diǎn)等間隔采樣, 則,,當(dāng)然,,即首先將x(n)以M為周期進(jìn)行周期延拓， 取主值區(qū)序列xM(n)， 最后進(jìn)行M點(diǎn)DFT則可得到　　應(yīng)當(dāng)注意， M<N， 所以周期延拓x(n)時， 有重疊區(qū)， xM(n)在重疊區(qū)上的值等于重疊在n點(diǎn)處的所有序列值相加。,顯然， 由于頻域采樣點(diǎn)數(shù)M<N， 不滿足頻域采樣定理， 所以， 不能由X(

24、k)恢復(fù)x(n)，即丟失了x(n)的頻譜信息。 ?。劾?.4.8］ 已知序列　　　　　x(n)={1, 2, 2, 1}, h(n)={3, 2, －1, 1} （1）計(jì)算5點(diǎn)循環(huán)卷積y5(n)=x(n) L h(n); 　?。?）用計(jì)算循環(huán)卷積的方法計(jì)算線性卷積y(n)=x(n)*h(n)。 　　解：(1)這里是2個短序列的循環(huán)卷積計(jì)算， 可以用矩陣相乘的方法(即用教材第82頁式(3.2.7)）計(jì)算

25、， 也可以用類似于線性卷積的列表法。 因?yàn)橐?點(diǎn)循環(huán)卷積， 因此每個序列尾部加一個零值點(diǎn)， 按照教材式(3.2.7)寫出,,,得到y(tǒng)5(n)={4, 9, 9, 6, 2}。 注意上面矩陣方程右邊第一個5×5矩陣稱為x(n)的循環(huán)矩陣， 它的第一行是x(n)的5點(diǎn)循環(huán)倒相， 第二行是第一行的向右循環(huán)移一位， 第三行是第二行向右循環(huán)移一位， 依次類推。,用列表法可以省去寫矩陣方程， 下面用列表法解：,表中的第一

26、行是h(n)序列， 第2、 3、 4、 5、 6行的前五列即是x(n)的循環(huán)矩陣的對應(yīng)行。 同樣得到y(tǒng)5(n)={４, 9, 9, 6, 2}。 　?。?） 我們知道只有當(dāng)循環(huán)卷積的長度大于等于線性卷積結(jié)果的長度時， 循環(huán)卷積的結(jié)果才能等于線性卷積的結(jié)果。 該題目中線性卷積的長度為L＝4+4－1=7， 因此循環(huán)卷積的長度可選L=7， 這樣兩個序列的尾部分別加3個零點(diǎn)后， 進(jìn)行7點(diǎn)循環(huán)卷積， 其結(jié)果就是線性卷積的結(jié)果。

27、 即,,得到　　　　　　y(n)=x(n)*h(n)={3, 8, 9, 6, 2, 1, 1},［例3.4.9］　已知實(shí)序列x(n)和y(n)的DFT分別為X(k)和Y(k)， 試給出一種計(jì)算一次IDFT就可得出x(n)和y(n)的計(jì)算方法。 （選自2004年北京交通大學(xué)碩士研究生入學(xué)試題。）　　解： 令 w(n)=x(n)+jy(n)對其進(jìn)行DFT， 得到　　　　　　　　　W(k)=X(k

28、)+jY(k)　　　　　　　　　w(n)=IDFT［W(k)］因?yàn)閤(n)和y(n)分別為實(shí)序列， 因此　　　　　　　　　x(n)=Re［w(n)］　　　　　　　　　y(n)=Im［w(n)］,［例3.4.10］已知x(n) (n=0， 1， 2， …， 1023)， h(n) (n=0， 1， 2， …， 15)。 在進(jìn)行線性卷積時， 每次只能進(jìn)行16點(diǎn)線性卷積運(yùn)算。 試問為了得到y(tǒng)(n)=x(n)*h(n)的正確

29、結(jié)果， 原始數(shù)據(jù)應(yīng)作怎樣處理， 并如何進(jìn)行運(yùn)算。 （選自1996年西安電子科技大學(xué)碩士研究生入學(xué)試題。）　　解： 將x(n)進(jìn)行分組后， 采用書上介紹的重疊相加法。 x(n)的長度為1024點(diǎn)， 按照16分組， 共分64組， 記為xi(n), i=0, 1, 2, …, 63。 即,,,式中， yi(n)=xi(n)*h(n), i=0, 1, 2, …, 63。 可以用FFT計(jì)算16點(diǎn)的線性卷積yi(n)。

30、 最后結(jié)果y(n)的長度為1024+16－1＝1039?！　。劾?.4.11］ x(n)是一個長度M=142的信號序列， 即： x(n)=0， 當(dāng)n<0或n≥M時?，F(xiàn)希望用N＝100的DFT來分析頻譜。試問：如何通過一次N=100的DFT求得　　　　　　　　　　,　　 k=0, 1, 2, …, 99； 這樣進(jìn)行頻譜分析是否存在誤差？,,解： 通過頻率域采樣得到頻域離散函數(shù)， 再對其進(jìn)行IDFT得到的序列應(yīng)是原序列

31、x(n)以N為周期進(jìn)行周期化后的主值序列。 按照這一概念， 在頻域0~2π采樣100點(diǎn)， 那么相應(yīng)的時域應(yīng)以100為周期進(jìn)行延拓后截取主值區(qū)。 該題要求用一次100點(diǎn)的DFT求得， 可以用下式計(jì)算：,,式中, k對應(yīng)的頻率為　　　　　　。 這樣進(jìn)行頻譜分析存在誤差， 誤差是因?yàn)闀r域混疊引起的。,,,3.5 教材第3章習(xí)題與上機(jī)題解答　　 1． 計(jì)算以下序列的N點(diǎn)DFT， 在變換區(qū)間0≤n≤N－1內(nèi)， 序列定義為

32、　　 (1) x(n)=1　　 (2) x(n)=δ(n)　　 (3) x(n)=δ(n－n0) 0<n0<N　　 (4) x(n)=Rm(n) 0<m<N 　　 (5) 　　　　　　　　　　　  　 (6) 　　　　　　　　　　　 ,,,(7) x

33、(n)=ejω0nRN(n) 　 (8) x(n)=sin(ω0n)RN(n) 　 (9) x(n)=cos(ω0n)RN(N) 　 (10) x(n)=nRN(n)　　解：,(1),,,（2）,（3）,,,(4),,(5),,,0≤k≤N－1,(6),,,,0≤k≤N－1,(7),,,或,（8） 解法一 直接計(jì)算：,,,,,解法二 由DFT的共軛對稱性求解。　　因?yàn)?,所

34、以,,所以,,即,,結(jié)果與解法一所得結(jié)果相同。 此題驗(yàn)證了共軛對稱性?！　?9) 解法一 直接計(jì)算:,,,,,解法二 由DFT共軛對稱性可得同樣結(jié)果。 　　因?yàn)?,,,（10） 解法一,,上式直接計(jì)算較難， 可根據(jù)循環(huán)移位性質(zhì)來求解X(k)。 因?yàn)閤(n)=nRN(n)， 所以 x(n)－x((n－1))NRN(n)+Nδ(n)=RN(n)等式兩邊進(jìn)行DFT， 得到

35、 X(k)－X(k)WkN+N=Nδ(k),故,,當(dāng)k=0時， 可直接計(jì)算得出X(0)為,,這樣， X(k)可寫成如下形式：,,解法二 k=0時，,,k≠0時，,,,,,所以，,,，即,,2． 已知下列X(k)， 求x(n)=IDFT［X(k)］,(1),(2),,其中， m為正整數(shù)， 0<m<N/2, N為變換區(qū)間長度。,,,解: （1）,,,n=0, 1, …, N－1,(2),

36、,,,n=0, 1, …, N－1,3． 已知長度為N=10的兩個有限長序列：,≤,≤,≤,≤,,≤,≤,≤,≤,做圖表示x1(n)、 x2(n)和y(n)=x1(n) * x2(n)， 循環(huán)卷積區(qū)間長度L=10。 　　解: x1(n)、 x2(n)和y(n)=x1(n) * x2(n)分別如題3解圖（a）、 （b）、 （c）所示。,,,題3解圖,4． 證明DFT的對稱定理， 即假設(shè)X(k)=DFT［x(n)］， 證明　　　　　

37、　　　　DFT［X(n)］=Nx(N－k) 證： 因?yàn)?,所以,,,由于,,≤,≤,所以 DFT［X(n)］=Nx(N－k) k=0, 1, …, N－1 5． 如果X(k)=DFT［x(n)］， 證明DFT的初值定理,,證: 由IDFT定義式,,可知,,6． 設(shè)x(n)的長度為N， 且　　　　X(k)=DFT［x(n)］ 0≤k≤N－1令　　　

38、h(n)=x((n))NRmN(n) m為自然數(shù)　　　H(k)=DFT［h(n)］mN 0≤k≤mN－1求H(k)與X(k)的關(guān)系式。 　　解: H(k)=DFT［h(n)］ 0≤k≤mN－1　　令n=n′+lN, l=0, 1, …, m－1, n′=0, 1, …, N－1, 則,,,,因?yàn)?所以,,7． 證明: 若x(n)為實(shí)序列， X(k)=DFT［x(n)］N， 則

39、X(k)為共軛對稱序列， 即X(k)=X*（N－k)； 若x(n)實(shí)偶對稱， 即x(n)=x(N－n)， 則X(k)也實(shí)偶對稱； 若x(n)實(shí)奇對稱， 即x(n)=－x(N－n)， 則X(k)為純虛函數(shù)并奇對稱。,證: (1) 由教材(3.2.17)~(3.2.20)式知道， 如果將x(n)表示為　　　　　　x(n)=xr(n)+jxi(n)則　　　　X(k)=DFT［x(n)］=Xep(k)+Xop(k)其中， Xep

40、(k)=DFT［xr(n)］， 是X(k)的共軛對稱分量； Xop(k)=DFT［jxi(n)］, 是X(k)的共軛反對稱分量。 所以， 如果x(n)為實(shí)序列， 則Xop(k)=DFT［jxi(n)］=0， 故X(k)=DFT［x(n)］=Xep(k)， 即X(k)=X*(N－k)。,（2） 由DFT的共軛對稱性可知， 如果 　　　　　x(n)=xep(n)+xop(n)且　　　　　X(k)=Re［X

41、(k)］+j Im［X(k)］則　　Re［X(k)］=DFT［xep(n)］, j Im［X(k)］=DFT［xop(n)］所以， 當(dāng)x(n)=x(N－n)時， 等價(jià)于上式中xop(n)=0, x(n)中只有xep(n)成分， 所以X(k)只有實(shí)部， 即X(k)為實(shí)函數(shù)。 又由（1）證明結(jié)果知道， 實(shí)序列的DFT必然為共軛對稱函數(shù)， 即X(k)=X*(N－k)=X(N－k)， 所以X(k)實(shí)偶對稱。,,同理，

42、 當(dāng)x(n)=－x(N－n)時， 等價(jià)于x(n)只有xop(n)成分（即xep(n)=0）， 故X(k)只有純虛部， 且由于x(n)為實(shí)序列， 即X(k)共軛對稱， X(k)=X*(N－k)=－X(N－k), 為純虛奇函數(shù)。　8． 證明頻域循環(huán)移位性質(zhì)： 設(shè)X(k)=DFT［x(n)］， Y(k)=DFT［y(n)］， 如果Y(k)=X((k+l))NRN(k)， 則,,,,,證：,,,令m=k+l, 則,,,9． 已知x(n

43、)長度為N， X(k)=DFT［x(n)］，,,≤,≤,≤,≤,,,≤,≤,求Y(k)與X(k)的關(guān)系式。 　　解:,,10． 證明離散相關(guān)定理。 若　　　　　　　　　X(k)=X1* (k)Ｘ2(k)則,,證： 根據(jù)DFT的惟一性， 只要證明,,即可。,,,,,,令m=l+n， 則,,,所以,,≤,≤,當(dāng)然也可以直接計(jì)算X(k)=X1 *(k)X2(k)的IDFT。,,,,,0≤n≤N－1,,由于,,0≤n≤N－1,所以

44、,,11． 證明離散帕塞瓦爾定理。 若X(k)=DFT［x(n)］， 則,,證：,,,,,12． 已知f(n)=x(n)+jy(n)， x(n)與y(n)均為長度為N的實(shí)序列。 設(shè)　　　　　F(k)=DFT［f(n)］N 0≤k≤N－1,,(1),(2) 　　F(k)=1+jN試求X(k)=DFT［x(n)］N， Y(k)=DFT［y(n)］N以及x(n)和y(n)。 　　解: 由DFT的共軛對稱性可知

45、　　　　　　x(n)　　X(k)=Fep(k)　　　　　　jy(n)　　jY(k)=Fop(k),,方法一 （1）,,,,,,,0≤n≤N－1,由于,,0≤n, m≤N－1,所以 x(n)=an 0≤n≤N－1同理 y(n)=bn 0≤n≤N－1 （2） F(k)=

46、1+jN,,,,，,,方法二 令,,只要證明A(k)為共軛對稱的，B(k)為共軛反對稱， 則就會有 A(k)=Fep(k)=X(k), B(k)=Fop(k)=jY(k)因?yàn)?,，共軛對稱,,,，共軛反對稱,所以,,,由方法一知 x(n)=IDFT［X(k)］=anRN(n)　　　　 y(n)=IDFT［Y(k)］=bnRN(n) 1

47、3． 已知序列x(n)=anu(n)， 0<a<1, 對x(n)的Z變換X(z)在單位圓上等間隔采樣N點(diǎn)， 采樣序列為,,求有限長序列IDFT［X(k)］N。 　　解: 我們知道， , 是以2π為周期的周期函數(shù)， 所以,,,①,以N為周期， 將　　　看作一周期序列　　　的DFS系數(shù)， 則,,,,②,由式①知　　　為,,③,將式③代入式②得到,由于

48、,,所以,,由題意知,,所以根據(jù)有關(guān)X(k)與xN(n)的周期延拓序列的DFS系數(shù)的關(guān)系有,,,,由于0≤n≤N－1， 所以,,≥,≥,因此,,說明： 平時解題時， 本題推導(dǎo),的過程可省去， 直接引用頻域采樣理論給出的結(jié)論（教材中式（3.3.2）和(3.3.3)）即可。　　14． 兩個有限長序列x(n)和y(n)的零值區(qū)間為　　　　　x(n)=0 n<0, 8≤n　　　　　y(n)=0

49、n<0, 20≤n對每個序列作20點(diǎn)DFT， 即　　　　　X(k)=DFT［x(n)］ k=0, 1, …, 19　　　　　Y(k)=DFT［y(n)］ k=0, 1, …, 19試問在哪些點(diǎn)上f(n)與x(n)*y(n)值相等, 為什么？,解: 如前所述， 記fl(n)=x(n)*y(n)，而f(n)=IDFT［F(k)］=x(n) 20 y(n)。 fl(n)長度為27， f(n)

50、長度為20。 由教材中式（3.4.3）知道f(n)與fl(n)的關(guān)系為,,,只有在如上周期延拓序列中無混疊的點(diǎn)上， 才滿足f(n)=fl(n),所以 f(n)=fl(n)=x(n)*y(n) 7≤n≤19,15． 已知實(shí)序列x(n)的8點(diǎn)DFT的前5個值為0.25, 0.125-j0.3018, 0, 0.125-j0.0518, 0。 　?。?） 求X(k)的其

51、余3點(diǎn)的值； ,（2）,,求X1(k)=DFT［x1(n)］8；,（3）,,，求,,。,解： （1）因?yàn)閤(n)是實(shí)序列， 由第7題證明結(jié)果有X(k)=X*(N－k)， 即X(N－k)=X*(k), 所以， X（k）的其余3點(diǎn)值為　　　{X(5), X(6), X(7)}={0.125+j0.0518, 0, 0.125+j0.3018 （2） 根據(jù)DFT的時域循環(huán)移位性質(zhì)，,(3),,16． x(n)、 x1

52、(n)和x2(n)分別如題16圖(a)、 (b)和(c)所示， 已知X(k)=DFT［x(n)］8。 求,,和,,［注: 用X(k)表示X1(k)和X2(k)。］,解： 因?yàn)閤1(n)=x((n+3))8R8(n), x2(n)=x((n－2))8R8(n)， 所以根據(jù)DFT的時域循環(huán)移位性質(zhì)得到,,,17． 設(shè)x(n)是長度為N的因果序列， 且,,,,試確定Y(k)與X(ejω)的關(guān)系式。,,解： y(n)是x(n)以M為周期

53、的周期延拓序列的主值序列， 根據(jù)頻域采樣理論得到,,18． 用微處理機(jī)對實(shí)數(shù)序列作譜分析， 要求譜分辨率F≤50 Hz， 信號最高頻率為 1 kHz， 試確定以下各參數(shù)： 　　　　(1) 最小記錄時間Tp min； 　 (2) 最大取樣間隔Tmax； 　　(3) 最少采樣點(diǎn)數(shù)Nmin； 　　(4) 在頻帶寬度不變的情況下， 使頻率分辨率提高1倍（即F縮小一半）的N值。 ,解: （1） 已知F=50 Hz，

54、 因而,,（2）,,（3）,,（4） 頻帶寬度不變就意味著采樣間隔T不變， 應(yīng)該使記錄時間擴(kuò)大1倍， 即為0.04 s， 實(shí)現(xiàn)頻率分辨率提高1倍（F變?yōu)樵瓉淼?/2）。,,19． 已知調(diào)幅信號的載波頻率fc=1 kHz， 調(diào)制信號頻率fm=100 Hz， 用FFT對其進(jìn)行譜分析， 試求： 　 (1) 最小記錄時間Tp min;　 (2) 最低采樣頻率fs min;　 (3) 最少采樣點(diǎn)數(shù)Nmin。,解： 調(diào)制

55、信號為單一頻率正弦波時， 已調(diào)AM信號為　　　　x(t)=cos(2πfct+jc)［1+cos(2πfmt+jm)］所以， 已調(diào)AM信號x(t) 只有3個頻率： fc、 fc+fm、 fc－fm。 x(t)的最高頻率fmax=1.1 kHz， 頻率分辨率F≤100 Hz（對本題所給單頻AM調(diào)制信號應(yīng)滿足100/F=整數(shù)， 以便能采樣到這三個頻率成分）。 故,,(1),(2),,(3),,（注意， 對窄帶已調(diào)信號可以采

56、用亞奈奎斯特采樣速率采樣， 壓縮碼率。 而在本題的解答中， 我們僅按基帶信號的采樣定理來求解。 ）　　20． 在下列說法中選擇正確的結(jié)論。 線性調(diào)頻Z變換可以用來計(jì)算一個有限長序列h(n)在z平面實(shí)軸上諸點(diǎn){zk}的Z變換H(zk)， 使,(1) zk=ak, k=0, 1, …, N－1, a為實(shí)數(shù)，　a≠1; 　 (2) zk=ak, k=0, 1, …, N－1, a為實(shí)數(shù)， a≠1; 　 (3) (

57、1)和(2)都不行， 即線性調(diào)頻Z變換不能計(jì)算H(z)在z平面實(shí)軸上的取樣值。 　　解： 在chirp-Z變換中， 在z平面上分析的N點(diǎn)為　　　　　　　zk=AW－k k=0, 1, …, N－1其中所以　　當(dāng)A0=1, ω0=0, W0=a－1, j=0時， 　 　　　　　　zk=ak故說法（1）正確, 說法（2）、 （3）不正確。 ,,,21． 我們希望利用h(n)長度為N=

58、50的FIR濾波器對一段很長的數(shù)據(jù)序列進(jìn)行濾波處理， 要求采用重疊保留法通過DFT(即FFT)來實(shí)現(xiàn)。 所謂重疊保留法， 就是對輸入序列進(jìn)行分段(本題設(shè)每段長度為M=100個采樣點(diǎn))， 但相鄰兩段必須重疊V個點(diǎn)， 然后計(jì)算各段與h(n)的L點(diǎn)(本題取L=128)循環(huán)卷積， 得到輸出序列ym(n)， m表示第m段循環(huán)卷積計(jì)算輸出。 最后， 從ym(n)中選取B個樣值， 使每段選取的B個樣值連接得到濾波輸出y(n)。,(1) 求V； 　

59、　 (2) 求B； 　　 (3) 確定取出的B個采樣應(yīng)為ym(n)中的哪些樣點(diǎn)。 　　解: 為了便于敘述， 規(guī)定循環(huán)卷積的輸出序列ym(n)的序列標(biāo)號為n=0, 1, 2, …, 127。 　　先以h(n)與各段輸入的線性卷積ylm(n)分析問題， 因?yàn)楫?dāng)h(n)的50個樣值點(diǎn)完全與第m段輸入序列xm(n)重疊后， ylm(n)才與真正的濾波輸出y(n)相等， 所以， ylm(n)中第0點(diǎn)到第48點(diǎn)（共49個點(diǎn)

60、）不正確， 不能作為濾波輸出， 第49點(diǎn)到第99點(diǎn)（共51個點(diǎn)）為正確的濾波輸出序列y(n)的第m段， 即B=51。,所以， 為了去除前面49個不正確點(diǎn)， 取出51個正確的點(diǎn)連接, 得到不間斷又無多余點(diǎn)的y(n)， 必須重疊100－51=49個點(diǎn)， 即V=49。 　　下面說明， 對128點(diǎn)的循環(huán)卷積ym(n)， 上述結(jié)果也是正確的。 我們知道,,因?yàn)閥lm(n)長度為,N+M－1=50+100－1=149,所以n

61、從21到127區(qū)域無時域混疊， ym(n)=ylm(n)， 當(dāng)然， 第49點(diǎn)到第99點(diǎn)二者亦相等， 所以， 所取出的51點(diǎn)為從第49點(diǎn)到第99點(diǎn)的ym(n)。 　　綜上所述， 總結(jié)所得結(jié)論： 　　　　　　　V=49, 　B=51 選取ym(n)中第49～99點(diǎn)作為濾波輸出。 　　讀者可以通過作圖來理解重疊保留法的原理和本題的解答。 ,22． 證明DFT的頻域循環(huán)卷積定理。 　　證： DFT的

62、頻域循環(huán)卷積定理重寫如下: 　　設(shè)h(n)和x(n)的長度分別為N和M， 　　　　ym(n)=h(n)x(n)　　　　H(k)=DFT［h(n)］L, X(k)=DFT［X(n)］L則,,L X(k),,,其中， L≥max［N， M］。,根據(jù)DFT的惟一性， 只要證明ym(n)=IDFT［Ym(k)］=h(n)x(n)， 就證明了DFT的頻域循環(huán)卷積定理。,,23*． 已知序列x(n)={1, 2, 3, 3, 2

63、, 1}。 　?。?） 求出x(n)的傅里葉變換X(ejω)， 畫出幅頻特性和相頻特性曲線(提示： 用1024點(diǎn)FFT近似X(ejω))； 　　（2） 計(jì)算x(n)的N（N≥6）點(diǎn)離散傅里葉變換X(k)， 畫出幅頻特性和相頻特性曲線； 　?。?） 將X(ejω)和X(k)的幅頻特性和相頻特性曲線分別畫在同一幅圖中， 驗(yàn)證X(k)是X(ejω)的等間隔采樣， 采樣間隔為2π/N； 　?。?） 計(jì)算X(k)的N點(diǎn)IDFT，

64、驗(yàn)證DFT和IDFT的惟一性。,,解： 該題求解程序?yàn)閑x323.m， 程序運(yùn)行結(jié)果如題23*解圖所示。 第（1）小題用1024點(diǎn)DFT近似x(n)的傅里葉變換； 第（2）小題用32點(diǎn)DFT。 題23*解圖(e)和(f)驗(yàn)證了X(k)是X(ejω)的等間隔采樣， 采樣間隔為2π/N。 題23*解圖(g) 驗(yàn)證了IDFT的惟一性。,題23*解圖,24*．給定兩個序列: x1(n)={2, 1, 1, 2} , x2(n)

65、={1, －1, －1, 1}。 　?。?） 直接在時域計(jì)算x1(n)與x2(n)的卷積； 　?。?） 用DFT計(jì)算x1(n)與x2(n)的卷積， 總結(jié)出DFT的時域卷積定理。  　　解： 設(shè)x1(n)和x2(n)的長度分別為M1和M2， 　 X1(k)=DFT［x1(n)］N, X2(k)=DFT［x2(n)］N　 Yc(k)=X1(k)X2(k), yc(n)=IDFT［Yc(k)］N所謂DFT的

66、時域卷積定理， 就是當(dāng)N≥M1+M2－1時， yc(n)=x1(n)*x2(n)。,本題中， M1=M2=4， 所以， 程序中取N=7。 本題的求解程序ex324.m如下： 　　% 程序 ex324.m 　　x1n=［2 1 1 2］； x2n=［1 －1 －1 1］； 　　%時域直接計(jì)算卷積yn： 　　yn=conv(x1n， x2n)　　%用DFT計(jì)算卷積ycn： 　　M1=length(x1n)；M

67、2=length(x2n)； N=M1+M2－1；　　X1k=fft(x1n， N)； %計(jì)算x1n的N點(diǎn)DFT　　X2k=fft(x2n， N)； %計(jì)算x2n的N點(diǎn)DFT　　Yck=X1k.*X2k； ycn=ifft(Yck， N),,程序運(yùn)行結(jié)果：  　　直接在時域計(jì)算x1(n)與x2(n)的卷積yn和用DFT計(jì)算x1(n)與x2(n)的卷積ycn如下： 　　yn=［2 －

68、1 －2 2 －2 －1 2］　　ycn=［　2.0000 －1.0000 －2.0000 2.0000 　　　　?。?.0000 －1.0000 2.0000］,25*．已知序列h(n)=R6(n), x(n)=nR8(n)。 　　（1） 計(jì)算yc(n)=h(n) 8 x(n)； 　　（2） 計(jì)算yc(n)=h(n)