當(dāng)前位置:首頁(yè) > 物聯(lián)網(wǎng) > 《物聯(lián)網(wǎng)技術(shù)》雜志
[導(dǎo)讀]摘 要:針對(duì)實(shí)時(shí)高速信號(hào)處理要求,設(shè)計(jì)并實(shí)現(xiàn)了一種基于FPGA的高速流水線結(jié)構(gòu)的基4FFT處理器。根據(jù)各種不同基算法的運(yùn)算量、硬件面積和控制復(fù)雜度,選定按時(shí)間抽取的基4算法,同時(shí)采用單路延時(shí)反饋(Single-path Delay Feedback,SDF)流水線結(jié)構(gòu),提高了處理速度。通過(guò)Verilog HDL語(yǔ)言進(jìn)行模塊化描述和驗(yàn)證,結(jié)果表明,該FFT處理器具有較高性能。

引言

快速傅里葉變換 (Fast Fourier Transformation,F(xiàn)FT) 作為時(shí)域和頻域轉(zhuǎn)化的基本運(yùn)算,是數(shù)字譜分析的必要前提。FFT方法是信號(hào)處理領(lǐng)域的核心算法之一,它廣泛應(yīng)用于雷達(dá)信號(hào)處理、觀測(cè)、數(shù)字通信、數(shù)據(jù)變換、定時(shí)定位處理、無(wú)線通訊、圖像處理等領(lǐng)域。為便于硬件實(shí)現(xiàn),F(xiàn)FT 算法常采用分級(jí)運(yùn)算結(jié)構(gòu)。如今的 FFT 大多采用并行結(jié)構(gòu),但其運(yùn)算速度往往受到數(shù)據(jù)帶寬的限制,因而需要增加成倍的存儲(chǔ)單元才能滿足速度要求。本文對(duì) FFT 算法進(jìn)行了分析,基于節(jié)省運(yùn)算量、減少硬件面積和提高處理速率的考慮,給出了一個(gè)基于 FPGA的高速流水線結(jié)構(gòu)的基 4FFT 處理器的設(shè)計(jì)方法。

1 基 4FFT 算法

FFT 算法的基本思想是 :利用 DFT 系數(shù)的特性 ( 即周期性、對(duì)稱性和可約性 ) 來(lái)合并 DFT 運(yùn)算中的某些項(xiàng),把長(zhǎng)序列 DFT 變成短序列 DFT,從而減少其運(yùn)算量,達(dá)到提高速度的目的。一般的 FFT 算法可以分為兩類 :第一類對(duì)時(shí)間,對(duì)時(shí)間序列 x(n) 進(jìn)行逐次分解,稱為時(shí)域抽取 FFT 法(Decima-tion-In-Time-FFT,DIT-FFT);第二類對(duì)頻率,主要對(duì)傅里葉變換序列 X(k) 進(jìn)行分解,稱為頻域抽取 FFT 法 (Decimation-In-Frequency-FFT,DIF-FFT)。本設(shè)計(jì)采用 DIT-FFT 法進(jìn)行設(shè)計(jì)。

1.1 基 4 DIT-FFT 算法

DFT 將時(shí)域信號(hào)變換成頻域信號(hào)后,長(zhǎng)度為 N 的有限長(zhǎng)序列 x(n) 的離散傅里葉變換可以表示為 :

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

基 4 DIT-FFT 算法的基本原理是 :將一個(gè) N 點(diǎn)的 FFT分解為 4 個(gè) N/4 點(diǎn)的序列,再分別進(jìn)行 DFT 計(jì)算 ;然后再將每個(gè)N/4點(diǎn)進(jìn)一步分解為 4 個(gè)N/16點(diǎn)的計(jì)算,依此類推。同理,對(duì)于多點(diǎn)數(shù)還可以進(jìn)行多級(jí)分解。其基 4 蝶形運(yùn)算如下:

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

其中,X(K), X(k+N/4), X(k+2N/4), X(k+3N/4) 是蝶形運(yùn)算后的結(jié)果?;?4 蝶形運(yùn)算單元可以用圖 1 表示。

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

1.2 算法比較與選擇

一般常用乘法次數(shù)和加法次數(shù)來(lái)衡量一個(gè)算法的性能。例如,對(duì)于基 4FFT 算法的描述為 :每個(gè)蝶形運(yùn)算為 3 次復(fù)數(shù)乘法,每級(jí)共有 N/4 個(gè)基 4 蝶形單元,共有 m 級(jí) ( 其中,N=4m)。表 1 所列是 4 種常用基數(shù)算法運(yùn)算量的比較,表中,l=log2N。

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

一般情況下,基數(shù)越高,總計(jì)算量就越少,但是,控制復(fù)雜性也會(huì)相應(yīng)提高。就復(fù)雜性而言,基 2 算法最容易控制,操作簡(jiǎn)單 ;基 4 算法控制稍許復(fù)雜,但與基 2 相差不大 ;基 8和基 16 算法的控制復(fù)雜度與基 4 相比,難度會(huì)增大很多。綜合考慮運(yùn)算量與控制復(fù)雜度,本文選擇基 4 算法來(lái)實(shí)現(xiàn)設(shè)計(jì)。

2 基 4 FFT 算法的硬件實(shí)現(xiàn)

現(xiàn)今的 FFT 算法大多采用并行結(jié)構(gòu)來(lái)實(shí)現(xiàn)。由于并行結(jié)構(gòu)的數(shù)據(jù)輸入大多是串行連續(xù)輸入的,需要進(jìn)入串并轉(zhuǎn)換,這樣會(huì)浪費(fèi)大量時(shí)間,尤其是在一些實(shí)時(shí)高速處理的場(chǎng)合,并行結(jié)構(gòu)難以適應(yīng)。而流水線結(jié)構(gòu)在實(shí)時(shí)性和連續(xù)性等方面具有天然的優(yōu)勢(shì),所以,本設(shè)計(jì)采用流水線結(jié)構(gòu)來(lái)完成設(shè)計(jì)。

FFT 算法的流水線結(jié)構(gòu)一般分為 3 種:第一種是單路延時(shí)轉(zhuǎn)接器結(jié)構(gòu) (Single-path Delay Commutator,SDC) ;第二種是多路延時(shí)轉(zhuǎn)接器結(jié)構(gòu) (Multi-path Delay Commutator,MDC) ;第三種是單路延時(shí)反饋轉(zhuǎn)接器結(jié)構(gòu) (Single-path Delay Feedback,SDF)。表 2 所列是流水線結(jié)構(gòu) FFT 各種指標(biāo)的比較,其中,k=log4N。

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

從表 2 可以看出,在運(yùn)算量上,SDC 占優(yōu)勢(shì),但控制復(fù)雜度較高。綜合考慮運(yùn)算量、存儲(chǔ)單元及控制復(fù)雜度,SDF是最優(yōu)的選擇。因此,本設(shè)計(jì)采用 SDF 結(jié)構(gòu)。

本文設(shè)計(jì)實(shí)現(xiàn)的一個(gè) 1024 點(diǎn)流水線結(jié)構(gòu)基 4-SDF FFT的結(jié)構(gòu)框圖如圖 2 所示。

2.1 蝶形運(yùn)算單元

可以將蝶形運(yùn)算分割為下式 :

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

其中,基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)是蝶形運(yùn)算后一狀態(tài)的結(jié)果。經(jīng)過(guò)分割后,可以看出,整個(gè)蝶形運(yùn)算只有 a+b, a-b, a+jb, a-jb 四種計(jì)算,分別采用復(fù)數(shù)加法與減法器就可以完成蝶形運(yùn)算,從而可大大簡(jiǎn)化設(shè)計(jì)和實(shí)現(xiàn)的復(fù)雜度。圖 3 與圖 4 分別是蝶形單元所用到的復(fù)數(shù)加法器與減法器的框圖。

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

2.2高效乘法器

一般兩個(gè)復(fù)數(shù)分別為A=a+jb, B=C+jd的復(fù)數(shù)相乘的計(jì) 算過(guò)程為:

AB=(a+j b)(c+j d)=(ac-bd)+j(ad+bc)=Fre+j Yim                      (4)

其中,Yre為 AB 結(jié)果的實(shí)部,Yim為 AB 的虛部。

顯然,一次復(fù)數(shù)乘法共需要4次實(shí)數(shù)乘法和3次實(shí)數(shù)加 法,但是,如果進(jìn)行一定的變換,就可以減少實(shí)數(shù)乘法的次數(shù)。 即:

Yx=ac-bd=ac-ad+ad-bd=(c-d)a+(a-b)d                                      (5)

Yim=ad+bc=ad-bd+bd+bc=(c+d)b+(a-b)d                                 (6)

在計(jì)算前,將c-d,c+d,a-b的結(jié)果放在存儲(chǔ)單元中,這樣, 一次復(fù)數(shù)乘法就只需要3次實(shí)數(shù)乘法與5次實(shí)數(shù)加法,顯然 會(huì)大大節(jié)約硬件開(kāi)銷,同時(shí)也提高了計(jì)算速度。

本設(shè)計(jì)采用有符號(hào)數(shù)BOOTH編碼的乘法器,根據(jù)數(shù)據(jù) 量化,利用10位的被乘數(shù)和10位的乘數(shù)進(jìn)行運(yùn)算。其計(jì)算 結(jié)果乘積需要經(jīng)過(guò)飽和,最后取10位結(jié)果保留。

2.3旋轉(zhuǎn)因子存儲(chǔ)

本設(shè)計(jì)需要將旋轉(zhuǎn)因子向量= cos i +jsin i的實(shí)部和 虛部存儲(chǔ)在寄存器中,并利用查找表方式實(shí)現(xiàn)向量旋轉(zhuǎn)運(yùn)算。 這樣只需要取在1/8圓內(nèi),即[0,…,n/4]之間的旋轉(zhuǎn)因子, 其他的旋轉(zhuǎn)因子都是這1/8圓周區(qū)域內(nèi)旋轉(zhuǎn)因子的變換。按照 旋轉(zhuǎn)因子的周期性和對(duì)稱性,其他區(qū)域的旋轉(zhuǎn)因子,可通過(guò) 交換實(shí)部虛部和改變正負(fù)號(hào)來(lái)得到。

例如:設(shè)點(diǎn)A為[0,…,”4]的一個(gè)旋轉(zhuǎn)因子,假設(shè)它 寫(xiě)成矢量形式是A=cosx+jsinx,那么,映射到4個(gè)象限內(nèi)的 另外7個(gè)投影則是:

sinx+jcosx, -cosx +jsinx, -sinx +jcosx, -cosx+j(-sinx), -sinx+j(-cosx), sinx+j(-cosx), cosx+j(-sinx)

旋轉(zhuǎn)因子一共有8個(gè)數(shù)據(jù)。只需要將這樣的一個(gè)數(shù)據(jù)的 實(shí)部和虛部的數(shù)值(不包括符號(hào))分別存儲(chǔ)在寄存器同一個(gè)地 址的數(shù)據(jù)存儲(chǔ)單元里,就可以在取出這個(gè)數(shù)據(jù)后,通過(guò)變換 安排好它的實(shí)部和虛部,然后重新安排它的正負(fù)號(hào),就可得到 其他在該級(jí)運(yùn)算中所需要的另外7個(gè)旋轉(zhuǎn)因子。

2.4控制單元

每級(jí)蝶形運(yùn)算單元都有自己的控制單元,這主要是控制 蝶形運(yùn)算單元的工作模式,判斷是否進(jìn)入流水操作,操作數(shù) 的選取,RAM的選通,復(fù)數(shù)乘法的選通,以及產(chǎn)生RAM和 旋轉(zhuǎn)因子的地址。另外,控制單元還需要產(chǎn)生使能信號(hào),以供 下一級(jí)的輸入使用。

對(duì)于蝶形單元的控制,主要是控制其工作模式。在蝶形 單元中,輸入數(shù)據(jù)先存儲(chǔ)到第一個(gè)存儲(chǔ)單元中,同時(shí)從第一個(gè) 存儲(chǔ)單元的相同地址中取出上一次蝶形運(yùn)算的結(jié)果,然后把第 二、三段數(shù)據(jù)存儲(chǔ)到第二、三個(gè)存儲(chǔ)單元中,同時(shí)讀出相應(yīng)的 結(jié)果;當(dāng)最后的一段數(shù)據(jù)到來(lái)時(shí),從存儲(chǔ)單元中讀取相應(yīng)的 數(shù)據(jù)進(jìn)行蝶形運(yùn)算,同時(shí)輸出第一個(gè)運(yùn)算結(jié)果,并把其他3 個(gè)結(jié)果同址寫(xiě)回三個(gè)存儲(chǔ)單元相對(duì)應(yīng)的位置。

對(duì)于旋轉(zhuǎn)因子的控制,由于在寄存器中的旋轉(zhuǎn)因子都是 無(wú)符號(hào)數(shù),因此在進(jìn)行復(fù)數(shù)乘法之前,需要根據(jù)控制單元的 指示,重新安排它的正負(fù)號(hào)。

2.5輸出數(shù)據(jù)地址轉(zhuǎn)換

在系統(tǒng)中,F(xiàn)FT輸出的數(shù)據(jù)也許是給下一級(jí)使用。特別是 在OFDM系統(tǒng)中,也需要找回原來(lái)的順序。由于輸出數(shù)據(jù)的 地址是亂序,所以需要有地址產(chǎn)生模塊給數(shù)據(jù)產(chǎn)生地址,以 方便后級(jí)使用。輸出數(shù)據(jù)地址轉(zhuǎn)換應(yīng)按照00、01、10、11輸入, 并按照11、10、01、00順序輸出。

3仿真、綜合及FPGA實(shí)現(xiàn)

本文設(shè)計(jì)實(shí)現(xiàn)了一個(gè)1 024點(diǎn)的基4 FFT處理器,數(shù)據(jù) 處理精度為10位。采用Verilog HDL語(yǔ)言描述整個(gè)設(shè)計(jì),并 編寫(xiě)測(cè)試平臺(tái)。筆者利用Modelsim SE 6.5對(duì)本文的設(shè)計(jì)進(jìn)行 了功能仿真驗(yàn)證,運(yùn)算結(jié)果與Matlab計(jì)算的結(jié)果一致,從而 證明了本文算法的正確性。

在FPGA實(shí)現(xiàn)方面,本文選用Xilinx的Spartan-3E-XC- 3S500E芯片,該器件的內(nèi)部含有4個(gè)數(shù)字時(shí)鐘管理器(DCM), 73 kB 的分布 RAM, 360 kB 的 block RAM, 4 個(gè) 18X18 的專 用乘法器(Dedicated Multipliers)單元,其中乘法器的工作頻 率可達(dá)到300 MHz。綜合布線工具均采用Xilinx的設(shè)計(jì)平臺(tái)ISE9.1,表3所列是其該處理器與一些現(xiàn)有文獻(xiàn)中的FFT處 理器核的性能比較,可見(jiàn)本設(shè)計(jì)具有一定的優(yōu)勢(shì)。

基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

4結(jié)語(yǔ)

本文通過(guò)采用SDF流水線結(jié)構(gòu)設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于 FPGA的高速基4 FFT處理器,F(xiàn)PGA內(nèi)部資源消耗明顯減少, 并保持了比較高的工作頻率,能滿足信號(hào)處理系統(tǒng)實(shí)時(shí)處理的 要求。從實(shí)現(xiàn)結(jié)果可以看出,與并行結(jié)構(gòu)的FFT處理器相比, 流水線結(jié)構(gòu)的處理速度更快。該處理器可適用于超高速場(chǎng)合 以及需要密集型數(shù)字信號(hào)處理的領(lǐng)域,比如數(shù)字通信、數(shù)據(jù) 變換、定時(shí)定位處理、無(wú)線通訊、圖像處理等。

20210915_6141736b491a4__基于FPGA的高速基4FFT設(shè)計(jì)與實(shí)現(xiàn)

本站聲明: 本文章由作者或相關(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日 /美通社/ -- 英國(guó)汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開(kāi)發(fā)耗時(shí)1.5...

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

北京2024年8月28日 /美通社/ -- 越來(lái)越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來(lái)越多業(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中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開(kāi)幕式在貴陽(yáng)舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

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

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

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

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎ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)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國(guó)電影電視技術(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年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱"軟通動(dòng)力")與長(zhǎng)三角投資(上海)有限...

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