1、第五章離散傅里葉變換及其快速算法1 離散傅里葉變換(DFT) 的推導(1) 時域抽樣：目的：解決信號的離散化問題。效果：連續信號離散化使得信號的頻譜被周期延拓。(2) 時域截斷：原因：工程上無法處理時間無限信號。方法：通過窗函數 (一般用矩形窗 )對信號進行逐段截取。結果：時域乘以矩形脈沖信號，頻域相當于和抽樣函數卷積。(3) 時域周期延拓：目的：要使頻率離散，就要使時域變成周期信號。方法：周期延拓中的搬移通過與(t nTs) 的卷積來實現。表示：延拓后的波形在數學上可表示為原始波形與沖激串序列的卷積。結果：周期延拓后的周期函數具有離散譜。(4) 經抽樣、截斷和延拓后，信號時域和頻域都是離散、

2、周期的。過程見圖1。原函數0t0f用于抽樣0t0f抽樣后疊加干涉0t0f用于截斷0t0f截斷后有卷積波紋0t0f用于延拓0t0f延拓后0t0f定義 DFT0Nt 或 nTs0Nf 或 kf0圖 1 DFT 推導過程示意圖(5) 處理后信號的連續時間傅里葉變換：N 1j 2 kn / Nh( nTs )e( f kf 0 )H ( f )kn 0(i)f kf 0kk處存在沖激， 強度為 a k ，其H ( f ) 是離散函數， 僅在離散頻率點T0NTS余各點為 0。(ii)NN1N 個不同的幅值。H ( f ) 是周期函數，周期為Nf0NTs，每個周期內有T0Ts(iii) 時域的離散時間間隔

3、 (或周期 )與頻域的周期 (或離散間隔 )互為倒數。2DFT 及 IDFT的定義(1)DFT 定義：設 h nTs是連續函數 h (t) 的 N 個抽樣值 n0,1, N1 ，這 N 個點的寬度為N 的 DFT 為： DFTNN 1j 2 nk / Nkh(nT s)h(nTs) eH,(k0,1,., N1)n 0NTs(2)IDFT定義：設 Hk是連續頻率函數H ( f ) 的 N 個抽樣值 k0,1, , N1，這N個點NTs的寬度為 N 的 IDFT 為：DFT Nk1 N 1kh nTs ,( k0,1,., N1)1 HHej 2 nk / NNT sN k 0NTs(3) e

4、j 2 nk / N 稱為 N 點 DFT 的變換核函數， e j 2 nk / N 稱為 N 點 IDFT 的變換核函數。 它們互為共軛。(4) 同樣的信號， 寬度不同的 DFT 會有不同的結果。 DFT 正逆變換的對應關系是唯一的，或者說它們是互逆的。(5) 引入 WN e j 2 / N(i) 用途：(a) 正逆變換的核函數分別可以表示為WNnk 和 WN nk 。N 1(b) 核函數的正交性可以表示為：WNkn WNkr *N ( nr )k0N 1(c) DFT 可以表示為：Hkh(nTs )WNnk ,( k0,1, N1)NTsn 0(d) IDFT 可以表示為：1 N1knk

5、, ( n0,1, N1)h( nTs)HWNN k0NTs(ii) 性質：周期性和對稱性：(a)WNNe j 21(b)WNN /2e j1(c)WNN rW NN WNr WNr(d)WNN /2rWNN / 2WNrWNr(e) WNm 1 ( m Z )(f)WmNmne j 2 mn / mNe j2 n / NWNn(m, nZ)3 離散譜的性質(1) 離散譜定義： 稱 H k Hk( k Z ) 為離散序列 h (nTs )(0n N ) 的 DFT 離散譜， 簡稱離NTS散譜。(2) 性質：(i) 周期性：序列的 N 點的 DFT 離散譜是周期為 N 的序列。(ii) 共扼對稱

6、性：如果 x (nTs )(0 n N ) 為實序列，則其 N 點的 DFT 關于原點和 N/2 都具有共軛對稱性。即H kH k* ； H N k H k*； H NH *Nk2k2(iii) 幅度對稱性：如果x (nTs )(0n N ) 為實序列，則其N 點的 DFT 關于原點和 N/2 都具有幅度對稱性。即H kH k ； H N kH k ； H NH Nkk22(3) 改寫：(i) 簡記 h( nTs ) 為 h(n)(ii)簡記 Hk為 H ( k)NTs(iii)DFTDFT 對簡記為： h(n)H ( k) 或 h (n ) H ( k)N 1(iv)(v)4 DFT 總結H

7、 kDFT h( n)h(n)WNnk ,(k0,1, , N1)n0h(n)DFT 1 H (k)1 N 1H k WN nk ,(n 0,1,N 1)N k 0(1)DFT 的定義是針對任意的離散序列 x(nTs ) 中的有限個離散抽樣 (0 n N ) 的，它并不要求該序列具有周期性。k(2)由DFT求 出 的 離 散 譜 H ( k)H kH(kZ) 是 離 散 的 周 期 函 數 ， 周 期 為NT SNf 0N11f s1k 的周期為N /T0f s 、離散間隔為NTsf 0 。離散譜關于變元NTsTsN T0N。(3)如果稱離散譜經過IDFT 所得到的序列為重建信號，x'

8、(nTs )(n Z )，則重建信號是離散的周期函數，周期為NTsT01) 、離散間隔為( 對應離散譜的離散間隔的倒數f 0TsT01)。NTs / N( 對應離散譜周期的倒數NNf 0(4)經 IDFT 重建信號的基頻就是頻域的離散間隔，或時域周期的倒數，為f011。TNT0S(5)實序列的離散譜關于原點和N(如果 N 是偶數 )是共軛對稱和幅度對稱的。因此，真正2有用的頻譜信息可以從0 N1 范圍獲得，從低頻到高頻。2(6) 在時域和頻域 0 N 范圍內的 N 點分別是各自的主值區間或主值周期。5 DFT 性質MM(1)線性性：對任意常數am (1 m M ) ，有 DFTamxm ( n

9、)am DFT xm ( n)m 1m 1(2) 奇偶虛實性：(i) DFT 的反褶、平移：先把有限長序列周期延拓，再作相應反褶或平移，最后取主值區間的序列作為最終結果。(ii) DFT 有如下的奇偶虛實特性：奇奇；偶偶；實偶實偶；實奇虛奇；實(實偶 ) + j( 實奇 )；實(實偶 ) ·EXP( 實奇 )。(3) 反褶和共軛性：時域頻域反褶反褶共軛共軛反褶共軛反褶共軛(4)對偶性： X (n )Nx ( k)(i) 把離散譜序列當成時域序列進行DFT ，結果是原時域序列反褶的N 倍；(ii) 如果原序列具有偶對稱性，則DFT 結果是原時域序列的 N 倍。(5)時移性： x (n

10、m)X (k)WNkm 。序列的時移不影響 DFT 離散譜的幅度。(6)頻移性： x (n)WN nlX (kl )(7)時域離散圓卷積定理：x( n) y( n)X (k )Y (k)(i) 圓卷積：周期均為 N 的序列 x(n ) 與 y(n ) 之間的圓卷積為N 1x(n)y(n)x(i) y(n i)i 0x(n )y (n) 仍是 n 的序列，周期為 N。(ii) 非周期序列之間只可能存在線卷積，不存在圓卷積；周期序列之間存在圓卷積，但不存在線卷積。(8)頻域離散圓卷積定理：x( n) y(n)1X (k ) Y (k )N(9)時域離散圓相關定理：Rxy(P) (n)X (k)Y*

11、 (k)N 1周期為 N 的序列 x( n) 和 y( n) 的圓相關： R (P) x(n), y (n) Rxy(P ) (n)x(i ) y * (i n)i 0是 n 的序列，周期為N。(10)1*。其中 DFT k表示按 k 進行 DFT 運算。h(n)DFT k H *(k )N(11)帕斯瓦爾定理：N1x(n) 21 N1X (k ) 2n0N k06 快速傅里葉變換FFT(1) FFT 不是一種新的變換，而是DFT 的快速算法。(2) 直接 DFT 計算的復雜度： O( N 2 )計算 DFT 需要： N * NN 2 次復數乘法；N * NN 2 次復數加法。(3) FFT

12、算法推導：(i) 第 L 次迭代中對偶結點值的計算公式為：xL (K L )x L1(KL)x L 1 (K L )WNPLxL (K L )x L1(KL)x L 1 (K L )WNPL， K L 是循環控制變量。K LK L 2rLN2 LPLBRr ( K L(r L )(ii)對偶結點的關系如圖2 所示：1xL 1( KL )xL ( K L )(WNPL )1xL 1 ( K L )( WNPL )xL (K L )圖 2 FFT 中對偶結點關系圖(iii) 旋轉因子： WNk 被稱為旋轉因子，可預先算好并保存。(iv) 整序：經過 r 次迭代后， 得到結果 xr k 0 k1 k

13、 r 1 b ，實際結果應是 X kr 1 k1k 0 b ，所以流程的最后一步是按下標的正常二進制順序對結果進行整序。(4) FFT 算法特點： ( N 2r )(i) 共需 r 次迭代；(ii) 第 L (1Lr ) 次迭代對偶結點的偶距為K LK L2 r LN / 2 L ，因此一組結點覆蓋的序號個數是 2(K L K L )N。2 L1(iii) 第 L (1Lr ) 次迭代結點的組數為 N / 2(K LK L )2 L1 。(iv) WNPL 可以預先計算好，而且(5) FFT 算法流程： ( N 2r )(i) 初始化： x0 (n)x(n), 0nN(ii) 第 L (1 L

14、 r ) 次迭代：(a) 下標控制變量初始化 K(b) “結點對”的個數初始化PL 的變化范圍是 0 N1 。21 ；L 0； num 0 ;(c)NWHILE (numL)DO2按對偶結點對的計算公式進行置位運算，得到x L ( K L ) 和 xL (K L ) 的值；KLKL1 ； num num 1 ；跳過已經計算過的結點(即上面 KL所對應的那些結點 )： K LN/2L；如果 KLN ，轉到 b)繼續計算下一組結點；否則結束本次迭代。(iii) 當 r次迭代全部完成后，對結果xr 1 ( k)( 0 kN 1) 按下標二進制位進行整序，從而得到結果 X ( k)( 0k N1) 。(6) FFT 算法復雜度分析：( N2r ， W