從頭到尾徹底理解傅里葉變換算法、上經(jīng)典算法研究系列：十、從頭到尾徹底理解傅里葉變換算法、上
推薦閱讀：The Scientist and Engineer's Guide to Digital Signal Processing，By Steven W. Smith, Ph.D。此書地址：http://www./pdfbook.htm。 博主說明：I、本文中闡述離散傅里葉變換方法，是根據(jù)此書：The Scientist and Engineer's Guide to Digital Signal Processing，By Steven W. Smith, Ph.D.而翻譯而成的，此書地址：http://www./pdfbook.htm。II、同時(shí)，有相當(dāng)一部分內(nèi)容編輯整理自dznlong的博客，也貼出其博客地址，向原創(chuàng)的作者表示致敬：http://blog.csdn.net/dznlong 。這年頭，真正靜下心寫來原創(chuàng)文章的人，很少了。 第三章、復(fù)數(shù)
前言： 那么，到底什么是傅里葉變換算法列?傅里葉變換所涉及到的公式具體有多復(fù)雜列? 哦，傅里葉變換原來就是一種變換而已，只是這種變換是從時(shí)間轉(zhuǎn)換為頻率的變化。這下，你就知道了，傅里葉就是一種變換，一種什么變換列?就是一種從時(shí)間到頻率的變化或其相互轉(zhuǎn)化。 ok，咱們?cè)賮砜傮w了解下傅里葉變換，讓各位對(duì)其有個(gè)總體大概的印象，也順便看看傅里葉變換所涉及到的公式，究竟有多復(fù)雜：
這是將頻率域的函數(shù)F(ω)表示為時(shí)間域的函數(shù)f（t）的積分形式。 連續(xù)傅里葉變換的逆變換 (inverse Fourier transform)為：
即將時(shí)間域的函數(shù)f（t）表示為頻率域的函數(shù)F(ω)的積分。 一般可稱函數(shù)f（t）為原函數(shù)，而稱函數(shù)F(ω)為傅里葉變換的像函數(shù)，原函數(shù)和像函數(shù)構(gòu)成一個(gè)傅里葉變換對(duì)（transform pair）。 除此之外，還有其它型式的變換對(duì)，以下兩種型式亦常被使用。在通信或是信號(hào)處理方面，常以
或者是因系數(shù)重分配而得到新的變換對(duì)：
一種對(duì)連續(xù)傅里葉變換的推廣稱為分?jǐn)?shù)傅里葉變換（Fractional Fourier Transform）。分?jǐn)?shù)傅里葉變換(fractional Fourier transform,FRFT)指的就是傅里葉變換(Fourier transform,FT)的廣義化。 當(dāng)f（t）為偶函數(shù)（或奇函數(shù)）時(shí)，其正弦（或余弦）分量將消亡，而可以稱這時(shí)的變換為余弦變換（cosine transform）或正弦變換（sine transform）. 另一個(gè)值得注意的性質(zhì)是，當(dāng)f（t）為純實(shí)函數(shù)時(shí)，F(xiàn)(?ω) = F*(ω)成立. 傅里葉級(jí)數(shù)
其中Fn為復(fù)幅度。對(duì)于實(shí)值函數(shù)，函數(shù)的傅里葉級(jí)數(shù)可以寫成：
離散時(shí)域傅里葉變換 離散傅里葉變換 為了在科學(xué)計(jì)算和數(shù)字信號(hào)處理等領(lǐng)域使用計(jì)算機(jī)進(jìn)行傅里葉變換，必須將函數(shù)xn定義在離散點(diǎn)而非連續(xù)域內(nèi)，且須滿足有限性或周期性條件。這種情況下，使用離散傅里葉變換（DFT），將函數(shù)xn表示為下面的求和形式：
其中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)的非周期性。也就是說，時(shí)間上的離散性對(duì)應(yīng)著頻率上的周期性。同時(shí)，注意，離散時(shí)間傅里葉變換，時(shí)間離散，頻率不離散，它在頻域依然是連續(xù)的。 ok， 本文，接下來，由傅里葉變換入手，后重點(diǎn)闡述離散傅里葉變換、快速傅里葉算法，到最后徹底實(shí)現(xiàn)FFT算法，全篇力求通俗易懂、閱讀順暢，教你從頭到尾徹底理解傅里葉變換算法。由于傅里葉變換，也稱傅立葉變換，下文所稱為傅立葉變換，同一個(gè)變換，不同叫法，讀者不必感到奇怪。 第一部分、DFT 傅立葉是一位法國數(shù)學(xué)家和物理學(xué)家，原名是Jean Baptiste Joseph Fourier(1768-1830), Fourier于1807年在法國科學(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ā)表，而后在近50年的時(shí)間里，拉格朗日?qǐng)?jiān)持認(rèn)為傅立葉的方法無法表示帶有棱角的信號(hào)，如在方波中出現(xiàn)非連續(xù)變化斜率。直到拉格朗日死后15年這個(gè)論文才被發(fā)表出來。 為什么我們要用正弦曲線來代替原來的曲線呢？如我們也還可以用方波或三角波來代替呀，分解信號(hào)的方法是無窮多的，但分解信號(hào)的目的是為了更加簡(jiǎn)單地處理原來的信號(hào)。 二、傅立葉變換分類 這四種傅立葉變換都是針對(duì)正無窮大和負(fù)無窮大的信號(hào)，即信號(hào)的的長度是無窮大的，我們知道這對(duì)于計(jì)算機(jī)處理來說是不可能的，那么有沒有針對(duì)長度有限的傅立葉變換呢？沒有。因?yàn)檎嘞也ū欢x成從負(fù)無窮小到正無窮大，我們無法把一個(gè)長度無限的信號(hào)組合成長度有限的信號(hào)。 先來看一個(gè)變換實(shí)例，下圖是一個(gè)原始信號(hào)圖像：
9個(gè)余弦信號(hào)：
9個(gè)正弦信號(hào)：
把以上所有信號(hào)相加即可得到原始信號(hào)，至于是怎么分別變換出9種不同頻率信號(hào)的，我們先不急，先看看對(duì)于以上的變換結(jié)果，在程序中又是該怎么表示的，我們可以看看下面這個(gè)示例圖：
第二章、實(shí)數(shù)形式離散傅立葉變換（Real DFT）
上圖中至于每個(gè)波的振幅(amplitude)值(Re X[k],Im X[k])是怎么算出來的,這個(gè)是DFT的核心，也是最難理解的部分，我們先來看看如何把分解出來的正余弦波合成原始信號(hào)(Inverse DFT)。
如果有學(xué)過傅立葉級(jí)數(shù)，對(duì)這個(gè)等式就會(huì)有似曾相識(shí)的感覺，不錯(cuò)！這個(gè)等式跟傅立葉級(jí)數(shù)是非常相似的：
當(dāng)然，差別是肯定是存在的，因?yàn)檫@兩個(gè)等式是在兩個(gè)不同條件下運(yùn)用的，至于怎么證明DFT合成公式，這個(gè)我想需要非常強(qiáng)的高等數(shù)學(xué)理論知識(shí)了，這是研究數(shù)學(xué)的人的工作，對(duì)于普通應(yīng)用者就不需要如此的追根究底了，但是傅立葉級(jí)數(shù)是好理解的，我們起碼可以從傅立葉級(jí)數(shù)公式中看出DFT合成公式的合理性。
上面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，說明信號(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)的方法。
第二個(gè)式子中加了個(gè)負(fù)號(hào)，是為了保持復(fù)數(shù)形式的一致，前面我們知道在計(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ù)也是存在的，如：方波、三角波等形式的脈沖信號(hào)，所以原始信號(hào)也可被分解成這些信號(hào)，但這只是說可以這樣做，卻是沒有用的。
本人July對(duì)本博客所有任何文章、內(nèi)容和資料享有版權(quán)。 從頭到尾徹底理解傅里葉變換算法、下經(jīng)典算法研究系列：十、從頭到尾徹底理解傅里葉變換算法、下
推薦閱讀：The Scientist and Engineer's Guide to Digital Signal Processing，By Steven W. Smith, Ph.D。此書地址：http://www./pdfbook.htm。 從頭到尾徹底理解傅里葉變換算法、下
第三章、復(fù)數(shù) 復(fù)數(shù)擴(kuò)展了我們一般所能理解的數(shù)的概念，復(fù)數(shù)包含了實(shí)數(shù)和虛數(shù)兩部分，利用復(fù)數(shù)的形式可以把由兩個(gè)變量表示的表達(dá)式變成由一個(gè)變量(復(fù)變量)來表達(dá)，使得處理起來更加自然和方便。
其中h表示高度，g表示重力加速度(9.8m/s2)，v表示初速度，t表示時(shí)間?，F(xiàn)在反過來，假如知道了高度，要求計(jì)算到這個(gè)高度所需要的時(shí)間，這時(shí)我們又可以通過下式來計(jì)算：
上面中右邊的兩個(gè)式子分別是cos(x)和sin(x)的泰勒(Taylor)級(jí)數(shù)。 這樣子我們又可以把復(fù)數(shù)的表達(dá)式表示成指數(shù)的形式了：
第四章、復(fù)數(shù)形式離散傅立葉變換 復(fù)數(shù)形式的離散傅立葉變換非常巧妙地運(yùn)用了復(fù)數(shù)的方法，使得傅立葉變換變換更加自然和簡(jiǎn)潔，它并不是只是簡(jiǎn)單地運(yùn)用替換的方法來運(yùn)用復(fù)數(shù)，而是完全從復(fù)數(shù)的角度來分析問題，這一點(diǎn)跟實(shí)數(shù)DFT是完全不一樣的。 通過歐拉等式可以把正余弦函數(shù)表示成復(fù)數(shù)的形式： 從這個(gè)等式可以看出，如果把正余弦函數(shù)表示成復(fù)數(shù)后，它們變成了由正負(fù)頻率組成的正余弦波，相反地，一個(gè)由正負(fù)頻率組成的正余弦波，可以通過復(fù)數(shù)的形式來表示。 現(xiàn)在我們的原始信號(hào)變成了復(fù)數(shù)，我們要得到的當(dāng)然是復(fù)數(shù)的信號(hào)分量，我們是不是可以把它乘以一個(gè)復(fù)數(shù)形式的正交函數(shù)呢？答案是肯定的，正余弦函數(shù)都是正交函數(shù)，變成如下形式的復(fù)數(shù)后，仍舊還是正交函數(shù)（這個(gè)從正交函數(shù)的定義可以很容易得到證明）： cos x + j sin x, cos x – j sin x，……
N/2 ~ N-1（π~ 2π）是負(fù)頻部分，由于正余弦函數(shù)的對(duì)稱性，所以我們把 –π~ 0表示成π~ 2π，這是出于計(jì)算上方便的考慮。 現(xiàn)中我們一般是把它移到正的頻譜后面的。 從上圖可以看出，時(shí)域中的正余弦波（用來組成原始信號(hào)的正余弦波）在復(fù)數(shù)DFT的頻譜中被分成了正、負(fù)頻率的兩個(gè)組成部分，基于此等式中前面的比例系數(shù)是1/N（或1/2π），而不是2/N，這是因?yàn)楝F(xiàn)在把頻譜延伸到了2π,但把正負(fù)兩個(gè)頻率相加即又得到了2/N,又還原到了實(shí)數(shù)DFT的形式，這個(gè)在后面的描述中可以更清楚地看到。 由于復(fù)數(shù)DFT生成的是一個(gè)完整的頻譜，原始信號(hào)中的每一個(gè)點(diǎn)都是由正、負(fù)兩個(gè)頻率組合而成的，所以頻譜中每一個(gè)點(diǎn)的帶寬是一樣的，都是1/N，相對(duì)實(shí)數(shù)DFT，兩端帶寬比其它點(diǎn)的帶寬少了一半；復(fù)數(shù)DFT的頻譜特征具有周期性：-N/2 ~ 0與N/2 ~ N-1是一樣的，實(shí)域頻譜呈偶對(duì)稱性（表示余弦波頻譜），虛域頻譜呈奇對(duì)稱性（表示正弦波頻譜）。 四、 逆向傅立葉變換 cos(2πkn/N) – j si(2πkn/N)， x[n] = X[k] (cos(2πkn/N) + j sin(2πkn/N)) 我們現(xiàn)在來分析這個(gè)式子，會(huì)發(fā)現(xiàn)這個(gè)式其實(shí)跟實(shí)數(shù)傅立葉變換是可以得到一樣結(jié)果的。我們先把X[k]變換一下： X[k] = Re X[k] + j Im X[k]
x[n] = (Re X[k] + j Im X[k]) (cos(2πkn/N) + j sin(2πkn/N)) = ( Re X[k] cos(2πkn/N) + j Im X[k] cos(2πkn/N) +j Re X[k] sin(2πkn/N) - Im X[k] sin(2πkn/N) ) = ( Re X[k] （cos(2πkn/N) + j sin(2πkn/N)） + ---------------------(1) Im X[k] （ - sin(2πkn/N) + j cos(2πkn/N))） ---------------(2)
這時(shí)我們就把原來的等式分成了兩個(gè)部分，第一個(gè)部分是跟實(shí)域中的頻譜相乘，第二個(gè)部分是跟虛域中的頻譜相乘，根據(jù)頻譜圖我們可以知道，Re X[k]是個(gè)偶對(duì)稱的變量，Im X[k]是個(gè)奇對(duì)稱的變量，即 Re X[k] = Re X[- k] 但k的范圍是0 ~ N-1，0~N/2表示正頻率，N/2~N-1表示負(fù)頻率，為了表達(dá)方便我們把N/2~N-1用-k來表示，這樣在從0到N-1的求和過程中對(duì)于(1)和(2)式分別有N/2對(duì)的k和-k的和，對(duì)于（1）式有： Re X[k] (cos(2πkn/N) + j sin(2πkn/N)) + Re X[- k] (cos( - 2πkn/N) + j sin( -2πkn/N)) 根據(jù)偶對(duì)稱性和三角函數(shù)的性質(zhì)，把上式化簡(jiǎn)得到： 這個(gè)式子最后的結(jié)果是： 2 Re X[ k] cos(2πkn/N)。 -2 Im X[k] sin(2πkn/N) 注意上式前面多了個(gè)負(fù)符號(hào)，這是由于虛數(shù)變換的特殊性造成的，當(dāng)然我們肯定不能把負(fù)符號(hào)的正弦函數(shù)跟余弦來相加，還好，我們前面是用cos(2πkn/N) – j sin(2πkn/N)進(jìn)行相關(guān)性計(jì)算，得到的Im X[k]中有個(gè)負(fù)的符號(hào)，這樣最后的結(jié)果中正弦函數(shù)就沒有負(fù)的符號(hào)了，這就是為什么在進(jìn)行相關(guān)性計(jì)算時(shí)虛數(shù)部分要用到負(fù)符號(hào)的原因（我覺得這也許是復(fù)數(shù)形式DFT美中不足的地方，讓人有一種拼湊的感覺）。
本人July對(duì)本博客所有任何文章、內(nèi)容和資料享有版權(quán)。 |
|
|
來代換，而形成新的變換對(duì):
