數(shù)字信號處理第4章快速傅里葉變換FFTppt課件

1、第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.1 引言引言4.2 基基2FFT算法算法4.3 進一步減少運算量的措施進一步減少運算量的措施4.4 分裂基分裂基FFT算法算法4.5 離散哈特萊變換離散哈特萊變換(DHT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.1 引言引言 DFT是信號分析與處理中的一種重要變換。因直接計算DFT的計算量與變換區(qū)間長度N的平方成正比，當(dāng)N較大時，計算量太大，所以在快速傅里葉變換(簡稱FFT)出現(xiàn)以前，直接用DFT算法進行譜分析和信號的實時處理是不切實際的。直到1965年發(fā)現(xiàn)了DFT的一種

2、快速算法以后，情況才發(fā)生了根本的變化。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.2 基基2FFT算法算法 4.2.1 直接計算DFT的特點及減少運算量的基本途徑 長度為N的有限長序列x(n)的DFT為 考慮x(n)為復(fù)數(shù)序列的一般情況，對某一個k值，直接按(4.2.1)式計算X(k)值需要N次復(fù)數(shù)乘法、(N-1)次復(fù)數(shù)加法。 10( )( ),0,1,1NknNnX kx n WkN(4.2.1) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 如前所述，N點DFT的復(fù)乘次數(shù)等于N2。顯然，把N點DFT分解為幾個較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子WmN具有明

3、顯的周期性和對稱性。其周期性表現(xiàn)為22()jm lNjmm lNmNNNNWeeW(4.2.2) 其對稱性表現(xiàn)為2mN mN mmNNNNNmmNNWWWWWW 或者 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.2.2 時域抽取法基2FFT基本原理 F F T 算 法 基 本 上 分 為 兩 大 類 ： 時 域 抽 取 法FFT(Decimation In Time FFT,簡稱DIT-FFT)和頻域抽取法FFT(Decimation In Frequency FFT,簡稱DIFFFT)。下面先介紹DIFFFT算法。 設(shè)序列x(n)的長度為N，且滿足2 ,MNM為自然數(shù) 按n的奇偶

4、把x(n)分解為兩個N/2點的子序列12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 則x(n)的DFT為/2 1/2 12(21)00/2 1/2 121200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWx rWx r W由于222222/2jkrNjkrkrkrNNNWeeW所以 /2 1/2 11/22/21200( )( )( )( )( )NNkrkkrkNNNNrrX kx r WWx r WX k

5、W Xk第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 其中X1(k)和X2(k)分別為x1(r)和x2(r)的N/2點DFT，即 /2 111/210/2 122/220( )( )( )( )( )( )NkrNrNkrNrX kx r WDFT x rXkx r WDFT x r(4.2.5) (4.2.6) 由于X1(k)和X2(k)均以N/2為周期，且所以X(k)又可表示為前后對半分開兩部分2NkkNNWW 1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kX kW XkkNNX kX kW Xkk(4.2.7) (4.2.8) 第第4章章 快速

6、傅里葉變換快速傅里葉變換(FFT) 圖4.2.1 蝶形運算符號 CABA BCA BC第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.2 N點DFT的一次時域抽取分解圖(N=8) N/2點DFTWN0N/2點DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 二次分解：與第一次分解相同，將x1(r)按奇偶分解成兩個N/4長的子序列x3(l)和x4(l)

7、，即3241( )(2 ),0,1,1( )(21)4x lxlNlx lxl那么，X1(k)又可表示為 /4 1/4 12(21)11/21/200/4 1/4 13/4/24/4003/24( )(2 )(21)( )( )( )( ),0,1,/21NNklklNNiiNNklkklNNNiikNX kxl WxlWx l WWx l Wx kWXk kN(4.2.9) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 式中 /4 133/430/4 144/440( )( )( )( )( )( )NklNiNklNix kx l WDFT x lx kx l WDFT x l 同理

8、，由X3(k)和X4(k)的周期性和Wm N/2的對稱性 Wk+N/4 N/2=-Wk N/2 最后得到： 13/2413/24( )( )( ),0,1,/41(/4)( )( )kNkNX kXkWXkkNX kNXkWXk(4.2.10) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 用同樣的方法可計算出25/2625/26( )( )( ),0,1,/41(/4)( )kNkNXkXkWXkkNXkNX kWXk(4.2.11)其中 /4 155/450/4 166/4605262( )( )( )( )( )( )( )(2 ),0,1,/41( )(21)NklNiNklNi

9、Xkx l WDFT x lXkx l WDFT x lx lxllNx lxl第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.3 N點DFT的第二次時域抽取分解圖(N=8) N/4點DFTWN12WN12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4點DFTN/4點DFTN/4點DFTWN02WN02第第4章章 快速傅里葉變換快速傅里葉變換(FFT)

10、 圖4.2.4 N點DITFFT運算流圖(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.2.3 DITFFT算法與直接計算DFT運算量的比較 每一級運算都需要N/2次復(fù)數(shù)

11、乘和N次復(fù)數(shù)加(每個蝶形需要兩次復(fù)數(shù)加法)。所以，M級運算總共需要的復(fù)數(shù)乘次數(shù)為22(2)log22(2)logMANNCMNCN MNN復(fù)數(shù)加次數(shù)為 例如，N=210=1024時221048576204.8(/2)log5120NNN第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.5 FFT算法與直接計算DFT所需乘法次數(shù)的比較曲線 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.2.5 頻域抽取法FFT(DIFFFT) 在基2快速算法中，頻域抽取法FFT也是一種常用的快速算法，簡稱DIFFFT。 設(shè)序列x(n)長度為N=2M，首先將x(n)前后對半分開，得到兩個子序列

12、，其DFT可表示為如下形式：10/2 110/2/2 1/2 1(/2)00/2 1/20( ) ( )( )( )( )( )()2 ( )()2NkNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nW第第4章章 快速傅里葉變換快速傅里葉變換(FFT) /21,( 1)1kNkNkWk 偶數(shù) 奇數(shù) X(k)分解成偶數(shù)組與奇數(shù)組，當(dāng)k取偶數(shù)k=2r,r=0,1,N/2-1時 /2 120/2 12/20(2 ) ( )()2 ( )()2NrnNnNrnNnNXrx nx nWNx nx

13、nW(4.2.14)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 當(dāng)k取奇數(shù)(k=2r+1,r=0,1,N/2-1)時/2 1(21)0/2 1/20(21) ( )()2 ( )()2NnrNnNnnrNNnNXrx nx nWNx nx nWW(4.2.15) 將x1(n)和x2(n)分別代入(4.2.14)和(4.2.15)式，可得/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W (4.2.16) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.10 DIFFFT蝶形運算流圖符號 第第4章章 快速傅里葉變換快

14、速傅里葉變換(FFT) 圖4.2.11 DIFFFT一次分解運算流圖(N=8) N/2點DFTWN0N/2點DFTWN1WN2WN3X(0)x1(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.12 DIFFFT二次分解運算流圖(N=8) N/4點DFTWN0WN1WN2WN3x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X

15、(3)X(7)WN0WN2WN0WN2N/4點DFTN/4點DFTN/4點DFT第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.13 DIFFFT運算流圖(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.14 DITFFT的一種變形運算流圖WN0WN0WN2WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x

16、(4)x(5)x(6)x(7)WN0WN2WN1WN3WN2WN0WN0WN0第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.2.15 DITFFT的一種變形運算流圖WN0WN0WN2WN0X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN2WN1WN3WN2WN0WN0WN0第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.2.6 IDFT的高效算法 上述FFT算法流圖也可以用于離散傅里葉逆變換(Inverse Discrete Fourier Transform，簡稱IDFT)。比較DF

17、T和IDFT的運算公式： 1010( ) ( )( )1( ) ( )( )NkNnNknNkX kDFT x nx n Wx nIDFT x nX k WN第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 如果希望直接調(diào)用FFT子程序計算IFFT，則可用下面的方法： 由于 10101( )( )1( )( )NknNkNknNkx nX k WNx nXk WN對上式兩邊同時取共軛，得1011( )( )( )NknNkx nXk WDFT XkNN第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.3 進一步減少運算量的措施進一步減少運算量的措施 4.3.1 多類蝶形單元運算 由DI

18、TFFT運算流圖已得出結(jié)論，N=2M點FFT共需要MN/2次復(fù)數(shù)乘法。 由(4.2.12)式，當(dāng)L=1時，只有一種旋轉(zhuǎn)因子W0N=1，所以，第一級不需要乘法運算。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 綜上所述，先除去第一、二兩級后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是 從L=3至L=M共減少復(fù)數(shù)乘法次數(shù)為(2)(2)2MNCM(4.3.1) 13312( )2222MMLLLLNNN(4.3.2) 因而，DITFFT的復(fù)乘次數(shù)降至 (2)(2)(2)(3)2222MNNNCMM(4.3.3) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 22(1)()()222()()22()222()

19、()22defjxjyxjyjxyxyj xyRjIRxyIxyyx 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 從實數(shù)運算考慮，計算N=2M點DITFFT所需實數(shù)乘法次數(shù)為(2)4(3)2(2)2213(2)102MNNRMNM(4.3.4)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.3.2 旋轉(zhuǎn)因子的生成 在FFT運算中，旋轉(zhuǎn)因子WmN=cos(2m/N)-jsin(2m/N)，求正弦和余弦函數(shù)值的計算量是很大的。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.3.3 實序列的FFT算法 設(shè)x(n)為N點實序列，取x(n)的偶數(shù)點和奇數(shù)點分別作為新構(gòu)造序列y(

20、n)的實部和虛部，即1212( )(2 ),( )(21),0,1,12( )( )( ),0,1,12Nx nxn x nxnnNy nx njx n n對y(n)進行N/2點FFT，輸出Y(k)，那么1122( )( )( ),0,1,1( )( )( )2epopX kDFT x nYkNkXkDFT x njYk 根據(jù)DITFFT的思想及式(4.2.7)和(4.2.8)，可得到 12( )( )( ),0,1,2kNNX kX kW Xk k第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 由于x(n)為實序列，所以X(k)具有共軛對稱性，X(k)的另外N/2點的值為 ()( ),1

21、,2,12NX NkXk k第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.4 分裂基分裂基FFT算法算法 4.4.1 分裂基FFT算法原理 當(dāng)n=pq，且p=N/4，q=4時，n可表示為101010,03,0144NNnpnnnnnn并有 10110/4 13()41000( )( )()4NknNnNNknnNnnX kx n WNxnn W 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 010100/4 13104/4 1024040403304()4 ( )()()423()4NknknNnnNkknknkkNNNWxnn WNNx n Wx nWx nWNx nW WW

22、再將上式中的k表示為10104,01,034Nkkkkk第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 可得 1001010100000010010/4 1(4)0040823(4)(4)0404/4 120040403(4)04( )(4) ()()43()()24 ()()()423()4NkknkkkkknNNkknkkknNX kXkkNx nx nWNNx nWx nWWNNx nx nWx nWNx nWW 對k0=0,1,2,3,并用k表示k1，用n表示n0，可以寫出第第4章章 快速傅里葉變換快速傅里葉變換(FFT) /4 140/4 140/4 14203(4 ) ( )(

23、)()()4243(41) ( )()()()4243(42) ( )()()()424(43) ( )()()(42NknNnNkn nNnNknnNnNNNXkx nx nx nx nWNNNXkx njx nx njx nWNNNXkx nx nx nx nWNNXkx njx nx njx n/4 14303)4014NknnNnNWNk (4.4.1) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) /2 120/4 140/4 1340(2 ) ( )(),01223(41) ( )()()()4240143(43) ( )()()()424014NknNnNnknNNnNnk

24、nNNnNNXkx nx nWkNNNXkx njx nx njx nWWNkNNNXkx njx nx njx nWWNk(4.4.2) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 214234( )( )(),01223( ) ( )()()()4243( ) ( )()()()424014nNnNNNx nx nx nnNNNx nx njx nx njx nWNNNxnx njx nx njx nWNn(4.4.3) 令 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 那么(4.4.2)式可寫成如下更簡明的形式：/2 12220/4 1141440/4 1242440(2

25、)( )( ),012(41)( )( ),014(43)( )( ),014NknNnNknNnNknNnNXkx n WDFT x nkNXkxn WDFT x nkNXkxn WDFT xnk(4.4.4) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.4.1 分裂基第一次分解L形流圖 點DFT 點DFT 點DFTx2(1)x2(1 N/4)2N4N4N) 1 (14x) 1 (24x1NW3NWx(1)41Nx21Nx431Nx 1 1 1 j第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 例如，N=16，第一次抽選分解時，由式(4.4.3)得 x2(n)=x(n)+x

26、(n+8), 0n7x14(n)=x(n)-x(n+8)-jx(n+4)-x(n+12)Wn16, 0n3x24(n)=x(n)-x(n+8)+jx(n+4)-x(n+12)W3n16, 0n3 把上式代入式(4.4.4)，可得 X(2k)=DFTx2(n), 0k7 X(4k+1)=DFTx14(n), 0k3 X(4k+3)=DFTx24(n), 0k3 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.4.2 分裂基FFT算法L形排列示意圖與結(jié)構(gòu)示意圖(a)分裂基FFT算法L形排列示意圖；(b)分裂基FFT算法運算流圖結(jié)構(gòu)示意圖 ( a )( b )第第4章章 快速傅里葉變換快速

27、傅里葉變換(FFT) 圖4.4.3 16點分裂基第一次分解L形流圖(圖中省去箭頭) (8)點DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)點DFT點DFT)0(14x) 1 (14x)2(14x)3(14x)0(24x) 1 (24x)2(24x)3(24x44N44N2Nx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(8)x(9)x(10)x(11)x(12)x(13)x(14)x(15)0NW1NW3NW2NW0NW3NW6NW j j jX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(8)X(9)X(10)X

28、(11)X(12)X(13)X(14)X(15)X(2k)X(4k 1)X(4k 3)1111111111第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 第二次分解： 先對圖4.4.3中N/2點DFT進行分解。 令X1(l)=X(2l)，則有 X1(2l)=DFTy2(n), 0l3 X1(4l+1)=DFTy14(n), 0l1 X1(4l+3)=DFTy24(n), 0l1 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 其中y2(n)=x2(n)+x2(n+4), 0n3y14(n)=x2(n)-x2(n+4)-x2(n+2)x(n+6)Wn8,n=0,1y 2 4 ( n )

29、= x 2 ( n ) - x 2 ( n + 4 ) + jx2(n+2)x2(n+6)W3n8,n=0,1第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.4.4 圖4.4.4中N/2點DFT的分解L形流圖 (4)點DFTx2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)y2(0)y2(1)y2(2)y2(3)X1(0) X(0)X1(2) X(4)X1(4) X(8)X1(6) X(12)X1(1) X(2)X1(5) X(10)X1(3) X(6)X1(7) X(14)X1(2l)X1(4l 1 )X1(4l 3 )4N)0(14y) 1 (14y

30、) 1 (24y)0(24y12NW32NW j j11111111第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.4.5 4點分裂基L形運算流圖 v(0)v(1)v(2)v(3)V(0)V(2)V(1)V(3) j1111第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 圖4.4.6 16點分裂基FFT運算流圖 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(8)x(9)x(10)x(11)x(12)x(13)x(14)x(15)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X(8)X(9)X(10)X(11)X(12)X(13)X(14)X

31、(15) j1111 j j1111 j j111111111111 j j j jW 1W 2W 3W 3W 6W 9W 2W 6111111111111NNNNNNNN第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.4.2 分裂基FFT算法的運算量 設(shè)第j級有l(wèi)j個L形，j=1,2,M-1,M=log2N，則有l(wèi)1=N/4。由圖4.4.2(b)可見，第j-1列中的L形包含了第j列中的一部分結(jié)點的計算，即空白部分，所占結(jié)點數(shù)剛好等于第j-1列中所有L形對應(yīng)結(jié)點的一半，所以第j列L形個數(shù)就減少l j-1/2個，即 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 1112231042

32、41(1)424211(1)42424111()(1) 42424jjjijjilNlNlNlNlNlNlNNl第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 由于每個L形有兩次復(fù)(數(shù))乘運算，所以全部復(fù)乘次數(shù)為1122212() 3332122log( 1)399MMMjjMNClMNNN (4.4.5) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.5 離散哈特萊變換離散哈特萊變換(DHT) 4.5.1 離散哈特萊變換定義 設(shè)x(n),n=0,1,N-1，為一實序列，其DHT定義為102( ) ( )( )cos(),0,1,1NHnXkDHT x nx nkn kNN式中，

33、cas()=cos+sin。其逆變換(IDHT)為1012( )( )( )cos(),0,1,1NHHkx nIDHT XkXkkn nNNN (4.5.3) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.5.2 DHT與DFT之間的關(guān)系 為了便于比較，重寫DFT如下：211002110022( ) ( )( )( )cos()sin()1122( )( )( )cos()sin()NNjknNnnNNjknNkkX kDFT x nx n ex nknjknNNx nX k eX kknjknNNNN(4.5.5) (4.5.6) 容易看出，DHT的核函數(shù) DFT的核函數(shù) 的實部

34、與虛部之和。 222cos()cos()sin()knknknNNN222cos()()jknNeknjknNN第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 將XH(k)分解為奇對稱分量XHo(k)與偶對稱分量XHe(k)之和 ( )( )( )1( )( )()21( )( )()2HHeHoHeHHHoHHXkXkXkXkXkXNkXkXkXNk(4.5.7) (4.5.8)(4.5.9)由DHT定義有10102( )( )cos()2( )( )sin()NHenNHonXkx nknNXkx nknN(4.5.10a)(4.5.10b) 第第4章章 快速傅里葉變換快速傅里葉變換(

35、FFT) 所以，x(n)的DFT可表示為同理，x(n)的DHT可表示為因而，已知x(n)的DHT，則DFT可用下式求得： ( )( )( )HeHoX kXkjXk(4.5.11)( )( )Im( )HeXkH kX k(4.5.12)11( )( )()( )()22HHHHX kXkXNkj XkXNk(4.5.13) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.5.3 DHT的主要優(yōu)點 (1)DHT是實值變換，在對實信號或?qū)崝?shù)據(jù)進行譜分析時避免了復(fù)數(shù)運算，從而提高了運算效率，相應(yīng)的硬件也更簡單、更經(jīng)濟； (2)DHT的正、反變換(除因子1/N外)具有相同的形式，因而，實現(xiàn)D

36、HT的硬件或軟件既能進行DHT，也能進行IDHT； (3)DHT與DFT間的關(guān)系簡單，容易實現(xiàn)兩種譜之間的相互轉(zhuǎn)換。 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.5.4 DHT的性質(zhì) 1. 線性性質(zhì)11221212( ),( )( )( )( )( )( )HHHHxXkx nXkax nbx naXkbXk(4.5.14) 2. x(N-n)的DHT( )( ), ()()HHx nXkx NnXNn1022()( )cos()sin(),0,1,1NHnXNkx nknknkNNN (4.5.15)其中，當(dāng)k=0時，XH(N-k)=XH(N)=XH(0)。第第4章章 快速傅里葉

37、變換快速傅里葉變換(FFT) 3. 循環(huán)移位性質(zhì)00000022()( )( )cos()()sin()22()( )( )cos()()sin()NNHNNHx nnRnXkknH NkknNNx nnRnXkknH NkknNN(4.5.16) (4.5.17) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4. 奇偶性 奇對稱序列和偶對稱序列的DHT仍然是奇對稱序列或偶對稱序列，即DHT不改變序列的奇偶性。 5.循環(huán)卷積定理1122122121121212( )( ),( )( )( )( )( )( )()( )( )( )( )( )()( )HHHHeHHoHHeHHox n

38、Xkx nXkx nx nXk XkXNk Xkx nx nXk XkXNk Xk(4.5.18) (4.5.19) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 。 當(dāng)x1(n)或x2(n)是偶對稱序列時，則由DHT的奇偶性有1212( )( )( )( )( )HHHx nx nXkXk Xk(4.5.21)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 4.5.5 DHT的快速算法(FHT) 1.基2DITFHT算法及運算流圖 仿照快速DFT的分解方法，可通過時域抽取或頻域抽取的方式實現(xiàn)快速DHT。 x(n)的N=2M點DHT如下式：10011122002( )( )cos()

39、,01( )(2 ),01( )(21)222( )(2 )cos(2)(21)cos(21) )NHnNNHrrXkx nknkNNx rxrNrx rxrXkxrrkxrrkNN對x(n)進行奇偶抽取(4.5.22) (4.5.23)第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 與DFT的時域抽取分解比較， 不是 一個指數(shù)函數(shù)，所以處理要比W(2r+1)kN麻煩一些。根據(jù)三角公式有2cos(21)krN112201001210cos()coscoscos()sin222( )( )cos()cos()( )cos()/2/222sin()( )cos()/2HrrrXkx rrkkx rrkNNNkx rrkNN(4.5.24)(4.5.25) 第第4章章 快速傅里葉變換快速傅里葉變換(FFT) 令X0H(k)=DHTx0(n),X1H(k)=DHTx1(n)，并考慮DHT的周期性，(4.5.25)式可寫成01122( )( )cos()( )sin()()2HHHHNXkXkk Xkk XkNN 為了使以下推導(dǎo)中公式簡明，記 C(k)=cos (2/N)k ，S(k)=sin (2/N)/k 。將式(4.5.26)中的k分別取k，N/2+k,N/2-k和N-k四個值，并考慮X0H(k)和X1H(k)以N/2為周期，得到 第第4章章 快速傅里葉變換快速傅