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

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

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

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

5、NWW 3、 的可約性：的可約性：nkNW()22NNnknknkNNNNWWWW nknk mNN mWW 第第4 4章章 快速傅里葉變換快速傅里葉變換7/86 例如，對(duì)例如，對(duì)4點(diǎn)點(diǎn)DFT，直接計(jì)算需要，直接計(jì)算需要42=16次復(fù)數(shù)乘法。根據(jù)上述次復(fù)數(shù)乘法。根據(jù)上述 的性質(zhì)，可寫(xiě)成的性質(zhì)，可寫(xiě)成如下的矩陣形式如下的矩陣形式 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寫(xiě)成如下的矩陣形式寫(xiě)成如下的矩陣形式 第第4 4章章 快速傅里葉變換快速傅里葉變換8/8600004444012344440246444403694444(0)(0)(1)(1)(2)(2)(3)(3)XxWWWWXxWWWWXxWWWWXxWWWW 令令00004444012344440246444403694444WWWWWWWWWWWWWWWWW 00004444012344440202444403214444WWWWWWWWWWWWWWWWnkNW利利用用的的周周期期性性第第4 4章章 快速傅里葉變換快速傅里葉變換9/86利利用用

7、的的共共軛軛對(duì)對(duì)稱(chēng)稱(chēng)性性nkNW00004444010144440000444401014444WWWWWWWWWWWWWWWW 114411441111(0)(0)11(1)(1)1111(2)(2)11(3)(3)XxWWXxXxWWXx 則，則，4 4點(diǎn)點(diǎn)DFTDFT矩陣公式變?yōu)榫仃嚬阶優(yōu)?0004444012344440202444403214444WWWWWWWWWWWWWWWWW 第第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）利用利用 的性質(zhì)的性質(zhì)減少計(jì)算量。減少計(jì)算量。（2）把長(zhǎng)序列的）把長(zhǎng)序列的DFT分解成短序列的分解成短序列的DFT，也可以有，也可以有效的減少效的減少DFT運(yùn)算中復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)。運(yùn)算中復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)。 如果信號(hào)長(zhǎng)度為如果信號(hào)長(zhǎng)度為 N，它可表示

9、成：，它可表示成： 當(dāng)當(dāng) 時(shí)，上式可寫(xiě)成時(shí)，上式可寫(xiě)成 ，因子，因子 稱(chēng)稱(chēng)為基（為基（radix）。）。 當(dāng)當(dāng)FFT算法中進(jìn)行序列分解時(shí)是采用算法中進(jìn)行序列分解時(shí)是采用則稱(chēng)為基則稱(chēng)為基-2（radix-2）FFT。 knNWmrrrN21rrrrm21mrN rmN2第第4 4章章 快速傅里葉變換快速傅里葉變換12/86 N=2M，4.2 4.2 時(shí)間抽取的基時(shí)間抽取的基-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設(shè)：設(shè)：若若奇數(shù)序號(hào)奇數(shù)序號(hào)偶數(shù)序號(hào)偶數(shù)序號(hào) 點(diǎn)序列點(diǎn)序列2N 和和 的的 點(diǎn)點(diǎn)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對(duì)于對(duì)于 后后N/2的的DFT ：由于由于 （周期性）（周期性）因此因此)(kXkNNkNWW 2/)()()2(21kXWkXNkXkN 12,.,1 , 0 Nk第第4 4章章 快速傅里葉變換快速傅里葉變換15/86例：畫(huà)出例：畫(huà)出N=8N=8的時(shí)間抽取基的時(shí)間抽取基2FFT2FFT算法流圖。算法流圖。( ) (0), (1), (2), (3), (4), (5), (6), (7)x nxxxxxxxx ( )DFT ( )X kx

12、 n 解：解： 將將 按時(shí)間抽取基按時(shí)間抽取基2FFT2FFT算法進(jìn)行分解：算法進(jìn)行分解：( )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點(diǎn)點(diǎn)序列序列第第4 4章章 快速傅里葉變換快速傅里葉變換16/86仍然是偶數(shù)仍然是偶數(shù)第第4 4章章 快速傅里葉變換快速傅里葉變換17/86 由于由于 , ,因而因而N/2N/2仍是偶數(shù)仍是偶數(shù), ,可以進(jìn)一可以進(jìn)一步把每個(gè)步把每個(gè)N/2N/2點(diǎn)的序列再按其奇偶部分分解點(diǎn)的序

13、列再按其奇偶部分分解為兩個(gè)為兩個(gè)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因而有因而有對(duì)對(duì) 也可進(jìn)行同樣的分解：也可進(jìn)行同樣的分解： )(2kX25/2625/26( )( )( ) 014()( )( ) 4kNkNXkXkWXkNkNXkXkWXk （）13/2413/24( )(

14、)( ) 014()( )( ) 4kNkNX kXkWXkNkNX kXkWXk （）21342134( )( )( ) 014()( )( ) 4kNkNX kXkWXkNkNX kXkWXk （）22562256( )( )( ) 014()( )( ) 4kNkNXkXkWXkNkNXkXkWXk （）2/2kkNNWW統(tǒng)統(tǒng)一一系系數(shù)數(shù)：第第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點(diǎn)點(diǎn)序列序列第第4 4章章 快速傅里葉變換快速傅里葉變換20/86 如下圖所示：如下圖所示： 那么依次類(lèi)推，經(jīng)過(guò)那么依次類(lèi)推，經(jīng)過(guò)M-1次分解后，將次分解后，將N點(diǎn)點(diǎn)DFT分解分解成成N/2個(gè)兩點(diǎn)個(gè)兩點(diǎn)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時(shí)，分解為時(shí)，分解為4個(gè)兩點(diǎn)個(gè)兩點(diǎn)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時(shí)的一個(gè)完整基時(shí)的一個(gè)完整基-2DIT-FFT運(yùn)算流圖運(yùn)算流圖第第4 4章章 快速傅里葉變換快速傅里葉變換24/86對(duì)對(duì) 點(diǎn)序列

18、：點(diǎn)序列： 4.2.2 4.2.2 運(yùn)算量運(yùn)算量N N點(diǎn)點(diǎn)N/2N/2點(diǎn)點(diǎn)N/4N/4點(diǎn)點(diǎn)1 1點(diǎn)點(diǎn)2MN 1 1點(diǎn)序列的點(diǎn)序列的DFTDFT等于本身序列值等于本身序列值最后按時(shí)間抽取基最后按時(shí)間抽取基2FFT2FFT算法的計(jì)算法的計(jì)算量?jī)H由蝶行運(yùn)算產(chǎn)生。算量?jī)H由蝶行運(yùn)算產(chǎn)生。第第4 4章章 快速傅里葉變換快速傅里葉變換25/86一次蝶式運(yùn)算需：一次蝶式運(yùn)算需：1 1次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和2 2次復(fù)數(shù)加法次復(fù)數(shù)加法按時(shí)間抽取基按時(shí)間抽取基-2FFT-2FFT共有：共有： 個(gè)運(yùn)算蝶個(gè)運(yùn)算蝶2log22NNMN 基基-2FFT-2FFT 復(fù)數(shù)乘法：復(fù)數(shù)乘法： 復(fù)數(shù)加法：復(fù)數(shù)加法：2log2NN2

19、2log22logNNNN 直接直接DFTDFT 2N2N1212 ( )( )( ) 012()( )( )2kNkNX kX kW XkNkNX kX kW Xk （）第第4 4章章 快速傅里葉變換快速傅里葉變換26/860100200300400500600700800900100001234567891011x 105直接計(jì)直接計(jì)算算DFTDFTFFTFFT第第4 4章章 快速傅里葉變換快速傅里葉變換27/86DFT和和FFT運(yùn)算量比較運(yùn)算量比較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、直接利用定義計(jì)算、直接利用定義計(jì)算DFTDFTx=ones(1,1024);f=() FourierTran(x,1024);timeit(f)運(yùn)行結(jié)果：運(yùn)行結(jié)果：ans = 0.7239ans = 0.72392 2、利用、利用FFTFFT算法計(jì)算算法計(jì)算DFTDFTf1=() fft(x,1024);timeit(f1)運(yùn)行結(jié)果：運(yùn)

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

22、的序號(hào)及整序規(guī)律）輸入序列的序號(hào)及整序規(guī)律DITFFT算法的輸入序列的排序看起來(lái)似乎算法的輸入序列的排序看起來(lái)似乎很亂，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種排序是很有很亂，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種排序是很有規(guī)律的。由于規(guī)律的。由于N=2M，所以順序數(shù)可用，所以順序數(shù)可用M位二位二進(jìn)制數(shù)進(jìn)制數(shù)(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輸入的混序輸入的混序是通過(guò)輸入正序序列按是通過(guò)輸入正序序列按碼位倒置碼位倒置實(shí)現(xiàn)的實(shí)現(xiàn)的。自然順序自然順序( )n二進(jìn)制數(shù)二進(jìn)制數(shù) 倒位序二進(jìn)制數(shù)倒位序二進(jìn)制數(shù) 倒位順序倒位順序 ( )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)輸入數(shù)據(jù)的變址處理第第4 4章章 快速傅里葉變換快速傅里葉變換35/86 3 3）各類(lèi)蝶形運(yùn)算兩節(jié)點(diǎn)的）各類(lèi)蝶形運(yùn)算兩節(jié)點(diǎn)的“距離距離”及及 的變化規(guī)律的變化規(guī)律rNW對(duì)對(duì)N = 2M點(diǎn)點(diǎn)FFT，輸入倒位序，輸出自然序

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

26、確確定定2( )2Mmri （1 1）直接計(jì)算法）直接計(jì)算法第第4 4章章 快速傅里葉變換快速傅里葉變換37/86第第4 4章章 快速傅里葉變換快速傅里葉變換38/86級(jí)數(shù) 的取值范圍 重復(fù)組數(shù) 第一級(jí) 第二級(jí) 第三級(jí) 第m級(jí) 第M級(jí) 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 算法的基本原理算法的基本原理 設(shè)序列設(shè)序列x(n)長(zhǎng)度為長(zhǎng)度為N=2M，首先將，首先將x(n)前后對(duì)半分開(kāi)，前后對(duì)半分開(kāi)，得到兩個(gè)子序列，其得到兩個(gè)子序列，其DFT可表示為如下形式：可表示為如下形式： 12/02/12/0)2/(12/012/12/

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

29、章章 快速傅里葉變換快速傅里葉變換45/86設(shè)設(shè)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點(diǎn)點(diǎn)DFT，記為記為X1(k)和和X2(k)第第4 4章章 快速傅里葉變換快速傅里葉變換47/86DIF-FFT的一次分解運(yùn)算流圖（N=8）：第第4 4章章 快速傅里葉變換快速傅里葉變換48/86 由于由于N/2仍然為仍然為2的整數(shù)冪，繼續(xù)將的整數(shù)冪，繼續(xù)將N/2點(diǎn)點(diǎn)DFT分成偶數(shù)組和奇數(shù)組，這樣每個(gè)分成偶數(shù)組和奇數(shù)組，這樣每個(gè)N/2點(diǎn)點(diǎn)DFT又可分解成兩個(gè)又可分解成兩個(gè)N/4點(diǎn)點(diǎn)DFT，其輸，其輸入序列分別是按上下對(duì)半分圖開(kāi)后通過(guò)蝶入序列分別是按上下對(duì)半分圖開(kāi)后通過(guò)蝶式運(yùn)算構(gòu)成的式運(yùn)算構(gòu)成的4個(gè)子序列個(gè)子序列 ,如下圖如下圖第第4 4章章 快速傅里葉變換快速傅里葉變換49/86第

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

32、為空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。的二進(jìn)制數(shù)。rNW 的的確確定定12( )2mrk第第4 4章章 快速傅里葉變換快速傅里葉變換54/86 以上所討論的以上所討論的FFT的運(yùn)算方法同樣可用的運(yùn)算方法同樣可用于于IDFT的運(yùn)算，簡(jiǎn)稱(chēng)為的運(yùn)算，簡(jiǎn)稱(chēng)為IFFT。即快速。即快速傅傅里葉里葉反變換。從反變換。從IDFT的定義出發(fā)，可以的定義出發(fā)，可以導(dǎo)出下列二種利用導(dǎo)出下列二種利用FFT來(lái)計(jì)算來(lái)計(jì)算IFFT的方的方法法。4.4 快速傅里葉反變換快速傅里葉反變換第第4 4章章 快速傅里葉變換快速傅里葉變換55/8.1.1.稍微變動(dòng)稍微變動(dòng)FFTFFT程序和參數(shù)可實(shí)現(xiàn)程序和參數(shù)可實(shí)現(xiàn)IF

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

34、序直接實(shí)現(xiàn)的程序直接實(shí)現(xiàn)IFFTIFFT因?yàn)橐驗(yàn)樗运?101,.,0,)(1)(NknkNNnWkXNnx 10)(1)(NknkNWkXNnx兩邊取共軛有：兩邊取共軛有：101( )( ),0,.,1NnkNkx nXk WnNN 1DFT( )XkN 第第4 4章章 快速傅里葉變換快速傅里葉變換58/864.6 實(shí)序列的實(shí)序列的FFT算法算法n根據(jù)序列根據(jù)序列DFT的共軛對(duì)稱(chēng)性知道，任意的共軛對(duì)稱(chēng)性知道，任意復(fù)數(shù)序列的實(shí)部的復(fù)數(shù)序列的實(shí)部的DFT對(duì)應(yīng)于其對(duì)應(yīng)于其DFT共共軛對(duì)稱(chēng)分量，而其虛部的軛對(duì)稱(chēng)分量，而其虛部的DFT對(duì)應(yīng)于其對(duì)應(yīng)于其DFT共軛反對(duì)稱(chēng)分量，故可用一次共軛反對(duì)稱(chēng)分量，故

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

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

37、變換快速傅里葉變換62/86122122( )( )( )01()( )( )kNkNY kXkWXkkNY kNXkWXk 這相當(dāng)于一個(gè)這相當(dāng)于一個(gè)N點(diǎn)點(diǎn)DFT運(yùn)算加上運(yùn)算加上DIT-FFT蝶蝶形運(yùn)算，當(dāng)形運(yùn)算，當(dāng)N較大時(shí)，可節(jié)省近一半的計(jì)算較大時(shí)，可節(jié)省近一半的計(jì)算量。量。然后先求出然后先求出x1(n)和和x2(n)的的N點(diǎn)點(diǎn)DFTX1(k)和和X2(k)，因?yàn)椋驗(yàn)閤1(n)和和x2(n)分別是原序列分別是原序列x(n)的的偶、奇序列，這與按時(shí)間抽取的偶、奇序列，這與按時(shí)間抽取的FFT算法的算法的分解思路完全相同，故根據(jù)分解思路完全相同，故根據(jù)DIT-FFT蝶形運(yùn)蝶形運(yùn)算式，可得算式，可

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

39、用歐拉公式展開(kāi)可表示成用歐拉公式展開(kāi)可表示成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的核函數(shù)的核函數(shù)是是DFT核函數(shù)核函數(shù)的實(shí)部和虛部之和。的實(shí)部和虛部之和。將將 分解為奇對(duì)稱(chēng)分量和偶對(duì)稱(chēng)分量之和分解為奇對(duì)稱(chēng)分量和偶對(duì)稱(chēng)分量之和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次實(shí)數(shù)加法次實(shí)數(shù)加法運(yùn)算就能由運(yùn)算就能由DHT求出求出DFT。HHH( )( )( )(

41、)Re( )Im( )eoX kXkjXkXkX kX kHHHH1( )( )()( )()22jX kXkXNkXkXNk第第4 4章章 快速傅里葉變換快速傅里葉變換68/863. DHT的快速算法（的快速算法（FHT）n仿照快速仿照快速DFT的分解方法，可通過(guò)時(shí)域的抽取的分解方法，可通過(guò)時(shí)域的抽取或頻域抽取方式實(shí)現(xiàn)快速或頻域抽取方式實(shí)現(xiàn)快速DHT。將。將N=2M點(diǎn)的點(diǎn)的實(shí)序列實(shí)序列 進(jìn)行奇偶抽取進(jìn)行奇偶抽取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根據(jù)三角公式根據(jù)三角公式令令 ， ，根據(jù)，根據(jù)DHT的周期性，在的周期性，在 時(shí)時(shí)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類(lèi)似于類(lèi)似于DIT基基-2FFT分解的同址運(yùn)算思想，可用分解的同址運(yùn)算思想，可用 、 、 和和 四個(gè)四個(gè)點(diǎn)同址運(yùn)算得出點(diǎn)同址運(yùn)算得出 、 、和和 。這種運(yùn)算構(gòu)成了一個(gè)運(yùn)算蝶形，。這種運(yùn)算構(gòu)成了一個(gè)運(yùn)算蝶形，稱(chēng)為稱(chēng)為“哈特曼蝶形哈特曼蝶形”。設(shè)設(shè)將上式中將上式中k分別取分別取k、N/2+k、N/2-k和和N-k四個(gè)值四個(gè)值，并考慮，并考慮 和和 以以N/2為周期，當(dāng)為周期，當(dāng)時(shí)，得到時(shí)，得到 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上述的運(yùn)算可

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

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

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

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

49、卷積快速卷積。2-12NMM2253106log4(log)22mMMKMM 第第4 4章章 快速傅里葉變換快速傅里葉變換81/86 ，則，則 ，有，有LM 1NLML223logmMKL 4.7.2 有限長(zhǎng)序列無(wú)限長(zhǎng)序列線(xiàn)性卷積的有限長(zhǎng)序列無(wú)限長(zhǎng)序列線(xiàn)性卷積的FFT算法算法基本思路：基本思路： 把有限序列和無(wú)限序列之間的線(xiàn)性卷積把有限序列和無(wú)限序列之間的線(xiàn)性卷積變成若干個(gè)有限序列之間的線(xiàn)性卷積。變成若干個(gè)有限序列之間的線(xiàn)性卷積。具體方法：具體方法： 重疊相加法重疊相加法(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 為無(wú)限序列，為無(wú)限序列， 為為M M點(diǎn)有限序列，計(jì)算點(diǎn)有限序列，計(jì)算( )x n( )h n10( ) () ()Mih i x nin 思路：將長(zhǎng)序列思路：將長(zhǎng)序列 分段分段( )x n( )( )( )y nh nx n 第第4 4章章 快速傅里葉變換快速傅里葉變換83/86a.a.將將 均勻分段，每段長(zhǎng)度為均勻分

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

52、？ 思考：思考：第第4 4章章 快速傅里葉變換快速傅里葉變換85/86c. c. 相加相加10( )( )Piiy ny n ( )iy n長(zhǎng)度為長(zhǎng)度為L(zhǎng)+M-1相加時(shí)，相鄰相加時(shí)，相鄰 重疊重疊M-1個(gè)點(diǎn)。個(gè)點(diǎn)。( )iy n( )iy n起點(diǎn)為起點(diǎn)為iL第第4 4章章 快速傅里葉變換快速傅里葉變換86/86 由于由于xi (n)的長(zhǎng)度為的長(zhǎng)度為L(zhǎng)，h(n)的長(zhǎng)度為的長(zhǎng)度為M，所以所以yi (n)的長(zhǎng)度為的長(zhǎng)度為即即yi (n)的范圍為的范圍為將上式將上式xi (n)的范圍比較，顯然的范圍比較，顯然yi (n)的范圍比的范圍比xi (n)的的范圍大，超出的點(diǎn)數(shù)為范圍大，超出的點(diǎn)數(shù)為而而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點(diǎn)上，點(diǎn)上， yi (n)的后部分與的后部分與yi +1(n)的前部分發(fā)生了重疊。這樣的前部分發(fā)生了重疊。這樣對(duì)于在此范圍內(nèi)的每一個(gè)對(duì)于在此范圍內(nèi)的每一個(gè)n值，原序列值，原序列x(n)與與h(n)的的卷積結(jié)果應(yīng)該是卷積結(jié)果應(yīng)該是即并不是將各段線(xiàn)性卷積的結(jié)果簡(jiǎn)單地拼接在一起即并不是將各段線(xiàn)性卷積的結(jié)果簡(jiǎn)單地拼接在一起，在某些點(diǎn)上需要前后兩端的結(jié)果重疊相加。，在某些點(diǎn)上需要前后兩端的結(jié)果重疊相加。1( )( )( )iiy ny nyn 第第4 4章章 快速傅里葉變換快速傅里葉變換88/86第第4 4章章 快速傅里葉變換快速傅里葉變換89/86為了得到兩個(gè)序列為了得到兩個(gè)序列x(n)和和h(n)最終的線(xiàn)性卷積結(jié)果，最終的線(xiàn)性卷積結(jié)果，需將相鄰兩段的需將相鄰兩段的M-1個(gè)重疊點(diǎn)的值相加，故稱(chēng)為個(gè)重疊點(diǎn)的值相加，故稱(chēng)為重疊重疊相加法相加法。在求出各。在求出各yi (n)后，后，x(n)和和h(n)的線(xiàn)性卷積的線(xiàn)性卷積y(n)可分段表示為