理解離散傅立葉變換（一）

                     ——傅立葉變換的由來(lái)

       關(guān)于傅立葉變換，無(wú)論是書本還是在網(wǎng)上可以很容易找到關(guān)于傅立葉變換的描述，但是大都是些故弄玄虛的文章，太過(guò)抽象，盡是一些讓人看了就望而生畏的公式的羅列，讓人很難能夠從感性上得到理解，最近，我偶爾從網(wǎng)上看到一個(gè)關(guān)于數(shù)字信號(hào)處理的電子書籍，是一個(gè)叫Steven W. Smith, Ph.D.外國(guó)人寫的，寫得非常淺顯，里面有七章由淺入深地專門講述關(guān)于離散信號(hào)的傅立葉變換，雖然是英文文檔，我還是硬著頭皮看完了有關(guān)傅立葉變換的有關(guān)內(nèi)容，看了有茅塞頓開的感覺，在此把我從中得到的理解拿出來(lái)跟大家分享，希望很多被傅立葉變換迷惑的朋友能夠得到一點(diǎn)啟發(fā)，這電子書籍是免費(fèi)的，有興趣的朋友也可以從網(wǎng)上下載下來(lái)看一下，URL地址是：http://www./pdfbook.htm 

       要理解傅立葉變換，確實(shí)需要一定的耐心，別一下子想著傅立葉變換是怎么變換的，當(dāng)然，也需要定的高等數(shù)學(xué)基礎(chǔ)，最基本的是級(jí)數(shù)變換，其中傅立葉級(jí)數(shù)變換是傅立葉變換的基礎(chǔ)公式。 

一、傅立葉變換的提出 

       讓我們先看看為什么會(huì)有傅立葉變換？傅立葉是一位法國(guó)數(shù)學(xué)家和物理學(xué)家的名字，英語(yǔ)原名是Jean Baptiste Joseph Fourier(1768-1830), Fourier對(duì)熱傳遞很感興趣，于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è)論文的人，其中有兩位是歷史上著名的數(shù)學(xué)家拉格朗日(Joseph Louis Lagrange, 1736-1813)和拉普拉斯(Pierre Simon de Laplace, 1749-1827)，當(dāng)拉普拉斯和其它審查者投票通過(guò)并要發(fā)表這個(gè)論文時(shí)，拉格朗日?qǐng)?jiān)決反對(duì)，在近50年的時(shí)間里，拉格朗日?qǐng)?jiān)持認(rèn)為傅立葉的方法無(wú)法表示帶有棱角的信號(hào)，如在方波中出現(xiàn)非連續(xù)變化斜率。法國(guó)科學(xué)學(xué)會(huì)屈服于拉格朗日的威望，拒絕了傅立葉的工作，幸運(yùn)的是，傅立葉還有其它事情可忙，他參加了政治運(yùn)動(dòng)，隨拿破侖遠(yuǎn)征埃及，法國(guó)大革命后因會(huì)被推上斷頭臺(tái)而一直在逃避。直到拉格朗日死后15年這個(gè)論文才被發(fā)表出來(lái)。 

       誰(shuí)是對(duì)的呢？拉格朗日是對(duì)的：正弦曲線無(wú)法組合成一個(gè)帶有棱角的信號(hào)。但是，我們可以用正弦曲線來(lái)非常逼近地表示它，逼近到兩種表示方法不存在能量差別，基于此，傅立葉是對(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)表示。 

二、傅立葉變換分類 

       根據(jù)原信號(hào)的不同類型，我們可以把傅立葉變換分為四種類別：

       下圖是四種原信號(hào)圖例：

這四種傅立葉變換都是針對(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ú)窮大，我們無(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í)域傅立葉變換的方法。還有，也可以把信號(hào)用復(fù)制的方法進(jìn)行延伸，這樣信號(hào)就變成了周期性離解信號(hào)，這時(shí)我們就可以用離散傅立葉變換方法進(jìn)行變換。這里我們要學(xué)的是離散信號(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)說(shuō)是不可能實(shí)現(xiàn)的。所以對(duì)于離散信號(hào)的變換只有離散傅立葉變換（DFT）才能被適用，對(duì)于計(jì)算機(jī)來(lái)說(shuō)只有離散的和有限長(zhǎng)度的數(shù)據(jù)才能被處理，對(duì)于其它的變換類型只有在數(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ù)離散傅立葉變換(real DFT)，再去理解復(fù)數(shù)傅立葉就更容易了，所以我們先把復(fù)數(shù)的傅立葉放到一邊去，先來(lái)理解實(shí)數(shù)傅立葉變換，在后面我們會(huì)先講講關(guān)于復(fù)數(shù)的基本理論，然后在理解了實(shí)數(shù)傅立葉變換的基礎(chǔ)上再來(lái)理解復(fù)數(shù)傅立葉變換。 

       還有，這里我們所要說(shuō)的變換(transform)雖然是數(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ù)離散傅立葉變換(Real DFT)的例子 

       先來(lái)看一個(gè)變換實(shí)例，下圖是一個(gè)原始信號(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)表示方法，從左向右表示正向轉(zhuǎn)換(Forward DFT)，從右向左表示逆向轉(zhuǎn)換(Inverse DFT)，用小寫x[]表示信號(hào)在每個(gè)時(shí)間點(diǎn)上的幅度值數(shù)組, 用大寫X[]表示每種頻率的幅度值數(shù)組, 因?yàn)橛蠳/2+1種頻率，所以該數(shù)組長(zhǎng)度為N/2+1，X[]數(shù)組又分兩種，一種是表示余弦波的不同頻率幅度值：Re X[]，另一種是表示正弦波的不同頻率幅度值：Im X[]，Re是實(shí)數(shù)(Real)的意思，Im是虛數(shù)(Imaginary)的意思，采用復(fù)數(shù)的表示方法把正余弦波組合起來(lái)進(jìn)行表示，但這里我們不考慮復(fù)數(shù)的其它作用，只記住是一種組合方法而已，目的是為了便于表達(dá)（在后面我們會(huì)知道，復(fù)數(shù)形式的傅立葉變換長(zhǎng)度是N，而不是N/2+1）。

       下一節(jié)我們將來(lái)看一下實(shí)數(shù)傅立葉變換的具體方法。

理解離散傅立葉變換（二）

                              ——實(shí)數(shù)形式離散傅立葉變換（Real DFT）

       上一節(jié)我們看到了一個(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)是一一對(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è)弧度值，這種表示方法叫做自然頻率(natural frequency)：X[ω]，ω = 2πƒ = 2πk/N，取值范圍是0 ~ π；

4、  以赫茲(Hz)為單位來(lái)表示，這個(gè)一般是應(yīng)用于一些特殊應(yīng)用，如取樣率為10 kHz表示每秒有10,000個(gè)樣本數(shù)：取值范圍是0到取樣率的一半。 

二、           DFT基本函數(shù) 

c_k[i] = cos(2πki/N)

s_k[i] = sin(2πki/N)

    其中k表示每個(gè)正余弦波的頻率，如為2表示在0到N長(zhǎng)度中存在兩個(gè)完整的周期，10即有10個(gè)周期，如下圖：

       上圖中至于每個(gè)波的振幅(amplitude)值(Re X[k],Im X[k])是怎么算出來(lái)的,這個(gè)是DFT的核心，也是最難理解的部分，我們先來(lái)看看如何把分解出來(lái)的正余弦波合成原始信號(hào)(Inverse DFT)。 

三、        合成運(yùn)算方法(Real Inverse DFT) 

DFT合成等式：

如果有學(xué)過(guò)傅立葉級(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合成公式的合理性。 

       DFT合成等式中的Im [k]和Re [k]跟Im X[k]和Re X[k]是不一樣的，下面是轉(zhuǎ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è)可以從頻譜密度(spectral density)得到理解，如下圖就是個(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è)單位帶寬的振幅大小，但Im [k]和Re [k]表示2/N（或1/N）帶寬的振幅大小，所以Im [k]和Re [k]分別應(yīng)當(dāng)是Im X[k]和Re X[k]的2/N（或1/N）。 

頻譜密度就象物理中物質(zhì)密度，原始信號(hào)中的每一個(gè)點(diǎn)就象是一個(gè)混合物，這個(gè)混合物是由不同密度的物質(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í)加上了一個(gè)負(fù)號(hào)，Im [k]再加上負(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ì)算得出Im [k]和Re [k]的值；

2、  再根據(jù)DFT合成等式得到原始信號(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 TO 256

260   REX[K%] = REX[K%] / (N%/2)

270   IMX[K%] = -IMX[K%] / (N%/2)

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

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%] * 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% 

四、        分解運(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è)是我們后面將要介紹的方法；第三種方法是快速傅立葉變換（FFT），這是一個(gè)非常具有創(chuàng)造性和革命性的的方法，因?yàn)樗蟠筇岣吡诉\(yùn)算速度，使得傅立葉變換能夠在計(jì)算機(jī)中被廣泛應(yīng)用，但這種算法(//FFT只是實(shí)現(xiàn)DFT的一種算法)是根據(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算法效率較高。現(xiàn)在就讓我們來(lái)看一下相關(guān)性算法。 

利用信號(hào)的相關(guān)性(correlation)可以從噪聲背景中檢測(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)的相似程度。如下圖：

         上面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)的方法。 

       相應(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ì)算Im [k]時(shí)又加了個(gè)負(fù)號(hào)，所以這只是個(gè)形式的問(wèn)題，并沒(méi)有實(shí)際意義，你也可以把負(fù)號(hào)去掉，并在計(jì)算Im [k]時(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ù)形式是正交的，我們知道所有的正弦或余弦函數(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ù)形式的離散傅立葉變換。 

理解離散傅立葉變換（三）

                     ------復(fù)數(shù)

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

一、           復(fù)數(shù)的提出 

在此，先讓我們看一個(gè)物理實(shí)驗(yàn)：把一個(gè)球從某點(diǎn)向上拋出，然后根據(jù)初速度和時(shí)間來(lái)計(jì)算球所在高度，這個(gè)方法可以根據(jù)下面的式子計(jì)算得出：

其中h表示高度，g表示重力加速度(9.8m/s²)，v表示初速度，t表示時(shí)間?，F(xiàn)在反過(guò)來(lái)，假如知道了高度，要求計(jì)算到這個(gè)高度所需要的時(shí)間，這時(shí)我們又可以通過(guò)下式來(lái)計(jì)算：

經(jīng)過(guò)計(jì)算我們可以知道，當(dāng)高度是3米時(shí)，有兩個(gè)時(shí)間點(diǎn)到達(dá)該高度：球向上運(yùn)動(dòng)時(shí)的時(shí)間是0.38秒，球向下運(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é)家Girolamo Cardano（1501-1576），兩個(gè)世紀(jì)后，德國(guó)偉大數(shù)學(xué)家Carl Friedrich Gause（1777-1855）提出了復(fù)數(shù)的概念，為后來(lái)的應(yīng)用鋪平了道路，他對(duì)復(fù)數(shù)進(jìn)行這樣表示：復(fù)數(shù)由實(shí)數(shù)（real）和虛數(shù)(imaginary)兩部分組成，虛數(shù)中的根號(hào)負(fù)1用i來(lái)表示（在這里我們用j來(lái)表示，因?yàn)?/span>i在電力學(xué)中表示電流的意思）。 

       我們可以把橫坐標(biāo)表示成實(shí)數(shù)，縱坐標(biāo)表示成虛數(shù)，則坐標(biāo)中的每個(gè)點(diǎn)的向量就可以用復(fù)數(shù)來(lái)表示，如下圖：

       上圖中的ABC三個(gè)向量可以表示成如下的式子：

                    A = 2 + 6j

                 B = -4 – 1.5j

                 C = 3 – 7j

       這樣子來(lái)表達(dá)方便之處在于運(yùn)用一個(gè)符號(hào)就能把兩個(gè)原來(lái)難以聯(lián)系起來(lái)的數(shù)組合起來(lái)了，不方便的是我們要分辨哪個(gè)是實(shí)數(shù)和哪個(gè)是虛數(shù)，我們一般是用Re( )和Im( )來(lái)表示實(shí)數(shù)和虛數(shù)兩部分，如：

            Re A = 2      Im A = 6

         Re B = -4     Im B = -1.5

         Re C = 3      Im C = -7

       復(fù)數(shù)之間也可以進(jìn)行加減乘除運(yùn)算：

       這里有個(gè)特殊的地方是j²等于-1，上面第四個(gè)式子的計(jì)算方法是把分子和分母同時(shí)乘以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)來(lái)表示復(fù)數(shù)，其實(shí)更為普遍應(yīng)用的是極坐標(biāo)的表示方法，如下圖：

       上圖中的M即是數(shù)量積(magnitude)，表示從原點(diǎn)到坐標(biāo)點(diǎn)的距離，θ是相位角(phase angle)，表示從X軸正方向到某個(gè)向量的夾角，下面四個(gè)式子是計(jì)算方法：

       我們還可以通過(guò)下面的式子進(jìn)行極坐標(biāo)到直角坐標(biāo)的轉(zhuǎn)換： 

a + jb = M (cosθ + j sinθ)

       上面這個(gè)等式中左邊是直角坐標(biāo)表達(dá)式，右邊是極坐標(biāo)表達(dá)式。 

       還有一個(gè)更為重要的等式——歐拉等式（歐拉是瑞士的著名數(shù)學(xué)家，Leonhard Euler，1707-1783）：

e^jx = cos x  +  j sin x

       這個(gè)等式可以從下面的級(jí)數(shù)變換中得到證明：

       上面式中右邊的兩個(gè)式子分別是cos(x)和sin(x)的泰勒(Taylor)級(jí)數(shù)。 

       這樣子我們又可以把復(fù)數(shù)的表達(dá)式表示成指數(shù)的形式了：

a + jb = M e ^jθ （這便是復(fù)數(shù)的兩個(gè)表達(dá)式）

       指數(shù)形式是數(shù)字信號(hào)處理中數(shù)學(xué)方法的支柱，也許是因?yàn)橛弥笖?shù)形式進(jìn)行復(fù)數(shù)的乘除運(yùn)算極為簡(jiǎn)單的緣故吧：

三、復(fù)數(shù)是數(shù)學(xué)分析中的一個(gè)工具 

       為什么要使用復(fù)數(shù)呢？其實(shí)它只是個(gè)工具而已，就如釘子和錘子的關(guān)系，復(fù)數(shù)就象那錘子，作為一種使用的工具。我們把要解決的問(wèn)題表達(dá)成復(fù)數(shù)的形式（因?yàn)橛行﹩?wèn)題用復(fù)數(shù)的形式進(jìn)行運(yùn)算更加方便），然后對(duì)復(fù)數(shù)進(jìn)行運(yùn)算，最后再轉(zhuǎn)換回來(lái)得到我們所需要的結(jié)果。 

       有兩種方法使用復(fù)數(shù)，一種是用復(fù)數(shù)進(jìn)行簡(jiǎn)單的替換，如前面所說(shuō)的向量表達(dá)式方法和前一節(jié)中我們所討論的實(shí)域DFT，另一種是更高級(jí)的方法：數(shù)學(xué)等價(jià)(mathematical equivalence)，復(fù)數(shù)形式的傅立葉變換用的便是數(shù)學(xué)等價(jià)的方法，但在這里我們先不討論這種方法，這里我們先來(lái)看一下用復(fù)數(shù)進(jìn)行替換中的問(wèn)題。 

       用復(fù)數(shù)進(jìn)行替換的基本思想是：把所要分析的物理問(wèn)題轉(zhuǎn)換成復(fù)數(shù)的形式，其中只是簡(jiǎn)單地添加一個(gè)復(fù)數(shù)的符號(hào)j，當(dāng)返回到原來(lái)的物理問(wèn)題時(shí)，則只是把符號(hào)j去掉就可以了。 

       有一點(diǎn)要明白的是并不是所有問(wèn)題都可以用復(fù)數(shù)來(lái)表示，必須看用復(fù)數(shù)進(jìn)行分析是否適用，有個(gè)例子可以看出用復(fù)數(shù)來(lái)替換原來(lái)問(wèn)題的表達(dá)方式明顯是謬誤的：假設(shè)一箱的蘋果是5美元，一箱的桔子是10美元，于是我們把它表示成 5 + 10j，有一個(gè)星期你買了6箱蘋果和2箱桔子，我們又把它表示成6 + 2j，最后計(jì)算總共花的錢是(5 + 10j)(6 + 2j) = 10 + 70j，結(jié)果是買蘋果花了10美元的，買桔子花了70美元，這樣的結(jié)果明顯是錯(cuò)了，所以復(fù)數(shù)的形式不適合運(yùn)用于對(duì)這種問(wèn)題的解決。 

四、用復(fù)數(shù)來(lái)表示正余弦函數(shù)表達(dá)式 

       對(duì)于象M cos (ωt + φ)和A cos(ωt ) + B sin(ωt )表達(dá)式，用復(fù)數(shù)來(lái)表示，可以變得非常簡(jiǎn)潔，對(duì)于直角坐標(biāo)形式可以按如下形式進(jìn)行轉(zhuǎn)換：

       上式中余弦幅值A經(jīng)變換生成a，正弦幅值B的相反數(shù)經(jīng)變換生成b，但要注意的是，這不是個(gè)等式，只是個(gè)替換形式而已。 

       對(duì)于極坐標(biāo)形式可以按如下形式進(jìn)行轉(zhuǎn)換：

      上式中，

   這里虛數(shù)部分采用負(fù)數(shù)的形式主要是為了跟復(fù)數(shù)傅立葉變換表達(dá)式保持一致，對(duì)于這種替換的方法來(lái)表示正余弦，符號(hào)的變換沒(méi)有什么好處，但替換時(shí)總會(huì)被改變掉符號(hào)以跟更高級(jí)的等價(jià)變換保持形式上的一致。 

    在離散信號(hào)處理中，運(yùn)用復(fù)數(shù)形式來(lái)表示正余弦波是個(gè)常用的技術(shù)，這是因?yàn)槔脧?fù)數(shù)進(jìn)行各種運(yùn)算得到的結(jié)果跟原來(lái)的正余弦運(yùn)算結(jié)果是一致的，但是，我們要小心使用復(fù)數(shù)操作，如加、減、乘、除，有些操作是不能用的，如兩個(gè)正弦信號(hào)相加，采用復(fù)數(shù)形式進(jìn)行相加，得到的結(jié)果跟替換前的直接相加的結(jié)果是一樣的，但是如果兩個(gè)正弦信號(hào)相乘，則采用復(fù)數(shù)形式來(lái)相乘結(jié)果是不一樣的。幸運(yùn)的是，我們已嚴(yán)格定義了正余弦復(fù)數(shù)形式的運(yùn)算操作條件：

1、  參加運(yùn)算的所有正余弦的頻率必須是一樣的；

2、  運(yùn)算操作必須是線性的，如兩個(gè)正弦信號(hào)可以進(jìn)行相加減，但不能進(jìn)行乘除，象信號(hào)的放大、衰減、高低通濾波等系統(tǒng)都是線性的，象平方、縮短、取限等則不是線性的。要記住的是卷積和傅立葉分析也只有線性操作才可以進(jìn)行。  

下圖是一個(gè)相量變換(我們把正弦或余弦波變成復(fù)數(shù)的形式稱為相量變換，Phasor transform)的例子，一個(gè)連續(xù)信號(hào)波經(jīng)過(guò)一個(gè)線性處理系統(tǒng)生成另一個(gè)信號(hào)波，從計(jì)算過(guò)程我們可以看出采用復(fù)數(shù)的形式使得計(jì)算變化十分的簡(jiǎn)潔：

       前一節(jié)中我們描述的實(shí)數(shù)形式傅立葉變換也是一種替換形式的復(fù)數(shù)變換，但要注意的是那還不是復(fù)數(shù)傅立葉變換，只是一種代替方式而已。下一節(jié)我們就會(huì)知道復(fù)數(shù)傅立葉變換是一種更高級(jí)的變換，而不是這種簡(jiǎn)單的替換形式。

理解離散傅立葉變換（四）

                     ------復(fù)數(shù)形式離散傅立葉變換

       復(fù)數(shù)形式的離散傅立葉變換非常巧妙地運(yùn)用了復(fù)數(shù)的方法，使得傅立葉變換變換更加自然和簡(jiǎn)潔，它并不是只是簡(jiǎn)單地運(yùn)用替換的方法來(lái)運(yùn)用復(fù)數(shù)，而是完全從復(fù)數(shù)的角度來(lái)分析問(wèn)題，這一點(diǎn)跟實(shí)數(shù)DFT是完全不一樣的。 

一、           把正余弦函數(shù)表示成復(fù)數(shù)的形式 

通過(guò)歐拉等式可以把正余弦函數(shù)表示成復(fù)數(shù)的形式：

       cos( x ) = 1/2 e ^j(-x) + 1/2 e^jx

      sin( x ) = j (1/2 e ^j(-x) - 1/2 e^jx)

從這個(gè)等式可以看出，如果把正余弦函數(shù)表示成復(fù)數(shù)后，它們變成了由正負(fù)頻率組成的正余弦波，相反地，一個(gè)由正負(fù)頻率組成的正余弦波，可以通過(guò)復(fù)數(shù)的形式來(lái)表示。 

我們知道，在實(shí)數(shù)傅立葉變換中，它的頻譜是0 ~ π(0 ~ N/2),但無(wú)法表示-π~ 0的頻譜，可以預(yù)見，如果把正余弦表示成復(fù)數(shù)形式，則能夠把負(fù)頻率包含進(jìn)來(lái)。 

二、           把變換前后都看成復(fù)數(shù)的形式 

復(fù)數(shù)形式傅立葉變換成原始信號(hào)x[n]當(dāng)成是一個(gè)用復(fù)數(shù)來(lái)表示的信號(hào)，其中實(shí)數(shù)部分表示原始信號(hào)值，虛數(shù)部分為0，變換結(jié)果X[k]也是個(gè)復(fù)數(shù)的形式，但這里的虛數(shù)部分是有值的。在這里用復(fù)數(shù)的觀點(diǎn)來(lái)看原始信號(hào)非常的關(guān)鍵，是理解復(fù)數(shù)形式傅立葉變換的關(guān)鍵（如果有學(xué)過(guò)復(fù)變函數(shù)則可能更好理解，即把x[n]看成是一個(gè)復(fù)數(shù)變量，然后象對(duì)等實(shí)數(shù)那樣對(duì)這個(gè)復(fù)數(shù)變量進(jìn)行相同的變換）。 

三、           對(duì)復(fù)數(shù)進(jìn)行相關(guān)性算法（正向傅立葉變換） 

從實(shí)數(shù)傅立葉變換中可以知道，我們可以通過(guò)原始信號(hào)把乘以一個(gè)正交函數(shù)形式的信號(hào)，然后進(jìn)行求總和，最后就能得到這個(gè)原始信號(hào)所包含的正交函數(shù)信號(hào)的分量?，F(xiàn)在我們的原始信號(hào)變成了復(fù)數(shù)，我們要得到的是復(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，…… 

這里我采用上面的第二個(gè)式子進(jìn)行相關(guān)性求和，為什么用第二個(gè)式，我在后面會(huì)知道，正弦函數(shù)在虛數(shù)中變換后得到的是負(fù)的正弦函數(shù)，這里我們?cè)偌由弦粋€(gè)負(fù)號(hào)，使得最后的得到的是正的正弦波，根據(jù)這個(gè)于是我們很容易就可以得到了復(fù)數(shù)形式的DFT正向變換等式：

       這個(gè)式子很容易可以得到歐拉變換式子：

       其實(shí)我們是為了表過(guò)上的方便才用到歐拉變換式，在分析問(wèn)題是我們還是較多地用到正余弦表達(dá)式。 

       對(duì)于上面的等式，我們要清楚如下幾個(gè)方面（也是區(qū)別于實(shí)數(shù)DFT的地方）：

1、  X[k]、x[n]都是復(fù)數(shù)，但x[n]的虛數(shù)部分都是由0組成的，實(shí)數(shù)部分表示原始信號(hào)；

2、  k的取值范圍是0 ~ N-1 (也可以表達(dá)成0 ~ 2π)，其中0 ~ N/2（或0 ~ π）是正頻部分，N/2 ~ N-1（π~ 2π）是負(fù)頻部分，由于正余弦函數(shù)的對(duì)稱性，所以我們把 –π~ 0表示成π~ 2π，這是出于計(jì)算上方便的考慮。

3、  其中的j是一個(gè)不可分離的組成部分，就象一個(gè)等式中的變量一樣，不能隨便去掉，去掉之后意義就完全不一樣了，但我們知道在實(shí)數(shù)DFT中，j只是個(gè)符號(hào)而已，把j去掉，整個(gè)等式的意義不變；

4、  下圖是個(gè)連續(xù)信號(hào)的頻譜，但離散頻譜也是與此類似的：

              上面的頻譜圖把負(fù)頻率放到了左邊，是為了迎合我們的思維習(xí)慣，但在實(shí)際實(shí)現(xiàn)中我們一般是把它移到正的頻譜后面的。

從上圖可以看出，時(shí)域中的正余弦波（用來(lái)組成原始信號(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ì)稱性（表示正弦波頻譜）。 

四、           逆向傅立葉變換 

假設(shè)我們已經(jīng)得到了復(fù)數(shù)形式的頻譜X[k]，現(xiàn)在要把它還原到復(fù)數(shù)形式的原始信號(hào)x[n]，當(dāng)然應(yīng)該是把X[k]乘以一個(gè)復(fù)數(shù)，然后再進(jìn)行求和，最后得到原始信號(hào)x[n]，這個(gè)跟X[k]相乘的復(fù)數(shù)首先讓我們想到的應(yīng)該是上面進(jìn)行相關(guān)性計(jì)算的復(fù)數(shù)：cos(2πkn/N) – j sin(2πkn/N)，但其中的負(fù)號(hào)其實(shí)是為了使得進(jìn)行逆向傅立葉變換時(shí)的正弦函數(shù)變?yōu)檎姆?hào)，因?yàn)樘摂?shù)j的運(yùn)算特殊性，使得原來(lái)應(yīng)該是正的正弦函數(shù)變?yōu)榱素?fù)的正弦函數(shù)（我們后面的推導(dǎo)會(huì)看到這一點(diǎn)），所以這里的負(fù)號(hào)只是為了糾正符號(hào)的作用，在進(jìn)行逆向DFT時(shí)，我們可以把負(fù)號(hào)去掉，于是我們便得到了這樣的逆向DFT變換等式：

x[n] = X[k] (cos(2πkn/N) + j sin(2πkn/N))

我們現(xiàn)在來(lái)分析這個(gè)式子，會(huì)發(fā)現(xiàn)這個(gè)式其實(shí)跟實(shí)數(shù)傅立葉變換是可以得到一樣結(jié)果的。我們先把X[k]變換一下：

X[k] = Re X[k] + j Im X[k]

這樣我們就可以對(duì)x[n]再次進(jìn)行變換，如：

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í)我們就把原來(lái)的等式分成了兩個(gè)部分，第一個(gè)部分是跟實(shí)域中的頻譜相乘，第二個(gè)部分是跟虛域中的頻譜相乘，根據(jù)頻譜圖我們可以知道，Re X[k]是個(gè)偶對(duì)稱的變量，Im X[k]是個(gè)奇對(duì)稱的變量，即

Re X[k] = Re X[- k]

Im X[k] = - Im X[-k]

但k的范圍是0 ~ N-1，0~N/2表示正頻率，N/2~N-1表示負(fù)頻率，為了表達(dá)方便我們把N/2~N-1用-k來(lái)表示，這樣在從0到N-1的求和過(guò)程中對(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)得到：

Re X[k] (cos(2πkn/N) + j sin(2πkn/N)) + Re X[ k] (cos( 2πkn/N) - j sin( 2πkn/N))

這個(gè)式最后的結(jié)果是：

2 Re X[ k] cos(2πkn/N)

再考慮到求Re X[ k]等式中有個(gè)1/N，把1/N乘以2，這樣的結(jié)果不就是跟實(shí)數(shù)DFT中的式子一樣了嗎？ 

對(duì)于(2)式，用同樣的方法，我們也可以得到這樣的結(jié)果：

-2 Im X[k] sin(2πkn/N)

注意上式前面多了個(gè)負(fù)符號(hào)，這是由于虛數(shù)變換的特殊性造成的，當(dāng)然我們肯定不能把負(fù)符號(hào)的正弦函數(shù)跟余弦來(lái)相加，還好，我們前面是用cos(2πkn/N) – j sin(2πkn/N)進(jìn)行相關(guān)性計(jì)算，得到的Im X[k]前面有個(gè)負(fù)的符號(hào)，這樣最后的結(jié)果中正弦函數(shù)就沒(méi)有負(fù)的符號(hào)了，這就是為什么在進(jìn)行相關(guān)性計(jì)算時(shí)虛數(shù)部分要用到負(fù)符號(hào)的原因（我覺得這也許是復(fù)數(shù)形式DFT美中不足的地方，讓人有一種拼湊的感覺）。 

從上面的分析中可以看出，實(shí)數(shù)傅立葉變換跟復(fù)數(shù)傅立葉變換，在進(jìn)行逆變換時(shí)得到的結(jié)果是一樣的，只不過(guò)是殊途同歸吧。

[來(lái)源：CSDN，freebean最后整理]