第九章離散傅立葉變換及其快速算法

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

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

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

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

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

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

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

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

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

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

11、ksntjnnpeFtx1)(knjNkkpNeanx210)(所以知道DFT=X(k)就可以求得離散周期信號的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、. 對稱性對稱性若若 f(k) F(n)則則 F(k) N f(n)f(n)應是應是f(n)周期拓展之后反轉(zhuǎn)周期拓展之后反轉(zhuǎn)稱稱圓周反轉(zhuǎn)圓周反轉(zhuǎn)。9.4離散傅立葉變換的性質(zhì)離散傅立葉變換的性質(zhì)3. 時移特性圓周位移（循環(huán)位移）圓周位移（循環(huán)位移）： 將有限長序列將有限長序列f(k)周期拓展成周期序列周期拓展成周期序列fN(k)，再右移再右移m位，得到時移序列位，得到時移序列fN(k m)，最后取其主，最后取其主值而得到的序列稱為值而得到的序列稱為f(k)的的圓周位移圓周位移序列，記為序列，記為 f (k m)NGN(k)時移特性時移特性若若 f(k) F(n)則則 f (k m)NGN(k)

13、WmnF(n) DFT時移特性證明時移特性證明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. 時域循環(huán)

14、卷積（圓卷積）定理時域循環(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)卷積結果的長度仍為循環(huán)卷積結果的長度仍為N。若兩序列長度不等，采。若兩序列長度

15、不等，采用用補零法補零法。循環(huán)卷積循環(huán)卷積例例 求圖求圖 (a)和和(b)所示所示f1(k)與與f2(k)的循環(huán)卷積的循環(huán)卷積f(k)。解解 將將f1(k)補一個零點，補一個零點，使使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)卷積計算線卷積循環(huán)卷積便于利用數(shù)字計算機進行計算。循環(huán)卷積便于利用數(shù)字計算機進行計算。為借助循環(huán)卷積求線卷積，要使循環(huán)卷積的結果與線為借助循環(huán)卷積求線卷積，要使循環(huán)卷積的結果與線卷積結果相同，可以采用補零的方法，使卷積結果相同，可以采用補零的方法，使 f1(k)與與f2(k)的長度均為的長度均為LN+M1 則循環(huán)卷積與線卷積的結果相同。則循環(huán)卷積與線卷積的結果相同。時域循環(huán)卷積定理時域循環(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表明，在一個頻域帶限之內(nèi)，功率譜之和與信號的能表明，在一個頻域帶限之內(nèi)，功率譜之和與信號的能量成比例。量成比例。 若x(n)是一個有限長序列，長度為N，對x(n)進行Z變換 10)()(NnnznxzX比較Z變換與DFT，我們看到，當z=W-kN時 )()()(10nxDFTWnxzXNnnkN

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

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

20、cimationFFT-DITTime -In- DecimationFFTFFT時域抽取基2FFT算法（DIT-FFT） 算法的推導時域抽取算法是按 的奇偶把時間序列 分解為兩個長為N/2點的序列，即：)(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點DFT，即：X kXk12( )( )和x nx n12( )( )和12/02/11)()(NnknNWnxkX12,.,1 ,0Nk12/02/22)()(NnknNWnxkX12,.,1 ,0Nk這是 前N/2點DFT) 12/,.1 , 0)(NkkX時域抽取基2FFT算法（DIT-FFT）) 1, 2/)(NNkkXkNNkNWW2/)()()2(21kXWkXNkXkN12,.,1 , 0Nk顯然，可采用蝶式運算圖來表示上述前N/2和后N/2兩式 ，如下圖所示：時域抽取基2FFT算法（DIT-FFT）時域抽取基2

22、FFT算法（DIT-FFT）例如N=8時的DFT,可以分解為兩個N/2=4點DFT, 如下圖：時域抽取基2FFT算法（DIT-FFT）同理： , N/2仍可能是偶數(shù),可以進一步把每個N/2點的序列再按其奇偶部分分解為兩個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故時域抽取基

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

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

25、log2loglog) 1(NNN22log)2/( FFT算法的特點時域抽取基時域抽取基2FFT算法（算法（DIT-FFT） 倒碼倒碼即碼位倒置：是指將原二進制數(shù)的碼位倒過來 按從低位到高位排列。 順序順序 二進制數(shù)二進制數(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時，序號 “4” 用三位二進制表示正常碼為“100”，而其倒碼為 “001” ，變成了序號 “1” 。時域抽取基2FFT算法（DIT-FFT）由

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

27、果相同。時域抽取基2FFT算法（DIT-FFT）N=8 時輸入是正序、輸出是倒碼的DIT-FFT運算流圖例如將N=8時基2DIT-FFT信號流圖中與 、 水平相連的所有節(jié)點分別同與 、 水平相連的所有節(jié)點對調(diào)，保持其余節(jié)點位置不變，得到新形式的信號流圖。)4( x) 1 ( x)6( x) 3( x頻域抽取基2FFT算法（DIF-FFT） 算法的推導頻域抽取算法是把時間序列 前后對半分解為兩個長為N/2點的序列，則：)(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當 k 取偶數(shù)時（ k = 2 r，r = 0 , 1 , . , N / 2 1）為奇數(shù)為偶數(shù)kkWkkNN11)1(2/)(kX)(nx當 k 取奇數(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這一結論表明：求 的N點DFT 再次分解成 求兩個N/2 點DFT )(nx)(kX DIF-FFT的蝶式運算流圖)(nx)2/(Nnx)2/()(NnxnxnNWNnxnx)2/()(1nNW DIF-FFT的一次分解運算流圖頻域抽取基頻域抽取基2FFT算法（算法（DIF-FFT）先蝶式運算，后 DFT。例如：N=8時頻域抽取基頻域抽取基2FFT算法（算法（DIF-FFT） DIF-FFT的二次分解運算流圖通常 N/2 仍然為 2 的整數(shù)冪，繼續(xù)將 N/2 點DFT分成偶數(shù)組和奇數(shù)組，這樣每

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

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

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

33、出因 為 Lqxnx nqL 1010NcLmqNLqmynh mx nmqL Rnh m x nqLm Rn 10Nlmh m x nqLmynqL yc(n)是yl(n)以L為周期的周期延拓序列的主值序列。而yl(n)是個長度為N+M-1的序列，所以(1)如果L 2fc2) 譜分辨率F=Fs/N, 若N不變，要提高頻譜分辨率，必須降低Fs 若Fs不變，為提高頻譜分辨率，可增加采樣點數(shù)N，即增加觀察時間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)變換及其應用實例變換及其應用實例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矩陣。注意: 當變換矩陣為Hadamard矩陣HN時,稱為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：結果為Wa

37、lsh序結果為Hadamard序?qū)P系W序 H序0 01 22 33 1IWT：HFf WHT：HfNFH1Hadamard序的Walsh變換：3.Walsh序和Hadamard序的相互轉(zhuǎn)換變換結果為Hadamard序的，要轉(zhuǎn)換為Walsh序可以推導出以下轉(zhuǎn)換方法（N=4）：二進制碼格雷碼倒序碼 00 00 00 01 01 10 10 11 11 11 10 01（W序） （H序）對應關系W序 H序0 01 22 33 1N=8時的轉(zhuǎ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序）對應關系W序 H序0 01 42 63 24 35 76 57 14.一維Walsh變換的物理意義正如一維傅立葉變換（連續(xù)）是將一個函數(shù)分解成無窮個正弦波的疊加，而傅立葉幅度譜是這些正弦波的幅度系數(shù)。一維Walsh變換（連續(xù)）是將一個函數(shù)分解成無窮個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結果是Hadamard序，必須再轉(zhuǎn)換為Walsh序。0000100100001001行序號變0000010100000101列序號變4. 實際圖像變換舉例:WT移中FTWT將能量集中于頻率平面的左上角移中FT將能量集中于頻率平面的中央3.2.7二維離散二維離散Walsh變換的應用變換的應用用于圖像數(shù)據(jù)壓縮用于圖像數(shù)據(jù)壓縮),(yxfWT),(vuF截取圖像的左上角保存),(vuF),(vuF補0),(yxf經(jīng)反變換，恢復原圖像3.2.7二維離散二維離散Walsh變換的應