傅里葉變換算法詳細(xì)介紹

1、傅里葉變換算法詳細(xì)介紹作者:日期:從頭到尾徹底理解傅里葉變換算法、上 、八前言第一部分、DFT第一章、傅立葉變換的由來第二章、實(shí)數(shù)形式離散傅立葉變換(Rea 1 DF T)從頭到尾徹底理解傅里葉變換算法、下第四章、復(fù)數(shù)形式離散傅立葉變換/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */這一片的傅里葉變換算法，講解透徹，希望對(duì)大家會(huì)有所幫助。 感謝原作者們 J U ly、dz nio n g)的精心編寫。/* * * * * * * * * * * * * * * * * * * * * *

2、* * * * * * * * * * * */前言：？關(guān)于傅立葉變換，無論是書本還是在網(wǎng)上可以很容易找到關(guān)于傅立葉變換的描述,，讓但是大都是些故弄玄虛的文章，太過抽象，盡是一些讓人看了就望而生畏的公式的羅列人很難能夠從感性上得到理解”-dzniong ,那么,到底什么是傅里葉變換算法列？傅里葉變換所涉及到的公式具體有多復(fù)雜列傅里葉變換(F 0 urier tra nsfo rm )是一種線性的積分變換。因其基本思想首先由法國(guó) 學(xué)者傅里葉系統(tǒng)地提出，所以以其名字來命名以示紀(jì)念。哦，傅里葉變換原來就是一種變換而已，只是這種變換是從時(shí)間轉(zhuǎn)換為頻率的變化。這下,你就知道了，傅里葉就是一種變換， 一種

3、什么變換列？就是一種從時(shí)間到頻率的變化或其相 互轉(zhuǎn)化。，也順便看看傅里ok,咱們?cè)賮砜傮w了解下傅里葉變換，讓各位對(duì)其有個(gè)總體大概的印象葉變換所涉及到的公式，究竟有多復(fù)雜:以下就是傅里葉變換的 4種變體(摘自，維基百科)連續(xù)傅里葉變換？ 一般情況下，若傅里葉變換”一詞不加任何限定語，則指的是 連續(xù)傅里葉變換”。連續(xù)傅里葉變換將平方可積的函數(shù)f (t)表示成復(fù)指數(shù)函數(shù)的積分或級(jí)數(shù)形式。川丄)=鬥丁=川)Ln這是將頻率域的函數(shù)F( 3表示為時(shí)間域的函數(shù)f (t)的積分形式。連續(xù)傅里葉變換的逆變換(inv e rse F ou r ie r t r ans f orm)為:f=廠甘3)=y FS 叫0

4、30即將時(shí)間域的函數(shù)f(t)表示為頻率域的函數(shù)F( 3 的積分。般可稱函數(shù)f(t )為原函數(shù)，而稱函數(shù)F( 3)為傅里葉變換的像函數(shù)，原函數(shù)和像函數(shù)構(gòu)成一個(gè)傅里葉變換對(duì)(tran s f o rm p a ir)。除此之外，還有其它型式的變換對(duì)，以下兩種型式亦常被使用。在通信或是信號(hào)處理方面 常以2 7?來代換，而形成新的變換對(duì)：X/)=嚴(yán)工=f T(f)嚴(yán)H dt DCC工(0 =廠】氐(門=x(yv呵暢.或者是因系數(shù)重分配而得到新的變換對(duì):川）=廠1£3）=書IF（2）耳應(yīng)皿.m)er 叫 f兀一種對(duì)連續(xù)傅里葉變換的推廣稱為分?jǐn)?shù)傅里葉變換（Fractional Fouri e r

5、 T ra n sf o rm)。 分?jǐn)?shù)傅里葉變換(fracti o nal F ou rier tr a nsf o rm ,FRFT)指的就是傅里葉變換 (Fouriertransform , FT)的廣義化。分?jǐn)?shù)傅里葉變換的物理意義即做傅里葉變換a次，其中 a不一定要為整數(shù)；而做了分?jǐn)?shù)傅里葉變換之后，信號(hào)或輸入函數(shù)便會(huì)出現(xiàn)在介于時(shí)域（time doma i n）與頻域（f re quency domain) 之間的分?jǐn)?shù)域 (fr ac tio na l d omain)。當(dāng)f（t）為偶函數(shù)（或奇函數(shù)）時(shí)，其正弦（或余弦）分量將消亡，而可以稱這時(shí)的變換為余弦變換(cosi n e tr a

6、n sf or m) 或正弦變換 (s ine tran sform).另一個(gè)值得注意的性質(zhì)是，當(dāng)f （t）為純實(shí)函數(shù)時(shí),傅里葉級(jí)數(shù)？連續(xù)形式的傅里葉變換其實(shí)是傅里葉級(jí)數(shù)(Fou r ier se ries)的推廣，因?yàn)?，其傅里葉級(jí)數(shù)是存在的積分其實(shí)是一種極限形式的求和算子而已。對(duì)于周期函數(shù)OCIn=其中Fn為復(fù)幅度。對(duì)于實(shí)值函數(shù)屈數(shù)的傅里葉級(jí)數(shù)可以寫成OCQ譏 cos(?iz) + ® SUl(nT)?其中an和bn是實(shí)頻率分量的幅度。離散時(shí)域傅里葉變換？離散傅里葉變換是離散時(shí)間傅里葉變換（DTF T）的特例（有時(shí)作為后者的近似）。DTFT在時(shí)域上離散，在頻域上則是周期的。DTFT

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

8、,將函數(shù)xn表示為下面的求和形式其中X k是傅里葉幅度。直接使用這個(gè)公式計(jì)算的計(jì)算復(fù)雜度為O（n*n ）,而快速傅里葉變換（FF T）可以將復(fù)雜度改進(jìn)為 0（ n *l g n ）o（后面會(huì)具體闡述F （n * Ig n）的。）計(jì)算復(fù)雜度的降低以及數(shù)字電路計(jì)算能力的發(fā)展使得 領(lǐng)域十分實(shí)用且重要的方法。FT是如何將復(fù)雜度降為ODF T成為在信號(hào)處理F面，比較下上述傅立葉變換的4種變體,變換時(shí)閭am連續(xù)傅里葉變換連續(xù),非周期性;連續(xù),非周期性傅里葉級(jí)數(shù)非周期性1離散時(shí)間傅里葉變換離散,周期性離散里葉變換:離散,周期性離散,周期性如上，容易發(fā)現(xiàn)：函數(shù)在時(shí)（頻）域的離散對(duì)應(yīng)于其像函數(shù)在頻（時(shí)）域的周期

9、性。反之連續(xù)則意味著在對(duì)應(yīng)域的信號(hào)的非周期性。也就是說，時(shí)間上的離散性對(duì)應(yīng)著頻率上的周期性。同時(shí),注意，離散時(shí)間傅里葉變換，時(shí)間離散，頻率不離散，它在頻域依然是連續(xù)的。如果,讀到此,你不甚明白，大沒關(guān)系，不必糾結(jié)于以上4種變體，繼續(xù)往下看，你自會(huì)豁然 開朗。（有什么問題，也懇請(qǐng)?zhí)岢?，或者批評(píng)指正）0 k,本文,接下來，由傅里葉變換入手，后重點(diǎn)闡述離散傅里葉變換、快速傅里葉算法,到最后徹底實(shí)現(xiàn)FFT算法,全篇力求通俗易懂、閱讀順暢，教你從頭到尾徹底理解傅里葉變換算法。由于傅里葉變換，也稱傅立葉變換，下文所稱為傅立葉變換，同一個(gè)變換，不同叫法，讀者不必感到奇怪。第一部分、D FT ?第一章、傅立葉

10、變換的由來要理解傅立葉變換，先得知道傅立葉變換是怎么變換的礎(chǔ),最基本的是級(jí)數(shù)變換，其中傅立葉級(jí)數(shù)變換是傅立葉變換的基礎(chǔ)公式。，當(dāng)然，也需要一定的高等數(shù)學(xué)基一、傅立葉變換的提出傅立葉是一位法國(guó)數(shù)學(xué)家和物理學(xué)家，原名是Je an Bap t is t e Jose ph Fourier( 1 768- 1 830 ) , Fouri e r于1 8 0 7年在法國(guó)科學(xué)學(xué)會(huì)上發(fā)表了一篇論文，論文里描述運(yùn)用正弦曲線來描述溫度分布，論文里有個(gè)在當(dāng)時(shí)具有爭(zhēng)議性的決斷:任何連續(xù)周期信號(hào)都可以由一組適當(dāng)?shù)恼仪€組合而成。當(dāng)時(shí)審查這個(gè)論文拉格朗日?qǐng)?jiān)決反對(duì)此論文的發(fā)表，而后在近 日?qǐng)?jiān)持認(rèn)為傅立葉的方法無法表示帶

11、有棱角的信號(hào)5 0年的時(shí)間里，拉格朗,如在方波中出現(xiàn)非連續(xù)變化斜率。直到拉格朗日死后15年這個(gè)論文才被發(fā)表出來。誰是對(duì)的呢？拉格朗日是對(duì)的：正弦曲線無法組合成一個(gè)帶有棱角的信號(hào)。但是，我們可以用正弦曲線來非常逼近地表示它，逼近到兩種表示方法不存在能量差別，基于此，傅立葉是對(duì)的。為什么我們要用正弦曲線來代替原來的曲線呢？如我們也還可以用方波或三角波來代替 呀，分解信號(hào)的方法是無窮多的 ，但分解信號(hào)的目的是為了更加簡(jiǎn)單地處理原來的信號(hào)。? 用正余弦來表示原信號(hào)會(huì)更加簡(jiǎn)單，因?yàn)檎嘞覔碛性盘?hào)所不具有的性質(zhì)：正弦曲線 保真度。一個(gè)正余弦曲線信號(hào)輸入后，輸出的仍是正余弦曲線，只有幅度和相位可能發(fā)生變化

12、，但是頻率和波的形狀仍是一樣的。且只有正余弦曲線才擁有這樣的性質(zhì)，正因如此我們 才不用方波或三角波來表示。二、傅立葉變換分類根據(jù)原信號(hào)的不同類型，我們可以把傅立葉變換分為四種類別:1、非周期性連續(xù)信號(hào)傅立葉變換(Fo urier Trans f orm) 2?、周期性連續(xù)信傅立葉級(jí)數(shù)(Fou ri er Se rie s) 3?、非周期性離散信號(hào)離散時(shí)域傅立葉變換(D iscrete Time Fo ur ier T ra n sform )4、周期性離散信號(hào)離散傅立葉變換(DiscreteFo u r ie r Tr ansf orm) ?F圖是四種原信號(hào)圖例(從上到下，依次是F T ,FS

13、,D TF T, DF T ):Fourier Series,si即說 b rfiar at e conrinroifs 曲汩 pnodicDiscreie Time Fourier Traiisfomi sigriah fharare d賦冉館 皿丁日qi品Discrete Foiinei Traii5>fann fignch rhn：dfgcre館 andType of TransformFoutier TinsfoiinExample Siena I這四種傅立葉變換都是針對(duì)正無窮大和負(fù)無窮大的信號(hào)，即信號(hào)的的長(zhǎng)度是無窮大的，我們知道這對(duì)于計(jì)算機(jī)處理來說是不可能的，那么有沒有針對(duì)長(zhǎng)度

14、有限的傅立葉變換呢？沒有。因?yàn)檎嘞也ū欢x成從負(fù)無窮小到正無窮大,我們無法把一個(gè)長(zhǎng)度無限的信號(hào)組合成長(zhǎng)度有限的信號(hào)。面對(duì)這種困難，方法是：把長(zhǎng)度有限的信號(hào)表示成長(zhǎng)度無限的信號(hào)。女口，可以把信號(hào)無限地從左右進(jìn)行延伸，延伸的部分用零來表示，這樣，這個(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ī)來處理信號(hào)的。? 但是

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

16、散傅立葉變換(real DFT )，再去理解復(fù)數(shù)傅立葉變換就更容易了，所以我們先把復(fù)數(shù)的傅立葉變換放到一邊去，先來理解實(shí)數(shù)傅立葉變換，在后面我們會(huì)先講講關(guān)于復(fù)數(shù)的基本理論，然后在理解了實(shí)數(shù)傅立葉變換的基礎(chǔ)上再來理解復(fù)數(shù)傅立葉變換。還有，這里我們所要說的變換(t r a nsfo r m)雖然是數(shù)學(xué)意義上的變換，但跟函數(shù)變換是不同的，函數(shù)變換是符合一一映射準(zhǔn)則的，對(duì)于離散數(shù)字信號(hào)處理(D S P),有許多的變換:傅立葉變換、拉普拉斯變換、Z變換、希爾伯特變換、離散余弦變換等，這些都擴(kuò)展了函數(shù)變換的定義，允許輸入和輸出有多種的值，簡(jiǎn)單地說變換就是把一堆的數(shù)據(jù)變成另一堆的數(shù)據(jù)的方法。？三、一個(gè)關(guān)于實(shí)

17、數(shù)離散傅立葉變換(Real D FT)的例子先來看一個(gè)變換實(shí)例，下圖是一個(gè)原始信號(hào)圖像8040'0十丄丄i 丁早1-丄II4-404aSanjple iLumbeiL6這個(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é)合下面的1 8個(gè)正余弦圖，我想從計(jì)算機(jī)處理精度上就不難理解，一個(gè)長(zhǎng)度為N的信號(hào)，最多只能有N /2+1個(gè)不同頻率，再多的頻率就超過了計(jì)算機(jī)所能所處理的精度范圍)，如下圖:9個(gè)余弦信號(hào)：Cosine Waves器十4-43 Q 1? 14 leP4IIMII-> I叩* 牛+

18、畳出*I4-4h-441 I f II a1 i & 10 12 14 16":冷泠泠冷I I p p I -1*J ” ” = = F J B h -1'I'0丄占 & ta It 14 16_b1C-.£-，-4 d S 13 12 14 11S- 03 IQ 12 14 1(0-44£81< 12 14 If9個(gè)正弦信號(hào)：Sine Waves141IIr>IHIIP寸I4P01 f * f4r* -ii fI t=i=t I0?46 a 10 12 U 11 I P 1 h P Isdi_f_Ifii_I 0：46

19、 S 10 12 L4 I4Q :4 fl a 10 12 U 1把以上所有信號(hào)相加即可得到原始信號(hào)，至于是怎么分別變換出9種不同頻率信號(hào)的，我們先不急，先看看對(duì)于以上的變換結(jié)果，在程序中又是該怎么表示的，我們可以看看下面這個(gè)示例圖：Time DomainI I 1 I I I I L I 1 J【I J I I 0N samplesFrequency DomainReX0N/2W L sawpl eifcojinp iirai'f Hi骨】zcollecli V ely r e fen ecl to as X上圖中左邊表示時(shí)域中的信號(hào)，右邊是頻域信號(hào)表示方法，？從左向右，- >

20、,表示正向轉(zhuǎn)換(Fo r ward DF T),從右向左,信號(hào)在每個(gè)時(shí)間點(diǎn)上的幅度值數(shù)組<-,表示逆向轉(zhuǎn)換 (In ve rse D FT),?用小寫x表示,用大寫X :表示每種頻率的副度值數(shù)組(即時(shí)間x- >頻率X),因?yàn)橛蠳/2+ 1種頻率，所以該數(shù)組長(zhǎng)度為N/2+1 ,X數(shù)組又分兩種，一種是表示余弦波的不同頻率幅度值：R e X: ,?另一種是表示正弦 波的不同頻率幅度值：ImX,Re是實(shí)數(shù)(Real)的意思，1m是虛數(shù)(I m agi ne)的意思，采用復(fù)數(shù)的表示方法把正余弦波 組合起來進(jìn)行表示，但這里我們不考慮復(fù)數(shù)的其它作用，只記住是一種組合方法而已，目的N，而不是N /

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

22、的：X :k，取值范圍是0-N/2 ;2、分?jǐn)?shù)表示方法，根據(jù)時(shí)域中信號(hào)的樣本數(shù)的比例值取 圍是0 1 / 2 ;10 - 0. 5 : X ?: ,? = k/N，取值范3、用弧度值來表示，把 ？乘以一個(gè)2n得到一個(gè)弧度值，這種表示方法叫做自然頻率(natural freq u enc y ): X w w = 2 n ? = 2n k /N，取值范圍是0n 4?、以赫茲(Hz)為單位來表示，這個(gè)一般是應(yīng)用于一些特殊應(yīng)用，如取樣率為10 kHz表示每秒有10 , 000個(gè)樣本數(shù)：取值范圍是 0到取樣率的一半。D FT基本函數(shù)si n (2 nki /N)? 其中k表示每個(gè)正余弦波的頻率ck i

23、 = co s (2 n 0N)?sk i 如為也iA'-li2st JIITffi,o一二上 d=L 氓2表示在0到N長(zhǎng)度中存在兩個(gè)完整的周期，1 0即有10個(gè)周期，如下圖：4S«24ample ifiiniJber上圖中至于每個(gè)波的振幅 (amplitude )值(R e X k：,1 m X k)是怎么算出來的，這個(gè)是D FT的核心，也是最難理解的部分，我們先來看看如何把分解出來的正余弦波合成原始信號(hào)(I nv e rse D FT )。？ ？三、合成運(yùn)算方法(R e al In ver se DF T)?D FT合成等式(合成原始 時(shí)間信號(hào) 瀕率-> 時(shí)間，逆向

24、變換):vl/=N'?._工 ReXK cx)s(2tt和/y) + 工 刖聶R 燈/N) k=(i如果有學(xué)過傅立葉級(jí)數(shù)，對(duì)這個(gè)等式就會(huì)有似曾相識(shí)的感覺，不錯(cuò)!這個(gè)等式跟傅立葉級(jí)數(shù)是非常相似的:OOf (a*)二寸 + 2(叭 cosA;v + ® sin ,y)k1當(dāng)然,差別是肯定是存在的，因?yàn)檫@兩個(gè)等式是在兩個(gè)不同條件下運(yùn)用的，至于怎么證明D FT合成公式，這個(gè)我想需要非常強(qiáng)的高等數(shù)學(xué)理論知識(shí)了，這是研究數(shù)學(xué)的人的工作,對(duì)于普通應(yīng)用者就不需要如此的追根究底了，但是傅立葉級(jí)數(shù)是好理解的，我們起碼可以從傅立葉級(jí)數(shù)公式中看出 DFT合成公式的合理性。DFT合成等式中的Im Xk

25、和R e X k:跟之前提到的Im Xk和Re Xk是不一樣的，下面是轉(zhuǎn)換方法（關(guān)于此公式的解釋，見下文）：ReX k M2但k等于0和N/ 2時(shí),實(shí)數(shù)部分的計(jì)算要用下面的等式ReXQReXQRcXNi2jReX N/2 為什么要這樣上面四個(gè)式中的 N是時(shí)域中點(diǎn)的總數(shù)，k是從0到N/2的序號(hào)。T 進(jìn)行轉(zhuǎn)換呢？這個(gè)可以從頻譜密度（S pe C t ra l densi t y）得到理解，如下圖就是個(gè)頻譜圖：10S-I I I! ! I! L lai! i! i iI I I ill ri f I !I i I I f II illI卜I山 11 LN1f1JP11a'片11 1 1 1!

26、q111 r 1nr1E111111i1i IJN1 L 1 - 1 _ t " I '-I1inIiI1 I I I IBi45C>7B910 IL 1； IJ 1+1510Frequtncy sangjle imnibM這是一個(gè)頻譜圖，橫坐標(biāo)表示頻率大小，縱坐標(biāo)表示振幅大小，原始信號(hào)長(zhǎng)度為 N （這里是3 2 ），經(jīng)DFT轉(zhuǎn)換后得到的1 7個(gè)頻率的頻譜，頻譜密度表示每單位帶寬中為多大的振幅，那么帶寬是怎么計(jì)算出來的呢？看上圖，除了頭尾兩個(gè)，其余點(diǎn)的所占的寬度是2/N，這個(gè)寬度便是每個(gè)點(diǎn)的帶寬，頭尾兩個(gè)點(diǎn)的帶寬是1/N,而Im X k和Re X :k表示的是頻振幅大小

27、，所以I皿袞兇和X （kJ譜密度，即每一個(gè)單位帶寬的振幅大小，但I(xiàn)皿和尺亡X網(wǎng)表示2 /N（或1/N ）帶寬的 分別應(yīng)當(dāng)是I m X k和Re X : k的2 /N（或1 /N）。?頻譜密度就象物理中物質(zhì)密度，原始信號(hào)中的每一個(gè)點(diǎn)就象是一個(gè)混合物，這個(gè)混合物是由不同密度的物質(zhì)組成的，混合物中含有的每種物質(zhì)的質(zhì)量是一樣的，除了最大和最小兩個(gè)密 度的物質(zhì)外，這樣我們只要把每種物質(zhì)的密度加起來就可以得到該混合物的密度了，又該混 合物的質(zhì)量是單位質(zhì)量，所以得到的密度值跟該混合物的質(zhì)量值是一樣的。至于為什么虛數(shù)部分是負(fù)數(shù)，這是為了跟復(fù)數(shù) DFT保持一致，這個(gè)我們將在后面會(huì)知 道這是數(shù)學(xué)計(jì)算上的需要 （I

28、 m X : k 在計(jì)算時(shí)就已經(jīng)加上了一個(gè)負(fù)號(hào)（ 稍后，由下文，便可 知），Tm X國(guó)再加上負(fù)號(hào)，結(jié)果便是正的，等于沒有變化）。如果已經(jīng)得到了D FT結(jié)果，這時(shí)要進(jìn)行 逆轉(zhuǎn)換,即合成原始信號(hào)，則可按如下步驟進(jìn)行轉(zhuǎn)換：1?、先根據(jù)上面四個(gè)式子計(jì)算得出hn Xk和艮ft元関的值；2、再根據(jù)D FT合成等式得到原始信號(hào)數(shù)據(jù)。F面是用BA S IC語言來實(shí)現(xiàn)的轉(zhuǎn)換源代碼:100D FT逆轉(zhuǎn)換方法110'/XX數(shù)組存儲(chǔ)計(jì)算結(jié)果(時(shí)域中的原始信號(hào))R/EX 數(shù)組存儲(chǔ)頻域中的實(shí)數(shù)分量，IMX :為虛分量130?'140 DIM X X 511 150? DI M R EX2 5 6: 1?

29、6 0 DIM IMX25 6 1 7 0180? PI = 3 .1415 9 26 5190 N% =51 2 210? '200? GO SUB XXXX 轉(zhuǎn)到子函數(shù)去獲取 RE X 和IMX 數(shù)據(jù)22 0230'2 4 025 0FORK% = 0 T O 256260R EX:K % = REXK% :/ (N%/2)I MX K % = -IMXK% / (N %/2)2?8 0 N EX T k %2900?O REX 0：REX0 / N ? 3 1 0 REX : 256=REX25 6 / N330?初始化 XX:數(shù)組 340 ? F OR I% = 0 T

30、O 511?3 50 XX I% = 0N EXT I390?40? 04 10 420 F O R K% =0 TO 256 430 F O R I % = 0 TO 5 1 1440X X： I% = XXI % + R E X :K% * COS(2* PI *K%* I%N %)/ N%)XX : I %：= XX : I% + I MX : K % * S IN(2 * PI * K % *47080? NEXT I% 490? NE XT K %5?'500? 1 0 END ?上面代碼中4 20至4 9 0換成如下形式也許更好理解，但結(jié)果都是一樣的:FO R I% =0

31、TO 51143 0F O R K % = 0 T O 2564 40450X X I %= XX I % + R E X： K%* COS(2 * P I * K% *N%)?46 0 XXI% = XX : I % + I M XK% *SI N(2 * P I * K% * I % / N%)4?7 0分解運(yùn)算方法(DFT)4 8 0 NEX T I%?4 90 N EX T K %?四、看，要從N個(gè)已知值求N個(gè)未知值，需要N個(gè)聯(lián)立方程，且N個(gè)聯(lián)立方程必須是線性獨(dú)立的有三種完全不同的方法進(jìn)行DFT : 一種方法是通過聯(lián)立方程進(jìn)行求解，從代數(shù)的角度但這是這種方法計(jì)算量非常的大且極其復(fù)雜，所

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

33、FFT算法效率較高?，F(xiàn)在就讓我們來看一下相關(guān)性算法。？ ？利用第一種方法、信號(hào)的相關(guān)性(cor relat i o n )可以從噪聲背景中檢測(cè)出已知的信號(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)的相似程度。如下圖:-1Exampl 亡 1Example 2¥flj J 囂11訊§1»1七啦電 atiMyRMi Ita-J- 期巧凹唆I 隔 ng aaaWzed lai >o丈上社匚二-i!1諺JZ*s站崢I(yè)f-f

34、l1#i2Alba辛也 runtiQii br-inff ukHi-* 巨一1-S*-dl ba Th fniKti?口 htinjjr- * - 一 了廠 了- I O IIS膽則JlUp睦 DUtBlbeT卜珂7】If T】f】I-匚 -叮二 一t - 一一=IB I+-flarabtf1!l!H: :Y'll IIIy -b. !H)7Sxuap> nHtwFIGURE S-STwocxiiiiple凱回S 1(J)mide3JCulyzcdfai cocixjuxiug;tlw 'prifkb朋i、fbiiv：旳n ihg® nice) and«

35、;曲 和戸產(chǎn)(e)咼d (f) 5hcnv th? fult irulnplvie乍.uauh ampE?勺孚麗1 by tfae 蘇 fbcicricjfl FiEiire (e) hag an a:«3g< GfO ? mdiciiin? fhai tir KoaMim ihelKiusfinjccionmvith, wauqjbnid( of 1 0 Coiimidy. «0 a zero avciope uidicaiin diat :does not cotam 注it basis fuactioa上面a和b兩個(gè)圖是待檢測(cè)信號(hào)波，圖a很明顯可以看出是個(gè) 3個(gè)

36、周期的正弦信號(hào)c和d都是個(gè)3個(gè)周期的正弦信波，圖b的信號(hào)波則看不出是否含有正弦或余弦信號(hào)，圖 號(hào)波，圖e和f分別是a、 b兩圖跟c、d兩圖相乘后的結(jié)果，圖 e所有點(diǎn)的平均值是 0.5 ,說明信號(hào)a含有振幅為1的正弦信號(hào)C,但圖f所有點(diǎn)的平均值是0,則說明信號(hào)b不含有信號(hào)d。這個(gè)就是通過信號(hào)相關(guān)性來檢測(cè)是否含有某個(gè)信號(hào)的方法。第二種方法：相應(yīng)地，我也可以通過把輸入信號(hào)和每一種頻率的正余弦信號(hào)進(jìn)行相乘（關(guān)聯(lián)操作）,從而得到原始信號(hào)與每種頻率的關(guān)聯(lián)程度（即總和大小），這個(gè)結(jié)果便是我們所要的傅立葉變換結(jié)果，下面兩個(gè)等式便是我們所要的計(jì)算方法：ReXkN -1工丫打 cos(2;/r;7jV)J - 0

37、IinXk.V-1刀*訂 sm(2nki /N J - 0第二個(gè)式子中加了個(gè)負(fù)號(hào)，是為了保持復(fù)數(shù)形式的一致，前面我們知道在計(jì)算】m靈兇時(shí)又加了個(gè)負(fù)號(hào)，所以這只是個(gè)形式的問題，并沒有實(shí)際意義，你也可以把負(fù)號(hào)去掉 算|l皿X閑時(shí)也不加負(fù)號(hào)。，并在計(jì)這里有一點(diǎn)必須明白一個(gè)正交的概念：兩個(gè)函數(shù)相乘，如果結(jié)果中的每個(gè)點(diǎn)的總和為0,則可認(rèn)為這兩個(gè)函數(shù)為正交函數(shù)。要確保關(guān)聯(lián)性算法是正確的，則必須使得跟原始信號(hào)相乘的信號(hào)的函數(shù)形式是正交的，我們知道所有的正弦或余弦函數(shù)是正交的，這一點(diǎn)我們可以通過簡(jiǎn)單的高數(shù)知識(shí)就可以證明它，所以我們可以通過關(guān)聯(lián)的方法把原始信號(hào)分離出正余弦信號(hào)。當(dāng)然，其它的正交函數(shù)也是存在的，如

38、：方波、三角波等形式的脈沖信號(hào),所以原始信號(hào)也可被分解成這些信號(hào),但這只是說可以這樣做， 卻是沒有用的。F面是實(shí)域傅立葉變換的B A SI C語言代碼：100 'THE D1SCRET匚 FOURIER TRANSFORMILO 'The frqiieacy domaia signals, held mR£X and I>IX ,calculated from120 'the time domain sisual, held m XX.140 DIMXX511150 DIM REX256160 DIM IMX25<170ISO PJ = 5 141

39、59265190 N% = 5122QQ'2L0GOSUBXXXX22Cr2好240 FOR K% = 0 TO 256 'Zeco REX & IMX( w thev cnn be used 貼 acciiiniilatois250 REXK% = 0F260 IMXK% =0270 NEXT K%280 '290 '300 1310 FOR K% = 0 TO 256320S30&40350360570'XX holds the time domain signal'REX holds the real pi't of

40、 th電 frequency domain 1MX 1 holch the imaginaiy part of the frequency domain'Set the comtant, Pl"N% u the inimbev of poiiUs in XK'Mythical subroutine fo lofid data into XX'Correlale XX wuh the com?規(guī)nd &ineEq S-4K% loopi through each sample in 良EX J and &dX FOR 1% = 0 TO 511&

41、#39;1% loop冒 through exh sample in XXREXK%R£XK% + XXI% * COS(嚴(yán)PHK%耳 1%'K%) IMXK% = IMXEK% - XXI% * SIN2*Pt*K%*I%?N%)NEXT 1%S80 NEXT K%390 '400 END到此為止，我們對(duì)傅立葉變換便有了感性的認(rèn)識(shí)了吧。但要記住，這只是在實(shí)域上的離散傅立葉變換，其中雖然也用到了復(fù)數(shù)的形式，但那只是個(gè)替代的形式，并無實(shí)際意義，現(xiàn)實(shí)中一般使用的是復(fù)數(shù)形式的離散傅立葉變換，且快速傅立葉變換 是根據(jù)復(fù)數(shù)離散傅立葉變換來設(shè)計(jì)算法的，在后面我們先來復(fù)習(xí)一下有關(guān)復(fù)

42、數(shù)的內(nèi)容，然后再在理解實(shí)域離散傅立葉變換的基礎(chǔ)上來理解復(fù)數(shù)形式的離散傅立葉變換。復(fù)數(shù)擴(kuò)展了我們一般所能理解的數(shù)的概念，復(fù)數(shù)包含了實(shí)數(shù)和虛數(shù)兩部分，利用復(fù)數(shù)的形式可以把由兩個(gè)變量表示的表達(dá)式變成由一個(gè)變量（復(fù)變量）來表達(dá)，使得處理起來更加自然和方便。我們知道傅立葉變換的結(jié)果是由兩部分組成的，使用復(fù)數(shù)形式可以縮短變換表達(dá)式 使得我們可以單獨(dú)處理一個(gè)變量（這個(gè)在后面的描述中我們就可以更加確切地知道）,而且快速傅立葉變換正是基于復(fù)數(shù)形式的，所以幾乎所有描述的傅立葉變換形式都是復(fù)數(shù)的形式。？但是復(fù)數(shù)的概念超過了我們?nèi)粘Ｉ钪兴芾斫獾母拍?，要理解?fù)數(shù)是較難的,4-所以我們?cè)诶斫鈴?fù)數(shù)傅立葉變換之前，先來專

43、門復(fù)習(xí)一下有關(guān)復(fù)數(shù)的知識(shí)，這對(duì)后面的理解 非常重要。?一、復(fù)數(shù)的提出在此，先讓我們看一個(gè)物理實(shí)驗(yàn)：把一個(gè)球從某點(diǎn)向上拋出，然后根據(jù)初速度和時(shí)間來計(jì) 算球所在高度，這個(gè)方法可以根據(jù)下面的式子計(jì)算得出:其中h表示咼度，g表示重力加速度(9. 8 m/ S 2),v表示初速度,t表示時(shí)間?，F(xiàn)在反過來，假如知道了高度，要求計(jì)算到這個(gè)高度所需要的時(shí)間，這時(shí)我們又可以通過下式來計(jì)算:=1 土譏-加49(多謝J ERR Y _PRI提出:1、根據(jù)公式h = (gt 2 / 2) + V t (g t后面的2表示t的平方)，我們可以討論最終情況，也就是說小球運(yùn)動(dòng)到最高點(diǎn)時(shí)，v=gt,所以，可以得到t= S q

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

45、上運(yùn)動(dòng)時(shí)覺復(fù)數(shù)不能從實(shí)際出發(fā)去推到 ，只能從抽象的角度說明一下。)的時(shí)間是0. 3 8秒，球向下運(yùn)動(dòng)時(shí)的時(shí)間是1.62秒。但是如果高度等于10時(shí)，結(jié)果又是什么呢？根據(jù)上面的式子可以發(fā)現(xiàn)存在對(duì)負(fù)數(shù)進(jìn)行開平方運(yùn)算，我們知道這肯定是不現(xiàn)實(shí)的。第一次使用這個(gè)不一般的式子的人是意大利數(shù)學(xué)家Giro 1 am o C a rda no(l501-157 6 )，兩個(gè)世紀(jì)后，德國(guó)偉大數(shù)學(xué)家C arl Friedr 1 c h Gau s e( 1 77 7 1 8 55)提出了復(fù)數(shù)的概念，為后來的應(yīng)用鋪平了道路，他對(duì)復(fù)數(shù)進(jìn)行這樣表示：復(fù)數(shù)由實(shí)數(shù)(real)和虛數(shù)(imag i na r y)兩部分組成，虛數(shù)

46、中的根號(hào)負(fù)1用i來表示(在這里我們用j來表示，因?yàn)閕在電力學(xué)中表示電流的意思)。我們可以把橫坐標(biāo)表示成實(shí)數(shù)，縱坐標(biāo)表示成虛數(shù)，則坐標(biāo)中的每個(gè)點(diǎn)的向量就可以用復(fù)數(shù)來表示，如下圖：;一一!inInih iiMri I MIPJI I-7 -6 -5 4 -2 -2I I- I；*! I -I I I-I* hl 14 |l III It li'lil h 4I L I M I j hh *4 I J iri * Il M I m|i h 4 I b«i-1 0 1R&l *心Re A = 2Im A =6Re B = 4Im B = - 1 .5一、 w -L上圖中的AB

47、C三個(gè)向量可以表示成如下的式子：？C = 3-7 j ? ?這樣子來表達(dá)方便之處在于運(yùn)用不方便的是我們要分辨哪個(gè)是實(shí)數(shù)一個(gè)符號(hào)就能把兩個(gè)原來難以聯(lián)系起來的數(shù)組合起來了,和哪個(gè)是虛數(shù)，我們一般是用Re()和Im ()來表示實(shí)數(shù)和虛數(shù)兩部分，如:(ei 十 u)- j( b 4 d (C 亠 bj、- (r+力）(和 一一 /(i -(d bj (c +巧、ac 一 hd) - j be 亠 ad'St幻）（-曲）/it C+ bil.I b e - a d + 3這里有個(gè)特殊的地方是j2等于-1,上面第四個(gè)式子的計(jì)算方法是把分子和分母同時(shí)乘以c -dj,這樣就可消去分母中的J 了。 ？

48、？復(fù)數(shù)也符合代數(shù)運(yùn)算中的交換律、結(jié)合律、 分配律：A (B + C )= AB + AC(A + B)+ C = A + (B + C)?二、復(fù)數(shù)的極坐標(biāo)表示形式？前面提到的是運(yùn)用直角坐標(biāo)來表示復(fù)數(shù)，其實(shí)更為普 遍應(yīng)用的是極坐標(biāo)的表示方法，如下圖:-I I - V 1*1 4.;4;.4 © 刁旬一3- 3 刁 b <5rv'f" ! ! !* II 訓(xùn)I i 4 1 * ! III I'll "* i4IiIHI'I ti i'« I I'jni +4i Pl I * b1 I M m 11 h I I I

49、 I hh ImI山 IJ hMJ- IJ Lu 1-34- - - -4 - 5j orM 18.250= aicnii (-15,-4)TP-= -IIIII" 'ff "*'"t"*'6 S -4ll> III-irIIIIII1III 'll 'I'""IIII-''ir"0 1- = 3 十J.2+ 6/ or M = v40 0= arcianlaI 4 1*1 +4 |lh3 - Ij 01M >380= afCTau(*73)? 上圖

50、中的M即是數(shù)量積(m ag n itud e),表示從原點(diǎn)到坐標(biāo)點(diǎn)的距離，B是相位角(P h a se an g le)，表示從X軸正方向到某個(gè)向量的夾角，下面四個(gè)式子是計(jì)算方法：M 二他£ A” + (加”arciaiiI?h ARe ARe A = M cos (6)lui A - 21/ sin C 6)我們還可以通過下面的式子進(jìn)行極坐標(biāo)到直角坐標(biāo)的轉(zhuǎn)換:?a + j b = M (c o s 0 + j sin 0)上面這個(gè)等式中左邊是直角坐標(biāo)表達(dá)式，右邊是極坐標(biāo)表達(dá)式。還有一個(gè)更為重要的等式歐拉等式（歐拉，瑞士的著名數(shù)學(xué)家,L e on h ard Eul er,1707-

51、1783 ) :?ej X =c o s x + j s i n x ? ?這個(gè)等式可以從下面的級(jí)數(shù)變換中得到證明：K-(jxr4-J+ 1)!：上面中右邊的兩個(gè)式子分別是c 0 s（x）和 s in（ X）的泰勒（Tay 1 or）級(jí)數(shù)。？這樣子我們又可以把復(fù)數(shù)的表達(dá)式表示成指數(shù)的形式了:a + jbM e j 0 （這便是復(fù)數(shù)的兩個(gè)表達(dá)式）指數(shù)形式是數(shù)字信號(hào)處理中數(shù)學(xué)方法的支柱,也許是因?yàn)橛弥笖?shù)形式進(jìn)行復(fù)數(shù)的乘除運(yùn)算極為簡(jiǎn)單的緣故吧：耐2用TMJII lAM,e-?三、復(fù)數(shù)是數(shù)學(xué)分析中的一個(gè)工具為什么要使用復(fù)數(shù)呢？其實(shí)它只是個(gè)工具而已，就如釘子和錘子的關(guān)系，復(fù)數(shù)就象那錘(因?yàn)橛行﹩栴}用復(fù)數(shù)