中北大學(xué)數(shù)字信號(hào)處理原理及應(yīng)用快速傅里葉變換

1、第第4 4章章 快速傅里葉變換快速傅里葉變換1/86第第4 4章章 快速傅里葉變換快速傅里葉變換第第4 4章章 快速傅里葉變換快速傅里葉變換2/86 DFT是信號(hào)分析與處理中的一種重要變是信號(hào)分析與處理中的一種重要變換。直接計(jì)算換。直接計(jì)算DFT的計(jì)算量與變換區(qū)間長度的計(jì)算量與變換區(qū)間長度N的平方成正比，計(jì)算量太大，所以在快速的平方成正比，計(jì)算量太大，所以在快速傅里葉變換傅里葉變換(簡稱簡稱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í)域頻域都是離散的有限長序列時(shí)域頻域都是離散的有限長序列( )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)算量十分可觀。例，計(jì)算較大時(shí)，運(yùn)算量十分可觀。例，計(jì)算N=10點(diǎn)點(diǎn)的的DFT，需要，需要100次復(fù)數(shù)相乘，而次復(fù)數(shù)相乘，而N=1024點(diǎn)時(shí)點(diǎn)時(shí)，需要，需要1048576（一百多萬）次

4、復(fù)數(shù)乘法，如（一百多萬）次復(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、 的對稱性：的對稱性：nkNWnknk lNNNWW 2、 的周期性：的周期性：nkNW（ 為整數(shù)為整數(shù)）lnkmnkNm

5、NWW 3、 的可約性：的可約性：nkNW()22NNnknknkNNNNWWWW nknk mNN mWW 第第4 4章章 快速傅里葉變換快速傅里葉變換7/86 例如，對例如，對4點(diǎn)點(diǎn)DFT，直接計(jì)算需要，直接計(jì)算需要42=16次復(fù)數(shù)乘法。根據(jù)上述次復(fù)數(shù)乘法。根據(jù)上述 的性質(zhì)，可寫成的性質(zhì)，可寫成如下的矩陣形式如下的矩陣形式 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點(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）把長序列的）把長序列的DFT分解成短序列的分解成短序列的DFT，也可以有，也可以有效的減少效的減少DFT運(yùn)算中復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)。運(yùn)算中復(fù)數(shù)乘法和復(fù)數(shù)加法的次數(shù)。 如果信號(hào)長度為如果信號(hào)長度為 N，它可表示

9、成：，它可表示成： 當(dāng)當(dāng) 時(shí)，上式可寫成時(shí)，上式可寫成 ，因子，因子 稱稱為基（為基（radix）。）。 當(dāng)當(dāng)FFT算法中進(jìn)行序列分解時(shí)是采用算法中進(jìn)行序列分解時(shí)是采用則稱為基則稱為基-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對于對于 后后N/2的的DFT ：由于由于 （周期性）（周期性）因此因此)(kXkNNkNWW 2/)()()2(21kXWkXNkXkN 12,.,1 , 0 Nk第第4 4章章 快速傅里葉變換快速傅里葉變換15/86例：畫出例：畫出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因而有因而有對對 也可進(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 如下圖所示：如下圖所示： 那么依次類推，經(jīng)過那么依次類推，經(jīng)過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對對 點(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ì)算量僅由蝶行運(yùn)算產(chǎn)生。算量僅由蝶行運(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算法的輸入序列的排序看起來似乎算法的輸入序列的排序看起來似乎很亂，但仔細(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輸入的混序輸入的混序是通過輸入正序序列按是通過輸入正序序列按碼位倒置碼位倒置實(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）各類蝶形運(yùn)算兩節(jié)點(diǎn)的）各類蝶形運(yùn)算兩節(jié)點(diǎn)的“距離距離”及及 的變化規(guī)律的變化規(guī)律rNW對對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)長度為長度為N=2M，首先將，首先將x(n)前后對半分開，前后對半分開，得到兩個(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，其輸，其輸入序列分別是按上下對半分圖開后通過蝶入序列分別是按上下對半分圖開后通過蝶式運(yùn)算構(gòu)成的式運(yùn)算構(gòu)成的4個(gè)子序列個(gè)子序列 ,如下圖如下圖第第4 4章章 快速傅里葉變換快速傅里葉變換49/86第

31、第4 4章章 快速傅里葉變換快速傅里葉變換50/86 按照以上方法繼續(xù)分解下去，經(jīng)過按照以上方法繼續(xù)分解下去，經(jīng)過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)算，簡稱為的運(yùn)算，簡稱為IFFT。即快速。即快速傅傅里葉里葉反變換。從反變換。從IDFT的定義出發(fā)，可以的定義出發(fā)，可以導(dǎo)出下列二種利用導(dǎo)出下列二種利用FFT來計(jì)算來計(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的共軛對稱性知道，任意的共軛對稱性知道，任意復(fù)數(shù)序列的實(shí)部的復(fù)數(shù)序列的實(shí)部的DFT對應(yīng)于其對應(yīng)于其DFT共共軛對稱分量，而其虛部的軛對稱分量，而其虛部的DFT對應(yīng)于其對應(yīng)于其DFT共軛反對稱分量，故可用一次共軛反對稱分量，故

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è)長度為為兩個(gè)長度為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利用頻譜對稱性求實(shí)信號(hào)的利用頻譜對稱性求實(shí)信號(hào)的FFT第第4 4章章 快速傅里葉變換快速傅里葉變換60/86根據(jù)共軛對稱性，則根據(jù)共軛對稱性，則*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、用歐拉公式展開可表示成用歐拉公式展開可表示成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í)部和虛部之和。將將 分解為奇對稱分量和偶對稱分量之和分解為奇對稱分量和偶對稱分量之和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的分解方法，可通過時(shí)域的抽取的分解方法，可通過時(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類似于類似于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)算蝶形，稱為稱為“哈特曼蝶形哈特曼蝶形”。設(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 線性卷積和線性相關(guān)的線性卷積和線性相關(guān)的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 計(jì)算量（乘法次數(shù)）：計(jì)算量（乘法次數(shù)）：第第4 4章章 快速傅里葉變換快速傅里葉變換77/86用用FFT算法也就是用算法也就是用循環(huán)循環(huá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)就能代表線性卷積的結(jié)果。就能代表線性卷積的結(jié)果。( )( )y nx n ( )h nN第第4 4章章 快速傅里葉變換快速傅里葉變換78/86利用利用FFT進(jìn)行線性卷積的步驟：進(jìn)行線性卷積的步驟：1.將序列將序列x(n)和和h(n)補(bǔ)零，使其長度補(bǔ)零，使其長度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獲得線性卷積的結(jié)果為獲得線性卷積的結(jié)果為( )IFFT ( )01y nY knN第第4 4章章 快速傅

48、里葉變換快速傅里葉變換79/86整個(gè)過程中，共需要進(jìn)行三次整個(gè)過程中，共需要進(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超過超過64以后，以后，M越長越長循環(huán)循環(huán)卷積的卷積的好處越明顯。因而將好處越明顯。因而將循環(huán)循環(huán)卷積稱為卷積稱為快速

49、卷積快速卷積。2-12NMM2253106log4(log)22mMMKMM 第第4 4章章 快速傅里葉變換快速傅里葉變換81/86 ，則，則 ，有，有LM 1NLML223logmMKL 4.7.2 有限長序列無限長序列線性卷積的有限長序列無限長序列線性卷積的FFT算法算法基本思路：基本思路： 把有限序列和無限序列之間的線性卷積把有限序列和無限序列之間的線性卷積變成若干個(gè)有限序列之間的線性卷積。變成若干個(gè)有限序列之間的線性卷積。具體方法：具體方法： 重疊相加法重疊相加法(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點(diǎn)有限序列，計(jì)算點(diǎn)有限序列，計(jì)算( )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用線性卷積或循環(huá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長度為長度為L+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)的長度為的長度為L，h(n)的長度為的長度為M，所以所以yi (n)的長度為的長度為即即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ā)生了重疊。這樣對于在此范圍內(nèi)的每一個(gè)對于在此范圍內(nèi)的每一個(gè)n值，原序列值，原序列x(n)與與h(n)的的卷積結(jié)果應(yīng)該是卷積結(jié)果應(yīng)該是即并不是將各段線性卷積的結(jié)果簡單地拼接在一起即并不是將各段線性卷積的結(jié)果簡單地拼接在一起，在某些點(diǎn)上需要前后兩端的結(jié)果重疊相加。，在某些點(diǎn)上需要前后兩端的結(jié)果重疊相加。1( )( )( )iiy ny nyn 第第4 4章章 快速傅里葉變換快速傅里葉變換88/86第第4 4章章 快速傅里葉變換快速傅里葉變換89/86為了得到兩個(gè)序列為了得到兩個(gè)序列x(n)和和h(n)最終的線性卷積結(jié)果，最終的線性卷積結(jié)果，需將相鄰兩段的需將相鄰兩段的M-1個(gè)重疊點(diǎn)的值相加，故稱為個(gè)重疊點(diǎn)的值相加，故稱為重疊重疊相加法相加法。在求出各。在求出各yi (n)后，后，x(n)和和h(n)的線性卷積的線性卷積y(n)可分段表示為