1、第九章 離散傅立葉變換及其他離散正交變換 在離散時(shí)間信號(hào)與系統(tǒng)研究的歷史中，有一個(gè)終于的問題：“如何把數(shù)字計(jì)算機(jī)的應(yīng)用和信號(hào)分析與處理緊密地結(jié)合起來”。離散傅里葉變換（DFT）就是在解決這個(gè)矛盾中形成的一種概念和計(jì)算方法。 本章最后還介紹了傅里葉變換以外的其他離散正交變換，包括離散沃爾什變換和離散余弦變換。9.1引言引言9.2傅立葉變換的離散性和周期性傅立葉變換的離散性和周期性對(duì)稱關(guān)系對(duì)稱關(guān)系時(shí)域周期性時(shí)域周期性頻域離散性頻域離散性（時(shí)域重復(fù)（時(shí)域重復(fù)頻域抽樣）頻域抽樣）時(shí)域離散性時(shí)域離散性頻域周期性頻域周期性（時(shí)域抽樣（時(shí)域抽樣頻域重復(fù)）頻域重復(fù)）時(shí)域非周期時(shí)域非周期頻域連續(xù)性頻域連續(xù)性 （

2、頻域取包絡(luò)（頻域取包絡(luò) ） 時(shí)域連續(xù)性時(shí)域連續(xù)性頻域非周期頻域非周期（傅立葉變換的對(duì)偶性）（傅立葉變換的對(duì)偶性）nnFTF101)(4四種物理存在信號(hào)的傅立葉變換四種物理存在信號(hào)的傅立葉變換（1）連續(xù)周期信號(hào)）連續(xù)周期信號(hào)（2）連續(xù)非周期信號(hào)）連續(xù)非周期信號(hào)（3）離散非周期序列）離散非周期序列（4）離散周期序列）離散周期序列（1）連續(xù)周期信號(hào)的傅立葉變換 從從FS到到FT 從單脈沖的周期重復(fù)從單脈沖的周期重復(fù))(2)(1nFtfFTnn221111).(1TTtjnndtetfTF例1：周期矩形脈沖的FS和FT01T1TE)(tf1TE1E)(FnFtFSFT周期重復(fù))(2111nnSaEn)

3、(2)(1nFtfFTnn2).(111221111nSaTEdtetfTFTTtjnndtetfFtj)()(（2）連續(xù)非周期信號(hào)的傅立葉變換E)(0tf022tE)(0F220nFFT例2：2)(SaEF從傅立葉積分得到從傅立葉積分得到從周期信號(hào)取單脈沖得到從周期信號(hào)取單脈沖得到例例2：從周期信號(hào)取單脈沖得到：從周期信號(hào)取單脈沖得到1T1TE)(tftnFE)(0tf022t110)(nnTFF220FT2).(111221111nSaTEdtetfTFTTtjnn2)(SaEFnnjjenxeX)()(（3）離散非周期序列的傅立葉變換 從從Z變換的變量置換得到變換的變量置換得到 從非周期

4、信號(hào)的抽樣得到從非周期信號(hào)的抽樣得到 從離散周期信號(hào)取單周期得到從離散周期信號(hào)取單周期得到例3：從非周期信號(hào)抽樣得到離散非周期序列)(tf0t)(F01)(tP) 1 (0t0)(tfs相乘相卷)(sssss00tsT)(sFsT1FTFTFT頻域周期重復(fù))()(nsTnTttnssnp)()(時(shí)域抽樣)(1snsnFT2022-4-30例例4：從離散周期信號(hào)取單周期得到：從離散周期信號(hào)取單周期得到t0221T1T)(nfp022)(0nfsTE222sT2sT2t)(22snsnSaTE（4 4）離散周期序列的傅立葉變換）離散周期序列的傅立葉變換 從連續(xù)周期信號(hào)的抽樣得到從連續(xù)周期信號(hào)的抽樣

5、得到 從離散周期序列的從離散周期序列的DFS得到得到 從離散非周期信號(hào)的周期重復(fù)得到從離散非周期信號(hào)的周期重復(fù)得到10)()()(NkpLNkkXnTxFT從連續(xù)周期信號(hào)的抽樣得到從連續(xù)周期信號(hào)的抽樣得到1T1TE)(tft1E)(FFTsTE122sT2sT2t)(2111nnSaTEns例例4：離散周期矩形序列的傅立葉變換：離散周期矩形序列的傅立葉變換t0221T1T)(nfpE)(pFsTTE1222sT2sT2t220t后重復(fù))(1tf先抽樣022)(0nf離散非周期信號(hào)的周期重復(fù)離散非周期信號(hào)的周期重復(fù)9.3 從離散傅立葉級(jí)數(shù)從離散傅立葉級(jí)數(shù)(DFS)到離散到離散傅立葉變換傅立葉變換

6、(DFT) 效仿連續(xù)周期信號(hào)有傅立葉級(jí)數(shù)，記作：效仿連續(xù)周期信號(hào)有傅立葉級(jí)數(shù)，記作： 離散周期序列也有傅立葉級(jí)數(shù)，記作：離散周期序列也有傅立葉級(jí)數(shù)，記作：dtetxTFeFtxTTtjnpnntjnnp2211)(1)()(1)(1)(1010222kXNenxNaeaeanxpNnknjpkknjNkkknjkkpNNN周期性以N為周期1.2 , 1 , 0)(1)(1.2 , 1 , 0)()(221010NkekXNnxNnenxkXknjNkppNnknjppNN離散周期序列的傅立葉級(jí)數(shù)離散周期序列的傅立葉級(jí)數(shù)(DFS)的正負(fù)的正負(fù)運(yùn)算對(duì)運(yùn)算對(duì)周期序列的基頻是周期序列的基頻是 是是 K

7、次諧波分量，諧波系數(shù)是次諧波分量，諧波系數(shù)是 諧波成分中只有諧波成分中只有N個(gè)是獨(dú)立的個(gè)是獨(dú)立的 ， 是周期的是周期的njNe)(2)(kXp)()()(22NknjnkjNNeenkjNe)(2)(kXp)(nxpnN0N2N)(kXp0NN2kN有限長序列是周期序列的一個(gè)周期有限長序列是周期序列的一個(gè)周期 有限長序列 x(n)只有的N個(gè)值x(n)可看成是周期序列的主值序列，記作 周期序列 當(dāng) 叫做 的主值周期，記作 有限長序列的以N 為周期的周期延拓)(0) 10()()(otherNnnxnx)(0) 10()()(otherNnnxnxp1.2 , 1 , 0Nn1.2 , 1 , 0

8、Nn)(nxpNpnxnx)()()()()(nGnxnxNp)()()(nGnxnxNp的主值序列的主值序列 也是周期性的，相當(dāng)于有限長也是周期性的，相當(dāng)于有限長序列周期延拓序列周期延拓 當(dāng)當(dāng) 時(shí)，其主值序列時(shí)，其主值序列相當(dāng)于一個(gè)有限長序列相當(dāng)于一個(gè)有限長序列)(kXp10Nk)(kXpNpkXkX)()()()()(kGkXkXNp 和和 都取主值周期，得到離都取主值周期，得到離散傅立葉變換散傅立葉變換(DFT)對(duì)對(duì)1.2 , 1 , 0)(1)(1)(1.2 , 1 , 0)()()(10101010222NkWkXNekXNnxeWhereNnWnxenxkXnkNknkjNkjNn

9、nkNnknjNNN)(kX)(nxNjNeW2NjNeW22210)()(NnnkNNWnxnxDFT120120222)()()(NnnNNnnkNNkWnxWnxnxDFT周期為周期為N和周期為和周期為2N的不同的不同 當(dāng)主值周期為0N-1時(shí)， 點(diǎn)的DFT為 當(dāng)主值周期為02N-1時(shí)， 2N DFT（接下頁） 212101012)(2102120222) 1(1 )()()()()()()(22kNkkNNNnnNNnnNNNnNnkNNnnkNNnnkNNNXWWnxWnxWNnxWnxWnxnxDFTkXkk小結(jié)小結(jié) 是是 的主值序列的主值序列 是嚴(yán)格按傅立葉分析的概念得來的是嚴(yán)格按

10、傅立葉分析的概念得來的 只是一種借用形式，一種算法只是一種借用形式，一種算法 用用 計(jì)算信號(hào)的頻譜時(shí)，計(jì)算信號(hào)的頻譜時(shí)， 采樣頻率必須大于兩倍的信號(hào)最高截止頻率采樣頻率必須大于兩倍的信號(hào)最高截止頻率 對(duì)周期信號(hào)要取一個(gè)整周期對(duì)周期信號(hào)要取一個(gè)整周期DFTDFSDFSDFTDFT)(nxpnN0N2N)(kXp02NN2NkN0N0nk)(nx)(kXDFSDFT25 FS FT DFS FT)(2)(1nFtfFTnn102)(1)(1NnknjppkNenxNkXNa221111).(1TTtjnndtetfTF)()()()(12)(2)(10LNkkXnkXNTnaTtfFTNnnpsn

11、ksntjnnpeFtx1)(knjNkkpNeanx210)(所以知道DFT=X(k)就可以求得離散周期信號(hào)的FT,也就可以找到其他三種的FT例#：已知N 的x(n)序列的 DFT如圖所示，求下圖x1，x2，x3, , x4的FTN0N0nk)(nx)(kX)(1nxxpn0N)(2txxpTNTs02NN)(kX02N)(2kXNkkN22N2N1TNTs02N2Nk)(12)(kXNkXTs)(30txx N0n)(nx02N2NkN)(kXsT1. . 線性線性若若 f1(k) F1(n) f2(k) F2(n)則則 a1f1(k)+a2 f2(k) a1F1(n)+a2F2(n).

12、. 對(duì)稱性對(duì)稱性若若 f(k) F(n)則則 F(k) N f(n)f(n)應(yīng)是應(yīng)是f(n)周期拓展之后反轉(zhuǎn)周期拓展之后反轉(zhuǎn)稱稱圓周反轉(zhuǎn)圓周反轉(zhuǎn)。9.4離散傅立葉變換的性質(zhì)離散傅立葉變換的性質(zhì)3. 時(shí)移特性圓周位移（循環(huán)位移）圓周位移（循環(huán)位移）： 將有限長序列將有限長序列f(k)周期拓展成周期序列周期拓展成周期序列fN(k)，再右移再右移m位，得到時(shí)移序列位，得到時(shí)移序列fN(k m)，最后取其主，最后取其主值而得到的序列稱為值而得到的序列稱為f(k)的的圓周位移圓周位移序列，記為序列，記為 f (k m)NGN(k)時(shí)移特性時(shí)移特性若若 f(k) F(n)則則 f (k m)NGN(k)

13、WmnF(n) DFT時(shí)移特性證明時(shí)移特性證明DFT f (k m)NGN(k)=DFT fN (k m)GN(k) 102je)(NkknNNmkf令令i=k- -m，有，有DFT f (k m)NGN(k)=mnNmNmiinNNif2j12jee)(由于由于fN (k )和和 都是以都是以N為周期的函數(shù)，因此為周期的函數(shù)，因此inN2je)(e)(e)(102j12jnFififNiinNNmNmiinNN故故DFTf (k m)NGN(k)= WmnF(n) 4. 頻移特性（調(diào)制）頻移特性（調(diào)制）若若 f(k) F(n)則則 Wl kf (k) F(n l)NGN(n) 5. 時(shí)域循環(huán)

14、卷積（圓卷積）定理時(shí)域循環(huán)卷積（圓卷積）定理 線卷積：線卷積：有限長序列有限長序列f1(k)和和f2(k)的長度分別為的長度分別為N和和M，則兩，則兩序列的卷積和序列的卷積和f(k)(稱為稱為線卷積線卷積)仍為有限長序列序仍為有限長序列序列，長度為列，長度為N+M 1。 循環(huán)卷積：循環(huán)卷積：有限長序列有限長序列f1(k)和和f2(k)的長度相等，均為的長度相等，均為N，則，則f1(k)與與f2(k)的的循環(huán)卷積循環(huán)卷積定義為定義為1012102121)()()()()()(NmNNmNmkfmfmkfmfkfkf循環(huán)卷積結(jié)果的長度仍為循環(huán)卷積結(jié)果的長度仍為N。若兩序列長度不等，采。若兩序列長度

15、不等，采用用補(bǔ)零法補(bǔ)零法。循環(huán)卷積循環(huán)卷積例例 求圖求圖 (a)和和(b)所示所示f1(k)與與f2(k)的循環(huán)卷積的循環(huán)卷積f(k)。解解 將將f1(k)補(bǔ)一個(gè)零點(diǎn)，補(bǔ)一個(gè)零點(diǎn)，使使f1(k)與與f2(k)的長度均的長度均為為5。 )()()()(540521kGmkfmfkfm)0()()()0(540521Gmfmffmf(0)= f1(0) f2(0) + f1(1) f2(1) + f1(2) f2(2) + f1(3) f2(3) + f1(4) f2(4) =0+4+3+2+0=9) 1 ()1()() 1 (540521Gmfmffmf(1)= f1(0) f2(1) + f1

16、(1) f2(0) + f1(2) f2(1) + f1(3) f2(2) + f1(4) f2(3) =1+0+4+3+0=8借助循環(huán)卷積計(jì)算線卷積循環(huán)卷積便于利用數(shù)字計(jì)算機(jī)進(jìn)行計(jì)算。循環(huán)卷積便于利用數(shù)字計(jì)算機(jī)進(jìn)行計(jì)算。為借助循環(huán)卷積求線卷積，要使循環(huán)卷積的結(jié)果與線為借助循環(huán)卷積求線卷積，要使循環(huán)卷積的結(jié)果與線卷積結(jié)果相同，可以采用補(bǔ)零的方法，使卷積結(jié)果相同，可以采用補(bǔ)零的方法，使 f1(k)與與f2(k)的長度均為的長度均為LN+M1 則循環(huán)卷積與線卷積的結(jié)果相同。則循環(huán)卷積與線卷積的結(jié)果相同。時(shí)域循環(huán)卷積定理時(shí)域循環(huán)卷積定理若若 f1(k) F1(n) f2(k) F2(n)則則 f1(

17、k) * * f2(k) F1(n)F2(n)6. 頻域循環(huán)卷積定理頻域循環(huán)卷積定理若若 f1(k) F1(n) f2(k) F2(n)則則 f1(k) f2(k) F1(n) *F2(n)N17. 巴塞瓦爾定理巴塞瓦爾定理若若 f(k) F(n)則則210210| )(|1| )(|nFNkfNnNk表明，在一個(gè)頻域帶限之內(nèi)，功率譜之和與信號(hào)的能表明，在一個(gè)頻域帶限之內(nèi)，功率譜之和與信號(hào)的能量成比例。量成比例。 若x(n)是一個(gè)有限長序列，長度為N，對(duì)x(n)進(jìn)行Z變換 10)()(NnnznxzX比較Z變換與DFT，我們看到，當(dāng)z=W-kN時(shí) )()()(10nxDFTWnxzXNnnkN

18、WzkN即 kNWzzXkX)()(（1） 9.5 離散傅里葉變換與離散傅里葉變換與z變換的關(guān)系變換的關(guān)系 表明 是Z平面單位圓上幅角為 的點(diǎn)，也即將Z平面單位圓N等分后的第k點(diǎn)，所以X(k)也就是對(duì)X(z)在Z平面單位圓上N點(diǎn)等間隔采樣值，如圖所示。kNjkNeWz2kNWkN2lDFT的運(yùn)算量次）（復(fù)數(shù)加：，次復(fù)數(shù)乘：22101)1, 1 , 0()()()(NNNNNkWnxnxDFTkXNnnkNl減少DFT運(yùn)算量的方法將長度N變短。例如若將長度變?yōu)镹/2，則運(yùn)算量變成：利用 的性質(zhì)周期性：周期性： 共軛對(duì)稱性：共軛對(duì)稱性： 可約性：可約性：次復(fù)數(shù)加：，次復(fù)數(shù)乘：4/4/22NNnkN

19、W)(rNnNnNWW*)(nNnNWWnNrnrNWW9.6快速傅里葉變換（快速傅里葉變換（FFT）DFT的快速算法（FFT）綜述lFFT的算法分類FFT算法首先由Cooly-Tuky提出了基2FFT算法，它對(duì)DFT的發(fā)展起到了極大推進(jìn)作用。隨后又出現(xiàn)了混合基算法。本節(jié)僅對(duì)基2FFT算法作介紹，內(nèi)容包括：FFT的基本思想、時(shí)域與頻域抽取的基2FFT算法及其程序?qū)崿F(xiàn)。l基-2 FFT算法（DIT-FFT）指要求長度N滿足 （M為整數(shù)），若不滿足可將序列補(bǔ)零延長，使其滿足長度要求。MN2l時(shí)域抽取與頻域抽?。喎Q算法（按頻域抽?。喎Q算法（按時(shí)域抽取FFT-DIFFreqency-In-De

20、cimationFFT-DITTime -In- DecimationFFTFFT時(shí)域抽取基2FFT算法（DIT-FFT） 算法的推導(dǎo)時(shí)域抽取算法是按 的奇偶把時(shí)間序列 分解為兩個(gè)長為N/2點(diǎn)的序列，即：)(nxn)2()(1rxrx12/,.,1 ,0Nr) 12()(2rxrx10)()(NnknNWnxkX則12/02212/02112/0)12(12/02)()()12()2(NrkNkrNNrkrNNrrkNNrkrNWWrxWrxWrxWrxkrNkrNjKrNjkrNWeeW2/2/222212/,.,1 , 0)()()()()(2112/02/212/02/1NkkXWkXW

21、rxWWrxkXkNNrkrNkNNrkrN上式中 分別為 的N/2點(diǎn)DFT，即：X kXk12( )( )和x nx n12( )( )和12/02/11)()(NnknNWnxkX12,.,1 ,0Nk12/02/22)()(NnknNWnxkX12,.,1 ,0Nk這是 前N/2點(diǎn)DFT) 12/,.1 , 0)(NkkX時(shí)域抽取基2FFT算法（DIT-FFT）) 1, 2/)(NNkkXkNNkNWW2/)()()2(21kXWkXNkXkN12,.,1 , 0Nk顯然，可采用蝶式運(yùn)算圖來表示上述前N/2和后N/2兩式 ，如下圖所示：時(shí)域抽取基2FFT算法（DIT-FFT）時(shí)域抽取基2

22、FFT算法（DIT-FFT）例如N=8時(shí)的DFT,可以分解為兩個(gè)N/2=4點(diǎn)DFT, 如下圖：時(shí)域抽取基2FFT算法（DIT-FFT）同理： , N/2仍可能是偶數(shù),可以進(jìn)一步把每個(gè)N/2點(diǎn)的序列再按其奇偶部分分解為兩個(gè)N/4的子序列。MN2)12()()2()(1413lxlxlxlx)14/( , 1 ,0Nl14/0)12(2/114/022/11) 12()2()(NllkNNlklNWlxWlxkX14/04/42/14/04/3)()(NlklNkNNlklNWlxWWlx)()(42/3kXWkXkN14/, 1 , 0Nk)()()4(42/31kXWkXNkXkN故時(shí)域抽取基

23、2FFT算法（DIT-FFT）14/04/44414/04/333)()()()()()(NlklNNlklNWlxlxDFTkXWlxlxDFTkX其中對(duì) 也可進(jìn)行同樣的分解：X k2( )()()(62/52kXWkXkXkN)()()4/(62/52kXWkXNkXkN14/, 1 , 0Nk14/04/555)()()(NlklNWlxlxDFTkXklNNlWlxlxDFTkX4/614/066)()()()2()(25lxlx) 14/(,.,1 , 0) 12()(26Nllxlx時(shí)域抽取基2FFT算法（DIT-FFT）依次類推：經(jīng)過M-1次分解后，可將N點(diǎn)DFT分解成N/2個(gè)兩

24、點(diǎn)DFT。這樣又一次的分解得到4個(gè)N/4點(diǎn)DFT，見下圖。典 型 例 題例： 試畫出N=8時(shí)的完整的基-2 DIT-FFT運(yùn)算流圖。 運(yùn)算量時(shí)域抽取基時(shí)域抽取基2FFT算法（算法（DIT-FFT）由有關(guān)算法的討論知：當(dāng) 時(shí)，總共應(yīng)有M級(jí)分解，每級(jí)有N/2個(gè)“蝶式運(yùn)算”。每個(gè)“蝶式運(yùn)算”需一次復(fù)數(shù)乘、兩次復(fù)數(shù)加運(yùn)算，這樣M級(jí)總共需要的運(yùn)算量為：MN2NNMN2log22復(fù)數(shù)乘運(yùn)算次數(shù)NNMN2log復(fù)數(shù)加運(yùn)算次數(shù)如：若N1024，直接計(jì)算DFT與采用FFT運(yùn)算量之比約為205，“快速”得以充分體現(xiàn)。若N足夠大，通過直接計(jì)算DFT與采用FFT計(jì)算其運(yùn)算量之比為：NNNNNNNNNN22322222

25、log2loglog) 1(NNN22log)2/( FFT算法的特點(diǎn)時(shí)域抽取基時(shí)域抽取基2FFT算法（算法（DIT-FFT） 倒碼倒碼即碼位倒置：是指將原二進(jìn)制數(shù)的碼位倒過來 按從低位到高位排列。 順序順序 二進(jìn)制數(shù)二進(jìn)制數(shù) 倒碼倒碼 倒碼順序倒碼順序 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 000 100 010 110 001 101 011 000 0 4 2 6 1 5 3 7如：N=8時(shí)，序號(hào) “4” 用三位二進(jìn)制表示正常碼為“100”，而其倒碼為 “001” ，變成了序號(hào) “1” 。時(shí)域抽取基2FFT算法（DIT-FFT）由

26、完整的FFT流圖可見：從左到右計(jì)算下一級(jí)蝶式運(yùn)算時(shí)，僅需要用到本級(jí)的數(shù)據(jù)而不需要前一級(jí)的數(shù)據(jù)。例如在實(shí)施第二級(jí)蝶式運(yùn)算時(shí)，僅需要第一級(jí)蝶式運(yùn)算的結(jié)果，而不需要用到原來的輸入數(shù)據(jù) 。據(jù)此就可在數(shù)據(jù)輸入到存儲(chǔ)器以后，每一級(jí)運(yùn)算的結(jié)果存儲(chǔ)在同一組存儲(chǔ)單元中。直到最后輸出，中間無需其他存儲(chǔ)器。)(nx利用同一存儲(chǔ)單元存放蝶式運(yùn)算輸入和輸出數(shù)據(jù)的方法稱為原位運(yùn)算。原位運(yùn)算可節(jié)省存儲(chǔ)單元，降低FFT硬件實(shí)現(xiàn)的設(shè)備成本，從而使得FFT算法簡單、快速、高效。 DIT-FFT算法其他形式的流圖由信號(hào)流圖理論知道：只要保證各節(jié)點(diǎn)所連接的支路及其傳輸系數(shù)不變，無論各節(jié)點(diǎn)相對(duì)位置如何排列，所得到的流圖等效，DFT的結(jié)

27、果相同。時(shí)域抽取基2FFT算法（DIT-FFT）N=8 時(shí)輸入是正序、輸出是倒碼的DIT-FFT運(yùn)算流圖例如將N=8時(shí)基2DIT-FFT信號(hào)流圖中與 、 水平相連的所有節(jié)點(diǎn)分別同與 、 水平相連的所有節(jié)點(diǎn)對(duì)調(diào)，保持其余節(jié)點(diǎn)位置不變，得到新形式的信號(hào)流圖。)4( x) 1 ( x)6( x) 3( x頻域抽取基2FFT算法（DIF-FFT） 算法的推導(dǎo)頻域抽取算法是把時(shí)間序列 前后對(duì)半分解為兩個(gè)長為N/2點(diǎn)的序列，則：)(nx12/02/12/0)2/(12/012/12/010)2/()()2/()()()()()()(NnnkNNkNNnkNnNNnnkNNNnnkNNnnkNNnnkNWN

28、nxWnxWNnxWnxWnxWnxWnxnxDFTkX頻域抽取基2FFT算法（DIF-FFT）12/02/212/0)2/()()2/()()2(NnrnNrnNNnWNnxnxWNnxnxrX當(dāng) k 取偶數(shù)時(shí)（ k = 2 r，r = 0 , 1 , . , N / 2 1）為奇數(shù)為偶數(shù)kkWkkNN11)1(2/)(kX)(nx當(dāng) k 取奇數(shù)時(shí)（ k = 2 r1，r = 0 , 1 , . , N / 2 1）nNNnrnNnrNNnWWNnxnxWNnxnxrX12/02/)12(12/0)2/()()2/()()12()2/()()(1Nnxnxnx令nNWNnxnxnx)2/()

29、()(212/02/1)()2(NnrnNWnxrX則12/02/2)() 12(NnrnNWnxrX這一結(jié)論表明：求 的N點(diǎn)DFT 再次分解成 求兩個(gè)N/2 點(diǎn)DFT )(nx)(kX DIF-FFT的蝶式運(yùn)算流圖)(nx)2/(Nnx)2/()(NnxnxnNWNnxnx)2/()(1nNW DIF-FFT的一次分解運(yùn)算流圖頻域抽取基頻域抽取基2FFT算法（算法（DIF-FFT）先蝶式運(yùn)算，后 DFT。例如：N=8時(shí)頻域抽取基頻域抽取基2FFT算法（算法（DIF-FFT） DIF-FFT的二次分解運(yùn)算流圖通常 N/2 仍然為 2 的整數(shù)冪，繼續(xù)將 N/2 點(diǎn)DFT分成偶數(shù)組和奇數(shù)組，這樣每

30、個(gè) N/2 點(diǎn)DFT又可分解成兩個(gè) N/4 點(diǎn)DFT，其輸入序列分別是 和 按上下對(duì)半分開后通過蝶式運(yùn)算構(gòu)成的 4 個(gè)子序列，如下圖所示：)(1nx)(2nx頻域抽取基頻域抽取基2FFT算法（算法（DIF-FFT）按照以上方法繼續(xù)分解下去，經(jīng)過 M - 1 次分解，最后分解為 N/2 個(gè)兩點(diǎn)DFT，這 N/2 個(gè)2點(diǎn)DFT的輸出就是 N 點(diǎn)DFT的結(jié)果X(k) ，如下圖所示： 有關(guān)說明頻域抽取基頻域抽取基2FFT算法（算法（DIF-FFT）以上給出了 N=8 時(shí)完整的 DIF - FFT 的運(yùn)算流圖。由于這種方法是 按 在頻域進(jìn)行奇偶分解，因此稱之為頻域抽取基2 運(yùn)算。比較與相同點(diǎn)：運(yùn)算次數(shù)與

31、存儲(chǔ)量相同；不同點(diǎn)： 輸入序列為自然序列而輸出為碼位倒置序列 蝶式運(yùn)算過程不同 是序列先乘旋轉(zhuǎn)因子后相加減 是序列先相加減后乘旋轉(zhuǎn)因子)(kX1. 線性卷積實(shí)際應(yīng)用中一般以線性卷積和相關(guān)運(yùn)算處理為依據(jù)，如一個(gè)FIR數(shù)字濾波器的輸出等于輸入與濾波器的單位取樣響應(yīng)的線性卷積。DFT計(jì)算循環(huán)卷積DFT的快速算法FFT的出現(xiàn)， 使DFT在數(shù)字通信、 語言信號(hào)處理、 圖像處理、 功率譜估計(jì)、 仿真、 系統(tǒng)分析、 雷達(dá)理論、 光學(xué)、 醫(yī)學(xué)、 地震以及數(shù)值分析等各個(gè)領(lǐng)域都得到廣泛應(yīng)用。 3. 信號(hào)頻譜分析2. 快速相關(guān)（功率譜計(jì)算）9.7離散傅里葉變換的應(yīng)用離散傅里葉變換的應(yīng)用線性卷積 線性卷積不受主值區(qū)間

32、限制循環(huán)卷積 在一定條件下與線性卷積相等。兩個(gè)長度都為N的因果序列的循環(huán)卷積仍是一個(gè)長度為N的序列，而它們的線性卷積卻是一個(gè)長度為2N-1的序列。1、利用循環(huán)卷積計(jì)算線性卷積 如果能將線性卷積轉(zhuǎn)化成循環(huán)卷積，那么根據(jù)DFT的循環(huán)卷積性質(zhì)，就能夠用循環(huán)卷積來計(jì)算線性卷積，而循環(huán)卷積可以用FFT 進(jìn)行快速計(jì)算。因此，首先需要討論在什么條件下，循環(huán)卷積與線性 卷積相等的問題。 設(shè)h(n)和x(n)分別是長度為N和M的有限長序列，它們的線性卷積和循環(huán)卷積分別為 1010NlmLcLLmynh nx nh m x nmynh nx nh m xnmRn其中，L=maxN,M所以對(duì)照線性卷積的公式，可以看

33、出因 為 Lqxnx nqL 1010NcLmqNLqmynh mx nmqL Rnh m x nqLm Rn 10Nlmh m x nqLmynqL yc(n)是yl(n)以L為周期的周期延拓序列的主值序列。而yl(n)是個(gè)長度為N+M-1的序列，所以(1)如果L 2fc2) 譜分辨率F=Fs/N, 若N不變，要提高頻譜分辨率，必須降低Fs 若Fs不變，為提高頻譜分辨率，可增加采樣點(diǎn)數(shù)N，即增加觀察時(shí)間Tp。21cpfNFTF選取原則：（一）（一） 一維離散一維離散Walsh變換變換(WT)1. 定義正變換:1-N,0,1,u , ),()(1)(10,NxHWxuWxfNuF反變換:1-N

34、,0,1, , ),()()(10,xNuHWxuWuFxf)()(uFxfWT注意: Walsh正、反變換的變換核都一樣！9.8沃爾什沃爾什(Walsh)變換及其應(yīng)用實(shí)例變換及其應(yīng)用實(shí)例2.一維離散Walsh變換的矩陣算法正變換:1-N,0,1,u , ),()(1)(10NxWxuWxfNuF)1, 1 ()1()1 , 1 ()1 ()0 , 1 ()0(1)1 (NWNfWfWfNF) 1, 1() 1() 1 , 1() 1 ()0 , 1()0(1) 1(NNWNfNWfNWfNNF)1,0()1()1 ,0()1 ()0 ,0()0(1)0(NWNfWfWfNF展開：令：) 1(

35、) 1 () 0 (NFFFF) 1() 1 () 0 (NffffNNNNWNWNWNWWWNWWWW) 1, 1() 1 , 1() 0 , 1() 1, 1 () 1 , 1 () 0 , 1 () 1, 0 () 1 , 0 () 0 , 0 (IWT：WFf WT：WfNF1(1/N可以忽略不寫)注意: （1）正反變換的變換矩陣W都一樣； （2）W代表Walsh序的Walsh矩陣。注意: 當(dāng)變換矩陣為Hadamard矩陣HN時(shí),稱為Hadamard序的 Walsh變換。變換矩陣如下寫法：IWHT：HFf WHT：HfNF1(1/N可忽略不寫)其中H為Hadamaed序的Walsh矩陣

36、。IWT：WFf WT：WfNF1舉例:Txf2813)(求Walsh序的一維離散Walsh變換F(u).反變換：2813215 . 15 . 31111111111111111)(4FWxf215 . 15 . 3281311111111111111114141)(4fWuF正變換：Walsh序的Walsh變換：舉例:Txf2813)(求Walsh序的一維離散Walsh變換F(u)。用WHT。用WHT：15 . 125 . 3281311111111111111114141)(4fHuFH215 . 15 . 3281311111111111111114141)(4fWuF用WT：結(jié)果為Wa

37、lsh序結(jié)果為Hadamard序?qū)?yīng)關(guān)系W序 H序0 01 22 33 1IWT：HFf WHT：HfNFH1Hadamard序的Walsh變換：3.Walsh序和Hadamard序的相互轉(zhuǎn)換變換結(jié)果為Hadamard序的，要轉(zhuǎn)換為Walsh序可以推導(dǎo)出以下轉(zhuǎn)換方法（N=4）：二進(jìn)制碼格雷碼倒序碼 00 00 00 01 01 10 10 11 11 11 10 01（W序） （H序）對(duì)應(yīng)關(guān)系W序 H序0 01 22 33 1N=8時(shí)的轉(zhuǎn)換方法：二進(jìn)制碼 格雷碼倒序碼 000 000 000 001 001 100 010 011 110 011 010 010 100 110 011 101

38、 111 111 110 101 101 111 100 001（W序） （H序）對(duì)應(yīng)關(guān)系W序 H序0 01 42 63 24 35 76 57 14.一維Walsh變換的物理意義正如一維傅立葉變換（連續(xù)）是將一個(gè)函數(shù)分解成無窮個(gè)正弦波的疊加，而傅立葉幅度譜是這些正弦波的幅度系數(shù)。一維Walsh變換（連續(xù)）是將一個(gè)函數(shù)分解成無窮個(gè)Walsh函數(shù)（方波）的疊加，而F(u)是這些Walsh函數(shù)的幅度系數(shù).215 . 15 . 3)(2813)(uFxfWTT), 3(2), 2(), 1 (5 . 1), 0(5 . 3)(tWtWtWtWxfWWWW215 . 15 . 3)(2813)(uFx

39、fWTT), 3(2), 2(), 1 (5 . 1), 0(5 . 3)(tWtWtWtWxfWWWW), 0(tW), 1 ( tW), 2(tW), 3( tW0 12 3t), 0(5 . 3tW), 1 (5 . 1tW), 2(tW), 3(2tW0 12 3t)(xf3182（二（二) 二維離散二維離散Walsh變換變換1. 定義:正變換:1, 1 , 0,),(),(),(1),(1010NvuyvWxuWyxfNvuFNxNy反變換:1, 1 , 0,),(),(),(1),(1010NyxyvWxuWvuFNyxfNuNv注意：正變換和反變換的變換核都一樣。2. 矩陣算法:

40、WT：WfWNF1WFWNf1其中：W為Walsh矩陣WHT：HfHNFH1HHFNfH1其中：H為Hadamard矩陣3. 矩陣算法舉例: , 0000011001100000),(），（求vuWyxfWT：WfWNF1000001010000010111111111111111110000011001100000111111111111111141),(vuF正變換：反變換：000001100110000011111111111111110000010100000101111111111111111141),(yxf3. 矩陣算法舉例:用WHT：HfHNFH1100100000000100

41、111111111111111110000011001100000111111111111111141),(vuFH正變換：0000010100000101),(vuF結(jié)果是Hadamard序，必須再轉(zhuǎn)換為Walsh序。0000100100001001行序號(hào)變0000010100000101列序號(hào)變4. 實(shí)際圖像變換舉例:WT移中FTWT將能量集中于頻率平面的左上角移中FT將能量集中于頻率平面的中央3.2.7二維離散二維離散Walsh變換的應(yīng)用變換的應(yīng)用用于圖像數(shù)據(jù)壓縮用于圖像數(shù)據(jù)壓縮),(yxfWT),(vuF截取圖像的左上角保存),(vuF),(vuF補(bǔ)0),(yxf經(jīng)反變換，恢復(fù)原圖像3.2.7二維離散二維離散Walsh變換的應(yīng)