傅立葉變換，表示能將滿足一定條件的某個函數表示成三角函數（正弦和/或余弦函數）或者它們的積分的線性組合。在不同的研究領域，傅立葉變換具有多種不同的變體形式，如連續傅立葉變換和離散傅立葉變換。最初傅立葉分析是作為熱過程的解析分析的工具被提出的。

　　傅里葉變換怎么發現的

　　傅里葉分析方法的建立有過一段漫長的歷史，涉及到很多人的工作和許多不同物理現象的研究。利用“三角函數和”的概念（也即，成諧波關系的正弦和余弦函數或周期復指數函數的和）來描述周期性過程至少可以追溯到古代巴比倫人時代，當時他們利用這一想法來預測天體運動。這一問題目的近代歷史始于1748年歐拉在振動弦的研究工作中。圖3.1畫出了弦振動的前幾個標準振蕩模式。如果用f（t，x）來表示弦在時間z和沿著弦的某 橫向距離x處的垂直偏離，則對任意固定時刻t來說，所有這些振蕩模式均為x的正弦函數，并成諧波關系。

　　歐拉得出的結論是：如果在某一時刻振動弦的形狀是這些標準振蕩模的線性組合，那么在其后任何時刻，振動弦的形狀也都是這些振蕩模的線性組合。另外，歐拉還證明了在該線性組合中，其后面時間的加權系數可以直接從前面時間的加權系數中導得。與此同時，歐拉還完成了相同的計算形式，這一點將在下一節導出有關三角函數和的一個性質中看到， 這些性質使三角函數和的概念在LTI系統分析中變得十分有用。具體地說就是：如果一個LTI系統的輸入可以表示為周期復指數或正弦信號的線性組合，則輸出也一定能表示成這種形式；并且輸出線性組合中的加權系數是直接與輸入中對應的系數有關的。

　　顯然，除非很多有用信號都能用復指數的線性組合來表示，否則上面所討論的性質就不會是特別有用的。在18世紀中期，這一點曾是激烈爭論的主題。1753年D·伯努利（D. Bernoulli）曾經聲稱：一根弦的實際運動都可以用標準振蕩模的線性組合來表示。但是，他并投有繼續從數學上深入探求下去；問時，在當時他的想法也并未被廣泛接受。

　　事實上，歐拉本人后來也拋棄了三角級數的想法，并且在1759年J.L.拉格朗日（J.L.Lagrange）也曾強烈批評使用三角級數來研究振動弦運動的主張。他反對的論據是基于他自己的信念，即不可能用三角級數來表示一個具有間斷點的函數。因為振動弦的波形是由撥動弦而引起（即把弦繃緊再松開），所以拉格朗日認為三角級數的應用范圍非常有限。

　　正是在這種多少有些敵意和懷疑的處境下，J.B.J.傅里葉（Jean Baptiste Joseph Fourier）約于半個世紀后提出了他自己的想法。傅里葉1768年3月21日生于法國奧克斯雷（Allxerre）， 到他加入這場有關三角級數論戰的時候，他已有了相當的閱歷。他當時進行研究所處的境遇使他的很多貢獻（特別是以他的名字命名的級數和變換）更是令人難忘。

　　他的重大發現雖然在他自己的有生之年沒有得到完全的承認，但是，卻已對數學這門學科的發展產生了深刻的影響，并在極為廣泛的科學和工程領域內一直具有并仍然繼續具有很大的價值。

　　除了他在數學方面的研究外，傅里葉還有一段活躍的政治生涯。事實上，就在法國大革命后的那些年代里，他的一些活動幾乎導致他的垮臺。因為曾經有兩次，他都差一點走上了斷頭臺。其后，傅里葉又成為N.波拿馬（Napsleon Bonaparle）的伙伴而跟隨著他遠征埃及（在此期間，傅里葉搜集了后來作為他的“埃及學”論文基礎的有關資料）。在1802年被波拿馬任命為法國某一地區的行政長官，就在他任職行政長官的期間，傅里葉構思了關于三角級數的想法。

　　熱的傳播和擴散現象是導致傅里葉研究成果的實際物理背景。在當時數學物理學領城中大多數前人的研究巳經涉及到理論力學和天體力學的背景下，這一問題本身就是十分有意義的一步。到了1807年，傅里葉已經完成了一項研究，他發現在表示一個物體的溫度分布時，成諧波關系的正弦函數級數是非常有用的。

　　另外，他還斷言：“任何”周期信號都可以用這樣的級數來表示！？雖然在這一問題上他的論述是很有意義的，但是，隱藏在這一問題后面的其它很多基本概意己經被其他科學家們所發現；同時，傅里葉的數學證明也不是很完善的。后來于1829年，P.L.狄里赫利（P.L.Dirichlet）給出了若干精確的條件，在這些條件下，一個周期信號才可以用一個傅里葉級數表示。因此，傅里葉實際上并沒有對傅里葉級數的數學理論做出什么貢獻。然而，他確實洞察出這個級數表示法的潛在威力，井且在很大程度上正是由于他的工作和斷言，才大大激勵和推動了傅里葉級數問題的深入研究。

　　另外，傅里葉在這一問題上的研究成果比他的任何先驅者都大大前進了一步，這指的是他還得出了關于非周期信號的表示——不是成諧被關系的正弦信號的加權和，而是不全成諧波關系的正弦信號的加權積分。這就是第4和第5章所關注的從傅里葉級數到傅里葉積分（或變換）的推廣。和傅里葉級數一樣，傅里葉變換仍然是分析LTI系統最強有力的工具之一。

　　當時指定了4位著名的數學家和科學家來評審1807年傅里葉的論文，其中3位即S.F.拉克勞克斯（S.F.Lacroix）、G.孟濟（G.Monge）和P.S.拉普拉斯（P.S.Laplace）贊成發表傅里葉的論文，而第四位J.L.拉格朗日仍然頑固地堅持他于50年前就已經提出過的關于拒絕接受三角級數的論點。

　　由于拉格朗日的強烈反對，傅里葉的論文從未公開露面過。為了使他的研究成果能讓法蘭西研究院接受并發表，在經過了幾次其它的嘗試以后，傅里葉才把他的成果以另一種方式出現在“熱的分析理論”這本書中。這本書出版于1822年，也即比他首次在法蘭西研究院宣讀他的研究成果時晚15年！

　　直到傅里葉的晚年，他才得到了某種應有的承認！但是，對他來說最有意義的稱贊是他的研究成果已經在數學、科學和工程等如此眾多的領域內產生的巨大影響。傅里葉級數和積分的分析在很多數學問題中都留下了它的足跡，積分理論、點集拓撲和特征函數展開等僅是這方面的幾個例子。再者，除了最初在振動問題和傳熱問題的研究外，在科學和工程領域中有大量的其它問題，正弦信號（從而傅里葉級數和變換）在其中起著很重要的作用。

　　例如，在描述行星運動和反映地球氣候的周期性變化中，很自然地會出現正弦信號；交流電源產生的正弦電壓和電流；以及我們將要看到的，傅里葉分析方法能夠用來分析LTI系統的響應，比如一個電路對正弦輸入的響應等。同時，海浪也是由不同波長的正弦波的線性組合所組成的；無線電臺和電視臺發射的信號都是正弦的；以及依據傅里葉分析可以給出任何文本的快邊閱讀等等。總之，正弦信號和傅里葉分析方法的應用范圍遠遠超出以上所列舉的這幾個例子。

　　在前面一段中的許多應用，以及傅里葉和他的問伴們在數學物理學方面的最初研究都是集中在連續時間內的現象。與此同時，對于離散時間信號與系統的傅里葉分析方法卻有著它們自己不同的歷史根基，并且也有眾多的應用領域。尤其是，離散時間概念和方法是數值分析這門學科的基礎。

　　用于處理離散點集以產生數值近似的有關內插、積分和微分等方面的公式遠在17世紀的牛頓時代就被研究過。另外，在已知一組天體觀察數據序列下，預測某一天體運動的問題在18和19世紀曾吸引著包括高斯（Gauss）在內的許多著名科學家和數學家從事調和時間序列的研究，從而為大量的初始工作能在離散時間信號與系統下完成提供了第二個舞臺。

　　在20世紀60年代中期，一種稱之為快速傅里葉變換（FFT）的算法被引入。這一算法在1965年被庫利（Cooley）和圖基（Tukey）獨立地發現，其實它也有相當長的歷史。事實上，這一算法在高斯的手稿中已能找到。

　　之所以使得它成為重要的近代發現是由于FFT證明是非常適合于高效的數字實現，并且它將計算變換所需要的時間減少了幾個數量級。有了這一算法，在利用離散時間傅里葉級數和變換中許多有興趣而過去認為不切實際的想法突然變得實際起來，井且使離散時間信號與系統分析技術的發展加速向前邁進。

　　由這樣一個很長歷史的發展所涌現出的，對于連續時間和離散時間信號與系統分析來說是一個強有力而嚴謹的分析體系，以及有著極為廣泛的現存和潛在的應用范倒。這一章和后續幾章將建立這個體系中的一些基本方法，井研究其中某些重要的內涵。

　　傅里葉變換有什么用

　　盡管最初傅里葉分析是作為熱過程的解析分析的工具，但是其思想方法仍然具有典型的還原論和分析主義的特征。“任意”的函數通過一定的分解，都能夠表示為正弦函數的線性組合的形式，而正弦函數在物理上是被充分研究而相對簡單的函數類，這一想法跟化學上的原子論想法何其相似！奇妙的是，現代數學發現傅里葉變換具有非常好的性質，使得它如此的好用和有用，讓人不得不感嘆造物的神奇：

　　傅里葉變換是線性算子，若賦予適當的范數，它還是酉算子；

　　傅里葉變換的逆變換容易求出，而且形式與正變換非常類似；

　　正弦基函數是微分運算的本征函數，從而使得線性微分方程的求解可以轉化為常系數的代數方程的求解。在線性時不變的物理系統內，頻率是個不變的性質，從而系統對于復雜激勵的響應可以通過組合其對不同頻率正弦信號的響應來獲取；

　　著名的卷積定理指出：傅里葉變換可以化復雜的卷積運算為簡單的乘積運算，從而提供了計算卷積的一種簡單手段；

　　離散形式的傅里葉變換可以利用數字計算機快速的算出（其算法稱為快速傅里葉變換算法（FFT））。

　　正是由于上述的良好性質，傅里葉變換在物理學、數論、組合數學、信號處理、概率、統計、密碼學、聲學、光學等領域都有著廣泛的應用。

　　有關傅里葉變換的FPGA實現

　　傅里葉變換是數字信號處理中的基本操作，廣泛應用于表述及分析離散時域信號領域。但由于其運算量與變換點數N的平方成正比關系，因此，在N較大時，直接應用DFT算法進行譜變換是不切合實際的。然而，快速傅里葉變換技術的出現使情況發生了根本性的變化。本文主要描述了采用FPGA來實現2k/4k/8k點FFT的設計方法。