基-4FFT處理器的優(yōu)化設(shè)計(jì)與應(yīng)用

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

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

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

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

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

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

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

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

1 基本原理

1.1 FFT算法基本原理

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

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

(1)

1.2 基-4DIT-FFT算法

(2)

令

(3)

則可得:

(4)

基-4蝶形運(yùn)算原理如圖1所示。

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

圖1 基-4蝶形運(yùn)算原理示意圖

2 FFT處理器設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

2.1 預(yù)處理模塊

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

2.1.2 亂序處理模塊

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

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

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

2.2.1 基-4算法模塊

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

2.2.2 地址運(yùn)算模塊

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果與驗(yàn)證

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

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

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

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

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

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

圖6 算法的實(shí)際應(yīng)用結(jié)果

4 結(jié) 論

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