數字信號處理快速傅里葉變換

1、三、離散傅里葉變換（DFT）( )()rx nx nrN( )( )( )Nx nx n Rn ( )( )NX kXk( )( )( )NX kX k Rk同樣：X(k)也是一個N點的有限長序列( )( )Nx nNx n長度為 的有限長序列周期為 的周期序列( )Nx n( )x n的主值序列( )x n 的周期延拓有限長序列的DFT正變換和反變換：10( ) ( )( ) 01NnkNnX kDFT x nx n WkN101( )( )( ) 01NnkNkx nIDFT X kX k WnNN2jNNWe其中：10( )( )( )( )( )NnkNNNnX kx n WRkX k

2、 Rk或 101( )( )( )( )( )NnkNNNkx nX k WRnx n RnNx(n)的N點DFT是x(n)的z變換在單位圓上的N點等間隔抽樣；DFTz與序列的DTFT和 變換的關系：10( )( )NnnX zx n z10( )( )NnkNnX kx n W10()( )Njj nnX ex n e2()jkNX ex(n)的DTFT在區(qū)間0，2上的N點等間隔抽樣。2( )jkkNNz WeX z4( )( ),( )816DFTx nR nx n例：已知序列求的 點和點。 DTFTx n解：求的 jj nnX ex n e222222jjjjjjeeeeee32sin

3、2sin/2je30j nne411jjee 8 8x nDFTN 求的 點 28jkX kX e32 42sin 281 2sin28jkkek38sin2sin8jkkek 16 16x nDFTN 求的點 216jkX kX e3 22 162sin 2161 2sin2 16jkkek316sin4sin16jkkek四 、抽樣z變換頻域抽樣理論時域抽樣定理：在滿足奈奎斯特定理條件下，時域抽樣信號可以不失真地還原原連續(xù)信號。頻域抽樣呢？抽樣條件？內插公式？ ( )()( )kNnkNz WnX kNWznXX zx對在單位圓上 點等間隔抽樣，得周期序列：( )( )?X kx n分析：

4、( )z( )( )nnx nX zx n z任意絕對可和的非周期序列，其 變換： ( )( )NxnX kIDFS令為的：101( )( )( )NnkNNkxnIDFS X kX k WN101( )NmknkNNkmx m WWN 1()01( )Nm n kNmkx mWN()rx nrN1()0110Nm n kNkmnrNWmN其它r為任意整數x(n)為無限長序列混疊失真x(n)為有限長序列，長度為M( )X k由頻域抽樣序列 還原得到的周期序列是原非周期序列 的周期延拓序列，其周期為頻域抽樣點數N。( )x n所以：時域抽樣造成頻域周期延拓同樣，頻域抽樣造成時域周期延拓1 NM）

5、，不失真2NM），混疊失真頻率采樣定理若序列長度為M，則只有當頻域采樣點數:時，才有即可由頻域采樣 不失真地恢復原信號 ，否則產生時域混疊現象。NM( )( )( )( )( )NNNxn RnIDFS X k Rnx n( )X k( )x n1101( )1N NkkNzX kNWz( )Mx nNNM點有限長序列，頻域 點等間隔抽樣，且 1100( )( )( )MNnnnnX zx n zx n z11001( )NNnknNnkX k WzN11001( )NNnknNknX kWzN11011( )1NkNNNkkNWzX kNWz用頻域采樣 表示 的內插公式( )X k( )X

6、z1101( )( )1N NkkNzX kX zNWz內插公式：111( )1NkkNzzNWz內插函數：10( )( )( )NkkX zX kz則內插公式簡化為： 20,1,.,1jrNzerN零點：，20 (-1)jkNzeN極點：， 階()( )jjkkz eez ()jX e用頻域采樣 表示 的內插公式( )X k1(1)2sin21sin2kNjNjNNkNeeNkN10()( )( )()jNjjkz ekX eX zX ke12sin12 ( )sin2NjNeN內插函數：102 ()( )()NjkX eX kkN內插公式：212 ()20kikNkNiikN五 、用DFT

7、對模擬信號作頻譜分析對連續(xù)時間非周期信號的DFT逼近()( )j tX jx t edt 1( )2j tx tXjed()( )()j tj nTnX jx t edtx nT eT ntnTdtTdtT1）將 在 軸上等間隔（T）分段( )x tt2）將 截短成有限長序列( )x n00 tTN， 個時域抽樣點N-10()()j nTnX jTx nT e 002 F 0k 210( )NjnkNnTx n e3）頻域抽樣：一個周期分N段，采樣間隔 ，時域周期延拓， 周期為0F001/TF0N-100()()jknTnX jkTx nT e002/2 /sTFfN ( )T DFT x n

8、01()()2sj nTx nTX jed010001()2NjknTkX jke0100Nkdd 21000()NjnkNkFX jke21001()NjnkNskfX jkeN1NN01/()T IDFT X jk對連續(xù)時間非周期信號的DFT逼近過程1）時域抽樣2）時域截斷3）頻域抽樣0() ( )X jkT DFT x n01( )()x nIDFT X jkT近似逼近：對連續(xù)時間周期信號的DFS逼近000001()( )TjktX jkx t edtT00( )jktkx tXjke010001()()NjknTnX jkx nT eTT0100 NTntnTdtTdtT1）將 在 軸

9、上等間隔（T）分段( )x tt1 ( )DFS x nN02 /TN0TNT2101( )NjnkNnx n eN2）頻域截斷：長度正好等于一個周期0100()()NjknTkx nTX jke2100()NjnkNkX jke21001()NjnkNkNX jkeN0()N IDFS X jk01() ( )X jkDFS x nN0( )()x nN IDFS X jk近似逼近：信號的頻譜分析：計算信號的傅里葉變換00shTfTFNf時域采樣間隔時域采樣頻率信號記錄長度（頻率分辨率）頻域采樣間隔采樣點數信號最高頻率00sTfNTF1/sfT2shff001/TF0sfNF0TNT頻率響應

10、的混疊失真及參數的選擇00sTfNTF2shff時域抽樣：001/FT頻域抽樣：同時提高信號最高頻率和頻率分辨率，需增加采樣點數N。00sTfNTFhsff要增加信號最高頻率則0NF當 給定必，即分辨率0001FTF要提高頻率分辨率，即則shNTff當 給定 則要不產生混疊， 必信號最高頻率與頻率分辨率之間的矛盾hf信號最高頻率 的確定0/2htT0112hhfTtFFT例：有一頻譜分析用的處理器，其抽樣點數必須是2的整數冪，假設沒有采用任何的數據處理措施，已給條件為：11024HzkHz）頻率分辨率）信號最高頻率0 1 2T NT試確定以下參量：）最小記錄長度）抽樣點間的最大時間間隔 （即最

11、小抽樣頻率）3）在一個記錄中最少點數1解： ）最小記錄長度：00110.110TsF221/shsfffT）最大抽樣間隔 （ ）3110125224 10hTmsf .3）最小記錄點數30224 1080010hfNF 10221024800mN 取 1-14 有一調幅信號用DFT做頻譜分析，要求能分辨 的所有頻率分量，問(1)抽樣頻率應為多少赫茲（Hz）?(2)抽樣時間間隔應為多少秒（Sec）?(3)抽樣點數應為多少點？(4)若用 頻率抽樣，抽樣數據為512點，做頻譜分析，求 ，512點，并粗略畫出 的幅頻特性 ，標出主要點的坐標值。 1cos 2100cos 2600axttt axt3k

12、Hzsf ( ) ( )X kDFT x n( )X k( )X k（1）抽樣頻率應為 2 7001400sfHz解：（2）抽樣時間間隔應為110.000720.721400sTSecmsf 1cos 2100cos 2600axtttcos 260011 cos 2700cos 250022ttt61715cos 2cos 2cos 214214214nnn3( )( )at nTx nx t（ ）( )14x nN 為周期序列，周期14抽樣點數至少為點2/sTff 2/k N* /sffk N頻譜泄漏改善方法：對時域截短，使頻譜變寬拖尾，稱為泄漏1）增加x(n)長度2）緩慢截短柵欄效應改善

13、方法：增加頻域抽樣點數N（時域補零），使譜線更密DFT只計算離散點（基頻F0的整數倍處）的頻譜，而不是連續(xù)函數頻率分辨率提高頻率分辨率方法： 增加信號實際記錄長度 補零并不能提高頻率分辨率001/FT第四章第四章 快速傅里葉變換快速傅里葉變換FFT: Fast Fourier Transform一、直接計算DFT的問題及改進途徑10: ( ) ( )( )( )NnkNNnDFTX kDFT x nx n WRk10:1 ( )( )( )( )NnkNNkIDFTx nIDFT X kX k WRnN( )Nx n點有限長序列運算量復數乘法復數加法一個X(k)NN 1N個X(k)(N點DFT

14、)N 2N (N 1)實數乘法實數加法一次復乘42一次復加2一個X (k)4N2N+2 (N 1)=2 (2N 1)N個X (k)(N點DFT)4N 22N (2N 1)10( )NnkNnx n Wajbcjdacbdj adcbnkNW 的特性*()() ()nknkN n kn N kNNNNWWWW對稱性()() nkN n kn N kNNNWWW周期性 nkmnkNmNWW可約性/nknk mNN mWW0/2(/2) 11Nk NkNNNNWWWW 特殊點：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNee FFT算法分類:時間抽選法DIT:

15、Decimation-In-Time頻率抽選法DIF: Decimation-In-FrequencyFFTDFTDFTDFTDFT算法的基本思想： 利用系數的特性，合并運算中的某些項， 把長序列短序列，從而減少其運算量。二 、按時間抽選的基-2FFT算法1、算法原理設序列點數 N = 2L，L 為整數。 若不滿足，則補零 12221xrx rxrxr0,1,.,/2 1rN將序列x(n)按n的奇偶分成兩組：N為2的整數冪的FFT算法稱基-2FFT算法。則x(n)的DFT: 111000NNNnknknkNNNnnnX kx n Wx n Wx n Wn為偶數n為奇數/2 1/2 121200

16、221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r WWxr W 12kNXkW Xk,0,1,./2 1r kN再利用周期性求X(k)的后半部分1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/2 1kN 121122,/222XkXkNNNXkXkXkXk是以為周期的/22NkNkkNNNNWWWW 又分解后的運算量：復數乘法復數加法一個N / 2點DFT(N / 2)2N / 2 (N / 2 1)兩個N / 2點DFTN 2 / 2N (N / 2 1)一個