【正文】 0n n n??1000002 2 2 2( ) [ ( ) ( ) (c o s c o s sin s) ( )2 2 2inc o s sin2( ) ( ) ( ) ( )sin c o s ]Nnx n k n k n k n k nN N N Nk n k n k n k nN N N N? ? ? ?? ? ? ????????02( ) c o s( )HX k k nN??02( ) s in ( )HX N k k nN???63 快速傅里葉變換（ FFT） 1 1 1 12 2 2 2[ ( ) ( ) ] ( ) ( )HHD F T x n x N n X k X N k? ? ? ? ?[ ( ) ] ( )[ ( ) ] ( )HHD F T x n X kD F T x N n X N k?? ? ?1 1 1 12 2 2 2[ ( ) ( ) ] ( ) ( )HHD F T x n x N n X k X N k? ? ? ? ?64 快速傅里葉變換（ FFT） 1122[ ( ) ] ( )[ ( ) ] ( )HHD F T x n X kD F T x n X k??1 2 2 1 2 1( ) ( ) ( ) ( ) ( ) ( )H H e H H ox n x n X K X K X N K X K? ? ? ?1 2 1 2 1 2( ) ( ) ( ) ( ) ( ) ( )H H e H H ox n x n X K X K X N K X K? ? ? ?65 快速傅里葉變換（ FFT） ( ) ( ) ( )11[ ( ) ( ) ] [ ( ) ( ) ]22H e H oH H H HX k X k jX kX k X N k j X k X N k??? ? ? ? ? ?證明： 1 2 1 2[ ( ) ( ) ] ( ) ( )D F T x n x n X k X k? ? ?11 2 2211 2 2211 2 2211 2 22( ) ( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]H e H HH e H HH o H HH o H HX k X k X k X N kX k X k X N kX k X k X N kX k X k XjkjN? ? ?? ? ?? ? ?? ? ?66 ()HXK ?快速傅里葉變換（ FFT） ( ) R e [ ( ) ] l i m [ ( ) ]HX k X k X k??11 2 2211 2 2211 2 2211 2 22( ) ( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]( ) [ ( ) ( ) ]H e H HH e H HH o H HH o H HX k X k X k X N kX k X k X N kX k X k X N kX k X k XjkjN? ? ?? ? ?? ? ?? ? ?11 2 2 1 2 2211 2 2 1 2 221( ) ( ) [ ( ) ( ) ] ( )1( ) [ ( ) ( ) ] ( ) [ ( )[ ( ) ( ) ]( ) ]22H e H H H o HH H e H H H o H HHX k X k X k X N k X k X k X N kX k X k X N k X k X k X N k?? ? ? ? ? ?? ? ? ? ?21( ) ( )H H oX N K X K??21( ) ( )H H eX K X K12( ) ( )x n x n??67 快速傅里葉變換（ FFT） DHT的快速算法（ FHT）： 102( ) [ ( ) ] ( ) ( )NHnX k D H T x n x n c a s k nN????? ?2 MN ?設(shè) ：01 2( ) ( 2 ) ( ) ( 2 1 ) 0 , 1 , 1Nx r x r x r x r r? ? ? ? ?22110022( ) ( 2 ) ( 2 ) ( 2 1 ) [ ( 2 1 ) ]NNHrrX k x r c a s k r x r c a s k rNN??????? ? ? ???22211010011022( ) ( ) ( ) ( )/ 2 /2c os( )2sin(22( ) ( ))/2NNNrrrx r c as k r x r c as k rNNkx r c as kNNrNk?? ????????????????( ) c o s ( ) s i nc a s c a s c a s? ? ? ? ? ?? ? ? ? ? ?22,/2 k r kNN??????68 快速傅里葉變換（ FFT） 2221101001102 2 2( ) ( ) ( ) c os( ) ( ) ( )/ 2 / 222si n( ) ( ) ( )/2NNNHrrrX k x r c as k r k x r c as k rN N Nk x r c as k rNN? ? ????????????????0 ()HXk 2 1c o s ( ) ( )HN k X k?? 2 1 2s i n ( ) ( )NHN k X k???()HXk ?22( ) c o s ( ) 。 42 X1(k) = [X(k) + X(k+N)]/2 X2(k) = W2Nk[X(k) – X(k+N)]/2 由上面分析可得出運(yùn)算過程如下： （ 1）由 X(k)計(jì)算出 X1(k)和 X2(k)； （ 2）由 X1(k)和 X2(k)構(gòu)成 N點(diǎn)頻域序列 Y(k)： Y(k) = X1(k) + jX2(k) = Yep(k) + Yop(k) 其中 Yep(k) = X1(k)， Yop(k) = jX2(k)，進(jìn)行 N點(diǎn) IFFT運(yùn)算，得到 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)： 當(dāng) n = 偶數(shù)（ n = 0 , 1 , … , 2N1）時 x(n) = x1(n/2) 當(dāng) n = 奇數(shù)（ n = 0 , 1 , … , 2N1）時 x(n) = x2((n1)/2) 43 分裂基 FFT算法 快速傅里葉變換（ FFT） 1984年，法國的杜梅爾和霍爾曼將 基 2和基 4分解糅合在一起 ，提出了 分裂基 FFT算法 ，其運(yùn)算量有所減少，運(yùn)算流圖相似，運(yùn)算程序較短，是一種實(shí)用的高效算法。若已知 X(k)，要求：試設(shè)計(jì)用一次 N點(diǎn) IFFT完成計(jì)算 x(n )的高效算法。做法如下 ： 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點(diǎn) 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點(diǎn) FFT計(jì)算完成了計(jì)算 2N點(diǎn) DFT。 解： ? 本題的解題思路是 DIT－ FFT思想； ? 在時域分別抽取偶數(shù)點(diǎn)和奇數(shù)點(diǎn) x(n)，得到兩個 N點(diǎn)實(shí)序列 x1(n)和 x2(n)： ? x1(n) = x(2n) , n = 0, 1, …… , N1 x2(n) = x(2n+1) , n = 0, 1, …… , N1 ? 根據(jù) DIT－ FFT的思想，只要求得 x1(n)和 x2(n)的 N點(diǎn)DFT，再經(jīng)過簡單的一級蝶形運(yùn)算就可得到 x(n)的 2N點(diǎn) DFT。 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：設(shè) x(n)是長度為 2N的有限長實(shí)序列， X(k)為 x(n)的 2N點(diǎn) DFT。 30 快速傅里葉變換（ FFT） FFT的變形運(yùn)算 支路傳輸比 不變 ， 改變 輸入點(diǎn)，輸出點(diǎn)以及中間節(jié)點(diǎn)的排列 0NW1 2NW1 1 2NW1 0NW1 0NW1 0NW1 0NW1 (0)x(2)x(1)x(3)x(4)x(6)x(5)x(7)x0NW0NW(4)X(0)X(1)X(2)X(6)X(5)X(3)X(7)X1 1 1 1 2NW2NW3NW31 快速傅里葉變換（ FFT） IDFT的高效算法 10( ) [ ( ) ] ( )NknNnX k D F T x n x Wn???? ?10( ) [ ( ) ] ( )1 kNnNnWNx n I D F T X k X k????? ?1 1 2NW?1 0NW1 3NW?1 1NW?1 (0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)x0NW2NW?1 1 1 1 1 1 0NW2NW?1/N1/N1/N1/N1/N1/N1/N1/N(1)X(0)X(4)X(2)X(3)X(5)X(6)X(7)X1 1 212 NW?1 012 NW1 312 NW?1 112 NW?1 (0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)x012 NW212 NW?1 1 1 1 1 1 012 NW212 NW?(1)X(0)X(4)X(2)X(3)X(5)X(6)X(7)X1/21/21/21/21/21/21/21/21/21/21/21/21/21/21/21/2乘法次數(shù)增加了（ N/2)(M1）次 32 快速傅里葉變換（ FFT） 101( ) ( )N knNkx n X k WN????