基 2 FFT 算法的模塊化硬件實(shí)現(xiàn)與比較

作者 駱林依¹，王英喆²，徐圓飛²，張華平³，梁星¹(1.北華航天工業(yè)學(xué)院 電子與控制工程學(xué)院，河北 廊坊 065000;2.北京航星機(jī)器制造有限公司，北京 100013;3.鄭州中興智城實(shí)業(yè)有限公司，河南 鄭州 450016)

　　摘要：隨著快速傅里葉變化(FFT)在信號(hào)處理應(yīng)用領(lǐng)域的廣泛應(yīng)用，不同場合對(duì)硬件實(shí)現(xiàn)的 FFT 算法結(jié)構(gòu)提出了多樣化的要求，針對(duì)這種需求在硬件編程設(shè)計(jì)中將 FFT 分割成模塊化的三部分：數(shù)據(jù)存儲(chǔ)重排模塊、旋轉(zhuǎn)因子調(diào)用模塊、蝶形運(yùn)算模塊。通過時(shí)序調(diào)用可組成不同結(jié)構(gòu)的 FFT 處理器，實(shí)現(xiàn)流水結(jié)構(gòu)與遞歸結(jié)構(gòu)兩種方案，分別側(cè)重于處理速度與資源占用量兩方面的優(yōu)勢(shì)。在FPGA硬件設(shè)計(jì)中使用 Verilog 語言完成代碼編程，實(shí)現(xiàn)了兩種結(jié)構(gòu)的 512 點(diǎn)基 2 算法的快速傅里葉變換，使用 Modelsim 完成功能仿真。與 MATLAB 中 FFT 函數(shù)對(duì)比驗(yàn)證了結(jié)果的正確性。最后通過比較二者的處理速度和資源占用量，給出了方案性能分析，及兩種方案的最佳適用場合。

　　關(guān)鍵詞：FFT;硬件實(shí)現(xiàn);基 2 算法;模塊化設(shè)計(jì);流水線結(jié)構(gòu);遞歸結(jié)構(gòu)

　　*基金項(xiàng)目：河北省北華航天工業(yè)學(xué)院碩士研究生科研項(xiàng)目(YKY-2016-02)。

　　0 引言

　　快速傅里葉變換(FFT)作為信號(hào)處理的一種高效手段已經(jīng)被廣泛應(yīng)用在許多工程中。但不同的應(yīng)用場合對(duì) FFT 算法的實(shí)現(xiàn)有不同的特性要求。研究的主要熱點(diǎn)在于硬件資源的占用量與運(yùn)算速度^[1-3]。而這兩者又是互相制衡的關(guān)系。所以有必要比較實(shí)現(xiàn) FFT 算法的多種方案?；? 2 算法具有算法簡單、時(shí)序清晰、在高速實(shí)時(shí)數(shù)據(jù)處理中不容易出錯(cuò)的優(yōu)點(diǎn)。所以本文簡要介紹了基 2 FFT 的算法化簡原理，設(shè)計(jì)實(shí)現(xiàn)了將 FFT 處理器劃分為通用化的三個(gè)模塊。通過簡單的時(shí)序調(diào)用就可以實(shí)現(xiàn)基 2 FFT 的兩種性能側(cè)重不同的方案。以適應(yīng)多種工程需求，并分析了兩種方案在不同場合的應(yīng)用。

　　1 FFT算法原理

　　FFT(Fast Fourier Transformation)是離散傅氏變換(DFT)的快速算法

　　DFT 的運(yùn)算公式為：

　　FFT 通過將離散序列逐級(jí)分解成為短序列，并利用旋轉(zhuǎn)因子的周期性和對(duì)稱性^[4]簡化了 DFT 的運(yùn)算過程，提高了 DFT 的運(yùn)算效率 ^[5-6]。

　　FFT算法的本質(zhì)就是對(duì)數(shù)據(jù)逐級(jí)做蝶形運(yùn)算。如圖1所示是一個(gè)基2蝶形單元。蝶形運(yùn)算為復(fù)數(shù)運(yùn)算。每次運(yùn)算由兩個(gè)輸入數(shù)據(jù)的實(shí)部虛部和相對(duì)應(yīng)的復(fù)數(shù)旋轉(zhuǎn)因子共同參與，運(yùn)算結(jié)果成為下一級(jí)的輸入數(shù)據(jù)。

　　由以下公式可以看出：一個(gè)基 2 蝶形運(yùn)算單元中含有一個(gè)復(fù)數(shù)乘法和兩個(gè)復(fù)數(shù)加法。在硬件實(shí)現(xiàn)中可將復(fù)數(shù)運(yùn)算化簡成實(shí)數(shù)運(yùn)算^[7-8]。

　　從上兩式可以看出,(BrWr-BiWi)和(BrWi+BiWr)在上下兩式中是重復(fù)出現(xiàn)的，所以可以在蝶形模塊中得到運(yùn)算化簡。

　　2 兩種設(shè)計(jì)方案

　　遞歸結(jié)構(gòu)處理速度較慢，但占用資源量少;流水線結(jié)構(gòu)中量每一級(jí)運(yùn)算都在同時(shí)進(jìn)行著，輸出數(shù)據(jù)除了剛開始的一段時(shí)間延遲，之后會(huì)不間斷地輸出結(jié)果。因此，可提高運(yùn)算速度。

　　第一種設(shè)計(jì)方案是流水線^[9-10]串行結(jié)構(gòu)，系統(tǒng)框圖如圖2所示。流水線結(jié)構(gòu)的特點(diǎn)是把整體設(shè)計(jì)分為幾個(gè)順序的流程，這幾個(gè)流程是單項(xiàng)串聯(lián)的。數(shù)據(jù)在每一個(gè)流程中只運(yùn)算一次，總是在將上一級(jí)的運(yùn)算結(jié)果傳遞給下一級(jí)。直至一組數(shù)據(jù)經(jīng)過所有流程完成運(yùn)算。這種結(jié)構(gòu)開始運(yùn)算后的每一個(gè)流程都在同時(shí)高效的利用，處理來自上一級(jí)的連續(xù)數(shù)據(jù)流，所以在第一組數(shù)據(jù)開始輸出后，之后的結(jié)果數(shù)據(jù)就會(huì)不間斷地輸出。

　　流水結(jié)構(gòu)中實(shí)現(xiàn)512點(diǎn)基 2 FFT 須重復(fù)調(diào)用9次三個(gè)通用模塊，完成9級(jí)運(yùn)算。數(shù)據(jù)順序逐級(jí)流入，根據(jù)級(jí)數(shù)計(jì)數(shù)信號(hào)來控制各模塊的調(diào)整。

　　第二種設(shè)計(jì)方案是遞歸結(jié)構(gòu)^[11-12]，遞歸結(jié)構(gòu)是指運(yùn)算重復(fù)利用兩組存儲(chǔ)空間，每一級(jí)的運(yùn)算都要用到上一級(jí)的運(yùn)算結(jié)果。遞歸結(jié)構(gòu)系統(tǒng)框圖如圖3所示。其關(guān)鍵部分是時(shí)序控制模塊，作用是控制運(yùn)算節(jié)奏，記錄運(yùn)算級(jí)數(shù)，從而控制排序模塊在不同運(yùn)算級(jí)的 RAM 讀寫規(guī)律以及旋轉(zhuǎn)因子模塊的地址選取。

　　在數(shù)據(jù)排序模塊中，遞歸結(jié)構(gòu)只占用兩組 RAM 存儲(chǔ)空間。數(shù)據(jù)交叉存儲(chǔ)在兩組 RAM 存儲(chǔ)中。采用乒乓 RAM 結(jié)構(gòu)交錯(cuò)寫入讀取數(shù)據(jù)，無需中間級(jí)的等待時(shí)間，可減小系統(tǒng)的運(yùn)算速度。

　　3 FPGA的硬件編程實(shí)現(xiàn)

　　FPGA實(shí)現(xiàn)的系統(tǒng)主要有三個(gè)通用模塊構(gòu)成：數(shù)據(jù)存儲(chǔ)重排模塊、旋轉(zhuǎn)因子調(diào)用模塊、蝶形運(yùn)算模塊。

　　本硬件設(shè)計(jì)中輸入數(shù)據(jù)序列的長度為 512，輸入數(shù)據(jù)的位寬為 30 位的有符號(hào)數(shù)，最終輸出數(shù)據(jù)的位寬也是 30 位的有符號(hào)數(shù)。

　　以下來詳細(xì)描述本設(shè)計(jì)中各個(gè)模塊的硬件實(shí)現(xiàn)方法。

　　3.1 數(shù)據(jù)存儲(chǔ)重排模塊

　　FFT 中每級(jí)參與蝶形運(yùn)算的兩個(gè)數(shù)據(jù)是按規(guī)律挑取的。假設(shè) L 級(jí)運(yùn)算，每級(jí)中兩個(gè)運(yùn)算數(shù)據(jù)按原位置排列會(huì)相差2(L-1)的距離。所以數(shù)據(jù)存儲(chǔ)重排模塊的作用就是將上一級(jí)的運(yùn)算結(jié)果數(shù)據(jù)存儲(chǔ)并按規(guī)律重新排序，使得輸出的數(shù)據(jù)剛好是要進(jìn)行下一級(jí)蝶形運(yùn)算的兩個(gè)數(shù)。

　　在本模塊中，控制存儲(chǔ)空間 RAM 的讀寫規(guī)律尤為關(guān)鍵。因?yàn)樵?FFT 系統(tǒng)中，對(duì) RAM 的讀寫速度直接影響到系統(tǒng)的運(yùn)行速度。利用雙口 RAM 對(duì)數(shù)據(jù)的讀和寫同時(shí)進(jìn)行以提高系統(tǒng)運(yùn)算效率，節(jié)省運(yùn)算時(shí)間。

　　每級(jí)數(shù)據(jù)調(diào)用位置不同，所以在編程時(shí)，要考慮每一級(jí)數(shù)據(jù)的排序規(guī)律，寫入通用模塊中，在 FFT 調(diào)用時(shí)根據(jù)運(yùn)算級(jí)數(shù)控制數(shù)據(jù)的讀取地址方式。本設(shè)計(jì)中 RAM 有兩種存取方式：第一級(jí)數(shù)據(jù)按照二進(jìn)制碼位倒敘寫入，順序讀出。2 到 9 級(jí)寫入地址順序，讀出地址間距為 1。經(jīng)過驗(yàn)證這樣的排序方式可以滿足各級(jí)蝶形運(yùn)算數(shù)的配對(duì)要求。

　　3.2旋轉(zhuǎn)因子調(diào)用模塊

　　旋轉(zhuǎn)因子調(diào)用模塊的作用是存儲(chǔ)并按規(guī)律抽出旋轉(zhuǎn)因子給蝶形運(yùn)算模塊。當(dāng)參與 FFT 運(yùn)算的點(diǎn)數(shù)確定時(shí)，所需的旋轉(zhuǎn)因子值就是固定不變的。所以在硬件實(shí)現(xiàn)中，可以在系統(tǒng)運(yùn)行之前將旋轉(zhuǎn)因子數(shù)值表計(jì)算出來，并存儲(chǔ)在 ROM 中。

　　旋轉(zhuǎn)因子的調(diào)用跟運(yùn)算級(jí)數(shù)有關(guān)，通過改變旋轉(zhuǎn)因子的取數(shù)時(shí)間間隔和地址間隔，生成9種不同的旋轉(zhuǎn)因子調(diào)用規(guī)律。寫入通用模塊中。由時(shí)序控制模塊中的運(yùn)算級(jí)數(shù)計(jì)數(shù)器判斷在程序運(yùn)行中需要調(diào)用的旋轉(zhuǎn)因子。

　　512 點(diǎn)的序列根據(jù)旋轉(zhuǎn)因子的周期性和對(duì)稱性共需要用到 256 個(gè)旋轉(zhuǎn)因子。本設(shè)計(jì)共 9 級(jí)，假設(shè)第 L 級(jí)，則每級(jí)中會(huì)用到 2(L-1)個(gè)旋轉(zhuǎn)因子。每級(jí)運(yùn)算中會(huì)分為2(9-L)個(gè)運(yùn)算組，同一級(jí)的每組用到的旋轉(zhuǎn)因子都是相同的。每組中會(huì)用到本級(jí)所有的旋轉(zhuǎn)因子。

　　根據(jù) RAM 的取數(shù)規(guī)律，會(huì)按順序取完每組中的第一個(gè)蝶形運(yùn)算所需要的數(shù)據(jù)，他們所用到的旋轉(zhuǎn)因子是同一個(gè)，運(yùn)算完所有組的第一個(gè)蝶形，再取每組的下一個(gè)蝶形運(yùn)算所需要的數(shù)據(jù)，這樣按順序把每組中所需要的數(shù)據(jù)取完，完成一級(jí)運(yùn)算。

　　按照這種規(guī)律，運(yùn)算數(shù)據(jù)與 ROM 讀出的旋轉(zhuǎn)因子相配合，可以減少 ROM 讀地址的改變次數(shù)。這樣 ROM 的取數(shù)更清晰簡單，不同旋轉(zhuǎn)因子取數(shù)的地址只用改變一次。如圖 4，以 8 點(diǎn) FFT 運(yùn)算為例給出排序后的運(yùn)算數(shù)據(jù)與旋轉(zhuǎn)因子的對(duì)照表。

　　3.3 蝶形運(yùn)算模塊

　　由于本設(shè)計(jì)中只用到一種運(yùn)算基，所以只用一個(gè)基 2 蝶形單元就可以實(shí)現(xiàn)對(duì)數(shù)據(jù)的流水線處理。

　　本設(shè)計(jì)中 512 點(diǎn)的 FFT 共有 9 級(jí)運(yùn)算，蝶形運(yùn)算模塊內(nèi)部采用流水結(jié)構(gòu)，可將從 RAM 中輸出的數(shù)據(jù)不間斷地進(jìn)行計(jì)算。每級(jí)順序進(jìn)行 256 次蝶形運(yùn)算。

　　本設(shè)計(jì)中的蝶形運(yùn)算流程如圖 5 所示。通過上述對(duì)公式的化簡分析可得，一次蝶形運(yùn)算本質(zhì)上可轉(zhuǎn)化為 4 次實(shí)數(shù)乘法和 6 次實(shí)數(shù)加法運(yùn)算。內(nèi)部劃分為三級(jí)流水結(jié)構(gòu)，數(shù)據(jù)和旋轉(zhuǎn)因子并行輸入計(jì)算。提高了模塊運(yùn)算效率。

　　4 仿真結(jié)果

　　本設(shè)計(jì)采用 Verilog 硬件語言在quartus 16.0 平臺(tái)編寫，在 modelsim 上通過仿真，驗(yàn)證結(jié)果與 matlab 中的 FFT 函數(shù)結(jié)果相比較，達(dá)到系統(tǒng)所要求精度。

　　流水結(jié)構(gòu)的 modelsim 仿真結(jié)果如圖6所示，仿真采用 50 M 時(shí)鐘，在 105240 ns 時(shí)輸出使能信號(hào)拉高有效，開始連續(xù)的輸出運(yùn)算結(jié)果數(shù)據(jù)。

　　流水線結(jié)構(gòu)大幅度提高了處理器速度，同時(shí)不可避免的加大了資源占用量。本設(shè)計(jì)的資源占用情況見表 1.

　　遞歸結(jié)構(gòu)的 modelsim 仿真結(jié)果如圖7所示，仿真采用 50 M 時(shí)鐘，在 10500 ns 時(shí)開始輸出數(shù)據(jù)，由圖中仿真結(jié)果可以看出，兩種設(shè)計(jì)在運(yùn)算一次 512 點(diǎn)FFT的時(shí)間上非常接近，只是流水結(jié)構(gòu)在輸出第一組結(jié)果數(shù)據(jù)后可連續(xù)不斷的輸出下一組數(shù)據(jù)，遞歸結(jié)構(gòu)則需要再等待一次完整運(yùn)算時(shí)間，才能輸出下一組結(jié)果數(shù)據(jù)。

　　遞歸結(jié)構(gòu)的資源占用量較流水結(jié)構(gòu)相比減少很多。資源占用情況見表 2。

　　5 結(jié)果比較

　　FPGA實(shí)現(xiàn)中流水結(jié)構(gòu)的資源占用量較大，但用流水線結(jié)構(gòu)可以提高系統(tǒng)的工作頻率和吞吐率。將處理器速度得到了大幅度的提高，可應(yīng)用在實(shí)時(shí)性要求高的數(shù)據(jù)處理場合。進(jìn)行實(shí)時(shí)的 FFT 運(yùn)算。

　　從上面的分析可以看出，遞歸結(jié)構(gòu)兩次運(yùn)算輸出結(jié)果所需時(shí)間間隔較長。但在硬件實(shí)現(xiàn)中需要的存儲(chǔ)資源量很少。本設(shè)計(jì)通過采用乒乓 RAM 結(jié)構(gòu)和降低蝶形運(yùn)算單元中乘法數(shù)目的方法，節(jié)約了硬件資源，降低了設(shè)計(jì)成本。適合于應(yīng)用在對(duì)速度要求不高低成本的處理系統(tǒng)中。

　　通過比較二者資源量和數(shù)據(jù)，可以發(fā)現(xiàn)資源與速度在硬件實(shí)現(xiàn)中是互相制約的。所以要參照 FFT 所運(yùn)用的場合和用途來選擇最合適的算法。本設(shè)計(jì)中利用三個(gè)固定模塊可快速靈活的改變算法優(yōu)勢(shì)，滿足資源和速度的兩種需求。

　　參考文獻(xiàn)

　　[1]劉智.基于FPGA實(shí)現(xiàn)的FFT速度與規(guī)模分析[J].科技視界,2014(21):192-193.

　　[2]杜兆勝.基于FPGA的FFT硬件架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)[D].長春理工大學(xué),2016.

　　[3]余雷.基于FPGA的32點(diǎn)FFT算法的設(shè)計(jì)與實(shí)現(xiàn)[D].西安電子科技大學(xué),2014.

　　[4]錢輝,史瑤,龔敏,高博.結(jié)合頻譜移位的二維傅里葉變換FPGA實(shí)現(xiàn)[J].電子器件,2017,40(05):1092-1096.

　　[5]顧艷麗,周洪敏.基于FPGA的新型高速FFT算法研究與實(shí)現(xiàn)[J].電子器件,2008(4):1249-1251.

　　[6]王曉君,龍騰,周希元.二維級(jí)聯(lián)流水結(jié)構(gòu)大點(diǎn)數(shù)FFT運(yùn)算器實(shí)現(xiàn)研究[J].無線電工程,2010,40(11):19-22.

　　[7]于洪松.基于FPGA的實(shí)時(shí)圖像頻域處理[D].中國科學(xué)院研究生院(長春光學(xué)精密機(jī)械與物理研究所),2014.

　　[8]唐英杰,鐘凱.一種基于FPGA的高速FFT處理器實(shí)現(xiàn)[J].科技廣場,2015(12):15-17.

　　[9]王英喆,杜蓉.基于FPGA流水線結(jié)構(gòu)并行FFT的設(shè)計(jì)與實(shí)現(xiàn)[J].電子設(shè)計(jì)工程,2015,23(4):47-50.

　　[10]和玉梅.局部流水FFT處理器設(shè)計(jì)[J].蘭州理工大學(xué)學(xué)報(bào),2014,40(6):83-89.

　　[11]趙冬冬.基于FPGA的1024點(diǎn)FFT算法實(shí)現(xiàn)[D]. 蘇州大學(xué),2014.

　　[12]楊晶,康寧,王元慶.基于低成本FPGA的FFT設(shè)計(jì)實(shí)現(xiàn)[J].電子器件,2013,36(4):506-509.

　　作者簡介：

　　駱林依(1994-)，女，碩士生，主要研究方向：信號(hào)采集與處理。

本文來源于科技期刊《電子產(chǎn)品世界》2019年第2期第31頁，歡迎您寫論文時(shí)引用，并注明出處