DSP-第三章23-24

1、第三章第三章 離散傅里葉離散傅里葉變換及其快速算法變換及其快速算法3.3 快速傅里葉變換快速傅里葉變換 (FFT) 從前面的討論中看到，有限長序列在數字技術中占從前面的討論中看到，有限長序列在數字技術中占有很重要的地位。有限長序列的一個重要特點是其頻有很重要的地位。有限長序列的一個重要特點是其頻域可離散化，即離散傅里葉變換域可離散化，即離散傅里葉變換(DFT)。 雖然頻譜分析和雖然頻譜分析和DFT運算很重要，但在很長一段時運算很重要，但在很長一段時間里，由于間里，由于DFT運算復雜，并沒有得到真正的運用，運算復雜，并沒有得到真正的運用，而頻譜分析仍大多采用模擬信號濾波的方法解決，直而頻譜分析仍

2、大多采用模擬信號濾波的方法解決，直到到1965年首次提出年首次提出DFT運算的一種快速算法以后，情運算的一種快速算法以后，情況才發(fā)生了根本變化，人們開始認識到況才發(fā)生了根本變化，人們開始認識到DFT運算的一運算的一些內在規(guī)律，從而很快地發(fā)展和完善了一套高速有效些內在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運算方法的運算方法快速傅里葉變換快速傅里葉變換(FFT)算法。算法。 FFT的出現，使的出現，使DFT的運算大大簡化，運算時間的運算大大簡化，運算時間縮短縮短12個數量級，使個數量級，使DFT的運算在實際中得到廣的運算在實際中得到廣泛應用。泛應用。一、提出問題：設有限長序列一、提出問題：設有

3、限長序列x(n),非零值長度為非零值長度為N, 對對x(n)進行進行N點點DFT運算，共需多大的運算量運算，共需多大的運算量?10( ) ( )( )NnkNnX kDFT x nx n W k=0,1,2,N1n計算一個計算一個X(k)(一個頻率成分一個頻率成分)值，運算量為值，運算量為 例如，例如，k=1，則則 要進行要進行N次復數乘法次復數乘法和和(N-1)次復數加法次復數加法；n要完成整個要完成整個DFT運算，運算，需要計算需要計算N個個X(k)值值，所，所以以總總計算量為：計算量為： N*N次復數相乘和次復數相乘和N*(N-1)次復數加法次復數加法10(1)( )NnNnXx n W

4、 n在這些運算中，乘法比加法復雜，需要的運算時間在這些運算中，乘法比加法復雜，需要的運算時間多，尤其是復數相乘，每個復數相乘包括多，尤其是復數相乘，每個復數相乘包括4個實數個實數相乘和相乘和2個實數相加，例個實數相加，例 10( )( )( )( )( )NnknkeeNmmNnnknkemNmeNX kRx nRwIx nIwj Rx nIwIx nRw 又每個復數相加包括又每個復數相加包括2個實數相加，所以，每計算一個實數相加，所以，每計算一個個X(k)要進行要進行4N次實數相乘和次實數相乘和2N+2(N-1)=2(2N-1)次次實數相加。因此，整個實數相加。因此，整個DFT運算需要運算需

5、要 4N2實數相乘和實數相乘和2N(2N-1)次實數相加次實數相加 從上面的分析看到，在從上面的分析看到，在DFT計算中，不論是乘法計算中，不論是乘法和加法，運算量均與和加法，運算量均與N2成正比。因此，成正比。因此，N較大時，較大時，運算量十分可觀。運算量十分可觀。 反變換反變換IDFT與與DFT的運算結構相同，只是多乘一的運算結構相同，只是多乘一個常數個常數1/N，所以二者的計算量相同。，所以二者的計算量相同。例例1:當當N=1024點時，直接計算點時，直接計算DFT需要：需要： N2=220=1048576次，即一百多萬次的復乘運算次，即一百多萬次的復乘運算 例例2:石油勘探，石油勘探，

6、24道記錄，每道波形記錄長度道記錄，每道波形記錄長度5秒，若秒，若 每秒抽樣每秒抽樣500點點/秒，秒， 每道總抽樣點數每道總抽樣點數=500*5=2500點點 24道總抽樣點數道總抽樣點數=24*2500=6萬點萬點 DFT運算需要運算需要N2=(60000)2=36*108次次 如此之大的運算量，對計算機的處理能力和處理速度如此之大的運算量，對計算機的處理能力和處理速度都提出很高的要求；尤其在實時性很強的信號處理都提出很高的要求；尤其在實時性很強的信號處理(如雷如雷達信號處理達信號處理)中，對計算速度的要求十分苛刻；中，對計算速度的要求十分苛刻；迫切需要改進迫切需要改進DFT的計算方法，以

7、減少總的運算次數的計算方法，以減少總的運算次數二、改善二、改善DFT運算效率的基本途徑運算效率的基本途徑1利用利用nkNW的特點的特點2jNNWe 具有具有 1)周期性周期性 ()()nkn N kn kNNNNWWW 2)共軛性共軛性 ()()()nkNn kn NkNNNWWW 3)對稱性對稱性 ()2NkkNNWW 4)221NNNNWW 5)22nnNNWW ReImj8N0NW7NW6NW5NW4NW3NW2NW1NW2、FFT的思路的思路利用對稱性和周期性將長序利用對稱性和周期性將長序列列DFT分解為短序列分解為短序列DFTn因為因為DFT的運算量與的運算量與N2成正比的成正比的n

8、如果一個大點數如果一個大點數N的的DFT能分解為若干小點能分解為若干小點數數DFT的組合，則顯然可以達到減少運算工的組合，則顯然可以達到減少運算工作量的效果作量的效果n運算量分解示意圖如下：運算量分解示意圖如下：其運算量為：其運算量為：22)()()(NNNkXkXkX把把N點數據分成二半：點數據分成二半：2)2(N2)2(N2N再分二半：再分二半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+=24N這樣一直分下去，剩下這樣一直分下去，剩下兩點的變換兩點的變換。三、常見的三、常見的FFT算法算法n按抽取方法分：按抽取方法分： 時間抽取法時

9、間抽取法(DIT); 頻率抽取法頻率抽取法(DIF);n按按“基數基數”分：分： 基基-2FFT算法；算法； 基基-4FFT算法；算法； 混合基混合基FFT算法；算法；3.3.1 按時間抽取的按時間抽取的FFT1、先從、先從一一特殊情況開始，假定特殊情況開始，假定N是是2的整數次方，即的整數次方，即 N=2M，M：正整數：正整數 將序列將序列x(n)分解為兩組分解為兩組偶數項和奇數項偶數項和奇數項 r=0,1，N/2-1 12(2 )( )(21)( )xrx rxrx r 2101()()NNn kn kNNnnxnwxnw 偶偶奇奇 10X( )( )( )NnkNnkDFTx nx n

10、w DFT運算也相應分為兩組：運算也相應分為兩組：/2 1/2 12(21)00(2 )(21)NNrkrkNNrrxr wxrw /2 1/2 12200(2 )(21)NNrkkrkNNNrrxr wwxrw 因為因為 故故 其中其中 /2 102/2 102(2 )(21)NrkNrNrkNrG kxr WH kxrW 222222jnNjnnnNNNweew /2 1/2 10022(2 )(21)NNrkkrkNNNrrkNX kxr WWxrWG kW H kk=0,1,N/2-1應用系數應用系數wkN的周期性和對稱性：的周期性和對稱性：X(k)的后的后N/2個點（個點（ 即即N/

11、2N-1點），表示為點），表示為 ()/2222Nkr NkrkkNNNNwwWW 222222,0,1,12kNNkNG kNG kH kNH kX kNG kNWH kNNG kW H kk ,0,1,12(),0,1,122kNkNNX kG kW H kkNNX kG kW H kk依此類推，依此類推，G(k)和和H(k)可以繼續(xù)分下去，這種可以繼續(xù)分下去，這種按時間抽取算法是在輸入序列分成越來越小的按時間抽取算法是在輸入序列分成越來越小的子序列上執(zhí)行子序列上執(zhí)行DFT運算，最后再合成為運算，最后再合成為點的點的DFT。 一個一個N點的點的DFT被分解為兩個被分解為兩個N/2點的點的D

12、FT，這兩，這兩個個N/2點的點的DFT再合成為一個再合成為一個N點點DFT.2、蝶形信號流圖、蝶形信號流圖將將G(k)和和H(k) 合成合成X(k)運算可歸結為：運算可歸結為： abWabW Wa+bWa-bW-W1a+bWa-bWWabab蝶 形 運 算 的 簡蝶 形 運 算 的 簡化化(a)(a)(b)圖圖 (a)為實現這一運算的一般方法，它需要兩次乘法、為實現這一運算的一般方法，它需要兩次乘法、兩次加減法?？紤]到兩次加減法。考慮到-bW和和bW兩個乘法僅相差一負兩個乘法僅相差一負號，可將圖號，可將圖 (a)簡化成圖簡化成圖 (b)，此時僅需一次乘法、，此時僅需一次乘法、兩次加減法。兩次

13、加減法。圖圖 (b)的運算結構像一蝴蝶通常稱作蝶形運算結構簡的運算結構像一蝴蝶通常稱作蝶形運算結構簡稱蝶形結，采用這種表示法，就可以將以上所討論稱蝶形結，采用這種表示法，就可以將以上所討論的分解過程用流圖表示的分解過程用流圖表示。3、N=23=8 的例子的例子。 按照這個辦法，繼續(xù)把按照這個辦法，繼續(xù)把N/2用除，由于用除，由于N=2M，仍，仍然是偶數，可以被整除，因此，可以對兩個然是偶數，可以被整除，因此，可以對兩個N/2點點的的DFT再分別作進一步的分解。再分別作進一步的分解。 即對即對G(k)和和H(k)的計算，又可以分別通過計算的計算，又可以分別通過計算兩個長度為兩個長度為N/4=2點

14、的點的DFT，進一步節(jié)省計算量，見，進一步節(jié)省計算量，見圖。這樣，一個點的圖。這樣，一個點的DFT就可以分解為四個點的就可以分解為四個點的DFT。 最后剩下的是最后剩下的是2點點DFT，它可以用一個蝶形結表示：，它可以用一個蝶形結表示： 這樣，一個這樣，一個8點的完整的按時間抽取運算的流圖點的完整的按時間抽取運算的流圖 由于這種方法每一步分解都是按輸入時間序列是屬由于這種方法每一步分解都是按輸入時間序列是屬于偶數還是奇數來抽取的，所以稱為于偶數還是奇數來抽取的，所以稱為“按時間抽取法按時間抽取法”或或“時間抽取法時間抽取法”。) 1 ()0() 1 ()0() 1 () 1 ()0() 1 (

15、)0()0(1202xWxxWxXxWxxWxXoNoN按時間抽取的按時間抽取的8點點FFT4、時間抽取法、時間抽取法FFT的運算特點：的運算特點：(1)蝶形運算蝶形運算(2)原位計算原位計算 (3)序數重排序數重排(4)蝶形類型隨迭代次數成倍增加蝶形類型隨迭代次數成倍增加(1)蝶形運算蝶形運算 對于對于N=2M，總是可以通過，總是可以通過M次分解最后成為次分解最后成為2點的點的DFT運算。這樣構成從運算。這樣構成從x(n)到到X(k)的的M級運算過程。級運算過程。 從上面的流圖可看到，每一級運算都由從上面的流圖可看到，每一級運算都由N/2個蝶形運個蝶形運算構成。因此每一級運算都需要算構成。因

16、此每一級運算都需要N/2次復乘和次復乘和N次復次復加，這樣，經過時間抽取后加，這樣，經過時間抽取后M級運算總共需要的運算級運算總共需要的運算： 復乘復乘 復加復加 而直接運算時則與而直接運算時則與N2 成正比。成正比。 例例N=2048，N2=4194304，(N/2)log2N=11264，N2/ (N/2)log2N=392.4。FFT顯然要比直接法快得多。顯然要比直接法快得多。log222NNMNlog2NMNN(2)原位計算原位計算 當數據輸入到存儲器中以后，每一級運算的結果當數據輸入到存儲器中以后，每一級運算的結果仍然儲存在同一組存儲器中，直到最后輸出，中間仍然儲存在同一組存儲器中，

17、直到最后輸出，中間無需其它存儲器，這叫原位計算。無需其它存儲器，這叫原位計算。 每一級運算均可在原位進行，這種原位運算結構每一級運算均可在原位進行，這種原位運算結構可節(jié)省存儲單元，降低設備成本，還可節(jié)省尋址的可節(jié)省存儲單元，降低設備成本，還可節(jié)省尋址的時間。時間。(3)序數重排序數重排 對按時間抽取對按時間抽取FFT的原位運算結構，當運算完畢時，的原位運算結構，當運算完畢時，正好順序存放著正好順序存放著X(0)，X(1)，X(2)，X(7)，因此可，因此可直接按順序輸出，但這種原位運算的輸入直接按順序輸出，但這種原位運算的輸入x(n)卻不能按卻不能按這種自然順序存入存儲單元中，而是按這種自然順

18、序存入存儲單元中，而是按x(0)，x(4)，x(2)，x(6)，x(7)的順序存入存儲單元，這種順序看起來的順序存入存儲單元，這種順序看起來相當雜亂，然而它也是有規(guī)律的。當用二進制表示這個相當雜亂，然而它也是有規(guī)律的。當用二進制表示這個順序時，它正好是順序時，它正好是“碼位倒置碼位倒置”的順序。例如，原來的的順序。例如，原來的自然順序應是自然順序應是x(1)的地方，現在放著的地方，現在放著x(4)，用二進制碼表，用二進制碼表示這一規(guī)律時，則是在示這一規(guī)律時，則是在 x(0 0 1)處放著處放著 x(1 0 0)， x(0 1 1)處放著處放著 x(1 1 0)。自然順序自然順序二進碼表示二進碼

19、表示碼位倒置碼位倒置碼位倒置順序碼位倒置順序0000000010011004201001023011110641000011510110156110010371111117 在實際運算中，一般直接將輸入數據在實際運算中，一般直接將輸入數據x(n)按碼位倒置的順按碼位倒置的順序排好輸入很不方便，總是先按自然順序輸入存儲單元，然序排好輸入很不方便，總是先按自然順序輸入存儲單元，然后再通過變址運算將自然順序的存儲轉換成碼位倒置順序的后再通過變址運算將自然順序的存儲轉換成碼位倒置順序的存儲，然后進行存儲，然后進行FFT的原位計算。目前有許多通用的原位計算。目前有許多通用DSP芯片芯片支持這種碼位倒置的

20、尋址功能。支持這種碼位倒置的尋址功能。n第一次分偶、奇，根據最低位第一次分偶、奇，根據最低位n0的的0、1狀態(tài)來分，狀態(tài)來分，若若n0=0，則為偶序列；，則為偶序列；n0=1則為奇序列，得到兩組則為奇序列，得到兩組序列：序列： 000 010 100 110 001 011 101 111n第二次對這兩個偶、奇序列再分一次偶、奇序列，這第二次對這兩個偶、奇序列再分一次偶、奇序列，這就要根據就要根據n1的、狀態(tài)。若的、狀態(tài)。若n1=0，則為偶序列；，則為偶序列；n1=1則為奇序列，得到四組序列：則為奇序列，得到四組序列： 000 100 010 110 001 101 011 111n同理，再根

21、據同理，再根據n2的、狀態(tài)來分偶、奇序列，直到的、狀態(tài)來分偶、奇序列，直到不能再分偶、奇時為止。對于不能再分偶、奇時為止。對于N=8, n2已是最高位，已是最高位，最后一次分得結果為最后一次分得結果為 000 100 010 110 001 101 011 111(4)蝶形類型隨迭代次數成倍增加蝶形類型隨迭代次數成倍增加 觀察觀察8點點FFT的三次迭代運算的三次迭代運算: 第一級迭代，有一種類型的蝶形運算系數第一級迭代，有一種類型的蝶形運算系數W08，兩個數據點間隔為兩個數據點間隔為1； 第二級迭代，有二種類型的蝶形運算系數第二級迭代，有二種類型的蝶形運算系數W08、W28 ，參加運算的兩個數

22、據點間隔為參加運算的兩個數據點間隔為2； 第三級迭代，有四類蝶形運算系數第三級迭代，有四類蝶形運算系數W08、W18、W28、W38，參加運算的兩個數據點間隔為，參加運算的兩個數據點間隔為4； 結論：每迭代一次，蝶形類型增加一倍，數據點間結論：每迭代一次，蝶形類型增加一倍，數據點間 隔也增大一倍。每一級的取數間隔和蝶形類隔也增大一倍。每一級的取數間隔和蝶形類 型種類均為型種類均為2i-1，i=1,2,M。 3.3.2按頻率抽取的按頻率抽取的FFT(按輸出按輸出X(k)在頻域的在頻域的順序上屬于偶數還是奇數分解為兩組順序上屬于偶數還是奇數分解為兩組) 對于對于N=2M情況下的另外一種普遍使用的情

23、況下的另外一種普遍使用的FFT結構是結構是頻率抽取法。對于頻率抽取法，輸入序列不是按偶數奇頻率抽取法。對于頻率抽取法，輸入序列不是按偶數奇數，而是按前后對半分開，這樣便將數，而是按前后對半分開，這樣便將N點點DFT寫成前后寫成前后兩部分：兩部分： /( )( )( )2 1102NNnknkNNnn NX kx n Wx n W/()( )()2 12 12002NNNnknkNNnnNx n Wx nW/(/ ) ( )(/ )2 1202NNknkNNnx nWx nNW又又把把X(k)進一步分解為偶數組和奇數組：進一步分解為偶數組和奇數組： X(2r+1)= 奇數為偶數1, 1) 1(,

24、 1)2/(2/kWWkkNNNN/( ) ( )()(/ )2 1012NknkNnX kx nx nNW /() ( )(/ )2 12022NnrNnXrx nx nNW/ ( )(/ )2 1202NnrNnx nx nNW/() ( )(/ )2 12102NnrNnx nx nNW/ ( )(/ )2 1202NnnrNNnx nx nNW W令令 a(n)=x(n)+x(n+N/2)，b(n)=x(n)-x(n+N/2wnN這兩個序列都是這兩個序列都是N/2點的序列，將其代入上兩式，得點的序列，將其代入上兩式，得 這正是兩個這正是兩個N/2點的點的DFT運算，即將一個運算，即將一

25、個N點的點的DFT分解分解為兩個為兩個N/2點的點的DFT，上式的運算關系可用下圖表示，上式的運算關系可用下圖表示. /()( )2 1202NnrNnXra n W/()( )2 12021NnrNnXrb n Wx1(n)+ x2(n)WNnx1(n)x2(n)x1(n)-x2(n) WNn-1以以N=8的頻率抽取為例的頻率抽取為例x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1N/2點點DFTa(0)a(1)a(2)a(3)N/2點點DFTb(0)b(1)b(2)b(3)WN1WN2WN3X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)按頻

26、率抽取將按頻率抽取將8點點DFT分解成兩個分解成兩個4點點DFT按頻率抽取將按頻率抽取將8點點DFT分解成四個分解成四個2點點DFT 與時間抽取法一樣，由于與時間抽取法一樣，由于N=2M，N/2仍是一個偶仍是一個偶數數,這樣，一個這樣，一個N=2M點的點的DFT通過通過M次分解后，最次分解后，最后只剩下全部是后只剩下全部是2點的點的DFT，2點點DFT實際上只有加實際上只有加減運算。但為了比較，也為了統(tǒng)一運算的結構，仍減運算。但為了比較，也為了統(tǒng)一運算的結構，仍用一個系數為用一個系數為W0N 的蝶形運算來表示。的蝶形運算來表示。 頻率抽取法的流圖是時域抽取法流圖的左右翻轉頻率抽取法的流圖是時域

27、抽取法流圖的左右翻轉。下圖是。下圖是N=8的頻率抽取法的頻率抽取法FFT流圖。流圖。 N=8的按頻率抽取的按頻率抽取FFT運算流圖運算流圖頻率抽取法頻率抽取法FFT的運算特點：的運算特點：(1)蝶形運算蝶形運算 對于任何一個對于任何一個2的整數冪的整數冪N=2M，總是可以通過，總是可以通過M次分解最后完全成為次分解最后完全成為2點的點的DFT運算。這樣的運算。這樣的M次分次分解，就構成從解，就構成從x(n)到到X(k)的的M級運算過程。將頻率級運算過程。將頻率抽取法的流圖反轉，并將輸入變輸出，輸出變輸入抽取法的流圖反轉，并將輸入變輸出，輸出變輸入，得到的便是時間抽取法流圖，得到的便是時間抽取法

28、流圖(反映了時域，頻域的反映了時域，頻域的對稱法對稱法)。頻率抽取法也共有。頻率抽取法也共有M級運算級運算(N=2M)，其運，其運算量與時間抽取法相同。算量與時間抽取法相同。(2)原位計算原位計算 類似于時間抽取法，當數據輸入到存儲器中以后類似于時間抽取法，當數據輸入到存儲器中以后，每一級運算的結果仍然儲存在同一組存儲器中，每一級運算的結果仍然儲存在同一組存儲器中，直到最后輸出，中間無需其它存儲器，所以頻域抽直到最后輸出，中間無需其它存儲器，所以頻域抽取法也可進行原位計算。取法也可進行原位計算。(3)序數重排序數重排 它的輸入正好是自然順序。但它的輸出卻是碼位倒置它的輸入正好是自然順序。但它的

29、輸出卻是碼位倒置的順序。因此運算完畢后，要通過變址運算將碼位倒置的順序。因此運算完畢后，要通過變址運算將碼位倒置的順序轉換為自然順序，然后輸出，變址方法同時間抽的順序轉換為自然順序，然后輸出，變址方法同時間抽取法。取法。(4)蝶形類型隨迭代次數成倍減少蝶形類型隨迭代次數成倍減少(與時間抽取法相反與時間抽取法相反) 第一級迭代中有第一級迭代中有N/2種蝶形運算系數，參加蝶形運算種蝶形運算系數，參加蝶形運算的兩個數據相隔的兩個數據相隔N/2，隨后每次迭代，蝶形類形比前一，隨后每次迭代，蝶形類形比前一級減少一倍，間距也減少一倍，最后一級迭代，蝶形類級減少一倍，間距也減少一倍，最后一級迭代，蝶形類形只

30、有一種形只有一種W0N，數據間隔為，數據間隔為1。由這幾點規(guī)律可以看出，頻率抽取法與時間抽到法是兩由這幾點規(guī)律可以看出，頻率抽取法與時間抽到法是兩種等價的種等價的FFT運算。運算。3.3.3 N為組合數的為組合數的FFT(任意基數的任意基數的FFT算法算法) 以上討論的都是以以上討論的都是以2為基數的為基數的FFT算法，即算法，即N=2M，這種情況實際上使用得最多。這種情況實際上使用得最多。 優(yōu)點：程序簡單，效率高，使用方便。優(yōu)點：程序簡單，效率高，使用方便。 實際應用時，有限長序列的長度實際應用時，有限長序列的長度N很大程度上由人很大程度上由人為因素確定，因此多數場合可取為因素確定，因此多數

31、場合可取N=2M，從而直接使用，從而直接使用以以2 為基數的為基數的FFT算法。算法。 如要求準確的如要求準確的N點點DFT值值,可采用任意數為基數的可采用任意數為基數的 FFT算法算法 , 其其 計算效率低于以計算效率低于以2為基數為基數FFT算法。算法。 如如N為復合數，可分解為兩個整數為復合數，可分解為兩個整數p與與q的乘積的乘積,像前像前面以面以2為基數時一樣為基數時一樣,FFT的基本思想是將的基本思想是將DFT的運算的運算盡量分小盡量分小,因此因此,在在N=pq情況下情況下,也希望將也希望將N點的點的DFT分分解為解為p個個q點點DFT或或q個個p點點DFT,以減少計算量。以減少計算

32、量。如如N不能人為確定不能人為確定 , N的數值也不是以的數值也不是以2為基數的整數次為基數的整數次方方,處理方法有兩種處理方法有兩種: 補零補零: 將將x(n)補零補零 , 使使N=2M. 例如例如N=30,補上補上x(30)=x(31)=0兩點兩點,使使N=32=25,這樣可這樣可直接采用以直接采用以2為基數為基數M=5的的FFT程序。程序。 3.4 FFT應用中的幾個問題應用中的幾個問題1)IDFT的運算方法的運算方法101( )( )( )NnkNkx nIDFT X kX k WN 10X(k)=DFTx(n) =()NnkNnx n W 以上所討論的以上所討論的FFT算法可用于算法

33、可用于IDFT運算運算簡簡稱為稱為IFFT。 比較比較IDFT的定義式：的定義式： IDFT： DFT：IDFT與與DFT的差別的差別 1)把把DFT中的每一個系數中的每一個系數 改為改為 ， 2)再乘以常數再乘以常數 1/N ， 則以上所討論的時間抽取或頻率抽取的則以上所討論的時間抽取或頻率抽取的FFT運算均可直接用于運算均可直接用于IDFT運算，當然，蝶形中運算，當然，蝶形中的系數的系數 應改為應改為 。nkNWnkNW nkNW nkNW b)第二種方法，完全不需要改動第二種方法，完全不需要改動FFT程序，而是直接利程序，而是直接利 用它作用它作 IFFT。 考慮到考慮到 故故 IFFT

34、計算分三步：計算分三步： 將將X(k)取共軛取共軛(虛部乘以虛部乘以-1) 對對 直接作直接作FFT 對對FFT的結果取共軛并乘以的結果取共軛并乘以1/N，得，得x(n)。101( )( )NnkNkxnXk WN 1011( )( )( )NnkNkx nXk WDFT XkNN ( )Xk 3.4 FFT應用中的幾個問題應用中的幾個問題2)實數序列的實數序列的FFT以上討論的以上討論的FFT算法都是復數運算算法都是復數運算,包括序列包括序列x(n)也認也認為是復數為是復數,但大多數場合但大多數場合,信號是實數序列信號是實數序列,任何實數都任何實數都可看成虛部為零的復數可看成虛部為零的復數,

35、例如例如,求某實信號求某實信號x(n)的復譜的復譜,可認為是將實信號加上數值為零的虛部變成復信號可認為是將實信號加上數值為零的虛部變成復信號(x(n)+j0),再用再用FFT求其離散傅里葉變換。這種作法很求其離散傅里葉變換。這種作法很不經濟不經濟,因為把實序列變成復序列因為把實序列變成復序列,存儲器要增加一倍存儲器要增加一倍,且計算機運行時且計算機運行時,即使虛部為零即使虛部為零,也要進行涉及虛部的也要進行涉及虛部的運算運算,浪費了運算量。合理的解決方法是利用復數據浪費了運算量。合理的解決方法是利用復數據FFT對實數據進行有效計算對實數據進行有效計算,下面介紹兩種方法。下面介紹兩種方法。 (1

36、)用用 一個一個N點點FFT同時計算兩個同時計算兩個N點實序列的點實序列的DFT 設設x (n)、y (n)是彼此獨立的兩個是彼此獨立的兩個N點實序列點實序列,且且 X (k)=DFTx (n)，Y (k)=DFTy(n) 則則X (k)、Y(k)可通過一次可通過一次FFT運算同時獲得。運算同時獲得。 首先，將首先，將x (n)、y(n)分別當作一復序列的實部及虛分別當作一復序列的實部及虛部部, 令令 g(n)=x (n)+jy(n) riririirriG kX kjY kXkjXkjYkYkXkYkjXkjYkGkjGk *DFT Re121122rriig nX kG kGNkGkGNk

37、j GkGNk 通過通過FFT運算可獲得運算可獲得g(n)的的DFT值值利用離散傅里葉變換的共軛對稱性利用離散傅里葉變換的共軛對稱性通過通過g(n)的的FFT運算結果運算結果G(k),由上式可得到由上式可得到X (k) 的值。的值。通過通過g(n)FFT運算結果運算結果G(k),由上式也可得到由上式也可得到Y (k) 的值。的值。 *DFTIm121122rriijg njY kG kGNkG kG Nkj G kG Nk 1122iirrY kG kG N kj G kG N k 做一次做一次點復序列的點復序列的FFT，再通過加、減法運算就可以，再通過加、減法運算就可以將將X(k)與與Y(k

38、)分離出來。這將使運算效率提高一倍。分離出來。這將使運算效率提高一倍。 (2)用一個用一個N點的點的FFT運算獲得一個運算獲得一個2N點實序列的點實序列的DFT 設設x(n)是是2N點的實序列點的實序列,現人為地將現人為地將x(n)分為偶數分為偶數組組x1(n)和奇數組和奇數組x2(n) x1(n)=x(2n) n=0,1,N-1 x2(n)=x(2n+1) n=0,1,N-1 然后將然后將x1(n)及及x2(n)組成一個復序列：組成一個復序列： y(n)=x1(n)+jx2(n)通過通過N點點FFT運算可得到：運算可得到： Y(k)=X1(k)+jX2(k) ，N點點根據前面的討論，得到根據

39、前面的討論，得到 *1*21( )( )()2( )( )()2XkY kYNkjXkY kYNk 為求為求 2N 點點 x(n)所對應所對應 X(k)，需求出，需求出 X(k)與與 X1(k)、X2(k)的關系的關系 ： 而而 21112(21)22000( )( )(2 )(21)NNNnknknkNNnnnX kx n Wxn WxnW 11200(2 )(21)NNnkknkNNNnnxn WWxnW 1111001122100( )( )(2 )( )( )(21)NNnknkNNnnNNnknkNNnnXkx n Wxn WXkxn WxnW 所以所以1)由由x1(n)及及x2(n

40、)組成復序列，經組成復序列，經FFT運算求得運算求得 Y(k)，2)利用共軛對稱性求出利用共軛對稱性求出 X1(k)、X2(k)，3)最后利用上式求出最后利用上式求出 X(k), 達到用一個達到用一個N點的點的FFT計算計算一個一個2N點的實序列的點的實序列的DFT的目的。的目的。 X(k)=X1(k)+W2Nk X2(k) 3) 線性卷積的線性卷積的FFT算法算法 線性卷積是求離散系統(tǒng)響應的主要方法之一線性卷積是求離散系統(tǒng)響應的主要方法之一,許多重要許多重要應用都建立在這一理論基礎上應用都建立在這一理論基礎上,如卷積濾波等。如卷積濾波等。 以前曾討論了用圓周卷積計算線性卷積方法歸納如下以前曾

41、討論了用圓周卷積計算線性卷積方法歸納如下： 將長為將長為N2的序列的序列x(n)延長到延長到L,補補L-N2個零，個零， 將長為將長為N1的序列的序列h(n)延長到延長到L,補補L-N1個零，個零， 如果如果LN1+N2-1,則圓周卷積與線性卷積相等則圓周卷積與線性卷積相等,此時此時,可可用用FFT計算線性卷積，方法如下計算線性卷積，方法如下: a. 計算計算X(k)=FFTx(n)b. 求求H(k)=FFTh(n)c. 求求Y(k)=H(k)X(k) k=0L-1d. 求求y(n)=IFFTY(k) n=0L-1 可見可見, 只要進行二次只要進行二次FFT, 一次一次IFFT就可完成線就可完

42、成線性卷積計算。性卷積計算。 計算表明計算表明, L32時時, 上述計算線性卷積的方法上述計算線性卷積的方法比直接計算線卷積有明顯的優(yōu)越性比直接計算線卷積有明顯的優(yōu)越性, 因此因此, 也稱上也稱上述循環(huán)卷積方法為快速卷積法。述循環(huán)卷積方法為快速卷積法。 上述結論適用于上述結論適用于 x(n)、h(n) 兩序列長度比較接近或兩序列長度比較接近或相等的情況相等的情況,如果如果x(n)、h(n) 長度相差較多長度相差較多,例如例如, h(n) 為某濾波器的單位脈沖響應為某濾波器的單位脈沖響應,長度有限長度有限,用來處理一個用來處理一個很長的輸入信號很長的輸入信號 x(n),或者處理一個連續(xù)不斷的信號

43、，或者處理一個連續(xù)不斷的信號，按上述方法按上述方法, h(n) 要補許多零再進行計算要補許多零再進行計算,計算量有很計算量有很大的浪費，或者根本不能實現。大的浪費，或者根本不能實現。 為了保持快速卷積法的優(yōu)越性為了保持快速卷積法的優(yōu)越性,可將可將 x(n) 分為許多分為許多段段,每段的長度與每段的長度與 h(n) 接近接近 , 處理方法有兩種：處理方法有兩種：(1) 重疊相加法重疊相加法由分段卷積的各段相由分段卷積的各段相加構成總的卷積輸出加構成總的卷積輸出h(n)x(n) 假定假定 xi(n) 表示表示 x(n)序列的第序列的第i段段 ： 則輸入序列可表為：則輸入序列可表為： 于是輸出可分解

44、為：于是輸出可分解為： 其中其中 22( )(1)1( )0ix niNniNx n ( )( )iix nx n ( )( )* ( )( )* ( )( )iiiiy nx nh nx nh ny n ( )( )* ( )iiy nx nh n 1)先對先對h(n)及及xi(n)補零，補到具有補零，補到具有N點長度，點長度，N=N1+N2-1。一般選。一般選 N=2M。 2)用基用基2FFT計算計算 yi(n)=xi(n)*h(n)。 3)重疊部分相加構成最后的輸出序列。重疊部分相加構成最后的輸出序列。 由于由于yi(n)的長度為的長度為N，而，而xi(n)的長度為的長度為N2，因此相，

45、因此相鄰兩段鄰兩段 yi(n)序列必然有序列必然有N-N2=N1-1點發(fā)生重疊。點發(fā)生重疊。 ( )( )iiy ny n 計算步驟：計算步驟：a. 事先準備好濾波器參數事先準備好濾波器參數 H(k)=DFTh(n)，N點點b. 用用N點點FFT計算計算Xi(k)=DFTxi(n)c. Yi(k)=Xi(k)H(k)d. 用用N點點IFFT求求 yi(n)=IDFTYi(k)e. 將重疊部分相加將重疊部分相加(2)重疊保留重疊保留 這種方法和第一種方法稍有不同，即將上面分段序這種方法和第一種方法稍有不同，即將上面分段序列中補零的部分不是補零，而是保留原來的輸入序列列中補零的部分不是補零，而是保

46、留原來的輸入序列值，這時，如利用值，這時，如利用DFT實現實現h(n)和和xi(n)的循環(huán)卷積，的循環(huán)卷積，則每段卷積結果中有則每段卷積結果中有N1-1個點不等于線性卷積值需舍個點不等于線性卷積值需舍去。去。 重疊保留法與重疊相加法的計算量差不多，但省去重疊保留法與重疊相加法的計算量差不多，但省去了重疊相加法最后的相加運算。了重疊相加法最后的相加運算。 4)用用FFT計算相關函數計算相關函數 相關的概念很重要，互相關運算廣泛應用于信相關的概念很重要，互相關運算廣泛應用于信號分析與統(tǒng)計分析，如通過相關函數峰值的檢測測號分析與統(tǒng)計分析，如通過相關函數峰值的檢測測量兩個信號的時延差等。量兩個信號的時

47、延差等。 兩個長為兩個長為N的實離散時間序列的實離散時間序列 x(n)與與y(n)的互相的互相關函數定義為關函數定義為 1100( )() ( )( ) ()NNxynnrx ny nx n y n 則可以證明，則可以證明，rxy()的離散傅里葉變換為的離散傅里葉變換為 Rxy(k)= 其中其中 X(k)=DFTx(n), Y(k)=DFTy(n), Rxy(k)=DFTrxy()， 0kN-1*X (k)Y(k)互相關函數定義為互相關函數定義為 x(n)及及y(n)的卷積公式的卷積公式 相比較，我們可以得到相關和卷積的時域關系：相比較，我們可以得到相關和卷積的時域關系： 1100()() (

48、 )( ) ()NNxynnrmx nm y nx n y nm10()() ( )()()Nnf mx mn y nx my m 1100()() ( ) () ( )()()NNxynnrmx nm y nxmn y nxmy m 211001( )( ) ()( ) ( )NNjkNxynkrx n y nXk Y k eN 因因 得得 證畢。證畢。DFT ()( )*( )NNxnRnXk 當當x(n)=y(n)時，得到時，得到x(n)的自相關函數為：的自相關函數為： 維納維納辛欽定理：辛欽定理： 自相關函數與信號功率譜互為傅立葉變換對。自相關函數與信號功率譜互為傅立葉變換對。 10( )( ) ()Nxxnrx n x n 21201|() |NjkNkX keN 上面的推導表明，互相關和自相關函數的計算可上面的推導表明，互相關和自相關函數的計算可利用利用FFT實現。實現。 由