傅里葉變換能將滿足一定條件的某個(gè)函數(shù)表示成三角函數(shù)（正弦和/或余弦函數(shù)）或者它們的積分的線性組合.在不同的研究領(lǐng)域,傅里葉變換具有多種不同的變體形式,如連續(xù)傅里葉變換和離散傅里葉變換.最初傅里葉分析是作為熱過(guò)程的解析分析的工具被提出的.
目錄
定義中文譯名
應(yīng)用
概要介紹
基本性質(zhì)線性性質(zhì)
頻移性質(zhì)
微分關(guān)系
卷積特性
Parseval定理
傅里葉變換的不同變種連續(xù)傅里葉變換
傅里葉級(jí)數(shù)
離散傅里葉變換
時(shí)頻分析變換
數(shù)學(xué)領(lǐng)域整體結(jié)構(gòu)
蝶形運(yùn)算器的實(shí)現(xiàn)
FFT的地址
旋轉(zhuǎn)因子
存儲(chǔ)器的控制
硬件的選擇
相關(guān)書(shū)籍推薦定義 中文譯名
應(yīng)用
概要介紹
基本性質(zhì) 線性性質(zhì)
頻移性質(zhì)
微分關(guān)系
卷積特性
Parseval定理
傅里葉變換的不同變種 連續(xù)傅里葉變換
傅里葉級(jí)數(shù)
離散傅里葉變換
時(shí)頻分析變換
數(shù)學(xué)領(lǐng)域 整體結(jié)構(gòu)
蝶形運(yùn)算器的實(shí)現(xiàn)
FFT的地址
旋轉(zhuǎn)因子
存儲(chǔ)器的控制
硬件的選擇
相關(guān)書(shū)籍推薦
展開(kāi) 編輯本段定義
f(t)滿足傅立葉積分定理?xiàng)l件時(shí),下圖①式的積分運(yùn)算稱為f(t)的傅立葉變換, ②式的積分運(yùn)算叫做F(ω)的傅立葉逆變換.F(ω)叫做f(t)的象函數(shù),f(t)叫做 F(ω)的象原函數(shù). 傅里葉變換
① 傅里葉逆變換
②
中文譯名
Fourier transform 或Transformée de Fourier有多個(gè)中文譯名,常見(jiàn)的有“傅里葉變換”、“傅立葉變換”、“付立葉變換”、“傅里葉轉(zhuǎn)換”、“傅氏轉(zhuǎn)換”、“傅氏變換”、等等.為方便起見(jiàn),本文統(tǒng)一寫(xiě)作“傅里葉變換”.
編輯本段應(yīng)用
傅里葉變換在物理學(xué)、電子類學(xué)科、數(shù)論、組合數(shù)學(xué)、信號(hào)處理、概率論、統(tǒng)計(jì)學(xué)、密碼學(xué)、聲學(xué)、光學(xué)、海洋學(xué)、結(jié)構(gòu)動(dòng)力學(xué)等領(lǐng)域都有著廣泛的應(yīng)用（例如在信號(hào)處理中,傅里葉變換的典型用途是將信號(hào)分解成幅值分量和頻率分量）.
編輯本段概要介紹
概要參見(jiàn)：林家翹、西格爾著《自然科學(xué)中確定性問(wèn)題的應(yīng)用數(shù)學(xué)》,科學(xué)出版社,北京.原版書(shū)名為 C. C. Lin & L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences, Macmillan Inc., New York, 1974. * 傅里葉變換屬于諧波分析. * 傅里葉變換的逆變換容易求出,而且形式與正變換非常類似; * 正弦基函數(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ì)
線性性質(zhì)
兩函數(shù)之和的傅里葉變換等于各自變換之和.數(shù)學(xué)描述是：若函數(shù)f \left( x\right )和g \left(x \right)的傅里葉變換\mathcal[f]和\mathcal[g]都存在,α 和 β 為任意常系數(shù),則\mathcal[\alpha f+\beta g]=\alpha\mathcal[f]+\beta\mathcal[g]；傅里葉變換算符\mathcal可經(jīng)歸一化成為么正算符；
頻移性質(zhì)
若函數(shù)f \left( x\right )存在傅里葉變換,則對(duì)任意實(shí)數(shù) ω0,函數(shù)f(x) e^{i \omega_ x}也存在傅里葉變換,且有\(zhòng)mathcal[f(x)e^{i \omega_ x}]=F(\omega + \omega _0 ) .式中花體\mathcal是傅里葉變換的作用算子,平體F表示變換的結(jié)果（復(fù)函數(shù)）,e 為自然對(duì)數(shù)的底,i 為虛數(shù)單位\sqrt；
微分關(guān)系
若函數(shù)f \left( x\right )當(dāng)|x|\rightarrow\infty時(shí)的極限為0,而其導(dǎo)函數(shù)f'(x)的傅里葉變換存在,則有\(zhòng)mathcal[f'(x)]=-i \omega \mathcal[f(x)] ,即導(dǎo)函數(shù)的傅里葉變換等于原函數(shù)的傅里葉變換乘以因子 − 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 階導(dǎo)數(shù)的傅里葉變換等于原函數(shù)的傅里葉變換乘以因子( − iω)k.
卷積特性
若函數(shù)f \left( x\right )及g \left( x\right )都在(-\infty,+\infty)上絕對(duì)可積,則卷積函數(shù)f*g=\int_{-\infty}^{+\infty} f(x-\xi)g(\xi)d\xi的傅里葉變換存在,且\mathcal[f*g]=\mathcal[f]\cdot\mathcal[g] .卷積性質(zhì)的逆形式為\mathcal^[F(\omega)G(\omega)]=\mathcal^[F(\omega)]*\mathcal^[G(\omega)] ,即兩個(gè)函數(shù)乘積的傅里葉逆變換等于它們各自的傅里葉逆變換的卷積,同時(shí)還有兩個(gè)函數(shù)卷積的傅里葉逆變換等于它們各自的傅里葉逆變換的乘積.
Parseval定理
若函數(shù)f \left( x\right )可積且平方可積,則\int_{-\infty}^{+\infty} f^2 (x)dx = \frac{2\pi}\int_{-\infty}^{+\infty} |F(\omega)|^d\omega .其中 F(ω) 是 f(x) 的傅里葉變換.
編輯本段傅里葉變換的不同變種
連續(xù)傅里葉變換
主條目：連續(xù)傅立葉變換 一般情況下,若“傅立葉變換”一詞的前面未加任何限定語(yǔ),則指的是“連續(xù)傅里葉變換”.“連續(xù)傅里葉變換”將平方可積的函數(shù)f(t) 表示成復(fù)指數(shù)函數(shù)的積分或級(jí)數(shù)形式. f(t) = \mathcal^[F(\omega)] = \frac{\sqrt{2\pi}} \int\limits_{-\infty}^\infty F(\omega) e^{i\omega t}\,d\omega. 上式其實(shí)表示的是連續(xù)傅里葉變換的逆變換,即將時(shí)間域的函數(shù)f(t)表示為頻率域的函數(shù)F(ω)的積分.反過(guò)來(lái),其正變換恰好是將頻率域的函數(shù)F(ω)表示為時(shí)間域的函數(shù)f(t)的積分形式.一般可稱函數(shù)f(t)為原函數(shù),而稱函數(shù)F(ω)為傅里葉變換的像函數(shù),原函數(shù)和像函數(shù)構(gòu)成一個(gè)傅立葉變換對(duì)(transform pair). 一種對(duì)連續(xù)傅里葉變換的推廣稱為分?jǐn)?shù)傅里葉變換（Fractional Fourier Transform）. 當(dāng)f(t)為奇函數(shù)(或偶函數(shù))時(shí),其余弦(或正弦)分量將消亡,而可以稱這時(shí)的變換為余弦轉(zhuǎn)換(cosine transform) 或 正弦轉(zhuǎn)換(sine transform). 另一個(gè)值得注意的性質(zhì)是,當(dāng)f(t) 為純實(shí)函數(shù)時(shí),F(−ω) = F(ω)*成立.
傅里葉級(jí)數(shù)
主條目：傅里葉級(jí)數(shù) 連續(xù)形式的傅里葉變換其實(shí)是傅里葉級(jí)數(shù)的推廣,因?yàn)榉e分其實(shí)是一種極限形式的求和算子而已.對(duì)于周期函數(shù),其傅里葉級(jí)數(shù)是存在的： f(x) = \sum_{n=-\infty}^{\infty} F_n \,e^ , 其中Fn 為復(fù)振幅.對(duì)于實(shí)值函數(shù),函數(shù)的傅里葉級(jí)數(shù)可以寫(xiě)成： f(x) = \fraca_0 + \sum_{n=1}^\infty\left[a_n\cos(nx)+b_n\sin(nx)\right], 其中an和bn是實(shí)頻率分量的振幅. 離散時(shí)間傅里葉變換 主條目：離散時(shí)間傅里葉變換 離散傅里葉變換是離散時(shí)間傅里葉變換（DTFT）的特例（有時(shí)作為后者的近似）.DTFT在時(shí)域上離散,在頻域上則是周期的.DTFT可以被看作是傅里葉級(jí)數(shù)的逆.
離散傅里葉變換
主條目：離散傅里葉變換 為了在科學(xué)計(jì)算和數(shù)字信號(hào)處理等領(lǐng)域使用計(jì)算機(jī)進(jìn)行傅里葉變換,必須將函數(shù)xn 定義在離散點(diǎn)而非連續(xù)域內(nèi),且須滿足有限性或周期性條件.這種情況下, 使用離散傅里葉變換,將函數(shù) xn 表示為下面的求和形式： x_n = \frac1 \sum_{k=0}^ X_k e^{i\frac{2\pi} kn} \qquad n = 0,\dots,N-1 其中Xk是傅里葉振幅.直接使用這個(gè)公式計(jì)算的計(jì)算復(fù)雜度為\mathcal(n^2),而快速傅里葉變換（FFT）可以將復(fù)雜度改進(jìn)為\mathcal(n \log n).計(jì)算復(fù)雜度的降低以及數(shù)字電路計(jì)算能力的發(fā)展使得DFT成為在信號(hào)處理領(lǐng)域十分實(shí)用且重要的方法. 在阿貝爾群上的統(tǒng)一描述 以上各種傅里葉變換可以被更統(tǒng)一的表述成任意局部緊致的阿貝爾群上的傅里葉變換.這一問(wèn)題屬于調(diào)和分析的范疇.在調(diào)和分析中, 一個(gè)變換從一個(gè)群變換到它的對(duì)偶群(dual group).此外,將傅里葉變換與卷積相聯(lián)系的卷積定理在調(diào)和分析中也有類似的結(jié)論.傅里葉變換的廣義理論基礎(chǔ)參見(jiàn)龐特里雅金對(duì)偶性（英文版）中的介紹.
時(shí)頻分析變換
主條目：時(shí)頻分析變換 小波變換,chirplet轉(zhuǎn)換和分?jǐn)?shù)傅里葉轉(zhuǎn)換試圖得到時(shí)間信號(hào)的頻率信息.同時(shí)解析頻率和時(shí)間的能力在數(shù)學(xué)上受不確定性原理的限制. 傅里葉變換家族 下表列出了傅里葉變換家族的成員. 容易發(fā)現(xiàn),函數(shù)在時(shí)(頻)域的離散對(duì)應(yīng)于其像函數(shù)在頻(時(shí))域的周期性.反之連續(xù)則意味著在對(duì)應(yīng)域的信號(hào)的非周期性. 變換 時(shí)間 頻率 連續(xù)傅里葉變換 連續(xù), 非周期性 連續(xù), 非周期性 傅里葉級(jí)數(shù) 連續(xù), 周期性 離散, 非周期性 離散時(shí)間傅里葉變換 離散, 非周期性 連續(xù), 周期性 離散傅里葉變換 離散, 周期性 離散, 周期性 傅里葉變換的基本思想首先由法國(guó)學(xué)者傅里葉系統(tǒng)提出,所以以其名字來(lái)命名以示紀(jì)念. 從現(xiàn)代數(shù)學(xué)的眼光來(lái)看,傅里葉變換是一種特殊的積分變換.它能將滿足一定條件的某個(gè)函數(shù)表示成正弦基函數(shù)的線性組合或者積分.在不同的研究領(lǐng)域,傅里葉變換具有多種不同的變體形式,如連續(xù)傅里葉變換和離散傅里葉變換. 傅立葉變換屬于調(diào)和分析的內(nèi)容."分析"二字,可以解釋為深入的研究.從字面上來(lái)看,"分析"二字,實(shí)際就是"條分縷析"而已.它通過(guò)對(duì)函數(shù)的"條分縷析"來(lái)達(dá)到對(duì)復(fù)雜函數(shù)的深入理解和研究.從哲學(xué)上看,"分析主義"和"還原主義",就是要通過(guò)對(duì)事物內(nèi)部適當(dāng)?shù)姆治鲞_(dá)到增進(jìn)對(duì)其本質(zhì)理解的目的.比如近代原子論試圖把世界上所有物質(zhì)的本源分析為原子,而原子不過(guò)數(shù)百種而已,相對(duì)物質(zhì)世界的無(wú)限豐富,這種分析和分類無(wú)疑為認(rèn)識(shí)事物的各種性質(zhì)提供了很好的手段.
編輯本段數(shù)學(xué)領(lǐng)域
盡管最初傅立葉分析是作為熱過(guò)程的解析分析的工具,但是其思想方法仍然具有典型的還原論和分析主義的特征."任意"的函數(shù)通過(guò)一定的分解,都能夠表示為正弦函數(shù)的線性組合的形式,而正弦函數(shù)在物理上是被充分研究而相對(duì)簡(jiǎn)單的函數(shù)類,這一想法跟化學(xué)上的原子論想法何其相似!奇妙的是,現(xiàn)代數(shù)學(xué)發(fā)現(xiàn)傅立葉變換具有非常好的性質(zhì),使得它如此的好用和有用,讓人不得不感嘆造物的神奇: 1. 傅立葉變換是線性算子,若賦予適當(dāng)?shù)姆稊?shù),它還是酉算子; 2. 傅立葉變換的逆變換容易求出,而且形式與正變換非常類似; 3. 正弦基函數(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)獲取; 4. 著名的卷積定理指出:傅立葉變換可以化復(fù)雜的卷積運(yùn)算為簡(jiǎn)單的乘積運(yùn)算,從而提供了計(jì)算卷積的一種簡(jiǎn)單手段; 5. 離散形式的傅立葉變換可以利用數(shù)字計(jì)算機(jī)快速的算出(其算法稱為快速傅立葉變換算法(FFT)). 正是由于上述的良好性質(zhì),傅里葉變換在物理學(xué)、數(shù)論、組合數(shù)學(xué)、信號(hào)處理、概率、統(tǒng)計(jì)、密碼學(xué)、聲學(xué)、光學(xué)等領(lǐng)域都有著廣泛的應(yīng)用. 有関傅立葉變換的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ì)方法.
整體結(jié)構(gòu)
一般情況下,N點(diǎn)的傅立葉變換對(duì)為： 其中,WN＝exp(－2pi／N).X(k)和x(n)都為復(fù)數(shù).與之相對(duì)的快速傅立葉變換有很多種,如DIT(時(shí)域抽取法)、DIF（頻域抽取法）、Cooley－Tukey和Winograd等.對(duì)于2n傅立葉變換,Cooley－Tukey算法可導(dǎo)出DIT和DIF算法.本文運(yùn)用的基本思想是Cooley－Tukey算法,即將高點(diǎn)數(shù)的傅立葉變換通過(guò)多重低點(diǎn)數(shù)傅立葉變換來(lái)實(shí)現(xiàn).雖然DIT與DIF有差別,但由于它們?cè)诒举|(zhì)上都是一種基于標(biāo)號(hào)分解的算法,故在運(yùn)算量和算法復(fù)雜性等方面完全一樣,而沒(méi)有性能上的優(yōu)劣之分,所以可以根據(jù)需要任取其中一種,本文主要以DIT方法為對(duì)象來(lái)討論. N＝8192點(diǎn)DFT的運(yùn)算表達(dá)式為： 式中,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的傅立葉變換構(gòu)成.同理,4k傅立葉變換可由2×2k的傅立葉變換構(gòu)成.而2k傅立葉變換可由128×16的傅立葉變換構(gòu)成.128的傅立葉變換可進(jìn)一步由16×8的傅立葉變換構(gòu)成,歸根結(jié)底,整個(gè)傅立葉變換可由基2、基4的傅立葉變換構(gòu)成.2k的FFT可以通過(guò)5個(gè)基4和1個(gè)基2變換來(lái)實(shí)現(xiàn)；4k的FFT變換可通過(guò)6個(gè)基4變換來(lái)實(shí)現(xiàn)；8k的FFT可以通過(guò)6個(gè)基4和1個(gè)基2變換來(lái)實(shí)現(xiàn).也就是說(shuō)：FFT的基本結(jié)構(gòu)可由基2／4模塊、復(fù)數(shù)乘法器、存儲(chǔ)單元和存儲(chǔ)器控制模塊構(gòu)成,其整體結(jié)構(gòu)如圖1所示. 圖1中,RAM用來(lái)存儲(chǔ)輸入數(shù)據(jù)、運(yùn)算過(guò)程中的中間結(jié)果以及運(yùn)算完成后的數(shù)據(jù),ROM用來(lái)存儲(chǔ)旋轉(zhuǎn)因子表.蝶形運(yùn)算單元即為基2／4模塊,控制模塊可用于產(chǎn)生控制時(shí)序及地址信號(hào),以控制中間運(yùn)算過(guò)程及最后輸出結(jié)果.
蝶形運(yùn)算器的實(shí)現(xiàn)
基4和基2的信號(hào)流如圖2所示.圖中,若A＝r0＋j＊i0,B＝r1＋j＊i1,C＝r2＋j＊i2,D＝r3＋j＊i3是要進(jìn)行變換的信號(hào),Wk0＝c0＋j＊s0＝1,Wk1＝c1＋j＊s1,Wk2＝c2＋j＊s2,Wk3＝c3＋j＊s3為旋轉(zhuǎn)因子,將其分別代入圖2中的基4蝶形運(yùn)算單元,則有： 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的表達(dá)式代入圖2中的基2運(yùn)算的四個(gè)等式中,則有： 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）中有很多類同項(xiàng),如i1×c1＋r1×s1和r1×c1－i1×s1等,它們僅僅是加減號(hào)的不同,其結(jié)構(gòu)和運(yùn)算均類似,這就為簡(jiǎn)化電路提供了可能.同時(shí),在蝶形運(yùn)算中,復(fù)數(shù)乘法可以由實(shí)數(shù)乘法以一定的格式來(lái)表示,這也為設(shè)計(jì)復(fù)數(shù)乘法器提供了一種實(shí)現(xiàn)的途徑. 以基4為例,在其運(yùn)算單元中,實(shí)際上只需做三個(gè)復(fù)數(shù)乘法運(yùn)算,即只須計(jì)算BWk1、CWk2和DWk3的值即可,這樣在一個(gè)基4蝶形單元里面,最多只需要3個(gè)復(fù)數(shù)乘法器就可以了.在實(shí)際過(guò)程中,在不提高時(shí)鐘頻率下,只要將時(shí)序控制好?便可利用流水線（Pipeline）技術(shù)并只用一個(gè)復(fù)數(shù)乘法器就可完成這三個(gè)復(fù)數(shù)乘法,大大節(jié)省了硬件資源. 圖2 基2和基4蝶形算法的信號(hào)流圖
FFT的地址
FFT變換后輸出的結(jié)果通常為一特定的倒序,因此,幾級(jí)變換后對(duì)地址的控制必須準(zhǔn)確無(wú)誤. 倒序的規(guī)律是和分解的方式密切相關(guān)的,以基8為例,其基本倒序規(guī)則如下： 基8可以用2×2×2三級(jí)基2變換來(lái)表示,則其輸入順序則可用二進(jìn)制序列（n1 n2 n3）來(lái)表示,變換結(jié)束后,其順序?qū)⒆優(yōu)椋╪3 n2 n1）,如：X?011 → x?110 ,即輸入順序?yàn)?,輸出時(shí)順序變?yōu)?. 更進(jìn)一步,對(duì)于基16的變換,可由2×2×2×2,4×4,4×2×2等形式來(lái)構(gòu)成,相對(duì)于不同的分解形式,往往會(huì)有不同的倒序方式.以4×4為例,其輸入順序可以用二進(jìn)制序列（n1 n2 n3n4）來(lái)表示變換結(jié)束后,其順序可變?yōu)椋ǎ╪3 n4）（n1 n2））,如： X?0111 → x?1101 .即輸入順序?yàn)?,輸出時(shí)順序變?yōu)?3. 在2k／4k／8k的傅立葉變換中,由于要經(jīng)過(guò)多次的基4和基2運(yùn)算,因此,從每次運(yùn)算完成后到進(jìn)入下一次運(yùn)算前,應(yīng)對(duì)運(yùn)算的結(jié)果進(jìn)行倒序,以保證運(yùn)算的正確性.
旋轉(zhuǎn)因子
N點(diǎn)傅立葉變換的旋轉(zhuǎn)因子有著明顯的周期性和對(duì)稱性.其周期性表現(xiàn)為： FFT之所以可使運(yùn)算效率得到提高,就是利用 FFT之所以可使運(yùn)算效率得到提高,就是利用了對(duì)稱性和周期性把長(zhǎng)序列的DFT逐級(jí)分解成幾個(gè)序列的DFT,并最終以短點(diǎn)數(shù)變換來(lái)實(shí)現(xiàn)長(zhǎng)點(diǎn)數(shù)變換. 根據(jù)旋轉(zhuǎn)因子的對(duì)稱性和周期性,在利用ROM存儲(chǔ)旋轉(zhuǎn)因子時(shí),可以只存儲(chǔ)旋轉(zhuǎn)因子表的一部分,而在讀出時(shí)增加讀出地址及符號(hào)的控制,這樣可以正確實(shí)現(xiàn)FFT.因此,充分利用旋轉(zhuǎn)因子的性質(zhì),可節(jié)省70％以上存儲(chǔ)單元. 實(shí)際上,由于旋轉(zhuǎn)因子可分解為正、余弦函數(shù)的組合,故ROM中存的值為正、余弦函數(shù)值的組合.對(duì)2k／4k／8k的傅立葉變換來(lái)說(shuō),只是對(duì)一個(gè)周期進(jìn)行不同的分割.由于8k變換的旋轉(zhuǎn)因子包括了2k／4k的所有因子,因此,實(shí)現(xiàn)時(shí)只要對(duì)讀ROM的地址進(jìn)行控制,即可實(shí)現(xiàn)2k／4k／8k變換的通用.存儲(chǔ)器的控制
因FFT是為時(shí)序電路而設(shè)計(jì)的,因此,控制信號(hào)要包括時(shí)序的控制信號(hào)及存儲(chǔ)器的讀寫(xiě)地址,并產(chǎn)生各種輔助的指示信號(hào).同時(shí)在計(jì)算模塊的內(nèi)部,為保證高速,所有的乘法器都須始終保持較高的利用率.這意味著在每一個(gè)時(shí)鐘來(lái)臨時(shí)都要向這些單元輸入新的操作數(shù),而這一切都需要控制信號(hào)的緊密配合. 為了實(shí)現(xiàn)FFT的流形運(yùn)算,在運(yùn)算的同時(shí),存儲(chǔ)器也要接收數(shù)據(jù).這可以采用乒乓RAM的方法來(lái)完成.這種方式?jīng)Q定了實(shí)現(xiàn)FFT運(yùn)算的最大時(shí)間.對(duì)于4k操作,其接收時(shí)間為4096個(gè)數(shù)據(jù)周期,這樣?FFT的最大運(yùn)算時(shí)間就是4096個(gè)數(shù)據(jù)周期.另外,由于輸入數(shù)據(jù)是以一定的時(shí)鐘為周期依次輸入的,故在進(jìn)行內(nèi)部運(yùn)算時(shí),可以用較高的內(nèi)部時(shí)鐘進(jìn)行運(yùn)算,然后再存入RAM依次輸出. 為節(jié)省資源,可對(duì)存儲(chǔ)數(shù)據(jù)RAM采用原址讀出原址寫(xiě)入的方法,即在進(jìn)行下一級(jí)變換的同時(shí),首先應(yīng)將結(jié)果回寫(xiě)到讀出數(shù)據(jù)的RAM存貯器中；而對(duì)于ROM,則應(yīng)采用與運(yùn)算的數(shù)據(jù)相對(duì)應(yīng)的方法來(lái)讀出存儲(chǔ)器中旋轉(zhuǎn)因子的值. 在2k／4k／8k傅立葉變換中,要實(shí)現(xiàn)通用性,控制器是最主要的模塊.2k、4k、8k變換具有不同的內(nèi)部運(yùn)算時(shí)間和存儲(chǔ)器地址,在設(shè)計(jì)中,針對(duì)不同的點(diǎn)數(shù)應(yīng)設(shè)計(jì)不同的存儲(chǔ)器存取地址,同時(shí),在完成變換后,還要對(duì)開(kāi)始輸出有用信號(hào)的時(shí)刻進(jìn)行指示.
硬件的選擇
本設(shè)計(jì)的硬件實(shí)現(xiàn)選用的是現(xiàn)場(chǎng)可編程門(mén)陣列(FPGA)來(lái)滿足較高速度的需要.本系統(tǒng)在設(shè)計(jì)時(shí)選用的是ALTERA公司的STRATIX芯片,該芯片中包含有DSP單元,可以完成較為耗費(fèi)資源的乘法器單元.同時(shí),該器件也包含有大量存儲(chǔ)單元,從而可保證旋轉(zhuǎn)因子的精度. 除了一些專用引腳外,FPGA上幾乎所有的引腳均可供用戶使用,這使得FPGA信號(hào)處理方案具有非常好的I／O帶寬.大量的I／O引腳和多塊存儲(chǔ)器可使設(shè)計(jì)獲得優(yōu)越的并行處理性能.其獨(dú)立的存儲(chǔ)塊可作為輸入／工作存儲(chǔ)區(qū)和結(jié)果的緩存區(qū),這使得I／O可與FFT計(jì)算同時(shí)進(jìn)行.在實(shí)現(xiàn)的時(shí)間方面,該設(shè)計(jì)能在4096個(gè)時(shí)鐘周期內(nèi)完成一個(gè)4096點(diǎn)的FFT.若采用10MHz的輸入時(shí)鐘,其變換時(shí)間在200μs左右.而由于最新的FPGA使用了MultiTrack互連技術(shù),故可在250MHz以下頻率穩(wěn)定地工作,同時(shí),FFT的實(shí)現(xiàn)時(shí)間也可以大大縮小. FFT運(yùn)算結(jié)果的精度與輸入數(shù)據(jù)的位數(shù)及運(yùn)算過(guò)程中的位數(shù)有關(guān),同時(shí)和數(shù)據(jù)的表示形式也有很大關(guān)系.一般來(lái)說(shuō),浮點(diǎn)方式比定點(diǎn)方式精度高.而在定點(diǎn)計(jì)算中,存儲(chǔ)器數(shù)據(jù)的位數(shù)越大,運(yùn)算精度越高,使用的存儲(chǔ)單元和邏輯單元也越多.在實(shí)際應(yīng)用中,應(yīng)根據(jù)實(shí)際情況折衷選擇精度和資源.本設(shè)計(jì)通過(guò)MATLAB進(jìn)行仿真證明：其實(shí)現(xiàn)的變換結(jié)果與MATLAB工具箱中的FFT函數(shù)相比,信噪比可以達(dá)到65db以上,完全可以滿足一般工程的實(shí)際應(yīng)用要求.