DSP-第三章23-24

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

2、大多采用模擬信號(hào)濾波的方法解決，直到到1965年首次提出年首次提出DFT運(yùn)算的一種快速算法以后，情運(yùn)算的一種快速算法以后，情況才發(fā)生了根本變化，人們開(kāi)始認(rèn)識(shí)到?jīng)r才發(fā)生了根本變化，人們開(kāi)始認(rèn)識(shí)到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)算大大簡(jiǎn)化，運(yùn)算時(shí)間的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)間縮短縮短12個(gè)數(shù)量級(jí)，使個(gè)數(shù)量級(jí)，使DFT的運(yùn)算在實(shí)際中得到廣的運(yùn)算在實(shí)際中得到廣泛應(yīng)用。泛應(yīng)用。一、提出問(wèn)題：設(shè)有限長(zhǎng)序列一、提出問(wèn)題：設(shè)有

3、限長(zhǎng)序列x(n),非零值長(zhǎng)度為非零值長(zhǎng)度為N, 對(duì)對(duì)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ì)算一個(gè)計(jì)算一個(gè)X(k)(一個(gè)頻率成分一個(gè)頻率成分)值，運(yùn)算量為值，運(yùn)算量為 例如，例如，k=1，則則 要進(jìn)行要進(jìn)行N次復(fù)數(shù)乘法次復(fù)數(shù)乘法和和(N-1)次復(fù)數(shù)加法次復(fù)數(shù)加法；n要完成整個(gè)要完成整個(gè)DFT運(yùn)算，運(yùn)算，需要計(jì)算需要計(jì)算N個(gè)個(gè)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)算時(shí)間在這些運(yùn)算中，乘法比加法復(fù)雜，需要的運(yùn)算時(shí)間多，尤其是復(fù)數(shù)相乘，每個(gè)復(fù)數(shù)相乘包括多，尤其是復(fù)數(shù)相乘，每個(gè)復(fù)數(shù)相乘包括4個(gè)實(shí)數(shù)個(gè)實(shí)數(shù)相乘和相乘和2個(gè)實(shí)數(shù)相加，例個(gè)實(shí)數(shù)相加，例 10( )( )( )( )( )NnknkeeNmmNnnknkemNmeNX kRx nRwIx nIwj Rx nIwIx nRw 又每個(gè)復(fù)數(shù)相加包括又每個(gè)復(fù)數(shù)相加包括2個(gè)實(shí)數(shù)相加，所以，每計(jì)算一個(gè)實(shí)數(shù)相加，所以，每計(jì)算一個(gè)個(gè)X(k)要進(jìn)行要進(jìn)行4N次實(shí)數(shù)相乘和次實(shí)數(shù)相乘和2N+2(N-1)=2(2N-1)次次實(shí)數(shù)相加。因此，整個(gè)實(shí)數(shù)相加。因此，整個(gè)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較大時(shí)，較大時(shí)，運(yùn)算量十分可觀。運(yùn)算量十分可觀。 反變換反變換IDFT與與DFT的運(yùn)算結(jié)構(gòu)相同，只是多乘一的運(yùn)算結(jié)構(gòu)相同，只是多乘一個(gè)常數(shù)個(gè)常數(shù)1/N，所以二者的計(jì)算量相同。，所以二者的計(jì)算量相同。例例1:當(dāng)當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算點(diǎn)時(shí)，直接計(jì)算DFT需要：需要： N2=220=1048576次，即一百多萬(wàn)次的復(fù)乘運(yùn)算次，即一百多萬(wàn)次的復(fù)乘運(yùn)算 例例2:石油勘探，石油勘探，

6、24道記錄，每道波形記錄長(zhǎng)度道記錄，每道波形記錄長(zhǎng)度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萬(wàn)點(diǎn)萬(wàn)點(diǎn) DFT運(yùn)算需要運(yùn)算需要N2=(60000)2=36*108次次 如此之大的運(yùn)算量，對(duì)計(jì)算機(jī)的處理能力和處理速度如此之大的運(yùn)算量，對(duì)計(jì)算機(jī)的處理能力和處理速度都提出很高的要求；尤其在實(shí)時(shí)性很強(qiáng)的信號(hào)處理都提出很高的要求；尤其在實(shí)時(shí)性很強(qiáng)的信號(hào)處理(如雷如雷達(dá)信號(hào)處理達(dá)信號(hào)處理)中，對(duì)計(jì)算速度的要求十分苛刻；中，對(duì)計(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)對(duì)稱(chēng)性對(duì)稱(chēng)性 ()2NkkNNWW 4)221NNNNWW 5)22nnNNWW ReImj8N0NW7NW6NW5NW4NW3NW2NW1NW2、FFT的思路的思路利用對(duì)稱(chēng)性和周期性將長(zhǎng)序利用對(duì)稱(chēng)性和周期性將長(zhǎng)序列列DFT分解為短序列分解為短序列DFTn因?yàn)橐驗(yàn)镈FT的運(yùn)算量與的運(yùn)算量與N2成正比的成正比的n

8、如果一個(gè)大點(diǎn)數(shù)如果一個(gè)大點(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)的變換。三、常見(jiàn)的三、常見(jiàn)的FFT算法算法n按抽取方法分：按抽取方法分： 時(shí)間抽取法時(shí)

9、間抽取法(DIT); 頻率抽取法頻率抽取法(DIF);n按按“基數(shù)基數(shù)”分：分： 基基-2FFT算法；算法； 基基-4FFT算法；算法； 混合基混合基FFT算法；算法；3.3.1 按時(shí)間抽取的按時(shí)間抽取的FFT1、先從、先從一一特殊情況開(kāi)始，假定特殊情況開(kāi)始，假定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的周期性和對(duì)稱(chēng)性：的周期性和對(duì)稱(chēng)性：X(k)的后的后N/2個(gè)點(diǎn)（個(gè)點(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依此類(lèi)推，依此類(lèi)推，G(k)和和H(k)可以繼續(xù)分下去，這種可以繼續(xù)分下去，這種按時(shí)間抽取算法是在輸入序列分成越來(lái)越小的按時(shí)間抽取算法是在輸入序列分成越來(lái)越小的子序列上執(zhí)行子序列上執(zhí)行DFT運(yùn)算，最后再合成為運(yùn)算，最后再合成為點(diǎn)的點(diǎn)的DFT。 一個(gè)一個(gè)N點(diǎn)的點(diǎn)的DFT被分解為兩個(gè)被分解為兩個(gè)N/2點(diǎn)的點(diǎn)的D

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

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

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

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

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

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

18、序存入存儲(chǔ)單元中，而是按x(0)，x(4)，x(2)，x(6)，x(7)的順序存入存儲(chǔ)單元，這種順序看起來(lái)的順序存入存儲(chǔ)單元，這種順序看起來(lái)相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進(jìn)制表示這個(gè)相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進(jìn)制表示這個(gè)順序時(shí)，它正好是順序時(shí)，它正好是“碼位倒置碼位倒置”的順序。例如，原來(lái)的的順序。例如，原來(lái)的自然順序應(yīng)是自然順序應(yīng)是x(1)的地方，現(xiàn)在放著的地方，現(xiàn)在放著x(4)，用二進(jìn)制碼表，用二進(jìn)制碼表示這一規(guī)律時(shí)，則是在示這一規(guī)律時(shí)，則是在 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)按碼位倒置的順按碼位倒置的順序排好輸入很不方便，總是先按自然順序輸入存儲(chǔ)單元，然序排好輸入很不方便，總是先按自然順序輸入存儲(chǔ)單元，然后再通過(guò)變址運(yùn)算將自然順序的存儲(chǔ)轉(zhuǎn)換成碼位倒置順序的后再通過(guò)變址運(yùn)算將自然順序的存儲(chǔ)轉(zhuǎn)換成碼位倒置順序的存儲(chǔ)，然后進(jìn)行存儲(chǔ)，然后進(jìn)行FFT的原位計(jì)算。目前有許多通用的原位計(jì)算。目前有許多通用DSP芯片芯片支持這種碼位倒置的

20、尋址功能。支持這種碼位倒置的尋址功能。n第一次分偶、奇，根據(jù)最低位第一次分偶、奇，根據(jù)最低位n0的的0、1狀態(tài)來(lái)分，狀態(tài)來(lái)分，若若n0=0，則為偶序列；，則為偶序列；n0=1則為奇序列，得到兩組則為奇序列，得到兩組序列：序列： 000 010 100 110 001 011 101 111n第二次對(duì)這兩個(gè)偶、奇序列再分一次偶、奇序列，這第二次對(duì)這兩個(gè)偶、奇序列再分一次偶、奇序列，這就要根據(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)來(lái)分偶、奇序列，直到的、狀態(tài)來(lái)分偶、奇序列，直到不能再分偶、奇時(shí)為止。對(duì)于不能再分偶、奇時(shí)為止。對(duì)于N=8, n2已是最高位，已是最高位，最后一次分得結(jié)果為最后一次分得結(jié)果為 000 100 010 110 001 101 011 111(4)蝶形類(lèi)型隨迭代次數(shù)成倍增加蝶形類(lèi)型隨迭代次數(shù)成倍增加 觀察觀察8點(diǎn)點(diǎn)FFT的三次迭代運(yùn)算的三次迭代運(yùn)算: 第一級(jí)迭代，有一種類(lèi)型的蝶形運(yùn)算系數(shù)第一級(jí)迭代，有一種類(lèi)型的蝶形運(yùn)算系數(shù)W08，兩個(gè)數(shù)據(jù)點(diǎn)間隔為兩個(gè)數(shù)據(jù)點(diǎn)間隔為1； 第二級(jí)迭代，有二種類(lèi)型的蝶形運(yùn)算系數(shù)第二級(jí)迭代，有二種類(lèi)型的蝶形運(yùn)算系數(shù)W08、W28 ，參加運(yùn)算的兩個(gè)數(shù)

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

23、況下的另外一種普遍使用的FFT結(jié)構(gòu)是結(jié)構(gòu)是頻率抽取法。對(duì)于頻率抽取法，輸入序列不是按偶數(shù)奇頻率抽取法。對(duì)于頻率抽取法，輸入序列不是按偶數(shù)奇數(shù)，而是按前后對(duì)半分開(kāi)，這樣便將數(shù)，而是按前后對(duì)半分開(kāi)，這樣便將N點(diǎn)點(diǎn)DFT寫(xiě)成前后寫(xiě)成前后兩部分：兩部分： /( )( )( )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這兩個(gè)序列都是這兩個(gè)序列都是N/2點(diǎn)的序列，將其代入上兩式，得點(diǎn)的序列，將其代入上兩式，得 這正是兩個(gè)這正是兩個(gè)N/2點(diǎn)的點(diǎn)的DFT運(yùn)算，即將一個(gè)運(yùn)算，即將一

25、個(gè)N點(diǎn)的點(diǎn)的DFT分解分解為兩個(gè)為兩個(gè)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分解成兩個(gè)分解成兩個(gè)4點(diǎn)點(diǎn)DFT按頻率抽取將按頻率抽取將8點(diǎn)點(diǎn)DFT分解成四個(gè)分解成四個(gè)2點(diǎn)點(diǎn)DFT 與時(shí)間抽取法一樣，由于與時(shí)間抽取法一樣，由于N=2M，N/2仍是一個(gè)偶仍是一個(gè)偶數(shù)數(shù),這樣，一個(gè)這樣，一個(gè)N=2M點(diǎn)的點(diǎn)的DFT通過(guò)通過(guò)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)，仍用一個(gè)系數(shù)為用一個(gè)系數(shù)為W0N 的蝶形運(yùn)算來(lái)表示。的蝶形運(yùn)算來(lái)表示。 頻率抽取法的流圖是時(shí)域抽取法流圖的左右翻轉(zhuǎn)頻率抽取法的流圖是時(shí)域

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)算 對(duì)于任何一個(gè)對(duì)于任何一個(gè)2的整數(shù)冪的整數(shù)冪N=2M，總是可以通過(guò)，總是可以通過(guò)M次分解最后完全成為次分解最后完全成為2點(diǎn)的點(diǎn)的DFT運(yùn)算。這樣的運(yùn)算。這樣的M次分次分解，就構(gòu)成從解，就構(gòu)成從x(n)到到X(k)的的M級(jí)運(yùn)算過(guò)程。將頻率級(jí)運(yùn)算過(guò)程。將頻率抽取法的流圖反轉(zhuǎn)，并將輸入變輸出，輸出變輸入抽取法的流圖反轉(zhuǎn)，并將輸入變輸出，輸出變輸入，得到的便是時(shí)間抽取法流圖，得到的便是時(shí)間抽取法

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

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

30、有一種形只有一種W0N，數(shù)據(jù)間隔為，數(shù)據(jù)間隔為1。由這幾點(diǎn)規(guī)律可以看出，頻率抽取法與時(shí)間抽到法是兩由這幾點(diǎn)規(guī)律可以看出，頻率抽取法與時(shí)間抽到法是兩種等價(jià)的種等價(jià)的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)：程序簡(jiǎn)單，效率高，使用方便。優(yōu)點(diǎn)：程序簡(jiǎn)單，效率高，使用方便。 實(shí)際應(yīng)用時(shí)，有限長(zhǎng)序列的長(zhǎng)度實(shí)際應(yīng)用時(shí)，有限長(zhǎng)序列的長(zhǎng)度N很大程度上由人很大程度上由人為因素確定，因此多數(shù)場(chǎng)合可取為因素確定，因此多數(shù)

31、場(chǎng)合可取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ù)，可分解為兩個(gè)整數(shù)為復(fù)合數(shù)，可分解為兩個(gè)整數(shù)p與與q的乘積的乘積,像前像前面以面以2為基數(shù)時(shí)一樣為基數(shù)時(shí)一樣,FFT的基本思想是將的基本思想是將DFT的運(yùn)算的運(yùn)算盡量分小盡量分小,因此因此,在在N=pq情況下情況下,也希望將也希望將N點(diǎn)的點(diǎn)的DFT分分解為解為p個(gè)個(gè)q點(diǎn)點(diǎn)DFT或或q個(gè)個(gè)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(chóng)(30)=x(31)=0兩點(diǎn)兩點(diǎn),使使N=32=25,這樣可這樣可直接采用以直接采用以2為基數(shù)為基數(shù)M=5的的FFT程序。程序。 3.4 FFT應(yīng)用中的幾個(gè)問(wèn)題應(yīng)用中的幾個(gè)問(wèn)題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)算簡(jiǎn)簡(jiǎn)稱(chēng)為稱(chēng)為IFFT。 比較比較IDFT的定義式：的定義式： IDFT： DFT：IDFT與與DFT的差別的差別 1)把把DFT中的每一個(gè)系數(shù)中的每一個(gè)系數(shù) 改為改為 ， 2)再乘以常數(shù)再乘以常數(shù) 1/N ， 則以上所討論的時(shí)間抽取或頻率抽取的則以上所討論的時(shí)間抽取或頻率抽取的FFT運(yùn)算均可直接用于運(yùn)算均可直接用于IDFT運(yùn)算，當(dāng)然，蝶形中運(yùn)算，當(dāng)然，蝶形中的系數(shù)的系數(shù) 應(yīng)改為應(yīng)改為 。nkNWnkNW nkNW nkNW b)第二種方法，完全不需要改動(dòng)第二種方法，完全不需要改動(dòng)FFT程序，而是直接利程序，而是直接利 用它作用它作 IFFT。 考慮到考慮到 故故 IFFT

34、計(jì)算分三步：計(jì)算分三步： 將將X(k)取共軛取共軛(虛部乘以虛部乘以-1) 對(duì)對(duì) 直接作直接作FFT 對(duì)對(duì)FFT的結(jié)果取共軛并乘以的結(jié)果取共軛并乘以1/N，得，得x(n)。101( )( )NnkNkxnXk WN 1011( )( )( )NnkNkx nXk WDFT XkNN ( )Xk 3.4 FFT應(yīng)用中的幾個(gè)問(wèn)題應(yīng)用中的幾個(gè)問(wèn)題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ù)場(chǎng)合但大多數(shù)場(chǎng)合,信號(hào)是實(shí)數(shù)序列信號(hào)是實(shí)數(shù)序列,任何實(shí)數(shù)都任何實(shí)數(shù)都可看成虛部為零的復(fù)數(shù)可看成虛部為零的復(fù)數(shù),

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

36、)用用 一個(gè)一個(gè)N點(diǎn)點(diǎn)FFT同時(shí)計(jì)算兩個(gè)同時(shí)計(jì)算兩個(gè)N點(diǎn)實(shí)序列的點(diǎn)實(shí)序列的DFT 設(shè)設(shè)x (n)、y (n)是彼此獨(dú)立的兩個(gè)是彼此獨(dú)立的兩個(gè)N點(diǎn)實(shí)序列點(diǎn)實(shí)序列,且且 X (k)=DFTx (n)，Y (k)=DFTy(n) 則則X (k)、Y(k)可通過(guò)一次可通過(guò)一次FFT運(yùn)算同時(shí)獲得。運(yùn)算同時(shí)獲得。 首先，將首先，將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 通過(guò)通過(guò)FFT運(yùn)算可獲得運(yùn)算可獲得g(n)的的DFT值值利用離散傅里葉變換的共軛對(duì)稱(chēng)性利用離散傅里葉變換的共軛對(duì)稱(chēng)性通過(guò)通過(guò)g(n)的的FFT運(yùn)算結(jié)果運(yùn)算結(jié)果G(k),由上式可得到由上式可得到X (k) 的值。的值。通過(guò)通過(guò)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，再通過(guò)加、減法運(yùn)算就可以，再通過(guò)加、減法運(yùn)算就可以將將X(k)與與Y(k

38、)分離出來(lái)。這將使運(yùn)算效率提高一倍。分離出來(lái)。這將使運(yùn)算效率提高一倍。 (2)用一個(gè)用一個(gè)N點(diǎn)的點(diǎn)的FFT運(yùn)算獲得一個(gè)運(yùn)算獲得一個(gè)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)組成一個(gè)復(fù)序列：組成一個(gè)復(fù)序列： y(n)=x1(n)+jx2(n)通過(guò)通過(guò)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)所對(duì)應(yīng)所對(duì)應(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)利用共軛對(duì)稱(chēng)性求出利用共軛對(duì)稱(chēng)性求出 X1(k)、X2(k)，3)最后利用上式求出最后利用上式求出 X(k), 達(dá)到用一個(gè)達(dá)到用一個(gè)N點(diǎn)的點(diǎn)的FFT計(jì)算計(jì)算一個(gè)一個(gè)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ì)算線性卷積方法歸納如下： 將長(zhǎng)為將長(zhǎng)為N2的序列的序列x(n)延長(zhǎng)到延長(zhǎng)到L,補(bǔ)補(bǔ)L-N2個(gè)零，個(gè)零， 將長(zhǎng)為將長(zhǎng)為N1的序列的序列h(n)延長(zhǎng)到延長(zhǎng)到L,補(bǔ)補(bǔ)L-N1個(gè)零，個(gè)零， 如果如果LN1+N2-1,則圓周卷積與線性卷積相等則圓周卷積與線性卷積相等,此時(shí)此時(shí),可可用用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 可見(jiàn)可見(jiàn), 只要進(jìn)行二次只要進(jìn)行二次FFT, 一次一次IFFT就可完成線就可完

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

43、，或者處理一個(gè)連續(xù)不斷的信號(hào)，按上述方法按上述方法, 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) 分為許多分為許多段段,每段的長(zhǎng)度與每段的長(zhǎng)度與 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)先對(duì)先對(duì)h(n)及及xi(n)補(bǔ)零，補(bǔ)到具有補(bǔ)零，補(bǔ)到具有N點(diǎn)長(zhǎng)度，點(diǎn)長(zhǎng)度，N=N1+N2-1。一般選。一般選 N=2M。 2)用基用基2FFT計(jì)算計(jì)算 yi(n)=xi(n)*h(n)。 3)重疊部分相加構(gòu)成最后的輸出序列。重疊部分相加構(gòu)成最后的輸出序列。 由于由于yi(n)的長(zhǎng)度為的長(zhǎng)度為N，而，而xi(n)的長(zhǎng)度為的長(zhǎng)度為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ǔ)零，而是保留原來(lái)的輸入序列列中補(bǔ)零的部分不是補(bǔ)零，而是保

46、留原來(lái)的輸入序列值，這時(shí)，如利用值，這時(shí)，如利用DFT實(shí)現(xiàn)實(shí)現(xiàn)h(n)和和xi(n)的循環(huán)卷積，的循環(huán)卷積，則每段卷積結(jié)果中有則每段卷積結(jié)果中有N1-1個(gè)點(diǎn)不等于線性卷積值需舍個(gè)點(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)用于信號(hào)分析與統(tǒng)計(jì)分析，如通過(guò)相關(guān)函數(shù)峰值的檢測(cè)測(cè)號(hào)分析與統(tǒng)計(jì)分析，如通過(guò)相關(guān)函數(shù)峰值的檢測(cè)測(cè)量?jī)蓚€(gè)信號(hào)的時(shí)延差等。量?jī)蓚€(gè)信號(hào)的時(shí)

47、延差等。 兩個(gè)長(zhǎng)為兩個(gè)長(zhǎng)為N的實(shí)離散時(shí)間序列的實(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)和卷積的時(shí)域關(guān)系：相比較，我們可以得到相關(guān)和卷積的時(shí)域關(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)時(shí)，得到時(shí)，得到x(n)的自相關(guān)函數(shù)為：的自相關(guān)函數(shù)為： 維納維納辛欽定理：辛欽定理： 自相關(guān)函數(shù)與信號(hào)功率譜互為傅立葉變換對(duì)。自相關(guān)函數(shù)與信號(hào)功率譜互為傅立葉變換對(duì)。 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)。 由