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

　　傅里葉變換怎么發(fā)現(xiàn)的

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

　　歐拉得出的結(jié)論是：如果在某一時(shí)刻振動(dòng)弦的形狀是這些標(biāo)準(zhǔn)振蕩模的線性組合，那么在其后任何時(shí)刻，振動(dòng)弦的形狀也都是這些振蕩模的線性組合。另外，歐拉還證明了在該線性組合中，其后面時(shí)間的加權(quán)系數(shù)可以直接從前面時(shí)間的加權(quán)系數(shù)中導(dǎo)得。與此同時(shí)，歐拉還完成了相同的計(jì)算形式，這一點(diǎn)將在下一節(jié)導(dǎo)出有關(guān)三角函數(shù)和的一個(gè)性質(zhì)中看到， 這些性質(zhì)使三角函數(shù)和的概念在LTI系統(tǒng)分析中變得十分有用。具體地說(shuō)就是：如果一個(gè)LTI系統(tǒng)的輸入可以表示為周期復(fù)指數(shù)或正弦信號(hào)的線性組合，則輸出也一定能表示成這種形式；并且輸出線性組合中的加權(quán)系數(shù)是直接與輸入中對(duì)應(yīng)的系數(shù)有關(guān)的。

　　顯然，除非很多有用信號(hào)都能用復(fù)指數(shù)的線性組合來(lái)表示，否則上面所討論的性質(zhì)就不會(huì)是特別有用的。在18世紀(jì)中期，這一點(diǎn)曾是激烈爭(zhēng)論的主題。1753年D·伯努利（D. Bernoulli）曾經(jīng)聲稱：一根弦的實(shí)際運(yùn)動(dòng)都可以用標(biāo)準(zhǔn)振蕩模的線性組合來(lái)表示。但是，他并投有繼續(xù)從數(shù)學(xué)上深入探求下去；問(wèn)時(shí)，在當(dāng)時(shí)他的想法也并未被廣泛接受。

　　事實(shí)上，歐拉本人后來(lái)也拋棄了三角級(jí)數(shù)的想法，并且在1759年J.L.拉格朗日（J.L.Lagrange）也曾強(qiáng)烈批評(píng)使用三角級(jí)數(shù)來(lái)研究振動(dòng)弦運(yùn)動(dòng)的主張。他反對(duì)的論據(jù)是基于他自己的信念，即不可能用三角級(jí)數(shù)來(lái)表示一個(gè)具有間斷點(diǎn)的函數(shù)。因?yàn)檎駝?dòng)弦的波形是由撥動(dòng)弦而引起（即把弦繃緊再松開），所以拉格朗日認(rèn)為三角級(jí)數(shù)的應(yīng)用范圍非常有限。

　　正是在這種多少有些敵意和懷疑的處境下，J.B.J.傅里葉（Jean Baptiste Joseph Fourier）約于半個(gè)世紀(jì)后提出了他自己的想法。傅里葉1768年3月21日生于法國(guó)奧克斯雷（Allxerre）， 到他加入這場(chǎng)有關(guān)三角級(jí)數(shù)論戰(zhàn)的時(shí)候，他已有了相當(dāng)?shù)拈啔v。他當(dāng)時(shí)進(jìn)行研究所處的境遇使他的很多貢獻(xiàn)（特別是以他的名字命名的級(jí)數(shù)和變換）更是令人難忘。

　　他的重大發(fā)現(xiàn)雖然在他自己的有生之年沒有得到完全的承認(rèn)，但是，卻已對(duì)數(shù)學(xué)這門學(xué)科的發(fā)展產(chǎn)生了深刻的影響，并在極為廣泛的科學(xué)和工程領(lǐng)域內(nèi)一直具有并仍然繼續(xù)具有很大的價(jià)值。

　　除了他在數(shù)學(xué)方面的研究外，傅里葉還有一段活躍的政治生涯。事實(shí)上，就在法國(guó)大革命后的那些年代里，他的一些活動(dòng)幾乎導(dǎo)致他的垮臺(tái)。因?yàn)樵?jīng)有兩次，他都差一點(diǎn)走上了斷頭臺(tái)。其后，傅里葉又成為N.波拿馬（Napsleon Bonaparle）的伙伴而跟隨著他遠(yuǎn)征埃及（在此期間，傅里葉搜集了后來(lái)作為他的“埃及學(xué)”論文基礎(chǔ)的有關(guān)資料）。在1802年被波拿馬任命為法國(guó)某一地區(qū)的行政長(zhǎng)官，就在他任職行政長(zhǎng)官的期間，傅里葉構(gòu)思了關(guān)于三角級(jí)數(shù)的想法。

　　熱的傳播和擴(kuò)散現(xiàn)象是導(dǎo)致傅里葉研究成果的實(shí)際物理背景。在當(dāng)時(shí)數(shù)學(xué)物理學(xué)領(lǐng)城中大多數(shù)前人的研究巳經(jīng)涉及到理論力學(xué)和天體力學(xué)的背景下，這一問(wèn)題本身就是十分有意義的一步。到了1807年，傅里葉已經(jīng)完成了一項(xiàng)研究，他發(fā)現(xiàn)在表示一個(gè)物體的溫度分布時(shí)，成諧波關(guān)系的正弦函數(shù)級(jí)數(shù)是非常有用的。

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

　　另外，傅里葉在這一問(wèn)題上的研究成果比他的任何先驅(qū)者都大大前進(jìn)了一步，這指的是他還得出了關(guān)于非周期信號(hào)的表示——不是成諧被關(guān)系的正弦信號(hào)的加權(quán)和，而是不全成諧波關(guān)系的正弦信號(hào)的加權(quán)積分。這就是第4和第5章所關(guān)注的從傅里葉級(jí)數(shù)到傅里葉積分（或變換）的推廣。和傅里葉級(jí)數(shù)一樣，傅里葉變換仍然是分析LTI系統(tǒng)最強(qiáng)有力的工具之一。

　　當(dāng)時(shí)指定了4位著名的數(shù)學(xué)家和科學(xué)家來(lái)評(píng)審1807年傅里葉的論文，其中3位即S.F.拉克勞克斯（S.F.Lacroix）、G.孟濟(jì)（G.Monge）和P.S.拉普拉斯（P.S.Laplace）贊成發(fā)表傅里葉的論文，而第四位J.L.拉格朗日仍然頑固地堅(jiān)持他于50年前就已經(jīng)提出過(guò)的關(guān)于拒絕接受三角級(jí)數(shù)的論點(diǎn)。

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

　　直到傅里葉的晚年，他才得到了某種應(yīng)有的承認(rèn)！但是，對(duì)他來(lái)說(shuō)最有意義的稱贊是他的研究成果已經(jīng)在數(shù)學(xué)、科學(xué)和工程等如此眾多的領(lǐng)域內(nèi)產(chǎn)生的巨大影響。傅里葉級(jí)數(shù)和積分的分析在很多數(shù)學(xué)問(wèn)題中都留下了它的足跡，積分理論、點(diǎn)集拓?fù)浜吞卣骱瘮?shù)展開等僅是這方面的幾個(gè)例子。再者，除了最初在振動(dòng)問(wèn)題和傳熱問(wèn)題的研究外，在科學(xué)和工程領(lǐng)域中有大量的其它問(wèn)題，正弦信號(hào)（從而傅里葉級(jí)數(shù)和變換）在其中起著很重要的作用。

　　例如，在描述行星運(yùn)動(dòng)和反映地球氣候的周期性變化中，很自然地會(huì)出現(xiàn)正弦信號(hào)；交流電源產(chǎn)生的正弦電壓和電流；以及我們將要看到的，傅里葉分析方法能夠用來(lái)分析LTI系統(tǒng)的響應(yīng)，比如一個(gè)電路對(duì)正弦輸入的響應(yīng)等。同時(shí)，海浪也是由不同波長(zhǎng)的正弦波的線性組合所組成的；無(wú)線電臺(tái)和電視臺(tái)發(fā)射的信號(hào)都是正弦的；以及依據(jù)傅里葉分析可以給出任何文本的快邊閱讀等等?？傊倚盘?hào)和傅里葉分析方法的應(yīng)用范圍遠(yuǎn)遠(yuǎn)超出以上所列舉的這幾個(gè)例子。

　　在前面一段中的許多應(yīng)用，以及傅里葉和他的問(wèn)伴們?cè)跀?shù)學(xué)物理學(xué)方面的最初研究都是集中在連續(xù)時(shí)間內(nèi)的現(xiàn)象。與此同時(shí)，對(duì)于離散時(shí)間信號(hào)與系統(tǒng)的傅里葉分析方法卻有著它們自己不同的歷史根基，并且也有眾多的應(yīng)用領(lǐng)域。尤其是，離散時(shí)間概念和方法是數(shù)值分析這門學(xué)科的基礎(chǔ)。

　　用于處理離散點(diǎn)集以產(chǎn)生數(shù)值近似的有關(guān)內(nèi)插、積分和微分等方面的公式遠(yuǎn)在17世紀(jì)的牛頓時(shí)代就被研究過(guò)。另外，在已知一組天體觀察數(shù)據(jù)序列下，預(yù)測(cè)某一天體運(yùn)動(dòng)的問(wèn)題在18和19世紀(jì)曾吸引著包括高斯（Gauss）在內(nèi)的許多著名科學(xué)家和數(shù)學(xué)家從事調(diào)和時(shí)間序列的研究，從而為大量的初始工作能在離散時(shí)間信號(hào)與系統(tǒng)下完成提供了第二個(gè)舞臺(tái)。

　　在20世紀(jì)60年代中期，一種稱之為快速傅里葉變換（FFT）的算法被引入。這一算法在1965年被庫(kù)利（Cooley）和圖基（Tukey）獨(dú)立地發(fā)現(xiàn)，其實(shí)它也有相當(dāng)長(zhǎng)的歷史。事實(shí)上，這一算法在高斯的手稿中已能找到。

　　之所以使得它成為重要的近代發(fā)現(xiàn)是由于FFT證明是非常適合于高效的數(shù)字實(shí)現(xiàn)，并且它將計(jì)算變換所需要的時(shí)間減少了幾個(gè)數(shù)量級(jí)。有了這一算法，在利用離散時(shí)間傅里葉級(jí)數(shù)和變換中許多有興趣而過(guò)去認(rèn)為不切實(shí)際的想法突然變得實(shí)際起來(lái)，井且使離散時(shí)間信號(hào)與系統(tǒng)分析技術(shù)的發(fā)展加速向前邁進(jìn)。

　　由這樣一個(gè)很長(zhǎng)歷史的發(fā)展所涌現(xiàn)出的，對(duì)于連續(xù)時(shí)間和離散時(shí)間信號(hào)與系統(tǒng)分析來(lái)說(shuō)是一個(gè)強(qiáng)有力而嚴(yán)謹(jǐn)?shù)姆治鲶w系，以及有著極為廣泛的現(xiàn)存和潛在的應(yīng)用范倒。這一章和后續(xù)幾章將建立這個(gè)體系中的一些基本方法，井研究其中某些重要的內(nèi)涵。

　　傅里葉變換有什么用

　　盡管最初傅里葉分析是作為熱過(guò)程的解析分析的工具，但是其思想方法仍然具有典型的還原論和分析主義的特征?！叭我狻钡暮瘮?shù)通過(guò)一定的分解，都能夠表示為正弦函數(shù)的線性組合的形式，而正弦函數(shù)在物理上是被充分研究而相對(duì)簡(jiǎn)單的函數(shù)類，這一想法跟化學(xué)上的原子論想法何其相似！奇妙的是，現(xiàn)代數(shù)學(xué)發(fā)現(xiàn)傅里葉變換具有非常好的性質(zhì)，使得它如此的好用和有用，讓人不得不感嘆造物的神奇：

　　傅里葉變換是線性算子，若賦予適當(dāng)?shù)姆稊?shù)，它還是酉算子；

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

　　正弦基函數(shù)是微分運(yùn)算的本征函數(shù)，從而使得線性微分方程的求解可以轉(zhuǎn)化為常系數(shù)的代數(shù)方程的求解。在線性時(shí)不變的物理系統(tǒng)內(nèi)，頻率是個(gè)不變的性質(zhì)，從而系統(tǒng)對(duì)于復(fù)雜激勵(lì)的響應(yīng)可以通過(guò)組合其對(duì)不同頻率正弦信號(hào)的響應(yīng)來(lái)獲取；

　　著名的卷積定理指出：傅里葉變換可以化復(fù)雜的卷積運(yùn)算為簡(jiǎn)單的乘積運(yùn)算，從而提供了計(jì)算卷積的一種簡(jiǎn)單手段；

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

　　正是由于上述的良好性質(zhì)，傅里葉變換在物理學(xué)、數(shù)論、組合數(shù)學(xué)、信號(hào)處理、概率、統(tǒng)計(jì)、密碼學(xué)、聲學(xué)、光學(xué)等領(lǐng)域都有著廣泛的應(yīng)用。

　　有關(guān)傅里葉變換的FPGA實(shí)現(xiàn)

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