從頭到尾徹底理解傅里葉變換算法、上

《從頭到尾徹底理解傅里葉變換算法、上》由會(huì)員分享，可在線閱讀，更多相關(guān)《從頭到尾徹底理解傅里葉變換算法、上（12頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、. July、dznlong 二零一一年二月二十日 推薦閱讀：The Scientist and Engineer's Guide to Digital Signal Processing,By Steven W. Smith, Ph.D。此書(shū)地址：。 博主說(shuō)明：I、本文中闡述離散傅里葉變換方法,是根據(jù)此書(shū)：The Scientist and Engineer's Guide to Digital Signal Processing,By Steven W. Smith, Ph.D.而翻譯而成的,此書(shū)地址：。II、同時(shí),有相當(dāng)一部分內(nèi)容編輯整理自dznlong的博客,也貼出其博客地址

2、,向原創(chuàng)的作者表示致敬： 。這年頭,真正靜下心寫(xiě)來(lái)原創(chuàng)文章的人,很少了。 ------------------------------------ 從頭到尾徹底理解傅里葉變換算法、上前言第一部分、 DFT第一章、傅立葉變換的由來(lái)第二章、實(shí)數(shù)形式離散傅立葉變換〔Real DFT 從頭到尾徹底理解傅里葉變換算法、下 第三章、復(fù)數(shù) 第四章、復(fù)數(shù)形式離散傅立葉變換 前言："關(guān)于傅立葉變換,無(wú)論是書(shū)本還是在網(wǎng)上可以很容易找到關(guān)于傅立葉變換的描述,但是大都是些故弄玄虛的文章,太過(guò)抽象,盡是一些讓人看了就望而生畏的公式的羅列,讓人很難能夠從感性上得到理解"---dznlong, 那么,到底什么

3、是傅里葉變換算法列?傅里葉變換所涉及到的公式具體有多復(fù)雜列? 傅里葉變換〔Fourier transform是一種線性的積分變換。因其基本思想首先由法國(guó)學(xué)者傅里葉系統(tǒng)地提出,所以以其名字來(lái)命名以示紀(jì)念。 哦,傅里葉變換原來(lái)就是一種變換而已,只是這種變換是從時(shí)間轉(zhuǎn)換為頻率的變化。這下,你就知道了,傅里葉就是一種變換,一種什么變換列?就是一種從時(shí)間到頻率的變化或其相互轉(zhuǎn)化。 ok,咱們?cè)賮?lái)總體了解下傅里葉變換,讓各位對(duì)其有個(gè)總體大概的印象,也順便看看傅里葉變換所涉及到的公式,究竟有多復(fù)雜： 以下就是傅里葉變換的4種變體〔摘自,維基百科 連續(xù)傅里葉變換一般情況下,若"傅里葉變換"一詞不加任

4、何限定語(yǔ),則指的是"連續(xù)傅里葉變換"。連續(xù)傅里葉變換將平方可積的函數(shù)f〔t表示成復(fù)指數(shù)函數(shù)的積分或級(jí)數(shù)形式。 這是將頻率域的函數(shù)F<ω>表示為時(shí)間域的函數(shù)f〔t的積分形式。 連續(xù)傅里葉變換的逆變換 為： 即將時(shí)間域的函數(shù)f〔t表示為頻率域的函數(shù)F<ω>的積分。 一般可稱函數(shù)f〔t為原函數(shù),而稱函數(shù)F<ω>為傅里葉變換的像函數(shù),原函數(shù)和像函數(shù)構(gòu)成一個(gè)傅里葉變換對(duì)〔transform pair。 除此之外,還有其它型式的變換對(duì),以下兩種型式亦常被使用。在通信或是信號(hào)處理方面,常以來(lái)代換,而形成新的變換對(duì): 或者是因系數(shù)重分配而得到新

5、的變換對(duì)： 一種對(duì)連續(xù)傅里葉變換的推廣稱為分?jǐn)?shù)傅里葉變換〔Fractional Fourier Transform。分?jǐn)?shù)傅里葉變換指的就是傅里葉變換的廣義化。 分?jǐn)?shù)傅里葉變換的物理意義即做傅里葉變換 a 次,其中 a 不一定要為整數(shù)；而做了分?jǐn)?shù)傅里葉變換之后,信號(hào)或輸入函數(shù)便會(huì)出現(xiàn)在介于時(shí)域與頻域之間的分?jǐn)?shù)域。 當(dāng)f〔t為偶函數(shù)〔或奇函數(shù)時(shí),其正弦〔或余弦分量將消亡,而可以稱這

6、時(shí)的變換為余弦變換〔cosine transform或正弦變換〔sine transform. 另一個(gè)值得注意的性質(zhì)是,當(dāng)f〔t為純實(shí)函數(shù)時(shí),F = F*<ω>成立. 傅里葉級(jí)數(shù)連續(xù)形式的傅里葉變換其實(shí)是傅里葉級(jí)數(shù) 的推廣,因?yàn)榉e分其實(shí)是一種極限形式的求和算子而已。對(duì)于周期函數(shù),其傅里葉級(jí)數(shù)是存在的： 其中Fn為復(fù)幅度。對(duì)于實(shí)值函數(shù),函數(shù)的傅里葉級(jí)數(shù)可以寫(xiě)成： 其中an和bn是實(shí)頻率分量的幅度。 離散時(shí)域傅里葉變換離散傅里葉變換是離散時(shí)間傅里葉變換〔DTFT的特例〔有時(shí)作為后者的近似。DTFT在時(shí)域上離散,在頻域上則是周期的。DTFT可以被

7、看作是傅里葉級(jí)數(shù)的逆變換。 離散傅里葉變換離散傅里葉變換〔DFT,是連續(xù)傅里葉變換在時(shí)域和頻域上都離散的形式,將時(shí)域信號(hào)的采樣變換為在離散時(shí)間傅里葉變換〔DTFT頻域的采樣。在形式上,變換兩端〔時(shí)域和頻域上的序列是有限長(zhǎng)的,而實(shí)際上這兩組序列都應(yīng)當(dāng)被認(rèn)為是離散周期信號(hào)的主值序列。即使對(duì)有限長(zhǎng)的離散信號(hào)作DFT,也應(yīng)當(dāng)將其看作經(jīng)過(guò)周期延拓成為周期信號(hào)再作變換。在實(shí)際應(yīng)用中通常采用快速傅里葉變換以高效計(jì)算DFT。 為了在科學(xué)計(jì)算和數(shù)字信號(hào)處理等領(lǐng)域使用計(jì)算機(jī)進(jìn)行傅里葉變換,必須將函數(shù)xn定義在離散點(diǎn)而非連續(xù)域內(nèi),且須滿足有限性或周期性條件。這種情況下,使用離散傅里葉變換〔DFT,將函數(shù)xn表示

8、為下面的求和形式： 其中Xk是傅里葉幅度。直接使用這個(gè)公式計(jì)算的計(jì)算復(fù)雜度為O〔n*n,而快速傅里葉變換〔FFT可以將復(fù)雜度改進(jìn)為O〔n*lgn?！埠竺鏁?huì)具體闡述FFT是如何將復(fù)雜度降為O〔n*lgn的。計(jì)算復(fù)雜度的降低以及數(shù)字電路計(jì)算能力的發(fā)展使得DFT成為在信號(hào)處理領(lǐng)域十分實(shí)用且重要的方法。 下面,比較下上述傅立葉變換的4種變體, 如上,容易發(fā)現(xiàn)：函數(shù)在時(shí)〔頻域的離散對(duì)應(yīng)于其像函數(shù)在頻〔時(shí)域的周期性。反之連續(xù)則意味著在對(duì)應(yīng)域的信號(hào)的非周期性。也就是說(shuō),時(shí)間上的離散性對(duì)應(yīng)著頻率上的周期性。同時(shí),注意,離散時(shí)間傅里葉變換,時(shí)間離散,頻率不離散,它在頻域依然是連續(xù)的。 如果,讀到此,你不

9、甚明白,大沒(méi)關(guān)系,不必糾結(jié)于以上4種變體,繼續(xù)往下看,你自會(huì)豁然開(kāi)朗。〔有什么問(wèn)題,也懇請(qǐng)?zhí)岢?或者批評(píng)指正 ok, 本文,接下來(lái),由傅里葉變換入手,后重點(diǎn)闡述離散傅里葉變換、快速傅里葉算法,到最后徹底實(shí)現(xiàn)FFT算法,全篇力求通俗易懂、閱讀順暢,教你從頭到尾徹底理解傅里葉變換算法。由于傅里葉變換,也稱傅立葉變換,下文所稱為傅立葉變換,同一個(gè)變換,不同叫法,讀者不必感到奇怪。 第一部分、DFT第一章、傅立葉變換的由來(lái)要理解傅立葉變換,先得知道傅立葉變換是怎么變換的,當(dāng)然,也需要一定的高等數(shù)學(xué)基礎(chǔ),最基本的是級(jí)數(shù)變換,其中傅立葉級(jí)數(shù)變換是傅立葉變換的基礎(chǔ)公式。 一、傅立葉變換的提出 傅

10、立葉是一位法國(guó)數(shù)學(xué)家和物理學(xué)家,原名是Jean Baptiste Joseph Fourier<1768-1830>, Fourier于1807年在法國(guó)科學(xué)學(xué)會(huì)上發(fā)表了一篇論文,論文里描述運(yùn)用正弦曲線來(lái)描述溫度分布,論文里有個(gè)在當(dāng)時(shí)具有爭(zhēng)議性的決斷：任何連續(xù)周期信號(hào)都可以由一組適當(dāng)?shù)恼仪€組合而成。 當(dāng)時(shí)審查這個(gè)論文拉格朗日?qǐng)?jiān)決反對(duì)此論文的發(fā)表,而后在近50年的時(shí)間里,拉格朗日?qǐng)?jiān)持認(rèn)為傅立葉的方法無(wú)法表示帶有棱角的信號(hào),如在方波中出現(xiàn)非連續(xù)變化斜率。直到拉格朗日死后15年這個(gè)論文才被發(fā)表出來(lái)。 誰(shuí)是對(duì)的呢？拉格朗日是對(duì)的：正弦曲線無(wú)法組合成一個(gè)帶有棱角的信號(hào)。但是,我們可以用正弦曲線來(lái)非

11、常逼近地表示它,逼近到兩種表示方法不存在能量差別,基于此,傅立葉是對(duì)的。 為什么我們要用正弦曲線來(lái)代替原來(lái)的曲線呢？如我們也還可以用方波或三角波來(lái)代替呀,分解信號(hào)的方法是無(wú)窮多的,但分解信號(hào)的目的是為了更加簡(jiǎn)單地處理原來(lái)的信號(hào)。 用正余弦來(lái)表示原信號(hào)會(huì)更加簡(jiǎn)單,因?yàn)檎嘞覔碛性盘?hào)所不具有的性質(zhì)：正弦曲線保真度。一個(gè)正余弦曲線信號(hào)輸入后,輸出的仍是正余弦曲線,只有幅度和相位可能發(fā)生變化,但是頻率和波的形狀仍是一樣的。且只有正余弦曲線才擁有這樣的性質(zhì),正因如此我們才不用方波或三角波來(lái)表示。 二、傅立葉變換分類(lèi)根據(jù)原信號(hào)的不同類(lèi)型,我們可以把傅立葉變換分為四種類(lèi)別： 1、非周期性連續(xù)信號(hào)

12、傅立葉變換〔Fourier Transform 2、周期性連續(xù)信號(hào) 傅立葉級(jí)數(shù) 3、非周期性離散信號(hào) 離散時(shí)域傅立葉變換〔Discrete Time Fourier Transform 4、周期性離散信號(hào) 離散傅立葉變換 下圖是四種原信號(hào)圖例〔從上到下,依次是FT,FS,DTFT,DFT： 這四種傅立葉變換都是針對(duì)正無(wú)窮大和負(fù)無(wú)窮大的信號(hào),即信號(hào)的的長(zhǎng)度是無(wú)窮大的,我們知道這對(duì)于計(jì)算機(jī)處理來(lái)說(shuō)是不可能的,那么有沒(méi)有針對(duì)長(zhǎng)度有限的傅立葉變換呢？沒(méi)有。因?yàn)檎嘞也ū欢x成從負(fù)無(wú)窮小到正無(wú)窮大

13、,我們無(wú)法把一個(gè)長(zhǎng)度無(wú)限的信號(hào)組合成長(zhǎng)度有限的信號(hào)。 面對(duì)這種困難,方法是：把長(zhǎng)度有限的信號(hào)表示成長(zhǎng)度無(wú)限的信號(hào)。如,可以把信號(hào)無(wú)限地從左右進(jìn)行延伸,延伸的部分用零來(lái)表示,這樣,這個(gè)信號(hào)就可以被看成是非周期性離散信號(hào),我們可以用到離散時(shí)域傅立葉變換〔DTFT的方法。也可以把信號(hào)用復(fù)制的方法進(jìn)行延伸,這樣信號(hào)就變成了周期性離散信號(hào),這時(shí)我們就可以用離散傅立葉變換方法〔DFT進(jìn)行變換。本章我們要講的是離散信號(hào),對(duì)于連續(xù)信號(hào)我們不作討論,因?yàn)橛?jì)算機(jī)只能處理離散的數(shù)值信號(hào),我們的最終目的是運(yùn)用計(jì)算機(jī)來(lái)處理信號(hào)的。 但是對(duì)于非周期性的信號(hào),我們需要用無(wú)窮多不同頻率的正弦曲線來(lái)表示,這對(duì)于計(jì)算機(jī)來(lái)

14、說(shuō)是不可能實(shí)現(xiàn)的。所以對(duì)于離散信號(hào)的變換只有離散傅立葉變換〔DFT才能被適用,對(duì)于計(jì)算機(jī)來(lái)說(shuō)只有離散的和有限長(zhǎng)度的數(shù)據(jù)才能被處理,對(duì)于其它的變換類(lèi)型只有在數(shù)學(xué)演算中才能用到,在計(jì)算機(jī)面前我們只能用DFT方法,后面我們要理解的也正是DFT方法。 這里要理解的是我們使用周期性的信號(hào)目的是為了能夠用數(shù)學(xué)方法來(lái)解決問(wèn)題,至于考慮周期性信號(hào)是從哪里得到或怎樣得到是無(wú)意義的。 每種傅立葉變換都分成實(shí)數(shù)和復(fù)數(shù)兩種方法,對(duì)于實(shí)數(shù)方法是最好理解的,但是復(fù)數(shù)方法就相對(duì)復(fù)雜許多了,需要懂得有關(guān)復(fù)數(shù)的理論知識(shí),不過(guò),如果理解了實(shí)數(shù)離散傅立葉變換,再去理解復(fù)數(shù)傅立葉變換就更容易了,所以我們先

15、把復(fù)數(shù)的傅立葉變換放到一邊去,先來(lái)理解實(shí)數(shù)傅立葉變換,在后面我們會(huì)先講講關(guān)于復(fù)數(shù)的基本理論,然后在理解了實(shí)數(shù)傅立葉變換的基礎(chǔ)上再來(lái)理解復(fù)數(shù)傅立葉變換。 還有,這里我們所要說(shuō)的變換雖然是數(shù)學(xué)意義上的變換,但跟函數(shù)變換是不同的,函數(shù)變換是符合一一映射準(zhǔn)則的,對(duì)于離散數(shù)字信號(hào)處理〔DSP,有許多的變換：傅立葉變換、拉普拉斯變換、Z變換、希爾伯特變換、離散余弦變換等,這些都擴(kuò)展了函數(shù)變換的定義,允許輸入和輸出有多種的值,簡(jiǎn)單地說(shuō)變換就是把一堆的數(shù)據(jù)變成另一堆的數(shù)據(jù)的方法。 三、一個(gè)關(guān)于實(shí)數(shù)離散傅立葉變換的例子 先來(lái)看一個(gè)變換實(shí)例,下圖是一個(gè)原始信

16、號(hào)圖像： 這個(gè)信號(hào)的長(zhǎng)度是16,于是可以把這個(gè)信號(hào)分解9個(gè)余弦波和9個(gè)正弦波〔一個(gè)長(zhǎng)度為N的信號(hào)可以分解成N/2+1個(gè)正余弦信號(hào),這是為什么呢？結(jié)合下面的18個(gè)正余弦圖,我想從計(jì)算機(jī)處理精度上就不難理解,一個(gè)長(zhǎng)度為N的信號(hào),最多只能有N/2+1個(gè)不同頻率,再多的頻率就超過(guò)了計(jì)算機(jī)所能所處理的精度范圍,如下圖： 9個(gè)余弦信號(hào)： 9個(gè)正弦信號(hào)： 把以上所有信號(hào)相加即可得到原始信號(hào),至于是怎么分別變換出9種不同頻率信號(hào)的,我們先不急,先看看對(duì)于以上的變換結(jié)果,在程序中又是該怎么表示的,我們可以看看下面這個(gè)示例圖： 上圖中左邊表示時(shí)域中的信號(hào),右邊是頻域信號(hào)表示方法, 從左向右

17、,-->,表示正向轉(zhuǎn)換,從右向左,<--,表示逆向轉(zhuǎn)換, 用小寫(xiě)x[]表示信號(hào)在每個(gè)時(shí)間點(diǎn)上的幅度值數(shù)組, 用大寫(xiě)X[]表示每種頻率的副度值數(shù)組〔即時(shí)間x-->頻率X, 因?yàn)橛蠳/2+1種頻率,所以該數(shù)組長(zhǎng)度為N/2+1, X[]數(shù)組又分兩種,一種是表示余弦波的不同頻率幅度值：Re X[], 另一種是表示正弦波的不同頻率幅度值：Im X[], Re是實(shí)數(shù)的意思,Im是虛數(shù)的意思,采用復(fù)數(shù)的表示方法把正余弦波組合起來(lái)進(jìn)行表示,但這里我們不考慮復(fù)數(shù)的其它作用,只記住是一種組合方法而已,目的是為了便于表達(dá)〔

18、在后面我們會(huì)知道,復(fù)數(shù)形式的傅立葉變換長(zhǎng)度是N,而不是N/2+1。如此,再回過(guò)頭去,看上面的正余弦各9種頻率的變化,相信,問(wèn)題不大了。 第二章、實(shí)數(shù)形式離散傅立葉變換〔Real DFT上一章,我們看到了一個(gè)實(shí)數(shù)形式離散傅立葉變換的例子,通過(guò)這個(gè)例子能夠讓我們先對(duì)傅立葉變換有一個(gè)較為形象的感性認(rèn)識(shí),現(xiàn)在就讓我們來(lái)看看實(shí)數(shù)形式離散傅立葉變換的正向和逆向是怎么進(jìn)行變換的。在此,我們先來(lái)看一下頻率的多種表示方法。 一、 頻域中關(guān)于頻率的四種表示方法 1、序號(hào)表示方法,根據(jù)時(shí)域中信號(hào)的樣本數(shù)取0 ~ N/2,用這種方法在程序中使用起來(lái)可以更直接地取得每種頻率的幅度值,因?yàn)轭l率值跟數(shù)組的序號(hào)是一

19、一對(duì)應(yīng)的: X[k],取值范圍是0 ~ N/2； 2、分?jǐn)?shù)表示方法,根據(jù)時(shí)域中信號(hào)的樣本數(shù)的比例值取0 ~ 0.5: X[?],? = k/N,取值范圍是0 ~ 1/2； 3、用弧度值來(lái)表示,把?乘以一個(gè)2π得到一個(gè)弧度值,這種表示方法叫做自然頻率：X[ω],ω = 2π? = 2πk/N,取值范圍是0 ~ π； 4、以赫茲為單位來(lái)表示,這個(gè)一般是應(yīng)用于一些特殊應(yīng)用,如取樣率為10 kHz表示每秒有10,000個(gè)樣本數(shù)：取值范圍是0到取樣率的一半。 二、 DFT基本函數(shù) ck[i] = cos<2πki/N> sk[i] = sin

20、<2πki/N> 其中k表示每個(gè)正余弦波的頻率,如為2表示在0到N長(zhǎng)度中存在兩個(gè)完整的周期,10即有10個(gè)周期,如下圖： 上圖中至于每個(gè)波的振幅值是怎么算出來(lái)的,這個(gè)是DFT的核心,也是最難理解的部分,我們先來(lái)看看如何把分解出來(lái)的正余弦波合成原始信號(hào)。 三、 合成運(yùn)算方法 DFT合成等式〔合成原始時(shí)間信號(hào),頻率-->時(shí)間,逆向變換： 如果有學(xué)過(guò)傅立葉級(jí)數(shù),對(duì)這個(gè)等式就會(huì)有似曾相識(shí)的感覺(jué),不錯(cuò)！這個(gè)等式跟傅立葉級(jí)數(shù)是非常相似的： 當(dāng)然,差別是肯定是存在的,因?yàn)檫@兩

21、個(gè)等式是在兩個(gè)不同條件下運(yùn)用的,至于怎么證明DFT合成公式,這個(gè)我想需要非常強(qiáng)的高等數(shù)學(xué)理論知識(shí)了,這是研究數(shù)學(xué)的人的工作,對(duì)于普通應(yīng)用者就不需要如此的追根究底了,但是傅立葉級(jí)數(shù)是好理解的,我們起碼可以從傅立葉級(jí)數(shù)公式中看出DFT合成公式的合理性。 _ _ DFT合成等式中的Im X[k]和Re X[k]跟之前提到的Im X[k]和Re X[k]是不一樣的,下面是轉(zhuǎn)換方法〔關(guān)于此公式的解釋,見(jiàn)下文: 但k等于0和N/2時(shí),實(shí)數(shù)部分的計(jì)算要用下面的等式: 上面四個(gè)式中的N是時(shí)域中點(diǎn)的總數(shù),k是從0到N/2的序號(hào)。 為什么要這樣進(jìn)行轉(zhuǎn)換呢？這個(gè)可以從頻譜密度

22、ensity>得到理解,如下圖就是個(gè)頻譜圖： 這是一個(gè)頻譜圖,橫坐標(biāo)表示頻率大小,縱坐標(biāo)表示振幅大小,原始信號(hào)長(zhǎng)度為N〔這里是32,經(jīng)DFT轉(zhuǎn)換后得到的17個(gè)頻率的頻譜,頻譜密度表示每單位帶寬中為多大的振幅,那么帶寬是怎么計(jì)算出來(lái)的呢？看上圖,除了頭尾兩個(gè),其余點(diǎn)的所占的寬度是2/N,這個(gè)寬度便是每個(gè)點(diǎn)的帶寬,頭尾兩個(gè)點(diǎn)的帶寬是1/N,而Im X[k]和Re X[k]表示的是頻譜密度,即每一個(gè)單位帶寬的振幅大小,但表示2/N〔或1/N帶寬的振幅大小,所以分別應(yīng)當(dāng)是Im X[k]和Re X[k]的2/N〔或1/N。 頻譜密度就象物理中物質(zhì)密度,原始信號(hào)中的每一個(gè)點(diǎn)就象是一個(gè)混合物,這個(gè)混

23、合物是由不同密度的物質(zhì)組成的,混合物中含有的每種物質(zhì)的質(zhì)量是一樣的,除了最大和最小兩個(gè)密度的物質(zhì)外,這樣我們只要把每種物質(zhì)的密度加起來(lái)就可以得到該混合物的密度了,又該混合物的質(zhì)量是單位質(zhì)量,所以得到的密度值跟該混合物的質(zhì)量值是一樣的。 至于為什么虛數(shù)部分是負(fù)數(shù),這是為了跟復(fù)數(shù)DFT保持一致,這個(gè)我們將在后面會(huì)知道這是數(shù)學(xué)計(jì)算上的需要〔Im X[k]在計(jì)算時(shí)就已經(jīng)加上了一個(gè)負(fù)號(hào)〔稍后,由下文,便可知,再加上負(fù)號(hào),結(jié)果便是正的,等于沒(méi)有變化。 如果已經(jīng)得到了DFT結(jié)果,這時(shí)要進(jìn)行逆轉(zhuǎn)換,即合成原始信號(hào),則可按如下步驟進(jìn)行轉(zhuǎn)換： 1、先根據(jù)上面四個(gè)式子計(jì)算得出的值； 2、再根據(jù)DFT

24、合成等式得到原始信號(hào)數(shù)據(jù)。 下面是用BASIC語(yǔ)言來(lái)實(shí)現(xiàn)的轉(zhuǎn)換源代碼： 100 ‘DFT逆轉(zhuǎn)換方法 110 ‘/XX[]數(shù)組存儲(chǔ)計(jì)算結(jié)果〔時(shí)域中的原始信號(hào) 120 ‘/REX[]數(shù)組存儲(chǔ)頻域中的實(shí)數(shù)分量,IMX[]為虛分量 130 ‘ 140 DIM XX[511] 150 DIM REX[256] 160 DIM IMX[256] 170 ‘ 180 PI = 3.14159265 190 N% = 512 200 ‘ 210 GOSUB XXXX ‘轉(zhuǎn)到子函數(shù)去獲取REX[]和IMX[]數(shù)據(jù) 220 ‘ 230 ‘ 240 ‘ 250 FOR K% = 0

25、 TO 256 260 REX[K%] = REX[K%] / 270 IMX[K%] = -IMX[K%] / 280 NEXT k% 290 ‘ 300 REX[0] = REX[0] / N 310 REX[256] = REX[256] / N 320 ‘ 330 ‘ 初始化XX[]數(shù)組 340 FOR I% = 0 TO 511 350 XX[I%] = 0 360 NEXT I% 370 ‘ 380 ‘ 390 ‘ 400 ‘ 410 ‘ 420 FOR K% =0 TO 256 430 FOR I%=0 TO 511

26、 440 ‘ 450 XX[I%] = XX[I%] + REX[K%] * COS<2 * PI * K% * I% / N%> 460 XX[I%] = XX[I%] + IMX[K%] * SIN<2 * PI * K% * I% / N%> 470 ‘ 480 NEXT I% 490 NEXT K% 500 ‘ 510 END 上面代碼中420至490換成如下形式也許更好理解,但結(jié)果都是一樣的： 420 FOR I% =0 TO 511 430 FOR K%=0 TO 256 440 ‘ 450 XX[I%] = XX[I%] + REX[K%] * C

27、OS<2 * PI * K% * I% / N%> 460 XX[I%] = XX[I%] + IMX[K%] * SIN<2 * PI * K% * I% / N%> 470 ‘ 480 NEXT I% 490 NEXT K% 四、 分解運(yùn)算方法〔DFT 有三種完全不同的方法進(jìn)行DFT：一種方法是通過(guò)聯(lián)立方程進(jìn)行求解, 從代數(shù)的角度看,要從N個(gè)已知值求N個(gè)未知值,需要N個(gè)聯(lián)立方程,且N個(gè)聯(lián)立方程必須是線性獨(dú)立的,但這是這種方法計(jì)算量非常的大且極其復(fù)雜,所以很少被采用；第二種方法是利用信號(hào)的相關(guān)性〔correlation進(jìn)行計(jì)算,這個(gè)是我們后面將要介紹的方法；第三種方法是快速

28、傅立葉變換〔FFT,這是一個(gè)非常具有創(chuàng)造性和革命性的的方法,因?yàn)樗蟠筇岣吡诉\(yùn)算速度,使得傅立葉變換能夠在計(jì)算機(jī)中被廣泛應(yīng)用,但這種算法是根據(jù)復(fù)數(shù)形式的傅立葉變換來(lái)實(shí)現(xiàn)的,它把N個(gè)點(diǎn)的信號(hào)分解成長(zhǎng)度為N的頻域,這個(gè)跟我們現(xiàn)在所進(jìn)行的實(shí)域DFT變換不一樣,而且這種方法也較難理解,這里我們先不去理解,等先理解了復(fù)數(shù)DFT后,再來(lái)看一下FFT。有一點(diǎn)很重要,那就是這三種方法所得的變換結(jié)果是一樣的,經(jīng)過(guò)實(shí)踐證明,當(dāng)頻域長(zhǎng)度為32時(shí),利用相關(guān)性方法進(jìn)行計(jì)算效率最好,否則FFT算法效率較高?，F(xiàn)在就讓我們來(lái)看一下相關(guān)性算法。 利用第一種方法、信號(hào)的相關(guān)性可以從噪聲背景中檢測(cè)出

29、已知的信號(hào),我們也可以利用這個(gè)方法檢測(cè)信號(hào)波中是否含有某個(gè)頻率的信號(hào)波：把一個(gè)待檢測(cè)信號(hào)波乘以另一個(gè)信號(hào)波,得到一個(gè)新的信號(hào)波,再把這個(gè)新的信號(hào)波所有的點(diǎn)進(jìn)行相加,從相加的結(jié)果就可以判斷出這兩個(gè)信號(hào)的相似程度。如下圖： 上面a和 b兩個(gè)圖是待檢測(cè)信號(hào)波,圖a很明顯可以看出是個(gè)3個(gè)周期的正弦信號(hào)波,圖b的信號(hào)波則看不出是否含有正弦或余弦信號(hào),圖c和d都是個(gè)3個(gè)周期的正弦信號(hào)波,圖e和f分別是a、b兩圖跟c、d兩圖相乘后的結(jié)果,圖e所有點(diǎn)的平均值是0.5,說(shuō)明信號(hào)a含有振幅為1的正弦信號(hào)c,但圖f所有點(diǎn)的平均值是0,則說(shuō)明信號(hào)b不含有信號(hào)d。這個(gè)就是通過(guò)信號(hào)相關(guān)性來(lái)檢測(cè)是否含有某個(gè)信號(hào)的方法。

30、 第二種方法：相應(yīng)地,我也可以通過(guò)把輸入信號(hào)和每一種頻率的正余弦信號(hào)進(jìn)行相乘〔關(guān)聯(lián)操作,從而得到原始信號(hào)與每種頻率的關(guān)聯(lián)程度〔即總和大小,這個(gè)結(jié)果便是我們所要的傅立葉變換結(jié)果,下面兩個(gè)等式便是我們所要的計(jì)算方法： 第二個(gè)式子中加了個(gè)負(fù)號(hào),是為了保持復(fù)數(shù)形式的一致,前面我們知道在計(jì)算時(shí)又加了個(gè)負(fù)號(hào),所以這只是個(gè)形式的問(wèn)題,并沒(méi)有實(shí)際意義,你也可以把負(fù)號(hào)去掉,并在計(jì)算時(shí)也不加負(fù)號(hào)。 這里有一點(diǎn)必須明白一個(gè)正交的概念：兩個(gè)函數(shù)相乘,如果結(jié)果中的每個(gè)點(diǎn)的總和為0,則可認(rèn)為這兩個(gè)函數(shù)為正交函數(shù)。要確保關(guān)聯(lián)性算法是正確的,則必須使得跟原始信號(hào)相乘的信號(hào)的函數(shù)形式是正交的,我們知道所有的正弦或余弦函

31、數(shù)是正交的,這一點(diǎn)我們可以通過(guò)簡(jiǎn)單的高數(shù)知識(shí)就可以證明它,所以我們可以通過(guò)關(guān)聯(lián)的方法把原始信號(hào)分離出正余弦信號(hào)。當(dāng)然,其它的正交函數(shù)也是存在的,如：方波、三角波等形式的脈沖信號(hào),所以原始信號(hào)也可被分解成這些信號(hào),但這只是說(shuō)可以這樣做,卻是沒(méi)有用的。 下面是實(shí)域傅立葉變換的BASIC語(yǔ)言代碼： 到此為止,我們對(duì)傅立葉變換便有了感性的認(rèn)識(shí)了吧。但要記住,這只是在實(shí)域上的離散傅立葉變換,其中雖然也用到了復(fù)數(shù)的形式,但那只是個(gè)替代的形式,并無(wú)實(shí)際意義,現(xiàn)實(shí)中一般使用的是復(fù)數(shù)形式的離散傅立葉變換,且快速傅立葉變換是根據(jù)復(fù)數(shù)離散傅立葉變換來(lái)設(shè)計(jì)算法的,在后面我們先來(lái)復(fù)習(xí)一下有關(guān)復(fù)數(shù)的內(nèi)容,然后再在理解實(shí)域離散傅立葉變換的基礎(chǔ)上來(lái)理解復(fù)數(shù)形式的離散傅立葉變換。更多見(jiàn)下文：十、從頭到尾徹底理解傅里葉變換算法、下〔July、dznlong 本人July對(duì)本博客所有任何文章、內(nèi)容和資料享有版權(quán)。轉(zhuǎn)載務(wù)必注明作者本人及出處,并通知本人。二零一一年二月二十一日。 .