1、第第4 4章章 快速傅里葉變換快速傅里葉變換1/86第第4 4章章 快速傅里葉變換快速傅里葉變換第第4 4章章 快速傅里葉變換快速傅里葉變換2/86 DFT是信號分析與處理中的一種重要變是信號分析與處理中的一種重要變換。直接計算換。直接計算DFT的計算量與變換區間長度的計算量與變換區間長度N的平方成正比，計算量太大，所以在快速的平方成正比，計算量太大，所以在快速傅里葉變換傅里葉變換(簡稱簡稱FFT)出現以前，直接用出現以前，直接用DFT算法進行譜分析和信號的實時處理是不切實算法進行譜分析和信號的實時處理是不切實際的。直到際的。直到1965年發現了年發現了DFT的一種快速算的一種快速算法以后，情

2、況才發生了根本的變化。法以后，情況才發生了根本的變化。 第第4 4章章 快速傅里葉變換快速傅里葉變換3/864.1 DFT4.1 DFT的運算量分析的運算量分析4.1.1 4.1.1 直接計算直接計算DFTDFT的運算量的運算量時域頻域都是離散的有限長序列時域頻域都是離散的有限長序列( )x n( )X k1010( )( ) (01)1( )( ) (01)NnkNnNnkNnX kx n WkNx nX k WnNN DFT計算量太大計算量太大第第4 4章章 快速傅里葉變換快速傅里葉變換4/86 復數乘法：復數乘法：2MCNNN 2(1) (1)ACN NNN 直接計算直接計算DFTDFT

3、需要：需要： 復數加法：復數加法：實數乘法：實數乘法：實數加法：實數加法：24MRN 2222(1)2 424ARN NNNNN直接計算直接計算DFTDFT所需計算量與所需計算量與 成正比！成正比！2N第第4 4章章 快速傅里葉變換快速傅里葉變換5/86 從上面的分析看到，在從上面的分析看到，在DFT計算中，不論計算中，不論是乘法和加法，運算量均與是乘法和加法，運算量均與N2成正比。因此，成正比。因此，N較大時，運算量十分可觀。例，計算較大時，運算量十分可觀。例，計算N=10點點的的DFT，需要，需要100次復數相乘，而次復數相乘，而N=1024點時點時，需要，需要1048576（一百多萬）次

4、復數乘法，如（一百多萬）次復數乘法，如果要求實時處理，則要求有很高的計算速度才果要求實時處理，則要求有很高的計算速度才能完成上述計算量。能完成上述計算量。 反變換反變換IDFT與與DFT的運算結構相同，只是的運算結構相同，只是多乘一個常數多乘一個常數1/N，所以二者的計算量相同。，所以二者的計算量相同。第第4 4章章 快速傅里葉變換快速傅里葉變換6/864.1.2 4.1.2 改善改善DFTDFT運算效率的基本途徑運算效率的基本途徑()()nkk N nnkNNNWWW1、 的對稱性：的對稱性：nkNWnknk lNNNWW 2、 的周期性：的周期性：nkNW（ 為整數為整數）lnkmnkNm

5、NWW 3、 的可約性：的可約性：nkNW()22NNnknknkNNNNWWWW nknk mNN mWW 第第4 4章章 快速傅里葉變換快速傅里葉變換7/86 例如，對例如，對4點點DFT，直接計算需要，直接計算需要42=16次復數乘法。根據上述次復數乘法。根據上述 的性質，可寫成的性質，可寫成如下的矩陣形式如下的矩陣形式 knNW0 00 10 (1)1 01 11 (1)2 02 12 (1)(1) 0(1) 1(1) (1)(0)(0)(1)(1)(1)(0)(1)(1)(2)(0)(1)(1)(1)(0)(1)(1)NNNNNNNNNNNNNNNNNNNXxWxWx NWXxWxW

6、x NWXxWxWx NWX NxWxWx NW DFT寫成如下的矩陣形式寫成如下的矩陣形式 第第4 4章章 快速傅里葉變換快速傅里葉變換8/8600004444012344440246444403694444(0)(0)(1)(1)(2)(2)(3)(3)XxWWWWXxWWWWXxWWWWXxWWWW 令令00004444012344440246444403694444WWWWWWWWWWWWWWWWW 00004444012344440202444403214444WWWWWWWWWWWWWWWWnkNW利利用用的的周周期期性性第第4 4章章 快速傅里葉變換快速傅里葉變換9/86利利用用

7、的的共共軛軛對對稱稱性性nkNW00004444010144440000444401014444WWWWWWWWWWWWWWWW 114411441111(0)(0)11(1)(1)1111(2)(2)11(3)(3)XxWWXxXxWWXx 則，則，4 4點點DFTDFT矩陣公式變為矩陣公式變為00004444012344440202444403214444WWWWWWWWWWWWWWWWW 第第4 4章章 快速傅里葉變換快速傅里葉變換10/86將該矩陣的第二列和第三列交換，得到將該矩陣的第二列和第三列交換，得到114411441111(0)(0)11(1)(2)1111(2)(1)11(3

8、)(3)XxWWXxXxWWXx 由此得到由此得到 1414(0)(0)(2)(1)(3)(1)(0)(2)(1)(3)(2)(0)(2)(1)(3)(3)(0)(2)(1)(3)XxxxxXxxxxWXxxxxXxxxxW 第第4 4章章 快速傅里葉變換快速傅里葉變換11/86 快速傅里葉算法的基本思想快速傅里葉算法的基本思想（1）利用利用 的性質的性質減少計算量。減少計算量。（2）把長序列的）把長序列的DFT分解成短序列的分解成短序列的DFT，也可以有，也可以有效的減少效的減少DFT運算中復數乘法和復數加法的次數。運算中復數乘法和復數加法的次數。 如果信號長度為如果信號長度為 N，它可表示

9、成：，它可表示成： 當當 時，上式可寫成時，上式可寫成 ，因子，因子 稱稱為基（為基（radix）。）。 當當FFT算法中進行序列分解時是采用算法中進行序列分解時是采用則稱為基則稱為基-2（radix-2）FFT。 knNWmrrrN21rrrrm21mrN rmN2第第4 4章章 快速傅里葉變換快速傅里葉變換12/86 N=2M，4.2 4.2 時間抽取的基時間抽取的基-2FFT-2FFT算法算法.2.1.算法的的基本原理算法的的基本原理1212( )( )( ) 012()( )( ) 2kNkNX kX kW XkNkNX kX kW Xk （）則：則： ( )DFT( )

10、 , 0,1,X kx nn kN1( )(2 ),x rxr 2( )(21),01,2Nx rxrr設：設：若若奇數序號奇數序號偶數序號偶數序號 點序列點序列2N 和和 的的 點點DFT1( )x r2( )xr2N1122( )DFT( ),01,( )DFT( )2X kx rNkXkx r 第第4 4章章 快速傅里葉變換快速傅里葉變換13/86 10)()(NnknNWnxkX/2 1/2 12(21)00(2 )(21)NNkrkrNNrrxr WxrW /2 1/2 1221200( )( )NNkrkrkNNNrrx r Wxr WW/2 1/2 11/22/20012( )(

11、 )( )( )0,1,.,/ 21NNkrkkrNNNrrkNx r WWx r WXkW XkkN第第4 4章章 快速傅里葉變換快速傅里葉變換14/86對于對于 后后N/2的的DFT ：由于由于 （周期性）（周期性）因此因此)(kXkNNkNWW 2/)()()2(21kXWkXNkXkN 12,.,1 , 0 Nk第第4 4章章 快速傅里葉變換快速傅里葉變換15/86例：畫出例：畫出N=8N=8的時間抽取基的時間抽取基2FFT2FFT算法流圖。算法流圖。( ) (0), (1), (2), (3), (4), (5), (6), (7)x nxxxxxxxx ( )DFT ( )X kx

12、 n 解：解： 將將 按時間抽取基按時間抽取基2FFT2FFT算法進行分解：算法進行分解：( )x n1( ) (0), (2), (4), (6)x nxxxx 2( ) (1), (3), (5), (7)x nxxxx 1111(0),(1),(2),(3)xxxx 2222(0),(1),(2),(3)xxxx 4點點序列序列第第4 4章章 快速傅里葉變換快速傅里葉變換16/86仍然是偶數仍然是偶數第第4 4章章 快速傅里葉變換快速傅里葉變換17/86 由于由于 , ,因而因而N/2N/2仍是偶數仍是偶數, ,可以進一可以進一步把每個步把每個N/2N/2點的序列再按其奇偶部分分解點的序

13、列再按其奇偶部分分解為兩個為兩個N/4N/4的子序列的子序列從而從而 可表示為可表示為 MN2 3141221( )()( )()x lxlx lxl0,1,(1)4Nl )(1kX4 14 12(21)1121200( )(2 )(21)NNklklNNllX kxl WxlW 324( )( )kNXkWXk0,1,14Nk 第第4 4章章 快速傅里葉變換快速傅里葉變換18/86因而有因而有對對 也可進行同樣的分解：也可進行同樣的分解： )(2kX25/2625/26( )( )( ) 014()( )( ) 4kNkNXkXkWXkNkNXkXkWXk （）13/2413/24( )(

14、)( ) 014()( )( ) 4kNkNX kXkWXkNkNX kXkWXk （）21342134( )( )( ) 014()( )( ) 4kNkNX kXkWXkNkNX kXkWXk （）22562256( )( )( ) 014()( )( ) 4kNkNXkXkWXkNkNXkXkWXk （）2/2kkNNWW統統一一系系數數：第第4 4章章 快速傅里葉變換快速傅里葉變換19/86第一次分解：第一次分解：第二次分解：第二次分解：1( ) (0), (2), (4), (6)x nxxxx 2( ) (1), (3), (5), (7)x nxxxx 3( ) (0), (4)

15、x nxx 33(0),(1)xx 4( ) (2), (6)x nxx 44(0),(1)xx 5( ) (1), (5)x nxx 55(0),(1)xx 6( ) (3), (7)x nxx 66(0),(1)xx 1111(0),(1),(2),(3)xxxx2222(0),(1),(2),(3)xxxx2點點序列序列第第4 4章章 快速傅里葉變換快速傅里葉變換20/86 如下圖所示：如下圖所示： 那么依次類推，經過那么依次類推，經過M-1次分解后，將次分解后，將N點點DFT分解分解成成N/2個兩點個兩點DFT第第4 4章章 快速傅里葉變換快速傅里葉變換21/86第三次分解：第三次分解

16、：3( ) (0), (4)x nxx 33(0),(1)xx 4( ) (2), (6)x nxx 44(0),(1)xx 5( ) (1), (5)x nxx 55(0),(1)xx 6( ) (3), (7)x nxx 66(0),(1)xx 7( ) (0)x nx 8( ) (4)x nx 9( ) (2)x nx 10( ) (6)xnx 11( ) (1)xnx 12( ) (5)xnx 13( ) (3)xnx 14( ) (7)xnx 第第4 4章章 快速傅里葉變換快速傅里葉變換22/86 例如例如N=8時，分解為時，分解為4個兩點個兩點DFT，其輸出分別為，其輸出分別為例如

17、：例如：即即上式中用到了上式中用到了3456( ),( ),( ),( )XkXkXkXk0,1k 4 116646400( )( )( ),0,1NklklNNllXkx l Wx l Wk 00066262(0)(0)(1)(3)(7)(3)(7)NXxW xxW xxW x 11066262(1)(0)(1)(3)(7)(3)(7)NXxW xxW xxW x 2j1j0221NWeeW 第第4 4章章 快速傅里葉變換快速傅里葉變換23/86 下圖為下圖為N=8時的一個完整基時的一個完整基-2DIT-FFT運算流圖運算流圖第第4 4章章 快速傅里葉變換快速傅里葉變換24/86對對 點序列

18、：點序列： 4.2.2 4.2.2 運算量運算量N N點點N/2N/2點點N/4N/4點點1 1點點2MN 1 1點序列的點序列的DFTDFT等于本身序列值等于本身序列值最后按時間抽取基最后按時間抽取基2FFT2FFT算法的計算法的計算量僅由蝶行運算產生。算量僅由蝶行運算產生。第第4 4章章 快速傅里葉變換快速傅里葉變換25/86一次蝶式運算需：一次蝶式運算需：1 1次復數乘法和次復數乘法和2 2次復數加法次復數加法按時間抽取基按時間抽取基-2FFT-2FFT共有：共有： 個運算蝶個運算蝶2log22NNMN 基基-2FFT-2FFT 復數乘法：復數乘法： 復數加法：復數加法：2log2NN2

19、2log22logNNNN 直接直接DFTDFT 2N2N1212 ( )( )( ) 012()( )( )2kNkNX kX kW XkNkNX kX kW Xk （）第第4 4章章 快速傅里葉變換快速傅里葉變換26/860100200300400500600700800900100001234567891011x 105直接計直接計算算DFTDFTFFTFFT第第4 4章章 快速傅里葉變換快速傅里葉變換27/86DFT和和FFT運算量比較運算量比較function Xk=FourierTran(xn,N)if nargin 2 N = length(xn);end n = 0 : N -

20、 1;k = 0 : N - 1;WN = exp( - j * 2 * pi / N);nk = n * k;WNnk = WN . nk;Xk = xn * WNnk;第第4 4章章 快速傅里葉變換快速傅里葉變換28/86Matlab程序演示程序演示1 1、直接利用定義計算、直接利用定義計算DFTDFTx=ones(1,1024);f=() FourierTran(x,1024);timeit(f)運行結果：運行結果：ans = 0.7239ans = 0.72392 2、利用、利用FFTFFT算法計算算法計算DFTDFTf1=() fft(x,1024);timeit(f1)運行結果：運

21、行結果：ans = 1.5766e-005ans = 1.5766e-0050.7239 / (1.5766e-005) = 4.5915e+004第第4 4章章 快速傅里葉變換快速傅里葉變換29/864.2.3.FFT4.2.3.FFT算法的特點算法的特點1 1）原位計算（同址運算）原位計算（同址運算）第第4 4章章 快速傅里葉變換快速傅里葉變換30/86m表示第表示第m級迭代，級迭代，i，j表示數據所在的行數表示數據所在的行數1111( )( )( )( )( )( )rmmmNrmmmNAiAiAj WAjAiAj W第第4 4章章 快速傅里葉變換快速傅里葉變換31/862 2）輸入序列

22、的序號及整序規律）輸入序列的序號及整序規律DITFFT算法的輸入序列的排序看起來似乎算法的輸入序列的排序看起來似乎很亂，但仔細分析就會發現這種排序是很有很亂，但仔細分析就會發現這種排序是很有規律的。由于規律的。由于N=2M，所以順序數可用，所以順序數可用M位二位二進制數進制數(nM-1nM-2n1n0)表示。表示。 第第4 4章章 快速傅里葉變換快速傅里葉變換32/86(0) (1) (2) (3) (4) (5) (6) (7)xxxxxxxx(0) (2) (4) (6)xxxx(1) (3) (5) (7)xxxx(0) (4)xx(2) (6)xx(1) (5)xx(3) (7)xx(

23、0) (4) (2) (6) (1) (5) (3) (7)xxxxxxxx000 010 100 110001 011 101 111000 100010 110001 101011 111000100010110001101011111000 001 010 011 100 101 110 111第第4 4章章 快速傅里葉變換快速傅里葉變換33/86輸入的混序輸入的混序是通過輸入正序序列按是通過輸入正序序列按碼位倒置碼位倒置實現的實現的。自然順序自然順序( )n二進制數二進制數 倒位序二進制數倒位序二進制數 倒位順序倒位順序 ( )n0123456700000101001110010111

24、011100010001011000110101111104261537第第4 4章章 快速傅里葉變換快速傅里葉變換34/86x(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)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)輸入數據的變址處理第第4 4章章 快速傅里葉變換快速傅里葉變換35/86 3 3）各類蝶形運算兩節點的）各類蝶形運算兩節點的“距離距離”及及 的變化規律的變化規律rNW對對N = 2M點點FFT，輸入倒位序，輸出自然序

25、，第，輸入倒位序，輸出自然序，第m級級運算每個蝶形的兩節點距離為運算每個蝶形的兩節點距離為 2m1，第，第m級運算：級運算：1111111( )( )(2)(2)( )(2)mrmmmNmmrmmmNAiAiXiWAiAiXiW 1111( )( )( )( )( )( )rmmmNrmmmNAiAiAj WAjAiAj W第第4 4章章 快速傅里葉變換快速傅里葉變換36/86蝶形運算兩節點的第一個節點為蝶形運算兩節點的第一個節點為i值，表示值，表示成成M位二進制數，左移位二進制數，左移M m位，把右邊空位，把右邊空出的位置補零，結果為出的位置補零，結果為r的二進制數。的二進制數。rNW 的的

26、確確定定2( )2Mmri （1 1）直接計算法）直接計算法第第4 4章章 快速傅里葉變換快速傅里葉變換37/86第第4 4章章 快速傅里葉變換快速傅里葉變換38/86級數 的取值范圍 重復組數 第一級 第二級 第三級 第m級 第M級 1rNW0NW2/N0NW4/NNW4/N0NW0NW0NW8/NNW8/2NNW8/3NNWmNNW2/1NWmNNW2/22NW mmNNW2/)12(112/NNW8/NmN 2/ （2 2）逆推法）逆推法第第4 4章章 快速傅里葉變換快速傅里葉變換39/86 4.2.4 4.2.4、DITDIT算法的其他形式流圖算法的其他形式流圖n輸入自然序輸出倒位序輸

27、入自然序輸出倒位序n輸入輸出均自然序輸入輸出均自然序n相同幾何形狀相同幾何形狀n輸入自然序輸出倒位序輸入自然序輸出倒位序第第4 4章章 快速傅里葉變換快速傅里葉變換40/86 第第4 4章章 快速傅里葉變換快速傅里葉變換41/86第第4 4章章 快速傅里葉變換快速傅里葉變換42/86第第4 4章章 快速傅里葉變換快速傅里葉變換43/864.3.1 算法的基本原理算法的基本原理 設序列設序列x(n)長度為長度為N=2M，首先將，首先將x(n)前后對半分開，前后對半分開，得到兩個子序列，其得到兩個子序列，其DFT可表示為如下形式：可表示為如下形式： 12/02/12/0)2/(12/012/12/

28、010)2/()()2/()()()()()(DFT)(NnnkNNkNNnkNnNNnnkNNNnnkNNnnkNNnnkNWNnxWnxWNnxWnxWnxWnxWnxnxkX4.3 頻域抽取基頻域抽取基-2 FFT算法算法第第4 4章章 快速傅里葉變換快速傅里葉變換44/86由于由于N點點DFT按按k的奇偶分組可分為兩個的奇偶分組可分為兩個N/2的的DFTk取偶數時（取偶數時（k=2r，r=0,1,.,N/2-1） /21( 1)1kNkNkWk 為為偶偶數數為為奇奇數數/2 120/2 1/20(2 )( )2( )2NrnNnNrnNnNXrx nx nWNx nx nW 第第4 4

29、章章 快速傅里葉變換快速傅里葉變換45/86設設2221(21)010(21)( )()2( )()2NNNnrNnnnrNnNXrx nx nWNx nx nWW 12( )( )+ ()20,1,12( )( )()2nNNx nx nx nNnNx nx nx nW 第第4 4章章 快速傅里葉變換快速傅里葉變換46/86 將將x1(n)和和x2(n)分別代入分別代入 和和 式，可得式，可得/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx nWXrx nW (2 )Xr(21)Xr則則X(2r)和和X(2r+1)分別是分別是x1(n)和和x2(n)的的

30、 N / 2點點DFT，記為記為X1(k)和和X2(k)第第4 4章章 快速傅里葉變換快速傅里葉變換47/86DIF-FFT的一次分解運算流圖（N=8）：第第4 4章章 快速傅里葉變換快速傅里葉變換48/86 由于由于N/2仍然為仍然為2的整數冪，繼續將的整數冪，繼續將N/2點點DFT分成偶數組和奇數組，這樣每個分成偶數組和奇數組，這樣每個N/2點點DFT又可分解成兩個又可分解成兩個N/4點點DFT，其輸，其輸入序列分別是按上下對半分圖開后通過蝶入序列分別是按上下對半分圖開后通過蝶式運算構成的式運算構成的4個子序列個子序列 ,如下圖如下圖第第4 4章章 快速傅里葉變換快速傅里葉變換49/86第

31、第4 4章章 快速傅里葉變換快速傅里葉變換50/86 按照以上方法繼續分解下去，經過按照以上方法繼續分解下去，經過M-1次次分解，最后分解為分解，最后分解為N/2個兩點個兩點DFT，這，這N/2個個2點點DFT的輸出就是的輸出就是N點點DFT的結果的結果X(k) ，如下圖，如下圖第第4 4章章 快速傅里葉變換快速傅里葉變換51/86第第4 4章章 快速傅里葉變換快速傅里葉變換52/86第第4 4章章 快速傅里葉變換快速傅里葉變換53/86蝶形運算兩節點的第一個節點為值蝶形運算兩節點的第一個節點為值k，表，表示成示成M位二進制數，左移位二進制數，左移m-1位，把右邊位，把右邊空出的位置補零，結果

32、為空出的位置補零，結果為r的二進制數。的二進制數。rNW 的的確確定定12( )2mrk第第4 4章章 快速傅里葉變換快速傅里葉變換54/86 以上所討論的以上所討論的FFT的運算方法同樣可用的運算方法同樣可用于于IDFT的運算，簡稱為的運算，簡稱為IFFT。即快速。即快速傅傅里葉里葉反變換。從反變換。從IDFT的定義出發，可以的定義出發，可以導出下列二種利用導出下列二種利用FFT來計算來計算IFFT的方的方法法。4.4 快速傅里葉反變換快速傅里葉反變換第第4 4章章 快速傅里葉變換快速傅里葉變換55/8.1.1.稍微變動稍微變動FFTFFT程序和參數可實現程序和參數可實現IF

33、FTIFFT1010DFT1IDFT( )( )( )( )( )( )NnkNnNnkNkX kx nx n Wx nX kX k WN只要只要DFT的每個系數的每個系數 換成換成 ,最后再乘以最后再乘以常數常數1/N就可以得到就可以得到IDFT的快速算法的快速算法-IFFT。另外另外,可以將常數可以將常數1/N分配到每級運算中分配到每級運算中, ,也就是每級也就是每級蝶形運算均乘以蝶形運算均乘以1/2。 MN)21(1 nkNWnkNW第第4 4章章 快速傅里葉變換快速傅里葉變換56/86第第4 4章章 快速傅里葉變換快速傅里葉變換57/8.2不改變不改變FFTFFT的程

34、序直接實現的程序直接實現IFFTIFFT因為因為所以所以 101,.,0,)(1)(NknkNNnWkXNnx 10)(1)(NknkNWkXNnx兩邊取共軛有：兩邊取共軛有：101( )( ),0,.,1NnkNkx nXk WnNN 1DFT( )XkN 第第4 4章章 快速傅里葉變換快速傅里葉變換58/864.6 實序列的實序列的FFT算法算法n根據序列根據序列DFT的共軛對稱性知道，任意的共軛對稱性知道，任意復數序列的實部的復數序列的實部的DFT對應于其對應于其DFT共共軛對稱分量，而其虛部的軛對稱分量，而其虛部的DFT對應于其對應于其DFT共軛反對稱分量，故可用一次共軛反對稱分量，故

35、可用一次N點點DFT計算兩個計算兩個N點實序列的點實序列的DFT。第第4 4章章 快速傅里葉變換快速傅里葉變換59/86設設 和和 為兩個長度為為兩個長度為N的實序列，的實序列，按如下方式構造新序列按如下方式構造新序列 ：1( )x n2( )x n( )y n12( )( )( )y nx njx nN點點DFT為為( )DFT ( )( )( )epopY ky nYkYk 4.6.1利用頻譜對稱性求實信號的利用頻譜對稱性求實信號的FFT第第4 4章章 快速傅里葉變換快速傅里葉變換60/86根據共軛對稱性，則根據共軛對稱性，則*1*21( )DFT( ) ( )()( )21( )DFT(

36、 ) ( )()( )2epNNopNNYkx nY kYNkRnYkjx nY kYNkRn 所以所以*11*221( )DFT( )( ) ( )()( )2( )DFT( )( ) ( )()( )2epNNopNNXkx nYkY kYNkRnjXkxnjYkY kYNkRn 第第4 4章章 快速傅里葉變換快速傅里葉變換61/86設一個設一個2N點的序列點的序列 ，現按偶、奇進行，現按偶、奇進行分解得：分解得：( )x n12( )(2 )01( )(21)x nxnnNx nxn 再構造復數序列再構造復數序列y(n)12( )( )( )y nx njx n第第4 4章章 快速傅里葉

37、變換快速傅里葉變換62/86122122( )( )( )01()( )( )kNkNY kXkWXkkNY kNXkWXk 這相當于一個這相當于一個N點點DFT運算加上運算加上DIT-FFT蝶蝶形運算，當形運算，當N較大時，可節省近一半的計算較大時，可節省近一半的計算量。量。然后先求出然后先求出x1(n)和和x2(n)的的N點點DFTX1(k)和和X2(k)，因為，因為x1(n)和和x2(n)分別是原序列分別是原序列x(n)的的偶、奇序列，這與按時間抽取的偶、奇序列，這與按時間抽取的FFT算法的算法的分解思路完全相同，故根據分解思路完全相同，故根據DIT-FFT蝶形運蝶形運算式，可得算式，可

38、得第第4 4章章 快速傅里葉變換快速傅里葉變換63/864.6.2 離散哈特曼變換1 1、離散哈特曼變換的定義、離散哈特曼變換的定義設設x x( (n n) )為一為一N N點的實序列，則其離散哈特曼變換點的實序列，則其離散哈特曼變換（DHTDHT）為）為1H02( )DHT ( )( )cas()01NnnkXkx nx nkNN逆變換為逆變換為1HH012( )IDHT( )( )cas()01Nknkx nXkXknNNN式中式中222cas()cos()sin()nknknkNNN第第4 4章章 快速傅里葉變換快速傅里葉變換64/862. DHT與與DFT的關系的關系DFT和和IDFT

39、用歐拉公式展開可表示成用歐拉公式展開可表示成12/010( )DFT ( )( )22( )cos()sin()01Njnk NnNnX kx nx n enknkx njkNNN12/010( )IDFT( )( )22( )cos()sin()01Njnk NkNkx nX kX k enknkX kjnNNN第第4 4章章 快速傅里葉變換快速傅里葉變換65/86可以看出，可以看出，DHT的核函數的核函數是是DFT核函數核函數的實部和虛部之和。的實部和虛部之和。將將 分解為奇對稱分量和偶對稱分量之和分解為奇對稱分量和偶對稱分量之和222cas()cos()sin()nknknkNNN2/2

40、2cos()sin()jnk NnknkejNNH( )XkHHH( )( )( )eoXkXkXk第第4 4章章 快速傅里葉變換快速傅里葉變換66/86其中其中由由DHT的定義可得的定義可得HHHHHH1( )( )()21( )( )()2eoXkXkXNkXkXkXNk1H01H02( )( )cos()2( )( )sin()NenNonnkXkx nNnkXkx nN第第4 4章章 快速傅里葉變換快速傅里葉變換67/86所以所以因此因此 如果不考慮因子如果不考慮因子1/2，只要增加，只要增加2N次實數加法次實數加法運算就能由運算就能由DHT求出求出DFT。HHH( )( )( )(

41、)Re( )Im( )eoX kXkjXkXkX kX kHHHH1( )( )()( )()22jX kXkXNkXkXNk第第4 4章章 快速傅里葉變換快速傅里葉變換68/863. DHT的快速算法（的快速算法（FHT）n仿照快速仿照快速DFT的分解方法，可通過時域的抽取的分解方法，可通過時域的抽取或頻域抽取方式實現快速或頻域抽取方式實現快速DHT。將。將N=2M點的點的實序列實序列 進行奇偶抽取進行奇偶抽取n則則12( )(2 )0,1,/2 1( )(21)x rxrrNx rxr/2 1/2 1H0022( )DHT ( )(2 )cas(2)(21)cas(21) )NNrrXkx

42、 nxrrkxrrkNN第第4 4章章 快速傅里葉變換快速傅里葉變換69/86根據三角公式根據三角公式令令 ， ，根據，根據DHT的周期性，在的周期性，在 時時cas()cascoscas()sin/2 1H10/2 1/2 122002( )( )cas()/22222cos()( )cas()sin()( )cas()/2/2NrNNrrXkx rrkNkx rrkkx rrkNNNN1H1( )DHT( )Xkx n2H2( )DHT( )Xkx n0k H1H2222( )( )cos()( )sin()()2HHNXkXkk Xkk XkNN第第4 4章章 快速傅里葉變換快速傅里葉變

43、換70/86類似于類似于DIT基基-2FFT分解的同址運算思想，可用分解的同址運算思想，可用 、 、 和和 四個四個點同址運算得出點同址運算得出 、 、和和 。這種運算構成了一個運算蝶形，。這種運算構成了一個運算蝶形，稱為稱為“哈特曼蝶形哈特曼蝶形”。設設將上式中將上式中k分別取分別取k、N/2+k、N/2-k和和N-k四個值四個值，并考慮，并考慮 和和 以以N/2為周期，當為周期，當時，得到時，得到 1H( )Xk2H( )Xk1H(/2)XNk2H(/2)XNkH( )XkH(/2)XNkH(/2)XNkH()XNk2cos()kckN2sin()kskN1H( )Xk2H( )Xk8N

44、第第4 4章章 快速傅里葉變換快速傅里葉變換71/86H1H22H1H22H1H22H1H22( )( )( )(/2)(/2)( )( )(/2)04(/2)(/2)( )(/2)()(/2)( )(/2)kHkHkHkHkHkHkHkHXkXkc Xks XNkXNkXkc Xks XNkNkXNkXNks Xkc XNkXNkXNks Xkc XNkH1H2H1H2(0)(0)(0)0(/2)(0)(0)HHXXXkXNXXH1H2H1H2(/4)(/4)(/4)(3/4)(/4)(/4)4HHXNXNXNNkXNXNXN第第4 4章章 快速傅里葉變換快速傅里葉變換72/86上述的運算可

45、用哈德曼蝶形表示如圖上述的運算可用哈德曼蝶形表示如圖4.5.1所示所示第第4 4章章 快速傅里葉變換快速傅里葉變換73/86四點的四點的FHT的蝶形圖如圖的蝶形圖如圖4.5.2所示。所示。第第4 4章章 快速傅里葉變換快速傅里葉變換74/86圖圖4.5.3顯示了顯示了8點的點的DIT基基-2FHT流圖流圖。第第4 4章章 快速傅里葉變換快速傅里葉變換75/86運算量運算量乘法次數乘法次數加法次數加法次數211(2)34MLHLmNNMN33222HaNMN2MN 第第4 4章章 快速傅里葉變換快速傅里葉變換76/864.7 線性卷積和線性相關的線性卷積和線性相關的FFT算法算法10( )( )

46、* ( )() ()Mmy nx nh nh m x nm 4.7.1 有限長序列線性卷積的有限長序列線性卷積的FFT算法算法序列：序列：x(n)（n=0L-1） h(n)（n=0M-1）線性卷積：線性卷積：y(n)的長度：的長度：1MLdmLM 計算量（乘法次數）：計算量（乘法次數）：第第4 4章章 快速傅里葉變換快速傅里葉變換77/86用用FFT算法也就是用算法也就是用循環循環卷積來代替線性卷積卷積來代替線性卷積時，為了不產生混疊，其必要條件是使時，為了不產生混疊，其必要條件是使x(n)，h(n)都補零值，補到至少都補零值，補到至少N=M+L-1，即，即( ) 01( )0 1h nnMh

47、 nMnN ( ) 01( )0 1x nnLx nLnN 這時，這時，y(n)就能代表線性卷積的結果。就能代表線性卷積的結果。( )( )y nx n ( )h nN第第4 4章章 快速傅里葉變換快速傅里葉變換78/86利用利用FFT進行線性卷積的步驟：進行線性卷積的步驟：1.將序列將序列x(n)和和h(n)補零，使其長度補零，使其長度NL+M-1 2.做做x(n)和和h(n)的的N點點FFT得到得到X(k)和和H(k)，并計，并計算算Y(k)=X(k)H(k)3.求求Y(k)的的IFFT獲得線性卷積的結果為獲得線性卷積的結果為( )IFFT ( )01y nY knN第第4 4章章 快速傅

48、里葉變換快速傅里葉變換79/86整個過程中，共需要進行三次整個過程中，共需要進行三次FFT運算，共需運算，共需 次相乘，還有步驟（次相乘，還有步驟（2）的）的N次相乘，次相乘，因此共需相乘次數為因此共需相乘次數為23log2NN2233log(1log)22FmNNNNN22332(1log)2(1)1log (1)22dmFmMLMLKmNNMLML 第第4 4章章 快速傅里葉變換快速傅里葉變換80/86x(n)與與h(n)點數差不多，點數差不多，設設M=L，當當M=L且且M超過超過64以后，以后，M越長越長循環循環卷積的卷積的好處越明顯。因而將好處越明顯。因而將循環循環卷積稱為卷積稱為快速

49、卷積快速卷積。2-12NMM2253106log4(log)22mMMKMM 第第4 4章章 快速傅里葉變換快速傅里葉變換81/86 ，則，則 ，有，有LM 1NLML223logmMKL 4.7.2 有限長序列無限長序列線性卷積的有限長序列無限長序列線性卷積的FFT算法算法基本思路：基本思路： 把有限序列和無限序列之間的線性卷積把有限序列和無限序列之間的線性卷積變成若干個有限序列之間的線性卷積。變成若干個有限序列之間的線性卷積。具體方法：具體方法： 重疊相加法重疊相加法(Overlap-add method) (Overlap-add method) 重疊保留法重疊保留法(Overlap-s

50、ave method)(Overlap-save method)第第4 4章章 快速傅里葉變換快速傅里葉變換82/86一、重疊相加法（一、重疊相加法（overlap-add methodoverlap-add method）1.1.主要思想主要思想( ) ()ih i x ni 為無限序列，為無限序列， 為為M M點有限序列，計算點有限序列，計算( )x n( )h n10( ) () ()Mih i x nin 思路：將長序列思路：將長序列 分段分段( )x n( )( )( )y nh nx n 第第4 4章章 快速傅里葉變換快速傅里葉變換83/86a.a.將將 均勻分段，每段長度為均勻分

51、段，每段長度為N N10( )( )Piix nx n 10( )( )* ( )( )* ( )Piiy nx nh nx nh n ( ) (1)1( )0 ix niLniLx nelse 10( )Piiy n (分段過程無重疊分段過程無重疊)( )x n( )iy n 第第4 4章章 快速傅里葉變換快速傅里葉變換84/86用線性卷積或循環卷積用線性卷積或循環卷積 b. b. 計算子段卷積計算子段卷積( )( )* ( )iiy nx nh n , (1)2niLiLM01iP , (1)1 0, 1iLiLM 計算方法：計算方法：用循環卷積計算需要注意什么？用循環卷積計算需要注意什么

52、？ 思考：思考：第第4 4章章 快速傅里葉變換快速傅里葉變換85/86c. c. 相加相加10( )( )Piiy ny n ( )iy n長度為長度為L+M-1相加時，相鄰相加時，相鄰 重疊重疊M-1個點。個點。( )iy n( )iy n起點為起點為iL第第4 4章章 快速傅里葉變換快速傅里葉變換86/86 由于由于xi (n)的長度為的長度為L，h(n)的長度為的長度為M，所以所以yi (n)的長度為的長度為即即yi (n)的范圍為的范圍為將上式將上式xi (n)的范圍比較，顯然的范圍比較，顯然yi (n)的范圍比的范圍比xi (n)的的范圍大，超出的點數為范圍大，超出的點數為而而yi

53、+1(n)的范圍為的范圍為1NML2(1)2iLniLLMiLM (1)2(1)11iLMiLM (1)(1)2(2)2iLniLLMiLM第第4 4章章 快速傅里葉變換快速傅里葉變換87/86 可以看出，由可以看出，由(i+1) L到到(i+1) L+M-2這這M-1點上，點上， yi (n)的后部分與的后部分與yi +1(n)的前部分發生了重疊。這樣的前部分發生了重疊。這樣對于在此范圍內的每一個對于在此范圍內的每一個n值，原序列值，原序列x(n)與與h(n)的的卷積結果應該是卷積結果應該是即并不是將各段線性卷積的結果簡單地拼接在一起即并不是將各段線性卷積的結果簡單地拼接在一起，在某些點上需要前后兩端的結果重疊相加。，在某些點上需要前后兩端的結果重疊相加。1( )( )( )iiy ny nyn 第第4 4章章 快速傅里葉變換快速傅里葉變換88/86第第4 4章章 快速傅里葉變換快速傅里葉變換89/86為了得到兩個序列為了得到兩個序列x(n)和和h(n)最終的線性卷積結果，最終的線性卷積結果，需將相鄰兩段的需將相鄰兩段的M-1個重疊點的值相加，故稱為個重疊點的值相加，故稱為重疊重疊相加法相加法。在求出各。在求出各yi (n)后，后，x(n)和和h(n)的線性卷積的線性卷積y(n)可分段表示為