從頭到尾徹底理解傅里葉變換算法、下_第1頁
從頭到尾徹底理解傅里葉變換算法、下_第2頁
從頭到尾徹底理解傅里葉變換算法、下_第3頁
從頭到尾徹底理解傅里葉變換算法、下_第4頁
從頭到尾徹底理解傅里葉變換算法、下_第5頁
已閱讀5頁,還剩11頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、經(jīng)典算法研究系列:十、從頭到尾徹底理解傅里葉變換算法、下作者:July、dznlong二零一一年二月二十二日推薦閱讀:The Scientist and Engineers Guide to Digital Signal Processing, BySteven W. Smith, Ph.D。此書地址:http:/ DFT )從頭到尾徹底理解傅里葉變換算法、下第三章、復(fù)數(shù)第四章、復(fù)數(shù)形式離散傅立葉變換前期回顧,在上一篇:十、從頭到尾徹底理解傅里葉變換算法、上 里,我們講了傅立葉變換的由來、和實(shí)數(shù)形式離散傅立葉變換(Real DFT )倆個問題, 本文接上文,著重講下復(fù)數(shù)、和復(fù)數(shù)形式離散傅立葉變

2、換等倆個問題。第三章、復(fù)數(shù)復(fù)數(shù)擴(kuò)展了我們一般所能理解的數(shù)的概念,復(fù)數(shù)包含了實(shí)數(shù)和虛數(shù)兩部分,利用復(fù)數(shù)的形式可以把由兩個變量表示的表達(dá)式變成由一個變量(復(fù)變量)來表達(dá),使得處理起來更加自然和方便。我們知道傅立葉變換的結(jié)果是由兩部分組成的,使用復(fù)數(shù)形式可以縮短變換表達(dá)式,使得我們可以單獨(dú)處理一個變量(這個在后面的描述中我們就可以更加確切地知道),而且快速傅立葉變換正是基于復(fù)數(shù)形式的,所以幾乎所有描述的傅立葉變換形式都是復(fù)數(shù)的形式。但是復(fù)數(shù)的概念超過了我們?nèi)粘I钪兴芾斫獾母拍?,要理解?fù)數(shù)是較難的,所以我們在理解復(fù)數(shù)傅立葉變換之前,先來專門復(fù)習(xí)一下有關(guān)復(fù)數(shù)的知識,這對后面的理解非常重要。一、復(fù)數(shù)的

3、提出在此,先讓我們看一個物理實(shí)驗(yàn):把一個球從某點(diǎn)向上拋出,然后根據(jù)初速度和時間來計算球所在高度,這個方法可以根據(jù)下面的式子計算得出:L 2 -gLh = + vr其中h表示高度,g表示重力加速度(9.8m/s2) , v表示初速度,t表示時間?,F(xiàn)在反過來, 假如知道了高度,要求計算到這個高度所需要的時間,這時我們又可以通過下式來計算:= 1士1 -人;4.9(多謝JERRY_PRI提出:1、 根據(jù)公式h=-(gt2/2)+Vt (gt后面的2表示t的平方),我們可以討論最終情況,也就是說小球運(yùn)動到最高點(diǎn)時,v=gt,所以,可以得到t=sqt(2h/g)且在您給的公式中,根號下為1-(2h)/g

4、,化成分?jǐn)?shù)形式為(g-2h)/g , g和h不能直接做加減運(yùn)算。2、g是重力加速度,單位是m/s2 , h的單位是m ,他們兩個相減的話在物理上沒有意義, 而且使用您給的那個公式反向回去的話推出的是h=-(gt2/2)+gt啊(gt后面的2表示t的平 方)。3、 直接推到可以得出t=v/g sqt(v2-2hg)/g2) (v和g后面的2都表示平方),那么也就是 說當(dāng)v22hg時會產(chǎn)生復(fù)數(shù),但是如果從實(shí)際的v2是不可能小于2hg的,所以我感覺復(fù)數(shù) 不能從實(shí)際出發(fā)去推到,只能從抽象的角度說明一下。)經(jīng)過計算我們可以知道,當(dāng)高度是3米時,有兩個時間點(diǎn)到達(dá)該高度:球向上運(yùn)動時的時 間是0.38秒,球

5、向下運(yùn)動時的時間是1.62秒。但是如果高度等于10時,結(jié)果又是什么呢?根據(jù)上面的式子可以發(fā)現(xiàn)存在對負(fù)數(shù)進(jìn)行開平方運(yùn)算,我們知道這肯定是不現(xiàn)實(shí)的。第一次使用這個不一般的式子的人是意大利數(shù)學(xué)家GirolamoCardano (1501-1576 ),兩個世紀(jì)后,德國偉大數(shù)學(xué)家Carl Friedrich Gause (1777-1855 )提出了復(fù)數(shù)的概念,為后來的應(yīng)用鋪平了道路,他對復(fù)數(shù)進(jìn)行這樣表示:復(fù)數(shù)由實(shí)數(shù)(real)和虛數(shù)(imaginary)兩部分 組成,虛數(shù)中的根號負(fù)1用i來表示(在這里我們用j來表示,因?yàn)閕在電力學(xué)中表示電流的意思)。我們可以把橫坐標(biāo)表示成實(shí)數(shù),縱坐標(biāo)表示成虛數(shù),則坐

6、標(biāo)中的每個點(diǎn)的向量就可以用復(fù)數(shù)來表示,如下圖:A = 2 + 6jB = -4 - 1.5jC = 3 - 7j這樣子來表達(dá)方便之處在于運(yùn)用一個符號就能把兩個原來難以聯(lián)系起來的數(shù)組合起來了,不上圖中的ABC三個向量可以表示成如下的式子:A AI sx=由曰=方便的是我們要分辨哪個是實(shí)數(shù)和哪個是虛數(shù),我們一般是用Re()和Im()來表示實(shí)數(shù)和虛數(shù)兩部分,如:Re A = 2 Im A = 6Re B = -4 Im B = -1.5Re C = 3 Im C = -7復(fù)數(shù)之間也可以進(jìn)行加減乘除運(yùn)算:(十/)十(仁+ 力)=(d +仁)+j(b -偵 +bj) -+ dj) = (a - c) *

7、 j(b -(7)(fjbj) (c + dj ) = (_ac一bd) + j (be + ad (口十/,) _itc bdI卜.|be - ad (c -dj )、廣+/) c2d2這里有個特殊的地方是j2等于-1 ,上面第四個式子的計算方法是把分子和分母同時乘以c -dj,這樣就可消去分母中的j了。復(fù)數(shù)也符合代數(shù)運(yùn)算中的交換律、結(jié)合律、分配律:A B = B A(A + B) + C = A + (B + C)A(B + C) = AB + AC二、復(fù)數(shù)的極坐標(biāo)表示形式前面提到的是運(yùn)用直角坐標(biāo)來表示復(fù)數(shù),其實(shí)更為普遍應(yīng)用的是極坐標(biāo)的表示方法,如下圖:上圖中的M即是數(shù)量積(magnitu

8、de),表示從原點(diǎn)到坐標(biāo)點(diǎn)的距離,。是相位角(phase angle),表示從X軸正方向到某個向量的夾角,下面四個式子是計算方法:M二JCKA尸 +而A)?ReA= Mcos(O)JrnA -Msin(6)十5 J or0=arcianImA-ReA .我們還可以通過下面的式子進(jìn)行極坐標(biāo)到直角坐標(biāo)的轉(zhuǎn)換:a + jb = M (cos。+j sin 0 )上面這個等式中左邊是直角坐標(biāo)表達(dá)式,右邊是極坐標(biāo)表達(dá)式。1707-1783 ):上面中右邊的兩個式子分別是cos(x)和sin(x)的泰勒(Taylor)級數(shù)。這樣子我們又可以把復(fù)數(shù)的表達(dá)式表示成指數(shù)的形式了:a + jb = M ej質(zhì)這便

9、是復(fù)數(shù)的兩個表達(dá)式)指數(shù)形式是數(shù)字信號處理中數(shù)學(xué)方法的支柱,也許是因?yàn)橛弥笖?shù)形式進(jìn)行復(fù)數(shù)的乘除運(yùn)算極為簡單的緣故吧:還有一個更為重要的等式歐拉等式(歐拉,瑞士的著名數(shù)學(xué)家,Leonhard Euler ,ejx = cos x + j sin x三、復(fù)數(shù)是數(shù)學(xué)分析中的一個工具為什么要使用復(fù)數(shù)呢?其實(shí)它只是個工具而已,就如釘子和錘子的關(guān)系,復(fù)數(shù)就象那錘子, 作為一種使用的工具。 我們把要解決的問題表達(dá)成復(fù)數(shù)的形式(因?yàn)橛行﹩栴}用復(fù)數(shù)的形式進(jìn)行運(yùn)算更加方便),然后對復(fù)數(shù)進(jìn)行運(yùn)算,最后再轉(zhuǎn)換回來得到我們所需要的結(jié)果。有兩種方法使用復(fù)數(shù),一種是用復(fù)數(shù)進(jìn)行簡單的替換,如前面所說的向量表達(dá)式方法和前一 節(jié)

10、中我們所討論的實(shí)域DFT,另一種是更高級的方法:數(shù)學(xué)等價(mathematical equivalence),復(fù)數(shù)形式的傅立葉變換用的便是數(shù)學(xué)等價的方法,但在這里我們先不討論這種方法,這里我們先來看一下用復(fù)數(shù)進(jìn)行替換中的問題。用復(fù)數(shù)進(jìn)行替換的基本思想是:把所要分析的物理問題轉(zhuǎn)換成復(fù)數(shù)的形式,其中只是簡單地添加一個復(fù)數(shù)的符號j,當(dāng)返回到原來的物理問題時,則只是把符號j去掉就可以了。有一點(diǎn)要明白的是并不是所有問題都可以用復(fù)數(shù)來表示,必須看用復(fù)數(shù)進(jìn)行分析是否適用, 有個例子可以看出用復(fù)數(shù)來替換原來問題的表達(dá)方式明顯是謬誤的:假設(shè)一箱的蘋果是5美元,一箱的桔子是10美元,于是我們把它表示成5 + 10

11、j ,有一個星期你買了6箱蘋果和2箱桔子,我們又把它表示成6 + 2j ,最后計算總共花的錢是(5 + 10j)(6 + 2j) = 10 + 70j ,結(jié)果是買蘋果花了10美元的,買桔子花了70美元,這樣的結(jié)果明顯是錯了,所以復(fù)數(shù)的 形式不適合運(yùn)用于對這種問題的解決。土)j(勺洌)L四、用復(fù)數(shù)來表示正余弦函數(shù)表達(dá)式對于象M cos ( cot +和)A cos( cot ) + B sin(黃注式,用復(fù)數(shù)來表示,可以變得非常簡潔, 對于直角坐標(biāo)形式可以按如下形式進(jìn)行轉(zhuǎn)換:Acos (wr) + 5siiiiwr)尊o + jbconvention at(conpUx上式中余弦幅值A(chǔ)經(jīng)變換生成

12、a,正弦幅值B的相反數(shù)經(jīng)變換生成b: A a , B -b ,但要注意的是,這不是個等式,只是個替換形式而已。對于極坐標(biāo)形式可以按如下形式進(jìn)行轉(zhuǎn)換:Mcos(cjf + )尸A/f?;erepj es&aTTOK) comp?ex上式中,M M , 0 4。這里虛數(shù)部分采用負(fù)數(shù)的形式主要是為了跟復(fù)數(shù)傅立葉變換表達(dá)式保持一致,對于這種替換的方法來表示正余弦,符號的變換沒有什么好處,但替換時總會被改變掉符號以跟更高級的 等價變換保持形式上的一致。在離散信號處理中,運(yùn)用復(fù)數(shù)形式來表示正余弦波是個常用的技術(shù),這是因?yàn)槔脧?fù)數(shù)進(jìn)行各種運(yùn)算得到的結(jié)果跟原來的正余弦運(yùn)算結(jié)果是一致的,但是,我們要小心

13、使用復(fù)數(shù)操作,如加、減、乘、除,有些操作是不能用的,如兩個正弦信號相加,采用復(fù)數(shù)形式進(jìn)行相加,得到的結(jié)果跟替換前的直接相加的結(jié)果是一樣的,但是如果兩個正弦信號相乘,則采用復(fù)數(shù)形式來相乘結(jié)果是不一樣的。幸運(yùn)的是,我們已嚴(yán)格定義了正余弦復(fù)數(shù)形式的運(yùn)算操作條件:1、 參加運(yùn)算的所有正余弦的頻率必須是一樣的;2、 運(yùn)算操作必須是線性的,如兩個正弦信號可以進(jìn)行相加減,但不能進(jìn)行乘除,象信號的 放大、衰減、高低通濾波等系統(tǒng)都是線性的,象平方、縮短、取限等則不是線性的。要記住 的是卷積和傅立葉分析也只有線性操作才可以進(jìn)行。下圖是一個相量變換(我們把正弦或余弦波變成復(fù)數(shù)的形式稱為相量變換,Phasor tra

14、nsform)的例子,一個連續(xù)信號波經(jīng)過一個線性處理系統(tǒng)生成另一個信號波,從計算過程我們可以看出采用復(fù)數(shù)的形式使得計算變化十分的簡潔:3 cos (wf -兀4)Of2 J213cost(ji)/) - 2.1213血(頃)0.5“m。Xor2.1213 p 2.12130.19H H0.4619在第二章中我們描述的實(shí)數(shù)形式傅立葉變換也是一種替換形式的復(fù)數(shù)變換,但要注意的是那還不是復(fù)數(shù)傅立葉變換,只是一種代替方式而已。下一章、即,第四章,我們就會知道復(fù)數(shù) 傅立葉變換是一種更高級的變換,而不是這種簡單的替換形式。第四章、復(fù)數(shù)形式離散傅立葉變換復(fù)數(shù)形式的離散傅立葉變換非常巧妙地運(yùn)用了復(fù)數(shù)的方法,使

15、得傅立葉變換變換更加自然和簡潔,它并不是只是簡單地運(yùn)用替換的方法來運(yùn)用復(fù)數(shù),而是完全從復(fù)數(shù)的角度來分析問題,這一點(diǎn)跟實(shí)數(shù)DFT是完全不一樣的。一、把正余弦函數(shù)表示成復(fù)數(shù)的形式通過歐拉等式可以把正余弦函數(shù)表示成復(fù)數(shù)的形式:Input signalOutput sign;LinearSystem1.5cos(wr-MCf1.3858cQwf);03741.5xsor1.3858 -/0.574(,一一I I Q-i-2Q-i-23 3-4-4 = =Lm=/=Lm=/cos( x ) = 1/2 e j(-x) + 1/2 ejxsin( x ) = j (1/2 e j(-x) - 1/2 ej

16、x)從這個等式可以看出, 如果把正余弦函數(shù)表示成復(fù)數(shù)后,它們變成了由正負(fù)頻率組成的正余弦波,相反地,一個由正負(fù)頻率組成的正余弦波,可以通過復(fù)數(shù)的形式來表示。我們知道,在實(shí)數(shù)傅立葉變換中,它的頻譜是0 兀(0 N/2),但無法表示-兀 0的頻譜,可 以預(yù)見,如果把正余弦表示成復(fù)數(shù)形式,則能夠把負(fù)頻率包含進(jìn)來。二、把變換前后的變量都看成復(fù)數(shù)的形式復(fù)數(shù)形式傅立葉變換把原始信號xn當(dāng)成是一個用復(fù)數(shù)來表示的信號,其中實(shí)數(shù)部分表示原始信號值,虛數(shù)部分為0,變換結(jié)果Xk也是個復(fù)數(shù)的形式,但這里的虛數(shù)部分是有值的。在這里要用復(fù)數(shù)的觀點(diǎn)來看原始信號,是理解復(fù)數(shù)形式傅立葉變換的關(guān)鍵(如果有學(xué)過復(fù)變函數(shù)則可能更好理

17、解,即把xn看成是一個復(fù)數(shù)變量, 然后象對待實(shí)數(shù)那樣對這個復(fù)數(shù)變量進(jìn)行相同的變換)。三、對復(fù)數(shù)進(jìn)行相關(guān)性算法(正向傅立葉變換)從實(shí)數(shù)傅立葉變換中可以知道,我們可以通過原始信號乘以一個正交函數(shù)形式的信號,然后進(jìn)行求總和,最后就能得到這個原始信號所包含的正交函數(shù)信號的分量。現(xiàn)在我們的原始信號變成了復(fù)數(shù), 我們要得到的當(dāng)然是復(fù)數(shù)的信號分量, 我們是不是可以把 它乘以一個復(fù)數(shù)形式的正交函數(shù)呢?答案是肯定的,正余弦函數(shù)都是正交函數(shù), 變成如下形式的復(fù)數(shù)后,仍舊還是正交函數(shù)(這個從正交函數(shù)的定義可以很容易得到證明):cos x + j sin x, cos x - j sin x , .這里我們采用上面的

18、第二個式子進(jìn)行相關(guān)性求和,為什么用第二個式子呢?,我們在后面會知道,正弦函數(shù)在虛數(shù)中變換后得到的是負(fù)的正弦函數(shù),這里我們再加上一個負(fù)號, 使得最后的得到的是正的正弦波,根據(jù)這個于是我們很容易就可以得到了復(fù)數(shù)形式的DFT正向變換等式:cos(2兀切/N) -Jsin(2網(wǎng)杼/N)N可 “ Ar-1T/f = .這個式子很容易可以得到歐拉變換式子:x幻二項衣3臉客而加其實(shí)我們是為了表達(dá)上的方便才用到歐拉變換式,在解決問題時我們還是較多地用到正余弦表達(dá)式。對于上面的等式,我們要清楚如下幾個方面(也是區(qū)別于實(shí)數(shù)DFT的地方):1、Xk、xn都是復(fù)數(shù),但xn的虛數(shù)部分都是由0組成的,實(shí)數(shù)部分表示原始信號

19、;2、k的取值范圍是0 N-1 (也可以表達(dá)成0 2兀,)其中0 N/2(或0 方是正頻部分,N/2 N-1(兀 2立是負(fù)頻部分,由于正余弦函數(shù)的對稱性,所以我們把 -兀睡示成兀2兀,這是出于計算上方便的考慮。3、 其中的j是一個不可分離的組成部分,就象一個等式中的變量一樣,不能隨便去掉,去掉之后意義就完全不一樣了,但我們知道在實(shí)數(shù)DFT中,j只是個符號而已,把j去掉,整個等式的意義不變;4、 下圖是個連續(xù)信號的頻譜,但離散頻譜也是與此類似的,所以不影響我們對問題的分析:ReXImXIFiequency上面的頻譜圖把負(fù)頻率放到了左邊, 是為了迎合我們的思維習(xí)慣,但在實(shí)際實(shí)現(xiàn)中我們一般是把它移到

20、正的頻譜后面的。從上圖可以看出,時域中的正余弦波(用來組成原始信號的正余弦波)在復(fù)數(shù)DFT的頻譜中被分成了正、負(fù)頻率的兩個組成部分, 基于此等式中前面的比例系數(shù)是1/N(或1/2兀), 而不是2/N,這是因?yàn)楝F(xiàn)在把頻譜延伸到了2兀,但把正負(fù)兩個頻率相加即又得到了2/N,又還 原到了實(shí)數(shù)DFT的形式,這個在后面的描述中可以更清楚地看到。由于復(fù)數(shù)DFT生成的是一個完整的頻譜,原始信號中的每一個點(diǎn)都是由正、負(fù)兩個頻率組合而成的,所以頻譜中每一個點(diǎn)的帶寬是一樣的,都是1/N ,相對實(shí)數(shù)DFT,兩端帶寬比其它點(diǎn)的帶寬少了一半; 復(fù)數(shù)DFT的頻譜特征具有周期性:-N/2 - 0與N/2 N-1是一樣的,

21、實(shí)域頻譜呈偶對稱性(表示余弦波頻譜),虛域頻譜呈奇對稱性(表示正弦波頻譜)。四、逆向傅立葉變換假設(shè)我們已經(jīng)得到了復(fù)數(shù)形式的頻譜Xk,現(xiàn)在要把它還原到復(fù)數(shù)形式的原始信號xn,當(dāng)然應(yīng)該是把Xk乘以一個復(fù)數(shù),然后再進(jìn)行求和,最后得到原始信號xn,這個跟Xk相乘的復(fù)數(shù)首先讓我們想到的應(yīng)該是上面進(jìn)行相關(guān)性計算的復(fù)數(shù):cos(2兀kn/N) j-si(2兀kn/N)但其中的負(fù)號其實(shí)是為了使得進(jìn)行逆向傅立葉變換時把正弦函數(shù)變?yōu)檎姆?,因?yàn)樘摂?shù)j的運(yùn)算特殊性,使得原來應(yīng)該是正的正弦函數(shù)變?yōu)榱素?fù)的正弦函數(shù)(我們從后面的推導(dǎo)會看到這一點(diǎn)),所以這里的負(fù)號只是為了糾正符號的作用,在進(jìn)行逆向DFT時,我們可以把負(fù)號

22、去掉,于是我們便得到了這樣的逆向DFT變換等式:xn = Xk (cos(2兀kn/N) + j sin(2兀kn/N)我們現(xiàn)在來分析這個式子,會發(fā)現(xiàn)這個式其實(shí)跟實(shí)數(shù)傅立葉變換是可以得到一樣結(jié)果的。我們先把Xk變換一下:Xk = Re Xk + j Im Xk這樣我們就可以對xn再次進(jìn)行變換,如:xn = (Re Xk + j Im Xk) (cos(2兀kn/N) + j sin(2兀kn/N)=(Re Xk cos(2兀kn/N) + j Im Xk cos(2兀kn/N) +j Re Xk sin(2 - Im Xk kn/N) sin(2兀kn/N)=(Re Xk (cos(2兀kn/N) + j sin(2兀kn/N+-(1)Im Xk( -sin(2兀kn/N) + j cos(2兀kr)/N)-(2)這時我們就把原來的等式分成了兩個部分,第一個部分是跟實(shí)域中的頻譜相乘,第二個部分是跟虛域中的頻譜相乘,根據(jù)頻譜圖我們可以知道,Re Xk是個偶對稱的變量,Im Xk是個奇對稱的變量,即Re Xk = Re X-

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論