一 傅立葉變換
定義
f(t)滿足傅立葉積分定理條件時,下圖①式的積分運算稱為f(t)的傅立葉變換,
②式的積分運算叫做F(ω)的傅立葉逆變換。F(ω)叫做f(t)的象函數,f(t)叫做
F(ω)的象原函數。
傅裏葉變換
①
傅裏葉逆變換
②
中文譯名
Transformée de Fourier有多種中文譯名,常見的有"傅裏葉變換"、"傅立葉變換"、"付立葉變換"、"富裏葉變換"、"富裏哀變換"等等。為方便起見,本文統一寫作"傅裏葉變換"。
應用
傅裏葉變換在物理學、電子類學科、數論、組合數學、信號處理、概率論、統計學、密碼學、聲學、光學、海洋學、結構動力學等領域都有著廣泛的應用(例如在信號處理中,傅裏葉變換的典型用途是將信號分解成幅值分量和頻率分量)。
概要介紹
概要參見:林家翹、西格爾著《自然科學中確定性問題的應用數學》,科學出版社,北京。原版書名為 C. C. Lin & L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Inc., New York, 1974。
* 傅裏葉變換屬於諧波分析。
* 傅裏葉變換的逆變換容易求出,而且形式與正變換非常類似;
* 正弦基函數是微分運算的本征函數,從而使得線性微分方程的求解可以轉化為常係數的代數方程的求解.在線性時不變的物理係統內,頻率是個不變的性質,從而係統對於複雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取;
* 卷積定理指出:傅裏葉變換可以化複雜的卷積運算為簡單的乘積運算,從而提供了計算卷積的一種簡單手段;
* 離散形式的傅裏葉變換可以利用數字計算機快速的算出(其算法稱為快速傅裏葉變換算法(FFT)).
基本性質
線性性質
兩函數之和的傅裏葉變換等於各自變換之和。數學描述是:若函數f \left( x\right )和g \left(x \right)的傅裏葉變換\mathcal[f]和\mathcal[g]都存在,α 和 β 為任意常係數,則\mathcal[\alpha f+\beta g]=\alpha\mathcal[f]+\beta\mathcal[g];傅裏葉變換算符\mathcal可經歸一化成為麽正算符;
頻移性質
若函數f \left( x\right )存在傅裏葉變換,則對任意實數 ω0,函數f(x) e^{i \omega_ x}也存在傅裏葉變換,且有\mathcal[f(x)e^{i \omega_ x}]=F(\omega + \omega _0 ) 。式中花體\mathcal是傅裏葉變換的作用算子,平體F表示變換的結果(複函數),e 為自然對數的底,i 為虛數單位\sqrt;
微分關係
若函數f \left( x\right )當|x|\rightarrow\infty時的極限為0,而其導函數f'(x)的傅裏葉變換存在,則有\mathcal[f'(x)]=-i \omega \mathcal[f(x)] ,即導函數的傅裏葉變換等於原函數的傅裏葉變換乘以因子 ? iω 。更一般地,若f(\pm\infty)=f'(\pm\infty)=\ldots=f^{(k-1)}(\pm\infty)=0,且\mathcal[f^{(k)}(x)]存在,則\mathcal[f^{(k)}(x)]=(-i \omega)^ \mathcal[f] ,即 k 階導數的傅裏葉變換等於原函數的傅裏葉變換乘以因子( ? iω)k。
卷積特性
若函數f \left( x\right )及g \left( x\right )都在(-\infty,+\infty)上絕對可積,則卷積函數f*g=\int_{-\infty}^{+\infty} f(x-\xi)g(\xi)d\xi的傅裏葉變換存在,且\mathcal[f*g]=\mathcal[f]\cdot\mathcal[g] 。卷積性質的逆形式為\mathcal^[F(\omega)G(\omega)]=\mathcal^[F(\omega)]*\mathcal^[G(\omega)] ,即兩個函數乘積的傅裏葉逆變換等於它們各自的傅裏葉逆變換的卷積,同時還有兩個函數卷積的傅裏葉逆變換等於它們各自的傅裏葉逆變換的乘積。
Parseval定理
若函數f \left( x\right )可積且平方可積,則\int_{-\infty}^{+\infty} f^2 (x)dx = \frac{2\pi}\int_{-\infty}^{+\infty} |F(\omega)|^d\omega 。其中 F(ω) 是 f(x) 的傅裏葉變換。
傅裏葉變換的不同變種
連續傅裏葉變換
主條目:連續傅立葉變換
一般情況下,若"傅立葉變換"一詞的前麵未加任何限定語,則指的是"連續傅裏葉變換"。"連續傅裏葉變換"將平方可積的函數f(t) 表示成複指數函數的積分或級數形式。
f(t) = \mathcal^[F(\omega)] = \frac{\sqrt{2\pi}} \int\limits_{-\infty}^\infty F(\omega) e^{i\omega t}\,d\omega.
上式其實表示的是連續傅裏葉變換的逆變換,即將時間域的函數f(t)表示為頻率域的函數F(ω)的積分。反過來,其正變換恰好是將頻率域的函數F(ω)表示為時間域的函數f(t)的積分形式。一般可稱函數f(t)為原函數,而稱函數F(ω)為傅裏葉變換的像函數,原函數和像函數構成一個傅立葉變換對(transform pair)。
一種對連續傅裏葉變換的推廣稱為分數傅裏葉變換(Fractional Fourier Transform)。
當f(t)為奇函數(或偶函數)時,其餘弦(或正弦)分量將消亡,而可以稱這時的變換為餘弦轉換(cosine transform) 或 正弦轉換(sine transform).
另一個值得注意的性質是,當f(t) 為純實函數時,F(?ω) = F(ω)*成立.
傅裏葉級數
主條目:傅裏葉級數
連續形式的傅裏葉變換其實是傅裏葉級數的推廣,因為積分其實是一種極限形式的求和算子而已。對於周期函數,其傅裏葉級數是存在的:
f(x) = \sum_{n=-\infty}^{\infty} F_n \,e^ ,
其中Fn 為複振幅。對於實值函數,函數的傅裏葉級數可以寫成:
f(x) = \fraca_0 + \sum_{n=1}^\infty\left[a_n\cos(nx)+b_n\sin(nx)\right],
其中an和bn是實頻率分量的振幅。
離散時間傅裏葉變換
主條目:離散時間傅裏葉變換
離散傅裏葉變換是離散時間傅裏葉變換(DTFT)的特例(有時作為後者的近似)。DTFT在時域上離散,在頻域上則是周期的。DTFT可以被看作是傅裏葉級數的逆。
離散傅裏葉變換
主條目:離散傅裏葉變換
為了在科學計算和數字信號處理等領域使用計算機進行傅裏葉變換,必須將函數xn 定義在離散點而非連續域內,且須滿足有限性或周期性條件。這種情況下, 使用離散傅裏葉變換,將函數 xn 表示為下麵的求和形式:
x_n = \frac1 \sum_{k=0}^ X_k e^{i\frac{2\pi} kn} \qquad n = 0,\dots,N-1
其中Xk是傅裏葉振幅。直接使用這個公式計算的計算複雜度為\mathcal(n^2),而快速傅裏葉變換(FFT)可以將複雜度改進為\mathcal(n \log n)。計算複雜度的降低以及數字電路計算能力的發展使得DFT成為在信號處理領域十分實用且重要的方法。
在阿貝爾群上的統一描述
以上各種傅裏葉變換可以被更統一的表述成任意局部緊致的阿貝爾群上的傅裏葉變換。這一問題屬於調和分析的範疇。在調和分析中, 一個變換從一個群變換到它的對偶群(dual group)。此外,將傅裏葉變換與卷積相聯係的卷積定理在調和分析中也有類似的結論。傅裏葉變換的廣義理論基礎參見龐特裏雅金對偶性(英文版)中的介紹。
時頻分析變換
主條目:時頻分析變換
小波變換,chirplet轉換和分數傅裏葉轉換試圖得到時間信號的頻率信息。同時解析頻率和時間的能力在數學上受不確定性原理的限製。
傅裏葉變換家族
下表列出了傅裏葉變換家族的成員. 容易發現,函數在時(頻)域的離散對應於其像函數在頻(時)域的周期性.反之連續則意味著在對應域的信號的非周期性.
變換 時間 頻率
連續傅裏葉變換 連續, 非周期性 連續, 非周期性
傅裏葉級數 連續, 周期性 離散, 非周期性
離散時間傅裏葉變換 離散, 非周期性 連續, 周期性
離散傅裏葉變換 離散, 周期性 離散, 周期性
傅裏葉變換的基本思想首先由法國學者傅裏葉係統提出,所以以其名字來命名以示紀念。
從現代數學的眼光來看,傅裏葉變換是一種特殊的積分變換。它能將滿足一定條件的某個函數表示成正弦基函數的線性組合或者積分。在不同的研究領域,傅裏葉變換具有多種不同的變體形式,如連續傅裏葉變換和離散傅裏葉變換。
傅立葉變換屬於調和分析的內容。"分析"二字,可以解釋為深入的研究。從字麵上來看,"分析"二字,實際就是"條分縷析"而已。它通過對函數的"條分縷析"來達到對複雜函數的深入理解和研究。從哲學上看,"分析主義"和"還原主義",就是要通過對事物內部適當的分析達到增進對其本質理解的目的。比如近代原子論試圖把世界上所有物質的本源分析為原子,而原子不過數百種而已,相對物質世界的無限豐富,這種分析和分類無疑為認識事物的各種性質提供了很好的手段。
數學領域
盡管最初傅立葉分析是作為熱過程的解析分析的工具,但是其思想方法仍然具有典型的還原論和分析主義的特征。"任意"的函數通過一定的分解,都能夠表示為正弦函數的線性組合的形式,而正弦函數在物理上是被充分研究而相對簡單的函數類,這一想法跟化學上的原子論想法何其相似!奇妙的是,現代數學發現傅立葉變換具有非常好的性質,使得它如此的好用和有用,讓人不得不感歎造物的神奇:
1. 傅立葉變換是線性算子,若賦予適當的範數,它還是酉算子;
2. 傅立葉變換的逆變換容易求出,而且形式與正變換非常類似;
3. 正弦基函數是微分運算的本征函數,從而使得線性微分方程的求解可以轉化為常係數的代數方程的求解.在線性時不變的物理係統內,頻率是個不變的性質,從而係統對於複雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取;
4. 著名的卷積定理指出:傅立葉變換可以化複雜的卷積運算為簡單的乘積運算,從而提供了計算卷積的一種簡單手段;
5. 離散形式的傅立葉變換可以利用數字計算機快速的算出(其算法稱為快速傅立葉變換算法(FFT)).
正是由於上述的良好性質,傅裏葉變換在物理學、數論、組合數學、信號處理、概率、統計、密碼學、聲學、光學等領域都有著廣泛的應用。
有関傅立葉變換的FPGA實現
傅立葉變換是數字信號處理中的基本操作,廣泛應用於表述及分析離散時域信號領域。但由於其運算量與變換點數N的平方成正比關係,因此,在N較大時,直接應用DFT算法進行譜變換是不切合實際的。然而,快速傅立葉變換技術的出現使情況發生了根本性的變化。本文主要描述了采用FPGA來實現2k/4k/8k點FFT的設計方法。
整體結構
一般情況下,N點的傅立葉變換對為:
其中,WN=exp(-2pi/N)。X(k)和x(n)都為複數。與之相對的快速傅立葉變換有很多種,如DIT(時域抽取法)、DIF(頻域抽取法)、Cooley-Tukey和Winograd等。對於2n傅立葉變換,Cooley-Tukey算法可導出DIT和DIF算法。本文運用的基本思想是Cooley-Tukey算法,即將高點數的傅立葉變換通過多重低點數傅立葉變換來實現。雖然DIT與DIF有差別,但由於它們在本質上都是一種基於標號分解的算法,故在運算量和算法複雜性等方麵完全一樣,而沒有性能上的優劣之分,所以可以根據需要任取其中一種,本文主要以DIT方法為對象來討論。
N=8192點DFT的運算表達式為:
式中,m=(4n1+n2)(2048k1+k2)(n=4n1+n2,k=2048k1+k2)其中n1和k2可取0,1,...,2047,k1和n2可取0,1,2,3。
由式(3)可知,8k傅立葉變換可由4×2k的傅立葉變換構成。同理,4k傅立葉變換可由2×2k的傅立葉變換構成。而2k傅立葉變換可由128×16的傅立葉變換構成。128的傅立葉變換可進一步由16×8的傅立葉變換構成,歸根結底,整個傅立葉變換可由基2、基4的傅立葉變換構成。2k的FFT可以通過5個基4和1個基2變換來實現;4k的FFT變換可通過6個基4變換來實現;8k的FFT可以通過6個基4和1個基2變換來實現。也就是說:FFT的基本結構可由基2/4模塊、複數乘法器、存儲單元和存儲器控製模塊構成,其整體結構如圖1所示。
圖1中,RAM用來存儲輸入數據、運算過程中的中間結果以及運算完成後的數據,ROM用來存儲旋轉因子表。蝶形運算單元即為基2/4模塊,控製模塊可用於產生控製時序及地址信號,以控製中間運算過程及最後輸出結果。
蝶形運算器的實現
基4和基2的信號流如圖2所示。圖中,若A=r0+j*i0,B=r1+j*i1,C=r2+j*i2,D=r3+j*i3是要進行變換的信號,Wk0=c0+j*s0=1,Wk1=c1+j*s1,Wk2=c2+j*s2,Wk3=c3+j*s3為旋轉因子,將其分別代入圖2中的基4蝶形運算單元,則有:
A′=[r0+(r1×c1-i1×s1)+(r2×c2-i2×s2)+(r3×c3-i3×s3)]+j[i0+(i1×c1+r1×s1)+(i2×c2+r2×s2)+(i3×c3+r3×s3)]? (4)
B′=[r0+(i1×c1+r1×s1)-(r2×c2-i2×s2)-(i3×c3+r3×s3)]+j[i0-(r1×c1-i1×s1)-(i2×c2+r2×s2)+(r3×c3-i3×s3)] (5)
C′=[r0-(r1×c1-i1×s1)+(r2×c2-i2×s2)-(r3×c3-i3×s3)]+j[i0-(i1×c1+r1×s1)+(i2×c2+r2×s2)-(i3×c3+r3×s3)] (6)
D′=[r0-(i1×c1+r1×s1)-(r2×c2-i2×s2)+(i3×c3+r3×s3)]+j[i0+(r1×c1-i1×s1)-(i2×c2+r2×s2)-(r3×c3-i3×s3)]? (7)
而在基2蝶形中,Wk0和Wk2的值均為1,這樣,將A,B,C和D的表達式代入圖2中的基2運算的四個等式中,則有:
A′=r0+(r1×c1-i1×s1)+j[i0+(i1×c1+r1×s1)]? (8)
B′=r0- (r1×c1-i1×s1)+j[i0-(i1×c1+r1×s1)] (9)
C′=r2+(r3×c3-i3×s3)+j[i0+(i3×c3+r3×s3)]? (10)
D′=r2-(r3×c3-i3×s3)+j[i0-(i3×c3+r3×s3)]? (11)
在上述式(4)~(11)中有很多類同項,如i1×c1+r1×s1和r1×c1-i1×s1等,它們僅僅是加減號的不同,其結構和運算均類似,這就為簡化電路提供了可能。同時,在蝶形運算中,複數乘法可以由實數乘法以一定的格式來表示,這也為設計複數乘法器提供了一種實現的途徑。
以基4為例,在其運算單元中,實際上隻需做三個複數乘法運算,即隻須計算BWk1、CWk2和DWk3的值即可,這樣在一個基4蝶形單元裏麵,最多隻需要3個複數乘法器就可以了。在實際過程中,在不提高時鍾頻率下,隻要將時序控製好?便可利用流水線(Pipeline)技術並隻用一個複數乘法器就可完成這三個複數乘法,大大節省了硬件資源。
圖2 基2和基4蝶形算法的信號流圖
FFT的地址
FFT變換後輸出的結果通常為一特定的倒序,因此,幾級變換後對地址的控製必須準確無誤。
倒序的規律是和分解的方式密切相關的,以基8為例,其基本倒序規則如下:
基8可以用2×2×2三級基2變換來表示,則其輸入順序則可用二進製序列(n1 n2 n3)來表示,變換結束後,其順序將變為(n3 n2 n1),如:X?011 → x?110 ,即輸入順序為3,輸出時順序變為6。
更進一步,對於基16的變換,可由2×2×2×2,4×4,4×2×2等形式來構成,相對於不同的分解形式,往往會有不同的倒序方式。以4×4為例,其輸入順序可以用二進製序列(n1 n2 n3n4)來表示變換結束後,其順序可變為((n3 n4)(n1 n2)),如: X?0111 → x?1101 。即輸入順序為7,輸出時順序變為13。
在2k/4k/8k的傅立葉變換中,由於要經過多次的基4和基2運算,因此,從每次運算完成後到進入下一次運算前,應對運算的結果進行倒序,以保證運算的正確性。
旋轉因子
N點傅立葉變換的旋轉因子有著明顯的周期性和對稱性。其周期性表現為:
FFT之所以可使運算效率得到提高,就是利用
FFT之所以可使運算效率得到提高,就是利用了對稱性和周期性把長序列的DFT逐級分解成幾個序列的DFT,並最終以短點數變換來實現長點數變換。
根據旋轉因子的對稱性和周期性,在利用ROM存儲旋轉因子時,可以隻存儲旋轉因子表的一部分,而在讀出時增加讀出地址及符號的控製,這樣可以正確實現FFT。因此,充分利用旋轉因子的性質,可節省70%以上存儲單元。
實際上,由於旋轉因子可分解為正、餘弦函數的組合,故ROM中存的值為正、餘弦函數值的組合。對2k/4k/8k的傅立葉變換來說,隻是對一個周期進行不同的分割。由於8k變換的旋轉因子包括了2k/4k的所有因子,因此,實現時隻要對讀ROM的地址進行控製,即可實現2k/4k/8k變換的通用。
存儲器的控製
因FFT是為時序電路而設計的,因此,控製信號要包括時序的控製信號及存儲器的讀寫地址,並產生各種輔助的指示信號。同時在計算模塊的內部,為保證高速,所有的乘法器都須始終保持較高的利用率。這意味著在每一個時鍾來臨時都要向這些單元輸入新的操作數,而這一切都需要控製信號的緊密配合。
為了實現FFT的流形運算,在運算的同時,存儲器也要接收數據。這可以采用乒乓RAM的方法來完成。這種方式決定了實現FFT運算的最大時間。對於4k操作,其接收時間為4096個數據周期,這樣?FFT的最大運算時間就是4096個數據周期。另外,由於輸入數據是以一定的時鍾為周期依次輸入的,故在進行內部運算時,可以用較高的內部時鍾進行運算,然後再存入RAM依次輸出。
為節省資源,可對存儲數據RAM采用原址讀出原址寫入的方法,即在進行下一級變換的同時,首先應將結果回寫到讀出數據的RAM存貯器中;而對於ROM,則應采用與運算的數據相對應的方法來讀出存儲器中旋轉因子的值。
在2k/4k/8k傅立葉變換中,要實現通用性,控製器是最主要的模塊。2k、4k、8k變換具有不同的內部運算時間和存儲器地址,在設計中,針對不同的點數應設計不同的存儲器存取地址,同時,在完成變換後,還要對開始輸出有用信號的時刻進行指示。
硬件的選擇
本設計的硬件實現選用的是現場可編程門陣列(FPGA)來滿足較高速度的需要。本係統在設計時選用的是ALTERA公司的STRATIX芯片,該芯片中包含有DSP單元,可以完成較為耗費資源的乘法器單元。同時,該器件也包含有大量存儲單元,從而可保證旋轉因子的精度。
除了一些專用引腳外,FPGA上幾乎所有的引腳均可供用戶使用,這使得FPGA信號處理方案具有非常好的I/O帶寬。大量的I/O引腳和多塊存儲器可使設計獲得優越的並行處理性能。其獨立的存儲塊可作為輸入/工作存儲區和結果的緩存區,這使得I/O可與FFT計算同時進行。在實現的時間方麵,該設計能在4096個時鍾周期內完成一個4096點的FFT。若采用10MHz的輸入時鍾,其變換時間在200μs左右。而由於最新的FPGA使用了MultiTrack互連技術,故可在250MHz以下頻率穩定地工作,同時,FFT的實現時間也可以大大縮小。
FFT運算結果的精度與輸入數據的位數及運算過程中的位數有關,同時和數據的表示形式也有很大關係。一般來說,浮點方式比定點方式精度高。而在定點計算中,存儲器數據的位數越大,運算精度越高,使用的存儲單元和邏輯單元也越多。在實際應用中,應根據實際情況折衷選擇精度和資源。本設計通過MATLAB進行仿真證明:其實現的變換結果與MATLAB工具箱中的FFT函數相比,信噪比可以達到65db以上,完全可以滿足一般工程的實際應用要求。
傅裏葉變換的實質是將一個信號分離為無窮多多正弦/複指數信號的加成,也就是說,把信號變成正弦信號相加的形式--既然是無窮多個信號相加,那對於非周期信號來說,每個信號的加權應該都是零--但有密度上的差別,你可以對比概率論中的概率密度來思考一下--落到每一個點的概率都是無限小,但這些無限小是有差別的。
所以,傅裏葉變換之後,橫坐標即為分離出的正弦信號的頻率,縱坐標對應的是加權密度對於周期信號來說,因為確實可以提取出某些頻率的正弦波成分,所以其加權不為零--在幅度譜上,表現為無限大--但這些無限大顯然是有區別的,所以我們用衝激函數表示 已經說過,傅裏葉變換是把各種形式的信號用正弦信號表示,因此非正弦信號進行傅裏葉變換,會得到與原信號頻率不同的成分--都是原信號頻率的整數倍。這些高頻信號是用來修飾頻率與原信號相同的正弦信號,使之趨近於原信號的。所以說,頻譜上頻率最低的一個峰(往往是幅度上最高的),就是原信號頻率
傅裏葉變換把信號由時域轉為頻域,因此把不同頻率的信號在時域上拚接起來進行傅裏葉變換是沒有意義的--實際情況下,我們隔一段時間采集一次信號進行變換,才能體現出信號在頻域上隨時間的變化。
我的語言可能比較晦澀,但我已盡我所能向你講述我的一點理解--真心希望能對你有用。我已經很久沒在知道上回答過問題了,之所以回答這個問題,是因為我本人在學習傅裏葉變換及拉普拉斯變換的過程中著實受益匪淺--它們幾乎改變了我對世界的認識。傅裏葉變換值得你用心去理解--哪怕苦苦思索幾個月也是值得的--我當初也想過:隻要會算題就行。但浙大校訓"求是"時時刻刻鞭策著我追求對理論的理解--最終經過很痛苦的一番思索才恍然大悟。建議你看一下我們信號與係統課程的教材:化學工業出版社的《信號與係統》,會有所幫助。