高 博, 尹若童, 張乙海, 宋紫祎

(1.四川大學 物理學院,四川 成都 610065;2.四川大學 吳玉章學院,四川 成都 610065)

離散傅里葉變換(discrete Fourier transform,DFT)在信號處理中有著重要應用,是確定研究信號時域和頻率轉(zhuǎn)換的最直接有效的數(shù)學過程。但在其實現(xiàn)過程中需要進行大量的復數(shù)乘法及正余弦函數(shù)運算,其計算量與變換區(qū)間長度N的平方成正比,隨著DFT輸入點數(shù)的增加,其運算量將會增大?？焖俑道锶~變換(fast Fourier transform,FFT)算法簡化了DFT算法過程,有效降低了運算量,FFT處理中提出了基-2、基-4、基-8等不同算法,各種算法所需運算量的評估結(jié)果見表1所列。

表1 幾種FFT算法復數(shù)乘法運算量比較

基-2FFT和基-4FFT算法運算量較少,結(jié)構(gòu)規(guī)整,易于實現(xiàn),并且具有可以同址運算、內(nèi)部數(shù)據(jù)不需重排等特點[1],而基-8FFT算法具有更快運算速度,但在此基礎上程序復雜度較高,靈活性有所欠缺[2-3]?；?4算法在速度和復雜度上是折中方案,且具有相對靈活的處理點數(shù)。

在實際應用中,為了提升運算速度和集成度,通常單獨設計用于實現(xiàn)FFT的處理器,但仍然存在占用資源多、計算速度慢、數(shù)據(jù)類型轉(zhuǎn)換復雜等問題[4-5]。為解決這些問題,文獻[6]通過可重構(gòu)蝶形運算器進行不同 FFT 算法的切換,使用基-2FFT 算法做更多序列長度的覆蓋,基-8FFT 算法進行長序列的加速。但這種設計結(jié)構(gòu)復雜,且存在延時問題,1 024點變換需要較多的時序遍歷所有的點數(shù),也有設計通過象限映射的方法節(jié)省存儲資源,并且在蝶形單元計算時采用超前進位的加法器,乘法器采用Booth編碼減少部分積[7],但這種算法會給后端布局布線工作產(chǎn)生影響,并不符合實際應用的需要。文獻[8]報道基-4FFT算法在50 MHz時鐘頻率下,進行1 024點運算需要消耗41.28 μs。

為解決處理器消耗資源多、計算速度慢等問題,本文進一步分析基-4FFT算法,優(yōu)化原有算法實現(xiàn)硬件結(jié)構(gòu)。通過分析數(shù)據(jù)流路徑,采用分時復用和流水線結(jié)構(gòu)設計電路實現(xiàn)低延遲。設計中采用MATLAB對伸縮系數(shù)和旋轉(zhuǎn)系數(shù)進行預處理,降低系統(tǒng)復雜性。

現(xiàn)場可編程邏輯門陣列(field programmable gate array,FPGA)原型結(jié)果表明,工作頻率在50 MHz下實現(xiàn)了11.90 μs完成1 024點傅里葉變換算法。該結(jié)果相對于同期研究中普遍使用的順序處理算法而言,延時降低約71.2%,同時該設計硬件資源消耗較少。

1 基本原理

1.1 FFT算法基本原理

設有時域有限長序列{x(n)}的長度為N,且滿足N=4M,其頻域值{X(k)}可表示為:

X(k)=DFT[x(n)]=

(1)

1.2 基-4DIT-FFT算法

(2)

令

(3)

則可得:

(4)

基-4蝶形運算原理如圖1所示。

從圖1可以看出,1個基-4蝶形運算的單元需要進行3次復數(shù)乘法和8次復數(shù)加法,則可得進行N=4M點基-4DIT-FFT運算需要進行3MN/4次復數(shù)乘法和2MN次復數(shù)加法,遠小于直接計算所需的N2次復數(shù)乘法和N(N-1)次復數(shù)加法,提高了運算速率。

圖1 基-4蝶形運算原理示意圖

2 FFT處理器設計與實現(xiàn)

FFT處理器由4個模塊構(gòu)成,分別為預處理模塊、數(shù)據(jù)處理模塊、數(shù)據(jù)存儲模塊和處理器狀態(tài)控制模塊,具體結(jié)構(gòu)如圖2所示。

圖2 系統(tǒng)結(jié)構(gòu)

預處理模塊包含旋轉(zhuǎn)因子置入模塊和亂序處理模塊，其中旋轉(zhuǎn)因子置入模塊的核心為高精度的坐標旋轉(zhuǎn)數(shù)字計算(coordinate rotation digital computer,CORDIC)算法。數(shù)據(jù)處理模塊主要用于循環(huán)運算及中間結(jié)果的存儲1 024點的32位數(shù)據(jù)經(jīng)過地址運算系統(tǒng)和RAM-in-4選擇需要的數(shù)據(jù)進行讀操作,然后經(jīng)過DIT-4模塊的計算,通過地址運算系統(tǒng)和RAM-out-4將運算結(jié)果寫到相應的地址位,再通過預處理模塊中的亂序處理模塊調(diào)整存儲順序。數(shù)據(jù)存儲模塊用于中間信息的存儲以及經(jīng)過多級運算后最終結(jié)果的存儲及輸出。處理器狀態(tài)控制模塊負責系統(tǒng)工作轉(zhuǎn)換。

2.1 預處理模塊

2.1.1 旋轉(zhuǎn)因子置入模塊

2.1.2 亂序處理模塊

由時間抽取基-4FFT原理可得,若DIT算法的輸出為順序排列,則要求其輸入為特定的規(guī)律排列,因此,設計亂序處理模塊將順序輸入的數(shù)據(jù)按照系統(tǒng)計算時所需要的亂序結(jié)構(gòu)重新排序。首先,將計算點數(shù)1 024點轉(zhuǎn)化為10位二進制的地址,然后將原地址為A1A2A3A4A5A6A7A8A9的數(shù)據(jù)轉(zhuǎn)存入地址A9A8A7A6A5A4A3A2A1。轉(zhuǎn)化后對應地址的數(shù)據(jù)作為后續(xù)模塊的輸入。

本文使用計數(shù)模塊,用10位二進制計數(shù)器,按照0～1 023的地址位讀取原始數(shù)據(jù),再將其按照亂序處理之后的地址置入新的RAM-initial中,完成數(shù)據(jù)的亂序排列。

2.2 數(shù)據(jù)處理模塊

2.2.1 基-4算法模塊

基-4算法模塊主要完成蝶形運算過程,需要按照地址運算模塊從隨機存儲器讀取等待處理的數(shù)據(jù),并將計算結(jié)果覆蓋存儲于相同存儲器的相同地址位。每一組基-4算法模塊由2個容量為4的32位存儲器RAM-in-4、RAM-out-4以及核心蝶形運算單元DIT-4構(gòu)成。其中,2個存儲器下,讀取并存儲每一點的數(shù)據(jù)進入RAM-1 024中。而核心蝶形運算單元采用圖1所示原理實現(xiàn)運算。該處理器采用分時復用技術設計每一級算法結(jié)構(gòu),因而每一級內(nèi)的運算只需要1個基-4算法模塊,有效地利用了硬件資源,減少了資源消耗。

2.2.2 地址運算模塊

目前基于FPGA的FFT硬件實現(xiàn)結(jié)構(gòu)主要分為遞歸結(jié)構(gòu)、流水線結(jié)構(gòu)和全并行結(jié)構(gòu)[10]。在數(shù)據(jù)處理模塊中,5級級聯(lián)的設計采用流水線級聯(lián)框架,如圖3所示。

圖3 混合構(gòu)架運算示意圖

為了減少硬件資源消耗,根據(jù)DIT每一級的計算規(guī)則,蝶形運算中采用分時復用技術實現(xiàn)。根據(jù)計算規(guī)則,本文將數(shù)據(jù)處理分為5級,第1級輸入順序為亂序處理后的順序排列,同級間由地址遞進規(guī)則置入基-4算法模塊,并依照地址運算輸出至下一級的輸入存儲器等待下一級計算。根據(jù)級聯(lián)間的時序,每一級進行一定次數(shù)的DIT計算后下一級即可開始,減少了等待每一級所有點數(shù)計算完畢所需的時間。

系統(tǒng)整體構(gòu)建時,基于基-4DIT變換的模式,當進行4M點運算時,需進行M級蝶形運算,即將第1級拆分成4M-1個4點蝶形運算,第2級拆分成4M-2個16點蝶型運算，以此類推至第M級進行1個4M蝶形運算。而在不同級之間,同一級內(nèi)的點參與計算的順序不同,此時順序需要由地址做遞進運算來確定。根據(jù)基-4DIT計算規(guī)則,在第M級內(nèi),按照順序分為4M組,根據(jù)地址計算,每次依次從1個組內(nèi)提取4個點的地址對應的數(shù)據(jù),將其地址對應的值置入于基-4算法模塊中的隨機存儲器RAM-in-4中。此時地址的計算為同級遞進運算。

同級遞進運算要求前一級已經(jīng)完成計算并將計算所得數(shù)據(jù)存入該級前置RAM中,但根據(jù)現(xiàn)有FFT計算方式,均將一級完全計算完畢后開始下一級的計算,為了從算法上減少完全計算所需的時間,本文采用級聯(lián)間的部分延時來滿足每一級對前一級數(shù)據(jù)的要求。因此,對于1 024點FFT計算,第1級蝶形運算單元需要延時4個周期;第2級蝶形運算單元需要延時16個周期;第3級蝶形運算單元需要延時64個周期;第4級蝶形運算單元需要延時256個周期;第5級蝶形運算單元需要延時1 024個周期。

每級陣列在延時完畢后,下一級陣列即開始順序運算,每級相互并行,同一級之間的每組運算級聯(lián)。每級運算結(jié)果都將由數(shù)據(jù)存儲器按位進行讀取操作,直到M級運算完成,即循環(huán)結(jié)束。

2.3 數(shù)據(jù)存儲模塊

數(shù)據(jù)存儲器在進行蝶形運算時,按位進行中間結(jié)果的讀取操作,直到循環(huán)結(jié)束。當多級運算完成后,數(shù)據(jù)存儲器中的結(jié)果即可作為最終結(jié)果讀出。本文采用的系統(tǒng)級數(shù)為5,按照虛部、實部共使用10個1 024×32的隨機存儲器RAM-1 024來存儲數(shù)據(jù)。

2.4 處理器狀態(tài)控制模塊

該模塊基本單元就是1個狀態(tài)機,主要控制地址運算模塊和亂序處理模塊,兩者獨立進行,包括ST-REVER、ST-1、ST-2、ST-3、ST-4、ST-5、NORMAL、ST-OUT共8個狀態(tài)，如圖4所示。

圖4 處理器狀態(tài)控制模塊結(jié)構(gòu)

其中:當沒有有效數(shù)據(jù)進入系統(tǒng)時,狀態(tài)機一直處于NORMAL狀態(tài);當檢測到新信號數(shù)據(jù)有效時,系統(tǒng)開始進入ST-REVER狀態(tài),亂序計數(shù)器開始計數(shù);亂序計數(shù)器計數(shù)完畢后,系統(tǒng)進入ST-1狀態(tài),第1級計數(shù)器開始計數(shù),每次計數(shù)置入相應4個地址的數(shù)據(jù)進入基-4運算模塊;當?shù)?級計數(shù)器計數(shù)為4時,狀態(tài)機進入ST-2狀態(tài),第2級計數(shù)器開始計數(shù),每一級計數(shù)后進行此次操作;當?shù)?級計數(shù)器計數(shù)為16時,狀態(tài)機進入ST-3狀態(tài),第3級計數(shù)器開始計數(shù);當?shù)?級計數(shù)器計數(shù)為64時,狀態(tài)機進入ST-4狀態(tài),第4級計數(shù)器開始計數(shù);當?shù)?級計數(shù)器計數(shù)為256時,狀態(tài)機進入ST-5狀態(tài),第5級計數(shù)器開始計數(shù);當?shù)?級計數(shù)器計數(shù)為256時,狀態(tài)機進入ST-OUT狀態(tài),讀出計數(shù)器開始工作,將最后計算的數(shù)據(jù)輸出。

3 結(jié)果與驗證

該處理器的測試在友晶DE2開發(fā)板上驗證,采用的FPGA是Cyclone Ⅱ EP2C35設計,所使用的硬件資源包括9 110個組合邏輯單元和3 418個時序邏輯單元,分別占總邏輯單元數(shù)的27%和10%。此外,還消耗存儲器356個,內(nèi)嵌乘法器35個。本文主要通過分時復用減少部分資源的消耗。雖然本文的資源相對于同期研究提高了1倍,但根據(jù)本文對算法的分析,若不采用本文算法,則僅增加流水線的寄存器而達到速度提升71.2%的效果需要資源消耗量提高約2.5倍。

依據(jù)算法,第1級蝶形運算單元需要4個額外周期;第2級蝶形運算單元需要16個額外周期;第3級蝶形運算單元需要64個額外周期;第4級蝶形運算單元需要256個額外周期;第5級蝶形運算單元需要256個額外周期。因此處理1組1 024的數(shù)需(4+16+64+256+256)=596個周期。時序仿真結(jié)果如圖5所示。

圖5 時序仿真結(jié)果

圖5中：cp信號為系統(tǒng)時序,為方波信號;rst為系統(tǒng)工作信號,低電平有效;rst1為系統(tǒng)預備信號,高電平有效;qq-i、qq-r分別為系統(tǒng)最后一級輸出信號的虛部與實部,有符號數(shù);系統(tǒng)頻率在50 MHz下,計算并置入旋轉(zhuǎn)因子需要22 μs,1 024點算法過程需要11.9 μs;時序分析結(jié)果表明該設計可以達到的最高頻率為200 MHz。

測試中使用實際采集的光電容積脈搏波信號作為信號源,經(jīng)過所設計處理器輸出結(jié)果如圖6所示。

由測試結(jié)果讀出主頻率點1.08 Hz,計算得到脈搏數(shù)為65次/min。這與醫(yī)用脈搏儀讀取數(shù)值一致，從而證明了處理器設計的正確性?；贔FT分析生理參數(shù)的監(jiān)測技術可應用于便攜、快速、準確地測量心率和呼吸率的研究,可作為醫(yī)院或家庭地日常監(jiān)護[11]。

圖6 算法的實際應用結(jié)果

4 結(jié) 論

本文通過分析基-4DIT-FFT算法流程,針對多級結(jié)構(gòu)特點采用分時復用和流水線數(shù)據(jù)處理方法設計了一款1 024點FFT處理器芯片。設計中通過提前置入旋轉(zhuǎn)因子的方法減少了系統(tǒng)準備時的時序消耗;在5級結(jié)構(gòu)中采用流水線技術構(gòu)架,且流水線內(nèi)不需要等待一級全部計算完畢再進行下一級計算,與普遍使用的順序處理算法相比,減少了進行整個基-4FFT運算時的時序消耗。同時在單級運算中蝶形算法設計采用分時復用技術減少了硬件資源的消耗。通過FPGA原型驗證得到,該處理在50 MHz條件下僅需要11.9 μs即可完成1 024點運算,與同期其他研究相比,速度提高71.2%。通過進一步優(yōu)化單級中采用部分并行算法可提高速度,但也會消耗更多資源。