DSP-第三章23-24

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

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

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

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

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

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

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

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

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

10、w DFT運(yùn)算也相應(yīng)分為兩組：運(yùn)算也相應(yīng)分為兩組：/2 1/2 12(21)00(2 )(21)NNrkrkNNrrxr wxrw /2 1/2 12200(2 )(21)NNrkkrkNNNrrxr wwxrw 因?yàn)橐驗(yàn)?故故 其中其中 /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應(yīng)用系數(shù)應(yīng)用系數(shù)wkN的周期性和對稱性：的周期性和對稱性：X(k)的后的后N/2個點(diǎn)（個點(diǎn)（ 即即N/

11、2N-1點(diǎn)），表示為點(diǎn)），表示為 ()/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運(yùn)算，最后再合成為運(yùn)算，最后再合成為點(diǎn)的點(diǎn)的DFT。 一個一個N點(diǎn)的點(diǎn)的DFT被分解為兩個被分解為兩個N/2點(diǎn)的點(diǎn)的D

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

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

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

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

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

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

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

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

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

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

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

23、況下的另外一種普遍使用的FFT結(jié)構(gòu)是結(jié)構(gòu)是頻率抽取法。對于頻率抽取法，輸入序列不是按偶數(shù)奇頻率抽取法。對于頻率抽取法，輸入序列不是按偶數(shù)奇數(shù)，而是按前后對半分開，這樣便將數(shù)，而是按前后對半分開，這樣便將N點(diǎn)點(diǎn)DFT寫成前后寫成前后兩部分：兩部分： /( )( )( )2 1102NNnknkNNnn NX kx n Wx n W/()( )()2 12 12002NNNnknkNNnnNx n Wx nW/(/ ) ( )(/ )2 1202NNknkNNnx nWx nNW又又把把X(k)進(jìn)一步分解為偶數(shù)組和奇數(shù)組：進(jìn)一步分解為偶數(shù)組和奇數(shù)組： X(2r+1)= 奇數(shù)為偶數(shù)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點(diǎn)的序列，將其代入上兩式，得點(diǎn)的序列，將其代入上兩式，得 這正是兩個這正是兩個N/2點(diǎn)的點(diǎn)的DFT運(yùn)算，即將一個運(yùn)算，即將一

25、個N點(diǎn)的點(diǎn)的DFT分解分解為兩個為兩個N/2點(diǎn)的點(diǎn)的DFT，上式的運(yùn)算關(guān)系可用下圖表示，上式的運(yùn)算關(guān)系可用下圖表示. /()( )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點(diǎn)點(diǎn)DFTa(0)a(1)a(2)a(3)N/2點(diǎn)點(diǎn)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點(diǎn)點(diǎn)DFT分解成兩個分解成兩個4點(diǎn)點(diǎn)DFT按頻率抽取將按頻率抽取將8點(diǎn)點(diǎn)DFT分解成四個分解成四個2點(diǎn)點(diǎn)DFT 與時間抽取法一樣，由于與時間抽取法一樣，由于N=2M，N/2仍是一個偶仍是一個偶數(shù)數(shù),這樣，一個這樣，一個N=2M點(diǎn)的點(diǎn)的DFT通過通過M次分解后，最次分解后，最后只剩下全部是后只剩下全部是2點(diǎn)的點(diǎn)的DFT，2點(diǎn)點(diǎn)DFT實(shí)際上只有加實(shí)際上只有加減運(yùn)算。但為了比較，也為了統(tǒng)一運(yùn)算的結(jié)構(gòu)，仍減運(yùn)算。但為了比較，也為了統(tǒng)一運(yùn)算的結(jié)構(gòu)，仍用一個系數(shù)為用一個系數(shù)為W0N 的蝶形運(yùn)算來表示。的蝶形運(yùn)算來表示。 頻率抽取法的流圖是時域抽取法流圖的左右翻轉(zhuǎn)頻率抽取法的流圖是時域

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

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

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

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

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

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

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

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

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

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

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

38、)分離出來。這將使運(yùn)算效率提高一倍。分離出來。這將使運(yùn)算效率提高一倍。 (2)用一個用一個N點(diǎn)的點(diǎn)的FFT運(yùn)算獲得一個運(yùn)算獲得一個2N點(diǎn)實(shí)序列的點(diǎn)實(shí)序列的DFT 設(shè)設(shè)x(n)是是2N點(diǎn)的實(shí)序列點(diǎn)的實(shí)序列,現(xiàn)人為地將現(xiàn)人為地將x(n)分為偶數(shù)分為偶數(shù)組組x1(n)和奇數(shù)組和奇數(shù)組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)組成一個復(fù)序列：組成一個復(fù)序列： y(n)=x1(n)+jx2(n)通過通過N點(diǎn)點(diǎn)FFT運(yùn)算可得到：運(yùn)算可得到： Y(k)=X1(k)+jX2(k) ，N點(diǎn)點(diǎn)根據(jù)前面的討論，得到根據(jù)

39、前面的討論，得到 *1*21( )( )()2( )( )()2XkY kYNkjXkY kYNk 為求為求 2N 點(diǎn)點(diǎn) x(n)所對應(yīng)所對應(yīng) X(k)，需求出，需求出 X(k)與與 X1(k)、X2(k)的關(guān)系的關(guān)系 ： 而而 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、)組成復(fù)序列，經(jīng)組成復(fù)序列，經(jīng)FFT運(yùn)算求得運(yùn)算求得 Y(k)，2)利用共軛對稱性求出利用共軛對稱性求出 X1(k)、X2(k)，3)最后利用上式求出最后利用上式求出 X(k), 達(dá)到用一個達(dá)到用一個N點(diǎn)的點(diǎn)的FFT計(jì)算計(jì)算一個一個2N點(diǎn)的實(shí)序列的點(diǎn)的實(shí)序列的DFT的目的。的目的。 X(k)=X1(k)+W2Nk X2(k) 3) 線性卷積的線性卷積的FFT算法算法 線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一,許多重要許多重要應(yīng)用都建立在這一理論基礎(chǔ)上應(yīng)用都建立在這一理論基礎(chǔ)上,如卷積濾波等。如卷積濾波等。 以前曾討論了用圓周卷積計(jì)算線性卷積方法歸納如下以前曾

41、討論了用圓周卷積計(jì)算線性卷積方法歸納如下： 將長為將長為N2的序列的序列x(n)延長到延長到L,補(bǔ)補(bǔ)L-N2個零，個零， 將長為將長為N1的序列的序列h(n)延長到延長到L,補(bǔ)補(bǔ)L-N1個零，個零， 如果如果LN1+N2-1,則圓周卷積與線性卷積相等則圓周卷積與線性卷積相等,此時此時,可可用用FFT計(jì)算線性卷積，方法如下計(jì)算線性卷積，方法如下: a. 計(jì)算計(jì)算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 可見可見, 只要進(jìn)行二次只要進(jìn)行二次FFT, 一次一次IFFT就可完成線就可完

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

43、，或者處理一個連續(xù)不斷的信號，按上述方法按上述方法, h(n) 要補(bǔ)許多零再進(jìn)行計(jì)算要補(bǔ)許多零再進(jìn)行計(jì)算,計(jì)算量有很計(jì)算量有很大的浪費(fèi)，或者根本不能實(shí)現(xiàn)。大的浪費(fèi)，或者根本不能實(shí)現(xiàn)。 為了保持快速卷積法的優(yōu)越性為了保持快速卷積法的優(yōu)越性,可將可將 x(n) 分為許多分為許多段段,每段的長度與每段的長度與 h(n) 接近接近 , 處理方法有兩種：處理方法有兩種：(1) 重疊相加法重疊相加法由分段卷積的各段相由分段卷積的各段相加構(gòu)成總的卷積輸出加構(gòu)成總的卷積輸出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)補(bǔ)零，補(bǔ)到具有補(bǔ)零，補(bǔ)到具有N點(diǎn)長度，點(diǎn)長度，N=N1+N2-1。一般選。一般選 N=2M。 2)用基用基2FFT計(jì)算計(jì)算 yi(n)=xi(n)*h(n)。 3)重疊部分相加構(gòu)成最后的輸出序列。重疊部分相加構(gòu)成最后的輸出序列。 由于由于yi(n)的長度為的長度為N，而，而xi(n)的長度為的長度為N2，因此相，

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

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

47、延差等。 兩個長為兩個長為N的實(shí)離散時間序列的實(shí)離散時間序列 x(n)與與y(n)的互相的互相關(guān)函數(shù)定義為關(guān)函數(shù)定義為 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)互相關(guān)函數(shù)定義為互相關(guān)函數(shù)定義為 x(n)及及y(n)的卷積公式的卷積公式 相比較，我們可以得到相關(guān)和卷積的時域關(guān)系：相比較，我們可以得到相關(guān)和卷積的時域關(guā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 當(dāng)當(dāng)x(n)=y(n)時，得到時，得到x(n)的自相關(guān)函數(shù)為：的自相關(guān)函數(shù)為： 維納維納辛欽定理：辛欽定理： 自相關(guān)函數(shù)與信號功率譜互為傅立葉變換對。自相關(guān)函數(shù)與信號功率譜互為傅立葉變換對。 10( )( ) ()Nxxnrx n x n 21201|() |NjkNkX keN 上面的推導(dǎo)表明，互相關(guān)和自相關(guān)函數(shù)的計(jì)算可上面的推導(dǎo)表明，互相關(guān)和自相關(guān)函數(shù)的計(jì)算可利用利用FFT實(shí)現(xiàn)。實(shí)現(xiàn)。 由