1、傅里葉變換算法詳細(xì)介紹 從頭到尾徹底理解傅里葉變換算法、上、/ 、 刖百第一部分、DFT第一章、傅立葉變換的由來第二章、實數(shù)形式離散傅立葉變換(Real DFT )從頭到尾徹底理解傅里葉變換算法、下第三章、復(fù)數(shù)第四章、復(fù)數(shù)形式離散傅立葉變換/* */這一片的傅里葉變換算法，講解透徹，希望對大 家會有所幫助。感謝原作者們(July、dznlong )的精心編寫。/* */前言：關(guān)于傅立葉變換，無論是書本還是在網(wǎng)上可以 很容易找到關(guān)于傅立葉變換的描述，但是大都是 些故弄玄虛的文章，太過抽象，盡是一些讓人看 了就望而生畏的公式的羅列，讓人很難能夠從感 性上得到理解"-dznlong ,那么

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

3、葉變換”一詞不加任何限 定語，則指的是連續(xù)傅里葉變換連續(xù)傅里葉 變換將平方可積的函數(shù)f (t)表示成復(fù)指數(shù)函數(shù) 的積分或級數(shù)形式。=f /ML 源一g這是將頻率域的函數(shù)F( 3展示為時間域的函數(shù) f (t)的積分形式。連續(xù)傅里葉變換的逆變換(inverse Fouriertransform)為：即將時間域的函數(shù)f (t)表示為頻率域的函數(shù)F( 3的積分。一般可稱函數(shù)f (t)為原函數(shù)，而稱函數(shù)F(co) 為傅里葉變換的像函數(shù)，原函數(shù)和像函數(shù)構(gòu)成一 個傅里葉變換對(transform pair )。除此之外，還有其它型式的變換對，以下兩種型 式亦常被使用。在通信或是信號處理方面，常以 ，一券來代

4、換，而形成新的變換對：CX=尸上(切 一 / T(f)h3CX好)=下TX(f) = J X, x或者是因系數(shù)重分配而得到新的變換對：刃/=/ me一8CO/=萬一或3 = ( / P3"心一種對連續(xù)傅里葉變換的推廣稱為分?jǐn)?shù)傅里葉 變換(Fractional Fourier Transform )。分?jǐn)?shù) 傅里葉變換(fractional Fouriertransform,FRFT)指的就是傅里葉變換(Fourier transform,FT)的廣義化。分?jǐn)?shù)傅里葉變換的物理意義即做傅里葉變換a次，其中a不一定要為整數(shù)；而做了分?jǐn)?shù)傅里 葉變換之后，信號或輸入函數(shù)便會出現(xiàn)在介于時域(tim

5、e domain) 與頻域(frequency domain) 之間的分?jǐn)?shù)域(fractional domain)。當(dāng)f (t)為偶函數(shù)(或奇函數(shù))時，其正弦(或 余弦)分量將消亡，而可以稱這時的變換為余弦 變換(cosine transform )或正弦變換(sine transform ).另一個值得注意的性質(zhì)是，當(dāng)f (t)為純實函數(shù) 時，F(xiàn)(-co) = F*( 城立.傅里葉級數(shù)連續(xù)形式的傅里葉變換其實是傅里葉級數(shù)(Fourier series)的推廣，因為積分其實是一種 極限形式的求和算子而已。對于周期函數(shù)，其傅 里葉級數(shù)是存在的：f=I； £*工 n=g其中Fn為復(fù)幅度。

6、對于實值函數(shù)，函數(shù)的傅里 葉級數(shù)可以寫成：gf =% + Z1+ bn sinfrij：）其中an和bn是實頻率分量的幅度。離散時域傅里葉變換離散傅里葉變換是離散時間傅里葉變換（DTFT）的特例（有時作為后者的近似）。DTFT 在時域上離散，在頻域上則是周期的。 DTFT可 以被看作是傅里葉級數(shù)的逆變換。離散傅里葉變換離散傅里葉變換（DFT）,是連續(xù)傅里葉變換 在時域和頻域上都離散的形式，將時域信號的采 樣變換為在離散時間傅里葉變換（DTFT）頻域 的采樣。在形式上，變換兩端（時域和頻域上） 的序列是有限長的，而實際上這兩組序列都應(yīng)當(dāng) 被認(rèn)為是離散周期信號的主值序列。即使對有限 長的離散信號作

7、DFT,也應(yīng)當(dāng)將其看作經(jīng)過周 期延拓成為周期信號再作變換。在實際應(yīng)用中通 常采用快速傅里葉變換以高效計算 DFT。為了在科學(xué)計算和數(shù)字信號處理等領(lǐng)域使用 計算機進(jìn)行傅里葉變換，必須將函數(shù) xn定義在 離散點而非連續(xù)域內(nèi)，且須滿足有限性或周期性條件。這種情況下，使用離散傅里葉變換(DFT), 將函數(shù)xn表示為下面的求和形式：JV1in = £ X/市""= 0,. Ar 1fc=O其中Xk是傅里葉幅度。直接使用這個公式計算 的計算復(fù)雜度為O (n*n),而快速傅里葉變換(FFT)可以將復(fù)雜度改進(jìn)為 O (n*lgn )。(后 面會具體闡述FFT是如何將復(fù)雜度降為O(

8、n*lgn )的。)計算復(fù)雜度的降低以及數(shù)字電 路計算能力的發(fā)展使得DFT成為在信號處理領(lǐng) 域十分實用且重要的方法。下面，比較下上述傅立葉變換的 4種變體，變換時向頻率連續(xù)僮里葉變換連續(xù)，非周期性連級，非周期性傅里葉級數(shù)遢兔周期性離散,非周期性高散時間傅里葉變換離跌非周期性連續(xù)，周期性離散傅里葉變換離散，周期性高散，周期性如上，容易發(fā)現(xiàn)：函數(shù)在時(頻)域的離散對 應(yīng)于其像函數(shù)在頻(時)域的周期性。反之連續(xù) 則意味著在對應(yīng)域的信號的非周期性。也就是說，時間上的離散性對應(yīng)著頻率上的周期性。同 時，注意，離散時間傅里葉變換，時間離散，頻 率不離散，它在頻域依然是連續(xù)的。如果，讀到此，你不甚明白，大沒

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

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

11、非常逼近地表示它，逼近到兩種表 示方法不存在能量差別，基于此，傅立葉是對的。為什么我們要用正弦曲線來代替原來的曲線 呢？如我們也還可以用方波或三角波來代替呀， 分解信號的方法是無窮多的，但分解信號的目的是為了更加簡單地處理原來的信號用正余弦來表示原信號會更加簡單，因為正 余弦擁有原信號所不具有的性質(zhì)：正弦曲線保真 度。一個正余弦曲線信號輸入后，輸出的仍是正 余弦曲線，只有幅度和相位可能發(fā)生變化，但是 頻率和波的形狀仍是一樣的。且只有正余弦曲線 才擁有這樣的性質(zhì)，正因如此我們才不用方波或 三角波來表示。二、傅立葉變換分類我們可以把傅立葉傅立葉變換(Fourier傅立葉級數(shù)(Fourier離散時域

12、傅立葉變換根據(jù)原信號的不同類型 變換分為四種類別：1、非周期性連續(xù)信號Transform )2、周期性連續(xù)信號Series)3、非周期性離散信號(Discrete Time Fourier Transform )4、周期性離散信號離散傅立葉變換(Discrete Fourier Transform)下圖是四種原信號圖例(從上到下，依次是 FT, FS, DTFT, DFT): ype of TransformExample SignalFourier Transfoiins電a rhar are conrtmoits 字位 aperiodicFouiiei已，sinls ihaTnve Ebk

13、門內(nèi)and ptMD由e這四種傅立葉變換都是針對正無窮大和負(fù)無 窮大的信號，即信號的的長度是無窮大的，我們 知道這對于計算機處理來說是不可能的，那么有 沒有針對長度有限的傅立葉變換呢？ 沒有。因為正余弦波被定義成從負(fù)無窮小到正無窮大，我們 無法把一個長度無限的信號組合成長度有限的信號面對這種困難，方法是：把長度有限的信號 表示成長度無限的信號。如，可以把信號無限地Difecreie Time Founer Transfoim dis crore ana apcnotiicDiscrete Founer Traiis；fbnxi thtif are dTcrere andpcjitxiic從左右

14、進(jìn)行延伸，延伸的部分用零來表示，這樣， 這個信號就可以被看成是非周期性離散信號，我 們可以用到離散時域傅立葉變換（DTFT）的方 法。也可以把信號用復(fù)制的方法進(jìn)行延伸，這樣 信號就變成了周期性離散信號，這時我們就可以 用離散傅立葉變換方法（DFT）進(jìn)行變換。本章 我們要講的是離散信號，對于連續(xù)信號我們不作 討論，因為計算機只能處理離散的數(shù)值信號，我 們的最終目的是運用計算機來處理信號的。但是對于非周期性的信號，我們需要用無窮 多不同頻率的正弦曲線來表示，這對于計算機來 說是不可能實現(xiàn)的。所以對于離散信號的變換只 有離散傅立葉變換（DFT）才能被適用，對于計 算機來說只有離散的和有限長度的數(shù)據(jù)才

15、能被 處理，對于其它的變換類型只有在數(shù)學(xué)演算中才 能用到，在計算機面前我們只能用 DFT方法， 后面我們要理解的也正是DFT方法。這里要理解的是我們使用周期性的信號目的 是為了能夠用數(shù)學(xué)方法來解決問題，至于考慮周 期性信號是從哪里得到或怎樣得到是無意義的。每種傅立葉變換都分成實數(shù)和復(fù)數(shù)兩種方法，對于實數(shù)方法是最好理解的， 但是復(fù)數(shù)方法 就相對復(fù)雜許多了，需要懂得有關(guān)復(fù)數(shù)的理論知 識，不過，如果理解了實數(shù)離散傅立葉變換(real DFT),再去理解復(fù)數(shù)傅立葉變換就更容易了， 所以我們先把復(fù)數(shù)的傅立葉變換放到一邊去，先 來理解實數(shù)傅立葉變換，在后面我們會先講講關(guān) 于復(fù)數(shù)的基本理論，然后在理解了實數(shù)

16、傅立葉變 換的基礎(chǔ)上再來理解復(fù)數(shù)傅立葉變換。還有，這里我們所要說的變換(transform)雖 然是數(shù)學(xué)意義上的變換，但跟函數(shù)變換是不同 的，函數(shù)變換是符合一一映射準(zhǔn)則的，對于離散數(shù)字信號處理(DSP),有許多的變換：傅立葉 變換、拉普拉斯變換、Z變換、希爾伯特變換、 離散余弦變換等，這些都擴展了函數(shù)變換的定 義，允許輸入和輸出有多種的值，簡單地說變換 就是把一堆的數(shù)據(jù)變成另一堆的數(shù)據(jù)的方法。三、一個關(guān)于實數(shù)離散傅立葉變換(Real DFT) 的例子先來看一個變換實例，下圖是一個原始信號 圖像：召三二.這個信號的長度是16,于是可以把這個信 號分解9個余弦波和9個正弦波（一個長度為N 的信號可

17、以分解成N/2+1個正余弦信號，這是 為什么呢？結(jié)合下面的18個正余弦圖，我想從計 算機處理精度上就不難理解，一個長度為N的信號，最多只能有N/2+1個不同頻率，再多的 頻率就超過了計算機所能所處理的精度范圍）， 如下圖：9個余弦信號：Cosine Waves0 2 4 6 8 10 12 14 160 2 4 6 3 10 12 14 !£9個正弦信號:把以上所有信號相加即可得到原始信號，至 于是怎么分別變換出9種不同頻率信號的，我們 先不急，先看看對于以上的變換結(jié)果，在程序中 又是該怎么表示的，我們可以看看下面這個示例 圖：Time DomainN samplesN-lFrequ

18、ency DomainRbX ImXi i 口 I in 口 i 口 i【in0N/20N/2N3"15通|吁卜3 W 2 + 1 siimpLse呼Itud”,rsine ”修1ty ampiihjfdesfcollectively iti'eired to 3 X上圖中左邊表示時域中的信號，右邊是頻域 信號表示方法，從左向右，- ,表示正向轉(zhuǎn)換(Forward DFT), 從右向左，-,表示逆向轉(zhuǎn)換(Inverse DFT), 用小寫x口表示信號在每個時間點上的幅度值數(shù) 組，用大寫X口表示每種頻率的副度值數(shù)組(即 時間x-頻率X),因為有N/2+1種頻率，所以該數(shù)組長度為

19、N/2+1 ,X口數(shù)組又分兩種，一種是表示余弦波的不同 頻率幅度值：Re X口，另一種是表示正弦波的不同頻率幅度值：ImX口，Re是實數(shù)(Real)的意思，Im是虛數(shù)(Imagine) 的意思，采用復(fù)數(shù)的表示方法把正余弦波組合起 來進(jìn)行表示，但這里我們不考慮復(fù)數(shù)的其它作 用，只記住是一種組合方法而已，目的是為了便 于表達(dá)(在后面我們會知道，復(fù)數(shù)形式的傅立葉 變換長度是N,而不是N/2+1 )。如此，再回過 頭去，看上面的正余弦各9種頻率的變化，相信, 問題不大了。第二章、實數(shù)形式離散傅立葉變換(Real DFT ) 上一章，我們看到了一個實數(shù)形式離散傅立 葉變換的例子，通過這個例子能夠讓我們先

20、對傅 立葉變換有一個較為形象的感性認(rèn)識，現(xiàn)在就讓 我們來看看實數(shù)形式離散傅立葉變換的正向和 逆向是怎么進(jìn)行變換的。在此，我們先來看一下 頻率的多種表示方法。一、頻域中關(guān)于頻率的四種表示方法1、序號表示方法，根據(jù)時域中信號的樣本數(shù)取0 N/2 ,用這種方法在程序中使用起來可以更 直接地取得每種頻率的幅度值，因為頻率值跟數(shù) 組的序號是一一對應(yīng)的：Xk,取值范圍是0 N/2;2、分?jǐn)?shù)表示方法，根據(jù)時域中信號的樣本數(shù)的 比例值取0 0.5: X? , ? = k/N ,取值范圍是0 1/2;3、用弧度值來表示，把？乘以一個2兀得到一 個弧度值，這種表示方法叫做自然頻率（natural frequenc

21、y） : Xa, w = 2 兀？ = 2 兀 k/N值范 圍是0 w4、以赫茲（Hz）為單位來表示，這個一般是應(yīng)用 于一些特殊應(yīng)用，如取樣率為 10 kHz表示每秒 有10,000個樣本數(shù)：取值范圍是0到取樣率的 一半。二、DFT基本函數(shù)cki = cos（2兀 ki/N）ski = sin（2兀 ki/N）其中k表示每個正余弦波的頻率，如為 2表示在0到N長度中存在兩個完整的周期，10即 有10個周期，如下圖：上圖中至于每個波的振幅(amplitude)值(Re Xk,Im Xk)是怎么算出來的，這個是DFT 的核心，也是最難理解的部分，我們先來看看如 何把分解出來的正余弦波合成原始信號(

22、Inverse DFT)。合成運算方法(Real Inverse DFT)DFT合成等式(合成原始 時間信號，頻率-> 時 間，逆向變換)：- X Rei供cs(2jik"N)十 £sm(2nki /N)k=aho如果有學(xué)過傅立葉級數(shù)，對這個等式就會有似曾 相識的感覺，不錯！這個等式跟傅立葉級數(shù)是非 常相似的：一8/ (x) = -+ 2(%. cos依 + 4 sinkx】 2k=i-當(dāng)然，差別是肯定是存在的，因為這兩個等式是在兩個不同條件下運用的， 至于怎么證 明DFT合成公式，這個我想需要非常強的高等 數(shù)學(xué)理論知識了，這是研究數(shù)學(xué)的人的工作，對 于普通應(yīng)用者就不

23、需要如此的追根究底了， 但是 傅立葉級數(shù)是好理解的，我們起碼可以從傅立葉 級數(shù)公式中看出DFT合成公式的合理性。DFT合成等式中的Im Xk和Re Xk跟之 前提到的Im Xk和Re Xk是不一樣的，下面 是轉(zhuǎn)換方法(關(guān)于此公式的解釋，見下文)：ReX 口 =IiuX A =ReX k N/2但k等于0和N/2時,實數(shù)部分的計算要用F面的等式：D 亍八？ReX 0ReX 0 二二一-NReX N12 = R"32 N上面四個式中的N是時域中點的總數(shù)，k 是從0到N/2的序號。為什么要這樣進(jìn)行轉(zhuǎn)換呢？這個可以從頻 譜密度(spectral density)得到理解，如下圖就 是個頻譜圖

24、：345 d 7 B 9 10 IL 12 13 L4 15 10Frequtnev sanmle muiLber- Jn 一 1Q * 7 6 5 4 3 2 nl_lz-L=<這是一個頻譜圖，橫坐標(biāo)表示頻率大小，縱 坐標(biāo)表示振幅大小，原始信號長度為N （這里是 32）,經(jīng)DFT轉(zhuǎn)換后得到的17個頻率的頻譜， 頻譜密度表示每單位帶寬中為多大的振幅，那么1/N）帶寬的振幅大小，所以3 K血和-x,帶寬是怎么計算出來的呢？看上圖， 除了頭尾兩 個，其余點的所占的寬度是2/N,這個寬度便是 每個點的帶寬，頭尾兩個點的帶寬是 1/N,而Im Xk和Re Xk表示的是頻譜密度，即每一個單 位帶寬

25、的振幅大小，但k更岡武麗表示2/N （或 分別應(yīng) 當(dāng)是 Im Xk和 Re Xk的 2/N （或 1/N）頻譜密度就象物理中物質(zhì)密度，原始信號中的每 一個點就象是一個混合物，這個混合物是由不同 密度的物質(zhì)組成的，混合物中含有的每種物質(zhì)的 質(zhì)量是一樣的，除了最大和最小兩個密度的物質(zhì) 外，這樣我們只要把每種物質(zhì)的密度加起來就可 以得到該混合物的密度了，又該混合物的質(zhì)量是 單位質(zhì)量，所以得到的密度值跟該混合物的質(zhì)量 值是一樣的。至于為什么虛數(shù)部分是負(fù)數(shù)，這是為了跟復(fù) 數(shù)DFT保持一致，這個我們將在后面會知道這 是數(shù)學(xué)計算上的需要（Im Xk在計算時就已經(jīng) 加上了一個負(fù)號（稍后，由下文，便可知）電 再

26、加上負(fù)號，結(jié)果便是正的，等于沒有變化）。如果已經(jīng)得到了 DFT結(jié)果，這時要進(jìn)行逆 轉(zhuǎn)換，即合成原始信號，則可按如下步驟進(jìn)行轉(zhuǎn) 換：1、先根據(jù)上面四個式子計算得出的天M和Re©匐的 值；2、再根據(jù)DFT合成等式得到原始信號數(shù)據(jù)。 下面是用BASIC語言來實現(xiàn)的轉(zhuǎn)換源代碼： 100 'DF逆轉(zhuǎn)換方法110 '/XXR組存儲計算結(jié)果(時域中的原始信 號)120 '/REX數(shù)組存儲頻域中的實數(shù)分量，IMX口 為虛分量130 '140 DIM XX511150 DIM REX256160 DIM IMX256170 '180 PI = 3.1415926

27、5190 N% = 512200 '210 GOSUB XXXX '轉(zhuǎn)至U子函數(shù)去獲取 REX 和IMX數(shù)據(jù) 220 '230 '240 '250 FOR K% = 0 TO 256260 REXK% = REXK% / (N%/2)270 IMXK% = -IMXK% / (N%/2)280 NEXT k%290 '300 REX0 = REX / N310 REX256 = REX256 / N320 '330 初始化XX數(shù)組340 FOR I% = 0 TO 511350 XXI% = 0360 NEXT I%370 '38

28、0 '390 '400 '410 '420 FOR K% =0 TO 256430 FOR I%=0 TO 511440 '450 XXI% = XXI% + REXK% * COS(2* PI * K% * I% / N%)460 XXI% = XXI% + IMXK% * SIN(2 *PI * K% * I% / N%)470 ' 480 NEXT I%490 NEXT K%500510 END上面代碼中420至490換成如下形式也許更好 理解，但結(jié)果都是一樣的：420 FOR I% =0 TO 511430 FOR K%=0 TO 256

29、440 '450 XXI% = XXI% + REXK% * COS(2* PI * K% * I% / N%)460 XXI% = XXI% + IMXK% * SIN(2 *PI * K% * I% / N%)470 '480 NEXT I%490 NEXT K%四、分解運算方法(DFT)有三種完全不同的方法進(jìn)行 DFT: 一種方法 是通過聯(lián)立方程進(jìn)行求解，從代數(shù)的角度看，要 從N個已知值求N個未知值，需要N個聯(lián)立方 程，且N個聯(lián)立方程必須是線性獨立的，但這是這種方法計算量非常的大且極其復(fù)雜，所以很 少被采用；第二種方法是利用信號的相關(guān)性(correlation )進(jìn)行計算

30、，這個是我們后面將要 介紹的方法；第三種方法是快速傅立葉變換(FFT),這是一個非常具有創(chuàng)造性和革命性的 的方法，因為它大大提高了運算速度，使得傅立 葉變換能夠在計算機中被廣泛應(yīng)用，但這種算法 是根據(jù)復(fù)數(shù)形式的傅立葉變換來實現(xiàn)的，它把N 個點的信號分解成長度為N的頻域，這個跟我 們現(xiàn)在所進(jìn)行的實域DFT變換不一樣，而且這 種方法也較難理解，這里我們先不去理解，等先 理解了復(fù)數(shù)DFT后，再來看一下FFT。有一點 很重要，那就是這三種方法所得的變換結(jié)果是一 樣的，經(jīng)過實踐證明，當(dāng)頻域長度為 32時，利 用相關(guān)性方法進(jìn)行計算效率最好，否則FFT算法效率較高?，F(xiàn)在就讓我們來看一下相關(guān)性算 法。利用第一

31、種方法、信號的相關(guān)性(correlation)可 以從噪聲背景中檢測出已知的信號，我們也可以 利用這個方法檢測信號波中是否含有某個頻率 的信號波：把一個待檢測信號波乘以另一個信號波，得到一個新的信號波，再把這個新的信號波 所有的點進(jìn)行相加，從相加的結(jié)果就可以判斷出 這兩個信號的相似程度。如下圖：EMinpk 2,_ I廠I3 xi . sisn.'1 t4i£2 rmalyzMlo 4 "三二二，：m-xhw-。-1 y'Fl-lJI-Example 1FIGURE S-STwoexampk v piaB、(4) and b. aie Analyzed ft

32、n ccnrauuog the specific tnsi& fuucuoa U»nm iu (c) uid(4. risize e刀3，f 5hoU'm卓 rcul* of tRiltipJviftg csh esamp拒bv th?bais fhqqttOD FgWe i?) Hje an*venft «0,5. mdicataigTiui jrl IcofflUins theftmtuoninth m anphtwSe of kO. Convemly.(0M, zeio avciage inciiLi= diat v：; doe、nor ton;am:

33、 jc basis fmicnon上面a和b兩個圖是待檢測信號波，圖a 很明顯可以看出是個3個周期的正弦信號波，圖 b的信號波則看不出是否含有正弦或余弦信號， 圖c和d都是個3個周期的正弦信號波，圖e 和f分別是a、b兩圖跟c、d兩圖相乘后的結(jié)果， 圖e所有點的平均值是0.5,說明信號a含有振 幅為1的正弦信號c,但圖f所有點的平均值是 0,則說明信號b不含有信號do這個就是通過 信號相關(guān)性來檢測是否含有某個信號的方法。第二種方法：相應(yīng)地，我也可以通過把輸入 信號和每一種頻率的正余弦信號進(jìn)行相乘(關(guān)聯(lián) 操作)，從而得到原始信號與每種頻率的關(guān)聯(lián)程 度(即總和大小)，這個結(jié)果便是我們所要的傅 立葉

34、變換結(jié)果，下面兩個等式便是我們所要的計 算方法：V - 1ReXk=cos(27l/r;/TV)f-0押7IniXk = - 52 x/ shi(2nki !N)第二個式子中加了個負(fù)號，是為了保持復(fù)數(shù) 形式的一致，前面我們知道在計算 h支因時又加了 個負(fù)號，所以這只是個形式的問題，并沒有實際 意義，你也可以把負(fù)號去掉，并在計算km對時也 不加負(fù)號。這里有一點必須明白一個正交的概念：兩個 函數(shù)相乘，如果結(jié)果中的每個點的總和為 0,則 可認(rèn)為這兩個函數(shù)為正交函數(shù)。要確保關(guān)聯(lián)性算 法是正確的，則必須使得跟原始信號相乘的信號 的函數(shù)形式是正交的，我們知道所有的正弦或余 弦函數(shù)是正交的，這一點我們可以通

35、過簡單的高 數(shù)知識就可以證明它，所以我們可以通過關(guān)聯(lián)的 方法把原始信號分離出正余弦信號。 當(dāng)然，其它 的正交函數(shù)也是存在的，如：方波、三角波等形 式的脈沖信號，所以原始信號也可被分解成這些 信號，但這只是說可以這樣做，卻是沒有用的。下面是實域傅立葉變換的BASIC語言代 碼：100 "HE DISCRETE IOURIER TKANSFOM11L0 Hhe frequeucv domain ngiiaB. held m REX and 口 1X1 , are cakuhted from 120 'the time domain signal, held in XX130 11

36、40 DIMXX511150 DM REX256160 DIMIMX25< 1701ISO PI = 3N% = 51220。2L0GOSUBXXXX220230 ''XX holds the time domain signalREX hold the real p5rt of th&frwqnoncv domamJMX holds the miaginaiy part of the frequency domain'Set the comtant, PI'N% is rhe number of points in XX

37、'Mythical subroutine to bad data into XX240 FOR K% = 0 TO 256 'Zero REX( & IMX0o thev can be LKRd a. accumulatoi250 REXK%l = 0250 IMXK% = 0270 NEXT Kflo2 80 J2901'Correlale XX with thf come and wave, Eq. 843O0J3L0 FOR K% = 0 TO 256K% loops through each sample in REX aud IMX320 FORI%

38、=0 TO 511 '1% loop* through each sample iti XX330 r340 REXK% = R£XK% + XXI% * CO$(尹PI*K%*I%N%)3 SO IMXK% = 1MxK% - XX(1%率 SINQ叩360 ,370 NEXT1如380 NEXT K%390 ,400 END到此為止，我們對傅立葉變換便有了感性的 認(rèn)識了吧。但要記住，這只是在實域上的離散傅 立葉變換，其中雖然也用到了復(fù)數(shù)的形式， 但那 只是個替代的形式，并無實際意義，現(xiàn)實中一般 使用的是復(fù)數(shù)形式的離散傅立葉變換， 且快速傅 立葉變換是根據(jù)復(fù)數(shù)離散傅立葉變換

39、來設(shè)計算法的，在后面我們先來復(fù)習(xí)一下有關(guān)復(fù)數(shù)的內(nèi) 容，然后再在理解實域離散傅立葉變換的基礎(chǔ)上 來理解復(fù)數(shù)形式的離散傅立葉變換。第三章、復(fù)數(shù)復(fù)數(shù)擴展了我們一般所能理解的數(shù)的概 念，復(fù)數(shù)包含了實數(shù)和虛數(shù)兩部分，利用復(fù)數(shù)的 形式可以把由兩個變量表示的表達(dá)式變成由一 個變量（復(fù)變量）來表達(dá)，使得處理起來更加自然 和方便。我們知道傅立葉變換的結(jié)果是由兩部分組 成的，使用復(fù)數(shù)形式可以縮短變換表達(dá)式，使得 我們可以單獨處理一個變量（這個在后面的描述 中我們就可以更加確切地知道），而且快速傅立 葉變換正是基于復(fù)數(shù)形式的，所以幾乎所有描述 的傅立葉變換形式都是復(fù)數(shù)的形式。但是復(fù)數(shù)的概念超過了我們?nèi)粘Ｉ钪兴?能

40、理解的概念，要理解復(fù)數(shù)是較難的，所以我們 在理解復(fù)數(shù)傅立葉變換之前，先來專門復(fù)習(xí)一下 有關(guān)復(fù)數(shù)的知識，這對后面的理解非常重要。復(fù)數(shù)的提出在此，先讓我們看一個物理實驗：把一個球 從某點向上拋出，然后根據(jù)初速度和時間來計算 球所在高度，這個方法可以根據(jù)下面的式子計算 得出：其中h表示高度，g表示重力加速度（9.8m/s2）, v表示初速度，t表示時間?，F(xiàn)在反過來，假如 知道了高度，要求計算到這個高度所需要的時 間，這時我們又可以通過下式來計算：z = 1- /;/4.9（多謝JERRY_PRI提出：1、根據(jù)公式h=-（gt2/2）+Vt （gt后面的2表 示t的平方），我們可以討論最終情況，也就是

41、 說小球運動到最高點時，v=gt ,所以，可以得到 t=sqt（2h/g）且在您給的公式中，根號下為1-（2h）/g ,化成分 數(shù)形式為（g-2h）/g ,g和h不能直接做加減運算。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)v2<2hg時會產(chǎn)生復(fù)數(shù)，但是如果從實際的 v2是不可能小于2hg的，所以我感覺復(fù)數(shù)不能 從實際出發(fā)去推到，

42、只能從抽象的角度說明一 下。)經(jīng)過計算我們可以知道，當(dāng)高度是 3米時， 有兩個時間點到達(dá)該高度：球向上運動時的時間 是0.38秒，球向下運動時的時間是1.62秒。但 是如果高度等于10時，結(jié)果又是什么呢？根據(jù) 上面的式子可以發(fā)現(xiàn)存在對負(fù)數(shù)進(jìn)行開平方運 算，我們知道這肯定是不現(xiàn)實的。第一次使用這個不一般的式子的人是意大 利數(shù)學(xué)家 Girolamo Cardano (1501-1576 ), 兩個世紀(jì)后，德國偉大數(shù)學(xué)家 Carl Friedrich Gause (1777-1855 )提出了復(fù)數(shù)的概念，為后 來的應(yīng)用鋪平了道路，他對復(fù)數(shù)進(jìn)行這樣表示：復(fù)數(shù)由實數(shù)（real）和虛數(shù)（imaginary

43、）兩部分組 成，虛數(shù)中的根號負(fù)1用i來表示（在這里我們 用j來表示，因為i在電力學(xué)中表示電流的意思）我們可以把橫坐標(biāo)表示成實數(shù)，縱坐標(biāo)表示 成虛數(shù)，則坐標(biāo)中的每個點的向量就可以用復(fù)數(shù) 來表示,如下圖：A W產(chǎn)8球=0EUI一raxis5 4 5 6上圖中的ABC三個向量可以表示成如下的 式子：A = 2 + 6jB = -4 - 1.5jC = 3 - 7j這樣子來表達(dá)方便之處在于運用一個符號 就能把兩個原來難以聯(lián)系起來的數(shù)組合起來了， 不方便的是我們要分辨哪個是實數(shù)和哪個是虛 數(shù)，我們一般是用Re()和Im()來表示實數(shù)和虛 數(shù)兩部分，如：Re A = 2Im A = 6Re B = -4I

44、m B = -1.5Re C = 3Im C = -7復(fù)數(shù)之間也可以進(jìn)行加減乘除運算:(o +)十(c:十力*) = (a c ) + j(b - d)9 + bjl - 3 +dj) = 3 - c) + j(b - d)* bj (r + dj ) = (ac - bd) + j(be + nd)(q +/>/> _ ac bef + . be - nd (-/) i c1 - fV 2 J ，I c 2 + d。,這里有個特殊的地方是j2等于-1,上面第 四個式子的計算方法是把分子和分母同時乘以c-dj ,這樣就可消去分母中的j 了。復(fù)數(shù)也符合代數(shù)運算中的交換律、結(jié)合律、 分

45、配律：A B = B A(A + B) + C = A + (B + C) A(B + C) = AB + AC二、復(fù)數(shù)的極坐標(biāo)表示形式前面提到的是運用直角坐標(biāo)來表示復(fù)數(shù)，其 實更為普遍應(yīng)用的是極坐標(biāo)的表示方法，如下圖：.2葉-3j十 . a 中 , H由” I，之十675 n： M = »400= ircm (6/2) j4件 I-4-15 J orM = 18 256 二 ircun (-1 5-4)| 3-7; oi*4 M = 58 ； 0= afcun(-73)i審一，小，j-” * j上圖中的M即是數(shù)量積(magnitude)表 示從原點到坐標(biāo)點的距離，0是相位角(pha

46、se angle)表示從X軸正方向到某個向量的夾角)下面四個式子是計算方法：M - /(Re A)2 + Im A2a Ihi A6 = arcian 一 Re A .Re A = M cos (6)Im A - M sin C 6 )我們還可以通過下面的式子進(jìn)行極坐標(biāo)到直 角坐標(biāo)的轉(zhuǎn)換：a + jb = M (cos 6 + j sin 0)上面這個等式中左邊是直角坐標(biāo)表達(dá)式，右 邊是極坐標(biāo)表達(dá)式。還有一個更為重要的等式 一一歐拉等式（歐 拉，瑞士的著名數(shù)學(xué)家，Leonhard Euler , 1707-1783 ）:ejx = cos x + j sin x這個等式可以從下面的級數(shù)變換中得

47、到證 明：工”二= 071 上面中右邊的兩個式子分別是 cos(x)和 sin(x)的泰勒(Taylor)級數(shù)。這樣子我們又可以把復(fù)數(shù)的表達(dá)式表示成指 數(shù)的形式了：a + jb = M ej8這便是復(fù)數(shù)的兩個表達(dá)式)指數(shù)形式是數(shù)字信號處理中數(shù)學(xué)方法的支 柱，也許是因為用指數(shù)形式進(jìn)行復(fù)數(shù)的乘除運算 極為簡單的緣故吧：三、復(fù)數(shù)是數(shù)學(xué)分析中的一個工具為什么要使用復(fù)數(shù)呢？其實它只是個工具 而已，就如釘子和錘子的關(guān)系，復(fù)數(shù)就象那錘子, 作為一種使用的工具。我們把要解決的問題表達(dá) 成復(fù)數(shù)的形式(因為有些問題用復(fù)數(shù)的形式進(jìn)行 運算更加方便)，然后對復(fù)數(shù)進(jìn)行運算，最后再 轉(zhuǎn)換回來得到我們所需要的結(jié)果。有兩種方

48、法使用復(fù)數(shù)，一種是用復(fù)數(shù)進(jìn)行簡 單的替換，如前面所說的向量表達(dá)式方法和前一 節(jié)中我們所討論的實域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去掉就可以了。有一點要明白的是并不是所有問題都可以 用復(fù)數(shù)來表示，必須看用復(fù)數(shù)進(jìn)行分析是否適 用，有個例子可以看出用復(fù)數(shù)來替換原來問題的 表達(dá)

49、方式明顯是謬誤的：假設(shè)一箱的蘋果是5美 元，一箱的桔子是10美元，于是我們把它表示 成5 + 10j ,有一個星期你買了 6箱蘋果和2箱 桔子，我們又把它表示成6 + 2j,最后計算總共 花的錢是(5 + 10j)(6 + 2j) = 10 + 70j ,結(jié)果是買 蘋果花了 10美元的，買桔子花了 70美元，這 樣的結(jié)果明顯是錯了，所以復(fù)數(shù)的形式不適合運 用于對這種問題的解決。四、用復(fù)數(shù)來表示正余弦函數(shù)表達(dá)式對于象 M cos ( w t + 和 A cos( w t ) + B sin( 3 t表達(dá)式，用復(fù)數(shù)來表示，可以變得非常 簡潔，對于直角坐標(biāo)形式可以按如下形式進(jìn)行轉(zhuǎn) 換：J cos (

50、tor) +匚 a + JbV。型f汕川be/，上式中余弦幅值A(chǔ)經(jīng)變換生成a,正弦幅值 B的相反數(shù)經(jīng)變換生成 b: A <=> a , B<=> -b , 但要注意的是，這不是個等式，只是個替換形式 而已。對于極坐標(biāo)形式可以按如下形式進(jìn)行轉(zhuǎn)換：M cos (or + <|>)戶 MeJQ上式中)M <=> M) 0 <=>小這里虛數(shù)部分采用負(fù)數(shù)的形式主要是為了跟復(fù)數(shù)傅立葉變換表達(dá)式保持一致，對于這種替換 的方法來表示正余弦，符號的變換沒有什么好 處，但替換時總會被改變掉符號以跟更高級的等 價變換保持形式上的一致。在離散信號處理中，運用

51、復(fù)數(shù)形式來表示 正余弦波是個常用的技術(shù)，這是因為利用復(fù)數(shù)進(jìn) 行各種運算得到的結(jié)果跟原來的正余弦運算結(jié) 果是一致的，但是，我們要小心使用復(fù)數(shù)操作， 如加、減、乘、除，有些操作是不能用的，如兩 個正弦信號相加，采用復(fù)數(shù)形式進(jìn)行相加，得到 的結(jié)果跟替換前的直接相加的結(jié)果是一樣的，但 是如果兩個正弦信號相乘，則采用復(fù)數(shù)形式來相 乘結(jié)果是不一樣的。幸運的是，我們已嚴(yán)格定義 了正余弦復(fù)數(shù)形式的運算操作條件：1、參加運算的所有正余弦的頻率必須是一樣的； 2、運算操作必須是線性的，如兩個正弦信號可 以進(jìn)行相加減，但不能進(jìn)行乘除，象信號的放大、 衰減、高低通濾波等系統(tǒng)都是線性的，象平方、 縮短、取限等則不是線性

52、的。要記住的是卷積和 傅立葉分析也只有線性操作才可以進(jìn)行。下圖是一個相量變換（我們把正弦或余弦波 變成復(fù)數(shù)的形式稱為相量變換，Phasor transform）的例子，一個連續(xù)信號波經(jīng)過一個線 性處理系統(tǒng)生成另一個信號波，從計算過程我們 可以看出采用復(fù)數(shù)的形式使得計算變化十分的 簡潔：Input signalOutput sian?1.5cos(wr-江電Ofl,3S58co(wf) - 0.57413 cos (or+二or2 1213co5(G)/) - 2J213sinML5 J*or1.3858 -/0.574(“療0.5/RS8X82.1213/2,12130.1913-J0.4&#

53、171;l9在第二章中我們描述的實數(shù)形式傅立葉變換 也是一種替換形式的復(fù)數(shù)變換，但要注意的是那 還不是復(fù)數(shù)傅立葉變換，只是一種代替方式而 已。下一章、即，第四章，我們就會知道復(fù)數(shù)傅立葉變換是一種更高級的變換，而不是這種簡單 的替換形式。第四章、復(fù)數(shù)形式離散傅立葉變換復(fù)數(shù)形式的離散傅立葉變換非常巧妙地運用 了復(fù)數(shù)的方法，使得傅立葉變換變換更加自然和 簡潔，它并不是只是簡單地運用替換的方法來運 用復(fù)數(shù)，而是完全從復(fù)數(shù)的角度來分析問題，這一點跟實數(shù)DFT是完全不一樣的。一、把正余弦函數(shù)表示成復(fù)數(shù)的形式通過歐拉等式可以把正余弦函數(shù)表示成復(fù)數(shù) 的形式：cos( x ) = 1/2 e j(-x) + 1

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

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