當(dāng)前位置:首頁 > 嵌入式 > 嵌入式教程
[導(dǎo)讀]基于高速定點(diǎn)FFT算法的FPGA設(shè)計(jì)方案

引 言
    快速傅里葉變換(FFT)作為計(jì)算和分析工具,在眾多學(xué)科領(lǐng)域(如信號(hào)處理、圖像處理、生物信息學(xué)、計(jì)算物理、應(yīng)用數(shù)學(xué)等)有著廣泛的應(yīng)用。在高速數(shù)字信號(hào)處理領(lǐng)域,如雷達(dá)信號(hào)處理,F(xiàn)FT的處理速度往往是整個(gè)系統(tǒng)設(shè)計(jì)性能的關(guān)鍵所在。
    針對(duì)高速實(shí)時(shí)信號(hào)處理的要求,軟件實(shí)現(xiàn)方法顯然滿足不了其需要。近年來現(xiàn)場(chǎng)可編程門陣列(FPGA)以其高性能、高靈活性、友好的開發(fā)環(huán)境、在線可編程等特點(diǎn),使得基于FPGA的設(shè)計(jì)可以滿足實(shí)時(shí)數(shù)字信號(hào)處理的要求,在市場(chǎng)競(jìng)爭(zhēng)中具有很大的優(yōu)勢(shì)。
    在FFT算法中,數(shù)據(jù)的寬度通常都是固定的寬度。然而,在FFT的運(yùn)算過程中,特別是乘法運(yùn)算中,運(yùn)算的結(jié)果將不可避免地帶來誤差。因此,為了保證結(jié)果的準(zhǔn)確性,采用定點(diǎn)分析是非常必要的。

1 FFT算法原理
    FFT算法的基本思想就是利用權(quán)函數(shù)的周期性、對(duì)稱性、特殊性及周期N的可互換性,將較長序列的DFT運(yùn)算逐次分解為較短序列的DFT運(yùn)算。針對(duì)N=2的整數(shù)次冪,F(xiàn)FT算法有基-2算法、基-4算法、實(shí)因子算法和分裂基算法等。這里,從處理速度和占用資源的角度考慮,選用基-4按時(shí)間抽取FFT算法 (DIT)。對(duì)于N=4γ,基-4 DIT具有l(wèi)og4N=γ次迭代運(yùn)算,每次迭代包含N/4個(gè)蝶形單元。蝶形單元的運(yùn)算表達(dá)式為:

  
    其信號(hào)流如圖1。式中:A,B,C,D和A′,B′,C′,D′均為復(fù)數(shù)據(jù);W=e-j2π/N。進(jìn)行1次蝶形運(yùn)算共需3次復(fù)乘和8次復(fù)加運(yùn)算。N=64 點(diǎn)的基-4DIT信號(hào)流其輸入數(shù)據(jù)序列是按自然順序排列的,輸出結(jié)果需經(jīng)過整序。64點(diǎn)數(shù)據(jù)只需進(jìn)行3次迭代運(yùn)算,每次迭代運(yùn)算含有N/4=16個(gè)蝶形單元。

2 FFT算法的硬件實(shí)現(xiàn)
2.1 流水線方式FFT算法的實(shí)現(xiàn)
    為了提高FFT工作頻率和節(jié)省FPGA資源,采用3級(jí)流水線結(jié)構(gòu)實(shí)現(xiàn)64點(diǎn)的FFT運(yùn)算。流水線處理器的結(jié)構(gòu)如圖2所示。

每級(jí)均由延時(shí)單元、轉(zhuǎn)接器(SW)、蝶形運(yùn)算和旋轉(zhuǎn)因子乘法4個(gè)模塊組成,延時(shí)節(jié)拍由方框中的數(shù)字表示。各級(jí)轉(zhuǎn)接器和延時(shí)單元起到對(duì)序列進(jìn)行碼位抽取并將數(shù)據(jù)拉齊的作用。每級(jí)延時(shí)在FPGA內(nèi)部用FIFO實(shí)現(xiàn),不需要對(duì)序列進(jìn)行尋址即可實(shí)現(xiàn)延時(shí)功能。數(shù)據(jù)串行輸入,經(jīng)過3級(jí)流水處理后,串行輸出。[!--empirenews.page--]

轉(zhuǎn)接器有一定的工作規(guī)律。例如,當(dāng)?shù)?級(jí)變換做完進(jìn)入轉(zhuǎn)接器SW1前,先對(duì)后三路數(shù)據(jù)進(jìn)行一定節(jié)拍的延時(shí),延遲節(jié)拍分別為4,8,12。為了說明規(guī)律,把輸入轉(zhuǎn)接器的四路數(shù)據(jù)按照前后次序進(jìn)行分組,每4個(gè)時(shí)鐘節(jié)拍為1組,共16組,如圖3(左)所示。在數(shù)據(jù)流串行經(jīng)過轉(zhuǎn)接器SW1時(shí),第0組中的數(shù)據(jù)保持不變,第1組中的數(shù)據(jù)與第4組中的數(shù)據(jù)交換;5不變,2和8交換,3和12交換,6和9交換;10不變,7和13交換,11和14交換,15不變。交換完畢后,前三路數(shù)據(jù)經(jīng)過延遲節(jié)拍分別為12,8,4的FIFO存儲(chǔ)器輸出,位置關(guān)系如圖3所示。

 

    上述轉(zhuǎn)換規(guī)律對(duì)于SW2也是適用的,只是轉(zhuǎn)接器前后的延時(shí)節(jié)拍和分組的大小有所不同。
2.2 存儲(chǔ)單元
    為了實(shí)現(xiàn)算法的流水線設(shè)計(jì),存儲(chǔ)器RAM設(shè)計(jì)為64×16 b的雙端口RAM,即在時(shí)鐘信號(hào)和寫控制信號(hào)同時(shí)為低電平時(shí),從輸入總線寫入RAM;在時(shí)鐘信號(hào)和讀控制信號(hào)同時(shí)為高電平時(shí),從RAM輸出數(shù)據(jù)。
    ROM為17×16 b的ROM,儲(chǔ)存經(jīng)過量化后的旋轉(zhuǎn)因子,旋轉(zhuǎn)因子為正弦函數(shù)和余弦函數(shù)的組合。根據(jù)旋轉(zhuǎn)因子的對(duì)稱性和周期性,在利用ROM存儲(chǔ)旋轉(zhuǎn)因子時(shí),可以只存儲(chǔ)旋轉(zhuǎn)因子的一部分。
2.3 運(yùn)算結(jié)構(gòu)
    Radix-4蝶形運(yùn)算單元是整個(gè)FFT處理器中的核心部件。在用Radix-4運(yùn)算器計(jì)算時(shí)需要并行輸入數(shù)據(jù),如果能以并發(fā)數(shù)據(jù)輸入的話,則同步性和控制度較好,但實(shí)際上常要進(jìn)行串并之間的轉(zhuǎn)換。存儲(chǔ)RAM按單節(jié)拍輸出16 b位寬數(shù)據(jù),選擇器不停旋轉(zhuǎn)送入到確定的位置,每4點(diǎn)全部到位后R-4使能有效;然后4個(gè)時(shí)鐘節(jié)拍得到有效結(jié)果數(shù)據(jù),再通過選擇器旋轉(zhuǎn)送入到對(duì)應(yīng)存儲(chǔ) RAM中。
    復(fù)數(shù)運(yùn)算中,對(duì)應(yīng)復(fù)數(shù)的實(shí)部和虛部RAM用同一個(gè)地址發(fā)生器。地址發(fā)生器在進(jìn)行RAM地址發(fā)生時(shí)采用兩套地址,第一套是計(jì)數(shù)器按時(shí)鐘節(jié)拍順序產(chǎn)生的,用于輸入數(shù)據(jù)的存儲(chǔ);第二套是由數(shù)據(jù)寬度為16 b的ROM產(chǎn)生的,ROM中存放的數(shù)據(jù)為下級(jí)運(yùn)算所需倒序的序列地址,發(fā)生地址給RAM,然后RAM按倒序地址輸出下級(jí)需要進(jìn)行運(yùn)算的數(shù)據(jù)。
2.4 塊浮點(diǎn)結(jié)構(gòu)
    數(shù)字信號(hào)處理系統(tǒng)可分為定點(diǎn)制、浮點(diǎn)制和塊浮點(diǎn)制,它們?cè)趯?shí)現(xiàn)時(shí)對(duì)系統(tǒng)資源的要求不同,工作速度也不同,有著不同的適用范圍。定點(diǎn)制算法簡單,速度快,但動(dòng)態(tài)范圍有限,需要用合適的溢出控制規(guī)則(如定比例法)適當(dāng)壓縮輸入信號(hào)的動(dòng)態(tài)范圍。浮點(diǎn)表示法動(dòng)態(tài)范圍大,可避免溢出,但系統(tǒng)實(shí)現(xiàn)復(fù)雜,硬件需求量大,速度慢。
    為了提高精度,并減少復(fù)雜度和存儲(chǔ)量,采用塊浮點(diǎn)結(jié)構(gòu)。塊浮點(diǎn)算法是以上兩種表示法的結(jié)合。這種表示方法是,一組數(shù)共用同一個(gè)階碼,這個(gè)階碼是這組數(shù)中最大數(shù)的階碼。塊浮點(diǎn)算法無需進(jìn)行額外的指數(shù)運(yùn)算,僅對(duì)尾數(shù)進(jìn)行運(yùn)算即可,其與定點(diǎn)運(yùn)算一樣方便,但需要在每級(jí)運(yùn)算結(jié)束后進(jìn)行本級(jí)運(yùn)算溢出最大位數(shù)判斷,以對(duì)數(shù)據(jù)塊進(jìn)行塊指數(shù)調(diào)整。在調(diào)整時(shí)僅保留一位符號(hào)位,因而能夠充分利用有限位長。這樣處理比定點(diǎn)方法擴(kuò)大了動(dòng)態(tài)范圍,并且提高了精度,比浮點(diǎn)運(yùn)算在速度上有了提高。塊浮點(diǎn)結(jié)構(gòu)如圖4所示。

3 結(jié) 語
    著重討論基于FPGA的64點(diǎn)高速FFT算法的實(shí)現(xiàn)方法。采用高基數(shù)結(jié)構(gòu)和流水線結(jié)構(gòu),大大提高了FFT處理器的運(yùn)行速度。同時(shí)塊浮點(diǎn)結(jié)構(gòu)的引入,也大幅減少了浮點(diǎn)操作占用FPGA器件的資源數(shù)目,兼顧了FPGA高精度、低資源、低功耗的特點(diǎn)。從實(shí)驗(yàn)結(jié)果看,該方法可以滿足高速實(shí)時(shí)處理數(shù)字信號(hào)的要求。

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡稱"軟通動(dòng)力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉