1、第第4 4章章 快速傅里葉變換快速傅里葉變換1/86第第4 4章章 快速傅里葉變換快速傅里葉變換第第4 4章章 快速傅里葉變換快速傅里葉變換2/864.1 DFT的運(yùn)算量分析10: ( ) ( )( )( )NnkNNnDFTX kDFT x nx n WRk10:1 ( )( )( )( )NnkNNkIDFTx nIDFT X kX k WRnN( )Nx n點(diǎn)有限長序列4.1.1 直接計(jì)算DFT的運(yùn)算量第第4 4章章 快速傅里葉變換快速傅里葉變換3/86實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個(gè)X (k)4N2N+2 (N 1)=2 (2N 1)N個(gè)X (k)(N點(diǎn)DFT)4N 22N

2、(2N 1)復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN 1N個(gè)X(k)(N點(diǎn)DFT)N 2N (N 1)10( )NnkNnx n Wajbcjdacbdj adcb第第4 4章章 快速傅里葉變換快速傅里葉變換4/86 從上面的分析看到，在從上面的分析看到，在DFTDFT計(jì)算中，不論是乘計(jì)算中，不論是乘法和加法，運(yùn)算量均與法和加法，運(yùn)算量均與N N2 2成正比。因此，成正比。因此，N N較大時(shí)較大時(shí)，運(yùn)算量十分可觀。例，計(jì)算，運(yùn)算量十分可觀。例，計(jì)算N=10N=10點(diǎn)的點(diǎn)的DFTDFT，需要，需要100100次復(fù)數(shù)相乘，而次復(fù)數(shù)相乘，而N=1024N=1024點(diǎn)時(shí)，需要點(diǎn)時(shí)，需要104857610485

3、76（一百多萬）次復(fù)數(shù)乘法，如果要求實(shí)時(shí)處理，則一百多萬）次復(fù)數(shù)乘法，如果要求實(shí)時(shí)處理，則要求有很高的計(jì)算速度才能完成上述計(jì)算量。要求有很高的計(jì)算速度才能完成上述計(jì)算量。 反變換反變換IDFTIDFT與與DFTDFT的運(yùn)算結(jié)構(gòu)相同，只是多乘的運(yùn)算結(jié)構(gòu)相同，只是多乘一個(gè)常數(shù)一個(gè)常數(shù)1/N1/N，所以二者的計(jì)算量相同。，所以二者的計(jì)算量相同。第第4 4章章 快速傅里葉變換快速傅里葉變換5/864.1.2 改善DFT運(yùn)算效率的基本途徑nkNW 的特性*()() ()nknkN n kn N kNNNNWWWW對稱性()() nkN n kn N kNNNWWW周期性0/2(/2) 11Nk NkNN

4、NNWWWW 特殊點(diǎn)：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNee nkmnkNmNWW可約性/nknk mNN mWW第第4 4章章 快速傅里葉變換快速傅里葉變換6/86n時(shí)域抽取與頻域抽?。?FFTDecimation - In- TimeDIT-FFTDecimation-In-FreqencyDIF-FFTFFT按時(shí)域抽取算法（，簡稱）按頻域抽取算法（，簡稱）FFTDFTDFTDFTDFT算法的基本思想： 利用系數(shù)的特性，合并運(yùn)算中的某些項(xiàng)， 把長序列短序列，從而減少其運(yùn)算量。第第4 4章章 快速傅里葉變換快速傅里葉變換7/864.2.1.算法

5、的的基本原理 按按n的奇偶把時(shí)間序列的奇偶把時(shí)間序列x(n)分解為兩個(gè)長為分解為兩個(gè)長為N/2點(diǎn)點(diǎn)的序列，即的序列，即因此因此)2()(1rxrx) 12()(2rxrx12,.,1 ,0Nr12,.,1 ,0NrknNNnWnxkX)()(10/2 1/2 12(21)00/2 1/2 1221200(2 )(21)( )( )NNkrkrNNrrNNkrkrkNNNrrxr WxrWx r Wxr WW4.2 時(shí)間抽取的基-2FFT算法第第4 4章章 快速傅里葉變換快速傅里葉變換8/86由于由于所以所以即其中即其中 分別為分別為 的的N/2N/2點(diǎn)點(diǎn)DFTDFT這是這是 前前N/2N/2點(diǎn)

6、點(diǎn)DFTDFT X kx r WWxr WXkW XkkNrNNkrNkrNNkrNk( )( )( )( )( ), ,.,/02 11202 122120121X kXk12( )( )和)()(21rxrx和2222/2/2jkrjkrkrkrNNNNWeeWkrNNrWrxkX2/112/01)()(12,.,1 ,0NkkrNNrWrxkX2/212/02)()(12,.,1 ,0Nk) 12,.1 , 0)(NkkX第第4 4章章 快速傅里葉變換快速傅里葉變換9/86對于對于 后后N/2N/2的的DFT DFT ：由于由于 （周期性）（周期性）因此因此可用蝶式運(yùn)算圖來表示上述前可用

7、蝶式運(yùn)算圖來表示上述前N/2N/2和后和后N/2N/2兩兩式式 ，如下圖所示，如下圖所示 )(kXkNNkNWW2/X kNX kW XkNk()( )( )21212,.,1 , 0Nk第第4 4章章 快速傅里葉變換快速傅里葉變換10/86 例如例如:N=8時(shí)的時(shí)的DFT,可以分解為兩個(gè)可以分解為兩個(gè)N/2=4點(diǎn)點(diǎn)DFT 如圖如圖4.2.2所示所示:圖4.2.2 8點(diǎn)DFT分解成兩個(gè)4點(diǎn)的DFT第第4 4章章 快速傅里葉變換快速傅里葉變換11/86分解后的運(yùn)算量：分解后的運(yùn)算量：復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)N / 2點(diǎn)DFT(N / 2)2N / 2 (N / 2 1)兩個(gè)N / 2點(diǎn)DFTN 2

8、/ 2N (N / 2 1)一個(gè)蝶形12N / 2個(gè)蝶形N / 2N總計(jì)22/2/2/2NNN2/2 1/2N NNN運(yùn)算量減少了近一半運(yùn)算量減少了近一半第第4 4章章 快速傅里葉變換快速傅里葉變換12/86 由于由于 , , 因而因而N/2N/2仍是偶數(shù)仍是偶數(shù), ,可以進(jìn)一步把可以進(jìn)一步把每個(gè)每個(gè)N/2N/2點(diǎn)的序列再按其奇偶部分分解為兩個(gè)點(diǎn)的序列再按其奇偶部分分解為兩個(gè)N/4N/4的的子序列子序列從而從而 可表示為可表示為 MN23141221( )()( )()x lxlx lxl) 14(,.,1 , 0Nl)(1kX) 12(2/114/022/114/01) 12()2()(lk

9、NNlklNNlWlxWlxkXklNNlkNklNNlWlxWWlx4/414/02/4/314/0)()()()(42/3kXWkXkN14,.1 , 0Nk第第4 4章章 快速傅里葉變換快速傅里葉變換13/86因而有因而有其中其中對對 也可進(jìn)行同樣的分解：也可進(jìn)行同樣的分解： k=0,1,.,N/4-1 13/24()( )( )4kNNX kXkWXkXkDFT x lx l WXkDFT x lx l WlNNkllNNkl3304 1344404 144( )( )( )( )( )( )/Xk2( )()()(62/52kXWkXkXkN)()()4(62/52kXWkXNkXk

10、N第第4 4章章 快速傅里葉變換快速傅里葉變換14/86其中其中這樣又一次的分解得到這樣又一次的分解得到4個(gè)個(gè)N/4點(diǎn)點(diǎn)DFTklNNlWlxlxDFTkX4/514/055)()()(klNNlWlxlxDFTkX4/614/066)()()()2()(25lxlx) 14(,.,1 , 0) 12()(26Nllxlx2/2kkNNWW統(tǒng)一系數(shù)：第第4 4章章 快速傅里葉變換快速傅里葉變換15/86如下圖所示：如下圖所示： 那么依次類推，經(jīng)過那么依次類推，經(jīng)過M-1次分解后，將次分解后，將N點(diǎn)點(diǎn)DFT分分解成解成N/2個(gè)兩點(diǎn)個(gè)兩點(diǎn)DFT第第4 4章章 快速傅里葉變換快速傅里葉變換16/86

11、 下圖為下圖為N=8時(shí)的一個(gè)完整基時(shí)的一個(gè)完整基-2DIT-FFT運(yùn)算流圖運(yùn)算流圖2M第第4 4章章 快速傅里葉變換快速傅里葉變換17/86 當(dāng)當(dāng) 時(shí)，總共有時(shí)，總共有M級分解，每級有級分解，每級有N/2個(gè)蝶式個(gè)蝶式運(yùn)算。每個(gè)蝶式運(yùn)算需一次復(fù)乘兩次復(fù)加，這樣運(yùn)算。每個(gè)蝶式運(yùn)算需一次復(fù)乘兩次復(fù)加，這樣M級總共需要的運(yùn)算量為級總共需要的運(yùn)算量為 復(fù)乘次數(shù)復(fù)乘次數(shù) 復(fù)加次數(shù)復(fù)加次數(shù)2MN NMNN222logNMNNlog24.2.2 運(yùn)算量第第4 4章章 快速傅里葉變換快速傅里葉變換18/86FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線 第第4 4章章 快速傅里葉變換快速傅里葉變換19/864

12、.2.3.FFT算法的特點(diǎn)1 1）原位計(jì)算（同址運(yùn)算）原位計(jì)算（同址運(yùn)算）第第4 4章章 快速傅里葉變換快速傅里葉變換20/86nm表示第表示第m級迭代，級迭代，i，j表示數(shù)據(jù)所在的行數(shù)表示數(shù)據(jù)所在的行數(shù)1111( )( )( )( )( )( )rmmmNrmmmNAiAiAj WAjAiAj W第第4 4章章 快速傅里葉變換快速傅里葉變換21/86n每一級的蝶形運(yùn)算的輸入和輸出在運(yùn)算前后可以存每一級的蝶形運(yùn)算的輸入和輸出在運(yùn)算前后可以存儲在同一地址的存儲單元中，這種存儲策略稱為同儲在同一地址的存儲單元中，這種存儲策略稱為同址計(jì)算。顯然，同址計(jì)算可以節(jié)省存儲單元，從而址計(jì)算。顯然，同址計(jì)算可

13、以節(jié)省存儲單元，從而降低算法對計(jì)算機(jī)存儲容量的要求，降低了硬件實(shí)降低算法對計(jì)算機(jī)存儲容量的要求，降低了硬件實(shí)現(xiàn)的成本?，F(xiàn)的成本。第第4 4章章 快速傅里葉變換快速傅里葉變換22/862 2）輸入序列的序號及整序規(guī)律）輸入序列的序號及整序規(guī)律DITFFT算法的輸入序列的排序看起來似乎很亂，算法的輸入序列的排序看起來似乎很亂，但仔細(xì)分析就會發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于但仔細(xì)分析就會發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于N=2M，所以順序數(shù)可用，所以順序數(shù)可用M位二進(jìn)制數(shù)位二進(jìn)制數(shù)(nM-1nM-2n1n0)表示。表示。 01010101010101(n2n1n0)20000426153710001011

14、0001101011111第第4 4章章 快速傅里葉變換快速傅里葉變換23/86在實(shí)際計(jì)算中，在實(shí)際計(jì)算中，輸入的混序輸入的混序是通過輸入正序序列是通過輸入正序序列按按碼位倒置碼位倒置實(shí)現(xiàn)的。存儲單元、正序和反序之間的關(guān)實(shí)現(xiàn)的。存儲單元、正序和反序之間的關(guān)系如下表系如下表存儲單元 自然序列 二進(jìn)制表示自然序列序號 序號碼位倒置碼位倒置后的序列(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A)0( x) 1 ( x)2( x) 3( x)4( x) 5( x)6( x)7( x)000( x)010( x)100( x)110( x)100( x)101( x)110( x)11

15、1( x)111( x)110( x)101( x)010( x)110( x)100( x)100( x)000( x)0( x)4( x)2( x)6( x) 1 ( x) 5( x) 3( x)7( x第第4 4章章 快速傅里葉變換快速傅里葉變換24/86從上表可以看出，表的第一列即是從上表可以看出，表的第一列即是FFTFFT輸出序列的順輸出序列的順序，第四列即是序，第四列即是FFTFFT輸入序列，因此輸出序列的順序輸入序列，因此輸出序列的順序與輸入序列的順序成反序關(guān)系，這里與輸入序列的順序成反序關(guān)系，這里稱為倒位序。稱為倒位序。下下圖示出了圖示出了N N=8=8時(shí)按自然順序存儲的數(shù)據(jù)，

16、調(diào)換成時(shí)按自然順序存儲的數(shù)據(jù)，調(diào)換成FFTFFT原位運(yùn)算所要求的倒位序存儲的變址情況。原位運(yùn)算所要求的倒位序存儲的變址情況。 第第4 4章章 快速傅里葉變換快速傅里葉變換25/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章章 快速傅里葉變換快速傅里葉變換26/86 3 3）各類蝶形運(yùn)算兩節(jié)點(diǎn)的）各類蝶形運(yùn)算兩節(jié)點(diǎn)的“距離距離”及及 的變化規(guī)律的變化規(guī)律r

17、NW對對N = 2M點(diǎn)點(diǎn)FFT，輸入倒位序，輸出自然序，第，輸入倒位序，輸出自然序，第m級級運(yùn)算每個(gè)蝶形的兩節(jié)點(diǎn)距離為運(yùn)算每個(gè)蝶形的兩節(jié)點(diǎn)距離為 2m1第第m級運(yùn)算：級運(yùn)算：1111111( )( )(2)(2)( )(2)mrmmmNmmrmmmNAkAiXiWA iAiXiW第第4 4章章 快速傅里葉變換快速傅里葉變換27/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 的確定2( )2M mri（1 1）直接計(jì)算法）直

18、接計(jì)算法第第4 4章章 快速傅里葉變換快速傅里葉變換28/86第第4 4章章 快速傅里葉變換快速傅里葉變換29/86級數(shù) 的取值范圍 重復(fù)組數(shù) 第一級 第二級 第三級 第m級 第M級 1kNW0NW2/N0NW4/NNW4/N0NW0NW0NW8/NNW8/2NNW8/3NNWmNNW2/mNNW2/mNNW2/2mNNW2/2mmNNW2/)12(112/NNW8/NmN 2/ （2 2）逆推法）逆推法第第4 4章章 快速傅里葉變換快速傅里葉變換30/86 4.2.4 4.2.4、DITDIT算法的其他形式流圖算法的其他形式流圖n輸入自然序輸出倒位序輸入自然序輸出倒位序n輸入輸出均自然序輸入

19、輸出均自然序n相同幾何形狀相同幾何形狀n輸入自然序輸出倒位序輸入自然序輸出倒位序第第4 4章章 快速傅里葉變換快速傅里葉變換31/86 第第4 4章章 快速傅里葉變換快速傅里葉變換32/86第第4 4章章 快速傅里葉變換快速傅里葉變換33/86第第4 4章章 快速傅里葉變換快速傅里葉變換34/864.2.5 DIT4.2.5 DIT基基-2FFT-2FFT的軟件編程思想的軟件編程思想n由由DIT基基-2FFT算法原理及特點(diǎn)，不難看出，算法原理及特點(diǎn)，不難看出，F(xiàn)FT計(jì)算程序主要包括變址和計(jì)算程序主要包括變址和M級遞推計(jì)算兩級遞推計(jì)算兩大部分。大部分。第第4 4章章 快速傅里葉變換快速傅里葉變換

20、35/861.1.變址（倒序）運(yùn)算變址（倒序）運(yùn)算n在實(shí)際運(yùn)算中，一般總是按自然順序?qū)⑤斎胄蛟趯?shí)際運(yùn)算中，一般總是按自然順序?qū)⑤斎胄蛄写嫒氪鎯卧?，故為?shí)現(xiàn)列存入存儲單元，故為實(shí)現(xiàn)DIT基基-2FFT首先首先必須將輸入序列必須將輸入序列x(n)按二進(jìn)制倒序數(shù)重排。倒按二進(jìn)制倒序數(shù)重排。倒序重排一般采用反向進(jìn)位加法來實(shí)現(xiàn)，圖序重排一般采用反向進(jìn)位加法來實(shí)現(xiàn)，圖4.2.12是反向進(jìn)位加法實(shí)現(xiàn)變址運(yùn)算的計(jì)算流是反向進(jìn)位加法實(shí)現(xiàn)變址運(yùn)算的計(jì)算流程。程。第第4 4章章 快速傅里葉變換快速傅里葉變換36/86第第4 4章章 快速傅里葉變換快速傅里葉變換37/862M級遞推計(jì)算n根據(jù)根據(jù)DIT基基-2 FF

21、T的特點(diǎn)，可以得出圖的特點(diǎn)，可以得出圖4.2.13的的M輪遞推計(jì)算的流程圖。整個(gè)輪遞推計(jì)算的流程圖。整個(gè)M輪遞推過程由輪遞推過程由三個(gè)嵌套循環(huán)構(gòu)成。外層循環(huán)控制三個(gè)嵌套循環(huán)構(gòu)成。外層循環(huán)控制M輪的順序輪的順序運(yùn)算，內(nèi)層的兩個(gè)循環(huán)控制同一輪的各個(gè)蝶形運(yùn)算，內(nèi)層的兩個(gè)循環(huán)控制同一輪的各個(gè)蝶形運(yùn)算，其中最內(nèi)一層循環(huán)控制同類（指有相同運(yùn)算，其中最內(nèi)一層循環(huán)控制同類（指有相同的旋轉(zhuǎn)因子）蝶形的運(yùn)算，而中間一層循環(huán)則的旋轉(zhuǎn)因子）蝶形的運(yùn)算，而中間一層循環(huán)則針對不同類的蝶形運(yùn)算。針對不同類的蝶形運(yùn)算。I和和IP代表的是一個(gè)代表的是一個(gè)蝶形運(yùn)算的兩個(gè)節(jié)點(diǎn)。蝶形運(yùn)算的兩個(gè)節(jié)點(diǎn)。第第4 4章章 快速傅里葉變換快速

22、傅里葉變換38/86第第4 4章章 快速傅里葉變換快速傅里葉變換39/864.3.1 算法的基本原理 設(shè)序列設(shè)序列x(n)長度為長度為N=2M，首先將，首先將x(n)前后對半分開，前后對半分開，得到兩個(gè)子序列，其得到兩個(gè)子序列，其DFT可表示為如下形式：可表示為如下形式：X kDFT x nx n Wx n Wx n Wx n Wx nNWx nWx nNWnNNnknNNnkn NNNnknNNnknNNn NknNNNkNnk( )( )( )( )( )( )(/ )( )(/ )/(/ )/0102 12102 102 1202 12224.3 頻域抽取基-2 FFT算法第第4 4章章

23、 快速傅里葉變換快速傅里葉變換40/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） WkkNkNk/()2111 為偶數(shù)為奇數(shù)Xrx nx nNWx nx nNWnNNrnnNNrn() ( )(/ )( )(/ )/22202 1202 12第第4 4章章 快速傅里葉變換快速傅里葉變換41/86設(shè)設(shè)2221210102122()()( )()( )()NNNnrNnnnrNnNXrx nx nWNx nx nWW1220 1122( )( )(), ,( )( )()nNNx nx nx nN

24、nNx nx nx nW第第4 4章章 快速傅里葉變換快速傅里葉變換42/86 將將x1(n)和和x2(n)分別代入分別代入 和和 式，可得式，可得/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W(2 )Xr(21)Xr則則X(2r)和和X(2r+1)分別是分別是x1(n)和和x2(n)的的 N / 2點(diǎn)點(diǎn)DFT，記為記為X1(k)和和X2(k)第第4 4章章 快速傅里葉變換快速傅里葉變換43/86如圖3.4.1 DIF-FFT的一次分解運(yùn)算流圖（N=8）：第第4 4章章 快速傅里葉變換快速傅里葉變換44/86 由于由于N/2仍然為仍

25、然為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章章 快速傅里葉變換快速傅里葉變換45/86第第4 4章章 快速傅里葉變換快速傅里葉變換46/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的的輸出就是輸出就是

26、N點(diǎn)點(diǎn)DFT的結(jié)果的結(jié)果X(k) ，如下圖，如下圖第第4 4章章 快速傅里葉變換快速傅里葉變換47/86第第4 4章章 快速傅里葉變換快速傅里葉變換48/86上圖給出了上圖給出了N=8時(shí)完整的時(shí)完整的DIF-FFT的運(yùn)算流圖。的運(yùn)算流圖。由于這種方法是由于這種方法是 按按()在頻域進(jìn)行奇偶分解，在頻域進(jìn)行奇偶分解，因此稱之為頻域抽取運(yùn)算因此稱之為頻域抽取運(yùn)算比較與：比較與：相同點(diǎn)：運(yùn)算次數(shù)與存儲量相同相同點(diǎn)：運(yùn)算次數(shù)與存儲量相同不同點(diǎn)：不同點(diǎn)：.輸入序列為自輸入序列為自然序列而輸出為碼位倒置序列然序列而輸出為碼位倒置序列.蝶式運(yùn)算過程不同蝶式運(yùn)算過程不同:是序列先乘旋轉(zhuǎn)因子后相加減是序列先乘旋

27、轉(zhuǎn)因子后相加減是序列先相加減后乘旋轉(zhuǎn)因子是序列先相加減后乘旋轉(zhuǎn)因子第第4 4章章 快速傅里葉變換快速傅里葉變換49/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é)果為置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。的二進(jìn)制數(shù)。rNW 的確定12( )2mrk第第4 4章章 快速傅里葉變換快速傅里葉變換50/86 以上所討論的以上所討論的FFT的運(yùn)算方法同樣可用于的運(yùn)算方法同樣可用于IDFT的運(yùn)算，簡稱為的運(yùn)算，簡稱為IFFT。即快速付里葉反。即快速付里葉反變換。從變換。從IDFT的定義出發(fā)，可

28、以導(dǎo)出下列二的定義出發(fā)，可以導(dǎo)出下列二種利用種利用FFT來計(jì)算來計(jì)算FFT的方法。的方法。4.4 快速傅里葉反變換快速傅里葉反變換第第4 4章章 快速傅里葉變換快速傅里葉變換51/864.1.1.稍微變動稍微變動FFT程序和參數(shù)可實(shí)現(xiàn)程序和參數(shù)可實(shí)現(xiàn)IFFT10101( )( )( )( )( )( )NnkNnNnkNkX kDFT x nx n Wx nIDFT X kX k WN第第4 4章章 快速傅里葉變換快速傅里葉變換52/86 比較兩式可知比較兩式可知,只要只要DFT的每個(gè)系數(shù)的每個(gè)系數(shù) 換成換成 ,最后再乘以常數(shù)最后再乘以常數(shù)1/N就可以得到就可以得到IDFT的快速算法的快速算法

29、-IFFT。 另外另外,可以將常數(shù)可以將常數(shù)1/N分配到每級運(yùn)算中分配到每級運(yùn)算中, ,也就是每級也就是每級蝶形運(yùn)算均乘以蝶形運(yùn)算均乘以1/2。 nkNW112NM ( )nkNW第第4 4章章 快速傅里葉變換快速傅里葉變換53/86第第4 4章章 快速傅里葉變換快速傅里葉變換54/864.4.2不改變不改變FFT的程序直接實(shí)現(xiàn)的程序直接實(shí)現(xiàn)IFFT因?yàn)橐驗(yàn)樗运詘 nNX k WnNNnkkN( )( ),.,10101xnNXk WNnkkN( )( )101第第4 4章章 快速傅里葉變換快速傅里葉變換55/86兩邊取共軛有：兩邊取共軛有： 此方法只需要一個(gè)此方法只需要一個(gè)FFTFFT程

30、序即可進(jìn)行正逆程序即可進(jìn)行正逆變換的快速計(jì)算。變換的快速計(jì)算。x nNX k WnNNnkkN( )( ),.,101011NDFT Xk( )第第4 4章章 快速傅里葉變換快速傅里葉變換56/864.5 實(shí)序列的FFT算法n在前面的討論中，認(rèn)為所考慮的有限長度序列在前面的討論中，認(rèn)為所考慮的有限長度序列為任意的復(fù)數(shù)序列，但在實(shí)際應(yīng)用中，通常處為任意的復(fù)數(shù)序列，但在實(shí)際應(yīng)用中，通常處理的是實(shí)信號。當(dāng)然，實(shí)信號可以看成是虛部理的是實(shí)信號。當(dāng)然，實(shí)信號可以看成是虛部是零的復(fù)信號，因此也可以利用是零的復(fù)信號，因此也可以利用FFT算法計(jì)算算法計(jì)算出實(shí)信號的出實(shí)信號的FFT。但是用這種方法來處理實(shí)信。但

31、是用這種方法來處理實(shí)信號，顯然浪費(fèi)了一半的存儲空間和約一半的運(yùn)號，顯然浪費(fèi)了一半的存儲空間和約一半的運(yùn)算量。算量。n根據(jù)序列根據(jù)序列DFT的共軛對稱性知道，任意復(fù)數(shù)序的共軛對稱性知道，任意復(fù)數(shù)序列的實(shí)部的列的實(shí)部的DFT對應(yīng)于其對應(yīng)于其DFT共軛對稱分量，共軛對稱分量，而其虛部的而其虛部的DFT對應(yīng)于其對應(yīng)于其DFT共軛反對稱分量，共軛反對稱分量，故可用一次故可用一次N點(diǎn)點(diǎn)DFT計(jì)算兩個(gè)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的點(diǎn)實(shí)序列的DFT。第第4 4章章 快速傅里葉變換快速傅里葉變換57/86設(shè)設(shè) 和和 為兩個(gè)長度為為兩個(gè)長度為N的實(shí)序列，按如下方的實(shí)序列，按如下方式構(gòu)造新序列式構(gòu)造新序列 ：1( )x n2

32、( )x n( )y n12( )( )( )y nx njx nN點(diǎn)點(diǎn)DFT為為( )DFT ( )( )( )epopY ky nYkYk根據(jù)共軛對稱性，則根據(jù)共軛對稱性，則*1*21( )DFT( ) ( )()( )21( )DFT( ) ( )()( )2epNNopNNYkx nY kYNkRnYkjx nY kYNkRn.1利用頻譜對稱性求實(shí)信號的利用頻譜對稱性求實(shí)信號的FFTFFT第第4 4章章 快速傅里葉變換快速傅里葉變換58/86所以所以*11*221( )DFT( )( ) ( )()( )2( )DFT( )( ) ( )()( )2epNNopNNX

33、kx nYkY kYNkRnjXkx njYkY kYNkRn 設(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第第4 4章章 快速傅里葉變換快速傅里葉變換59/86122122( )( )( )01()( )( )kNkNX kX kWXkkNX kNX kWXk這相當(dāng)于一個(gè)這相當(dāng)于一個(gè)N點(diǎn)點(diǎn)DFT運(yùn)算加上運(yùn)算加上DIT-FFT蝶形運(yùn)算，蝶形運(yùn)算，當(dāng)當(dāng)N較大時(shí)，可節(jié)省近一半的計(jì)算量。較大時(shí)，可節(jié)省近一半的計(jì)算量。再構(gòu)造復(fù)數(shù)序列再構(gòu)造復(fù)數(shù)序列y(n)。然后先求出。然后先求出x1(n)和和x

34、2(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)算式，可得式，可得第第4 4章章 快速傅里葉變換快速傅里葉變換60/864.5.2 離散哈特曼變換1 1、離散哈特曼變換的定義、離散哈特曼變換的定義設(shè)設(shè)x x( (n n) )為一為一N N點(diǎn)的實(shí)序列，則其離散哈特曼變換點(diǎn)的實(shí)序列，則其離散哈特曼變換（DHTDHT）為）為1H02( )DHT ( )( )cas()01NnnkX

35、kx nx nkNN逆變換為逆變換為1HH012( )IDHT( )( )cas()01Nknkx nXkXknNNN式中式中222cas()cos()sin()nknknkNNN第第4 4章章 快速傅里葉變換快速傅里葉變換61/862. DHT與與DFT的關(guān)系的關(guān)系DFT和和IDFT用歐拉公式展開可表示成用歐拉公式展開可表示成12/010( )DFT ( )( )22( )cos()sin()01Njnk NnNnX kx nx n enknkx njkNNN12/010( )IDFT( )( )22( )cos()sin()01Njnk NkNkx nX kX k enknkX kjnNN

36、N第第4 4章章 快速傅里葉變換快速傅里葉變換62/86可以看出，可以看出，DHT的核函數(shù)的核函數(shù)是是DFT核函數(shù)核函數(shù)的實(shí)部和虛部之和。的實(shí)部和虛部之和。將將 分解為奇對稱分量和偶對稱分量之和分解為奇對稱分量和偶對稱分量之和222cas()cos()sin()nknknkNNN2/22cos()sin()jnk NnknkejNNH( )XkHHH( )( )( )eoXkXkXk第第4 4章章 快速傅里葉變換快速傅里葉變換63/86其中其中由由DHT的定義可得的定義可得HHHHHH1( )( )()21( )( )()2eoXkXkXNkXkXkXNk1H01H02( )( )cos()2

37、( )( )sin()NenNonnkXkx nNnkXkx nN第第4 4章章 快速傅里葉變換快速傅里葉變換64/86所以所以因此因此 如果不考慮因子如果不考慮因子1/2，只要增加，只要增加2N次實(shí)數(shù)加法次實(shí)數(shù)加法運(yùn)算就能由運(yùn)算就能由DHT求出求出DFT。HHH( )( )( )( )Re( )Im( )eoX kXkjXkXkX kX kHHHH1( )( )()( )()22jX kXkXNkXkXNk第第4 4章章 快速傅里葉變換快速傅里葉變換65/863. DHT的快速算法（的快速算法（FHT）n仿照快速仿照快速DFT的分解方法，可通過時(shí)域的抽取的分解方法，可通過時(shí)域的抽取或頻域抽取

38、方式實(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 nxrrkxrrkNN第第4 4章章 快速傅里葉變換快速傅里葉變換66/86根據(jù)三角公式根據(jù)三角公式令令 ， ，根據(jù)，根據(jù)DHT的周期性，在的周期性，在 時(shí)時(shí)cas()cascoscas()sin/2 1H10/2 1/2 122002( )( )cas()/22222cos()( )cas()sin()( )

39、cas()/2/2NrNNrrXkx rrkNkx rrkkx rrkNNNN1H1( )DHT( )Xkx n2H2( )DHT( )Xkx n0k H1H2222( )( )cos()( )sin()()2HHNXkXkk Xkk XkNN第第4 4章章 快速傅里葉變換快速傅里葉變換67/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和

40、和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 第第4 4章章 快速傅里葉變換快速傅里葉變換68/86H1H22H1H22H1H22H1H22( )( )( )(/2)(/2)( )( )(/2)04(/2)(/2)( )(/2)()(/2)( )(/2)kHkHkHkHkHkHkHkHXkXkc Xks XNkXNkXkc Xks XNkNkXNkXNks

41、Xkc XNkXNkXNks Xkc XNkH1H2H1H2(0)(0)(0)0(/2)(0)(0)HHXXXkXNXXH1H2H1H2(/4)(/4)(/4)(3/4)(/4)(/4)4HHXNXNXNNkXNXNXN第第4 4章章 快速傅里葉變換快速傅里葉變換69/86上述的運(yùn)算可用哈德曼蝶形表示如圖上述的運(yùn)算可用哈德曼蝶形表示如圖4.5.1所示所示第第4 4章章 快速傅里葉變換快速傅里葉變換70/86四點(diǎn)的四點(diǎn)的FHT的蝶形圖如圖的蝶形圖如圖4.5.2所示。所示。第第4 4章章 快速傅里葉變換快速傅里葉變換71/86圖圖4.5.3顯示了顯示了8點(diǎn)的點(diǎn)的DIT基基-2FHT流圖流圖。第第4

42、 4章章 快速傅里葉變換快速傅里葉變換72/86運(yùn)算量運(yùn)算量乘法次數(shù)乘法次數(shù)加法次數(shù)加法次數(shù)211(2)34MLHLmNNMN33222HaNMN2MN 第第4 4章章 快速傅里葉變換快速傅里葉變換73/864.6 線性卷積和線性相關(guān)的FFT算法4.6.1 4.6.1 線性卷積的線性卷積的FFTFFT算法算法設(shè)設(shè) y(n)是是x(n)（n=0L-1）和）和h(n)（n=0M-1）的）的線性卷積：線性卷積： 由于每一個(gè)由于每一個(gè)x(n)的輸入值都必須和全部的的輸入值都必須和全部的h(n)相相乘一次，因而總共需要乘一次，因而總共需要LM次乘法次乘法。用用FFT算法也就是用圓周卷積來代替線性卷積時(shí)，

43、算法也就是用圓周卷積來代替線性卷積時(shí)，為了不產(chǎn)生混疊，其必要條件是使為了不產(chǎn)生混疊，其必要條件是使x(n)，h(n)都都補(bǔ)零值，補(bǔ)到至少補(bǔ)零值，補(bǔ)到至少N=M+L-1，即，即10( )( )* ( )() ()Mmy nx nh nh m x nm:( )y nL的長度為 第第4 4章章 快速傅里葉變換快速傅里葉變換74/86( ) 01( )0 1h nnMh nMnN( ) 01( )0 1x nnLx nLnN然后計(jì)算圓周卷積然后計(jì)算圓周卷積( )( )( )y nx nh n這時(shí)，這時(shí)，y(n)就能代表線性卷積的結(jié)果。就能代表線性卷積的結(jié)果。第第4 4章章 快速傅里葉變換快速傅里葉變換

44、75/86利用利用FFT進(jìn)行線性卷積的步驟如下：進(jìn)行線性卷積的步驟如下：1.將序列將序列x(n)和和h(n)補(bǔ)零延長，使其長度補(bǔ)零延長，使其長度 若采用基若采用基-2FFT，還應(yīng)使，還應(yīng)使N等于等于 2的最小整數(shù)次冪。的最小整數(shù)次冪。2.做做x(n)和和h(n)的長為的長為N點(diǎn)的點(diǎn)的FFT得到得到X(k)和和Y(k)，求它，求它們的積們的積Y(k)=X(k)H(k)3.求求Y（k）的）的IFFT并取前并取前N點(diǎn)獲得線性卷積的結(jié)果為點(diǎn)獲得線性卷積的結(jié)果為NL+M-1 01( ) ( )y nIDFT Y knN第第4 4章章 快速傅里葉變換快速傅里葉變換76/86整個(gè)過程中，共需要進(jìn)行三次整個(gè)過

45、程中，共需要進(jìn)行三次FFT運(yùn)算，共需運(yùn)算，共需 次相乘，還有步驟（次相乘，還有步驟（2）的）的N次相乘，因此共需相乘次次相乘，因此共需相乘次數(shù)為數(shù)為可以用線性相位可以用線性相位FIR濾波器來比較直接計(jì)算線性卷積濾波器來比較直接計(jì)算線性卷積和和FFT法計(jì)算線性卷積這兩種方法的乘法次數(shù)。法計(jì)算線性卷積這兩種方法的乘法次數(shù)。 代表直接線性卷積所用的乘法次數(shù)，則比值為代表直接線性卷積所用的乘法次數(shù)，則比值為23log2NN2233log(1log)22FmNNNNN22332(1log)2(1)1log (1)22dmFmMLMLKmNNMLMLdm第第4 4章章 快速傅里葉變換快速傅里葉變換77/86（1）x(n)與與h(n)點(diǎn)數(shù)差不多點(diǎn)數(shù)差不多例如，設(shè)例如，設(shè)M=L，則，則 ，則，則當(dāng)當(dāng)M8，16，32時(shí)，圓周卷積的運(yùn)算量大于線性