[工學]數字信號處理[第四章_快速傅里葉變換fft(編輯修改稿)

　

【文章內容簡介】 W W j? ? ? ? ?都 有 兩 個 旋 轉 因 子13312 ( ) 22 2 2LMMLLLNN N???? ? ???復 數 乘 法 運 算 減 少( 2 ) ( 2 ) ( 2 ) ( 3 ) 22 2 2M N N NMM? ? ? ? ? ? ?所 需 復 數 乘 法 次 數 C35 快速傅里葉變換（ FFT） /8 ( 1 ) 2 / 2NNWj ??特 殊 復 數22( 1 ) ( ) ( )222[ ( ) ( ) ]2j x jy x jy jx yx y j x y? ? ? ? ? ?? ? ? ?一 次 復 數 乘 法 運 算 需 要 四 次 實 數 乘 ， 兩 次 實 數 加節 省 二 次 實 數 乘32222MLLNN????L=3,實 數 乘 法運 算 減 少13( 2 ) 4 [ ( 3 ) 2 ] ( 2 ) ( 2 ) 1 02 2 2MNNR M N M? ? ? ? ? ? ? ?36 快速傅里葉變換（ FFT） 一類 蝶形單元運算：包括 所有 旋轉因子 蝶 形 單 元 類 型 越 多 ， 編 程 就 越 復 雜 ，但 乘 法 運 算 的 減 少 量 是 可 觀 的 。 二類 蝶形單元運算：去掉 旋轉因子 1rNW ?? 三類 蝶形單元運算：再去掉 旋轉因子 rNWj?? 四類 蝶形單元運算：再處理 旋轉因子 (1 ) 2 / 2rNWj??37 快速傅里葉變換（ FFT） c o s ( 2 / ) s i n ( 2 / )mNW m N j m N???? 一種方法是在每級運算中 直接產生 ； 二種方法是在 FFT程序開始前 預先計算 出旋轉因子， 存放在數組中，作為 旋轉因子表 ，在程序執行 中直 接查表 。 38 快速傅里葉變換（ FFT） FFT算法 12 2( ) ( 2 ) ( ) ( 2 1 ) 0 , 1 , 1Nx n x n x n x n n? ? ? ? ?12( ) ( ) ( )y n x n jx n??( ) ( ) ( )e p o pY k Y k Y k??11( ) [ ( ) ] ( )epY k D F T x n X k??22( ) [ ( ) ] ( )opY k D F T jx n jX k??12 2( ) ( ) ( ) 0 , 1 ,k NNX k X k W X k k? ? ?，2( ) ( ) 1 , 2 , 1NX N k X k k?? ? ? ?，39 例 1：設 x(n)是長度為 2N的有限長實序列， X(k)為 x(n)的 2N點 DFT。要求：試設計用一次 N點 FFT完成計算 X(k)的高效算法。 解： ? 本題的解題思路是 DIT－ FFT思想； ? 在時域分別抽取偶數點和奇數點 x(n)，得到兩個 N點實序列 x1(n)和 x2(n)： ? x1(n) = x(2n) , n = 0, 1, …… , N1 x2(n) = x(2n+1) , n = 0, 1, …… , N1 ? 根據 DIT－ FFT的思想，只要求得 x1(n)和 x2(n)的 N點DFT，再經過簡單的一級蝶形運算就可得到 x(n)的 2N點 DFT。 ? 因為 x1(n)和 x2(n)均為實序列，所以根據 DFT的共軛對稱性，可用一次 N點 FFT求得 X1(k)和 X2(k)。做法如下 ： 40 令 y(n) = x1(n) + jx2(n) ? Y(k) = DFT[y(n)] 則 X1(k)=DFT[x1(n)]=Yep(k)=[Y(k)+Y*(Nk)]/2 jX2(k)=DFT[x2(n)]=Yop(k)=[Y(k)Y*(Nk)]/2 2N點 DFT[x(n)] = X(k)可由 X1(k)和 X2(k)得到： X(k) = X1(k) + W2NkX2(k) X(k+N) = X1(k) W2NkX2(k) , k=0, 1, … , N1 這樣，通過一次 N點 FFT計算完成了計算 2N點 DFT。 41 例 2： 設 x(n)是長度為 2N的有限長實序列， X(k)為 x(n)的 2N點 DFT。若已知 X(k)，要求：試設計用一次 N點 IFFT完成計算 x(n )的高效算法。 解：設 x1(n) = x(2n) , n = 0, 1, …… , N 1 x2(n) = x(2n+1) , n = 0, 1, …… , N 1 X1(k) = DFT[x1(n)] , k = 1, 1, … , N 1 X2(k) = DFT[x2(n)] , k = 1, 1, … , N 1 由 DIT－ FFT的算法，有以下關系式： X(k) = X1(k) + W2NkX2(k) , k = 1, 1, … , N 1 X(k+N) = X1(k) W2NkX2(k) 由以上兩可解出 X1(k)和 X2(k) 。 42 X1(k) = [X(k) + X(k+N)]/2 X2(k) = W2Nk[X(k) – X(k+N)]/2 由上面分析可得出運算過程如下： （ 1）由 X(k)計算出 X1(k)和 X2(k)； （ 2）由 X1(k)和 X2(k)構成 N點頻域序列 Y(k)： Y(k) = X1(k) + jX2(k) = Yep(k) + Yop(k) 其中 Yep(k) = X1(k)， Yop(k) = jX2(k)，進行 N點 IFFT運算，得到 y(n) = IFFT[Y(k)] = Re[y(n)] + jIm[y(n)] , n = 0, 1, … , N1 由 DFT的共軛對稱性 Re[y(n)] = [y(n)+y*(n)]/2 = DFT[Yep(k)] = x1(n) jIm[y(n)] = [y(n)y*(n)]/2 = DFT[Yop(k)] = jx2(n) 由 x1(n)和 x2(n)合成 x(n)： 當 n = 偶數（ n = 0 , 1 , … , 2N1）時 x(n) = x1(n/2) 當 n = 奇數（ n = 0 , 1 , … , 2N1）時 x(n) = x2((n1)/2) 43 分裂基 FFT算法 快速傅里葉變換（ FFT） 1984年，法國的杜梅爾和霍爾曼將 基 2和基 4分解糅合在一起 ，提出了 分裂基 FFT算法 ，其運算量有所減少，運算流圖相似，運算程序較短，是一種實用的高效算法。 , / 4 , 4n p q p N q? ? ?當 且 時1 0 1 0 1 044 , 0 3 , 0 1NNn p n n n n n n? ? ? ? ? ? ? ? ?44 快速傅里葉變換（ FFT） 10011 / 4 1 3 ()4100 0 0( ) ( ) ( )4NNN k n nknNNn n nNX k x n W x n n W?? ?? ? ?? ? ?? ? ?1 0 1 04Nn pn n n n? ? ? ?0 101/ 4 1 31 0 400()4Nkn knNnnNW x n n W???????1112444NNj k nknNNknWeW????00/ 4 100 4 0 40230 4 0 4[ ( ) ( )43 ( ) ( ) ]24NknknkkNNx n W x n WNNx n W x n W W??? ? ?? ? ? ??1 0 1 044 , 0 1 , 0 3Nk k k k k? ? ? ? ? ? ?1001 0 1 0 1 0 0/ 4 141 0 0 0 402 ( 4 ) 3 ( 4 ) ( 4 )0 4 0 4( 4 ) [ ( ) ( )43 ( ) ( ) ]24Nkknk k k k k k nNNX k k x n x n WNNx n W x n W W???? ? ?? ? ? ?? ? ? ??45 快速傅里葉變換（ FFT） 1001 0 1 0 1 0 0/ 4 141 0 0 0 402 ( 4 ) 3 ( 4 ) ( 4 )0 4 0 4( 4 ) [ ( ) ( )43 ( ) ( ) ]24Nkknk k k k k k nNNX k k x n x n WNNx n W x n W W???? ? ?? ? ? ?? ? ? ??112 44 44 1j n knkWe ????000 0 1 0 0/ 4 10 0 402 3 ( 4 )0 4 0 4[ ( ) ( )43 ( ) ( ) ]24Nknk k k k nNNx n x n WNNx n W x n W W???? ? ?? ? ? ??1 0 1 044 , 0 1 , 0 3Nk k k k k? ? ? ? ? ? ?00 0 0/ 4 10402 3 ( 4 )44( 4 ) [ ( ) ( )43 ( ) ( ) ]24Nknk k k k nNNX k k x n x n WNNx n W x n W W???? ? ? ?? ? ? ??10,k k n n??46 快速傅里葉變換（ FFT） 00 0 0/ 4 10402 3 ( 4 )44( 4 ) [ ( ) ( )43 ( ) ( ) ]24Nknk k k k nNNX k k x n x n WNNx n W x n W W???? ? ? ?? ? ? ??003k??/ 4 1403( 4 ) [ ( ) ( ) ( ) ( ) ]4 2 4NknNnN N NX k x n x n x n x n W??? ? ? ? ? ? ??0 0 0230 4 4 40 , 1k k kk W W W? ? ? ?0 0 0230 4 4 41 , , 1 ,k k kk W j W W j? ? ? ? ? ?/ 4 1403( 4 1 ) [ ( ) ( ) ( ) ( ) ]4 2 4Nk n nNnN N NX k x n jx n x n jx n W? ??? ? ? ? ? ? ? ??0 04 42 , 1 1 , 1k kW W? ? ? ?/ 4 14203( 4 2 ) [ ( ) ( ) ( ) ( ) ]4 2 4Nk n nNnN N NX k x n x n x n x n W? ??? ? ? ? ? ? ? ??/ 4 14303( 4 3 ) [ ( ) ( ) ( ) ( ) ]4 2 4Nk n nNnN N NX k x n jx n x n jx n W? ??? ? ? ? ? ? ? ??0 0 0230 4 4 43 , , 1 ,k k kW j