一種高精度低開銷的FFT設(shè)計(jì)

北方工業(yè)大學(xué)信息學(xué)院 戴 瀾 皮義強(qiáng)

隨著5G等先進(jìn)通信技術(shù)的快速發(fā)展，系統(tǒng)對FFT的精度和成本開銷要求越來越高。本文提出了一種定點(diǎn)遞歸結(jié)構(gòu)的高精度低開銷1024點(diǎn)FFT設(shè)計(jì)方法：設(shè)計(jì)了一種簡單有效的地址產(chǎn)生方案對蝶形運(yùn)算單元所需數(shù)據(jù)的無等待訪問，使蝶形單元在每個(gè)運(yùn)算階段都處于高利用率狀態(tài)；提出了一種新穎的定點(diǎn)算法，在保留定點(diǎn)運(yùn)算結(jié)構(gòu)簡單、資源消耗少等特點(diǎn)的基礎(chǔ)上有效得提高了結(jié)果的精度。使用MATLAB進(jìn)行仿真分析，輸出信噪比為64.4dB，基于SMIC 130nm標(biāo)準(zhǔn)單元庫對處理器進(jìn)行綜合，在PVT條件為SS/1.08V/125℃下，面積為36.34kGE，吞吐量為1.50Gbps。

快速傅里葉變換（FFT）是離散傅里葉變換（DFT）的一種快速算法。FFT實(shí)現(xiàn)了數(shù)字信號的實(shí)時(shí)處理，并在超聲、雷達(dá)、通信等領(lǐng)域得到了廣泛的應(yīng)用。不同的應(yīng)用場景對FFT的功能需求各有側(cè)重，在OFDM應(yīng)用中，F(xiàn)FT的精度和硬件開銷對系統(tǒng)性能有著更加顯著的影響。目前，F(xiàn)FT運(yùn)算的數(shù)據(jù)格式可以分為定點(diǎn)、浮點(diǎn)和塊浮點(diǎn)三種類型，浮點(diǎn)運(yùn)算在三種方式中精度最高，但電路結(jié)果較為復(fù)雜且吞吐率低，定點(diǎn)運(yùn)算在硬件上最容易實(shí)現(xiàn)，往往不需要對輸入待計(jì)算數(shù)據(jù)做任何處理，但在移位、截位等操作后會(huì)引入誤差，尤其在多次進(jìn)行此類操作后，誤差將不斷累積而造成輸出結(jié)果精度的大幅降低。

在ASIC的結(jié)構(gòu)實(shí)現(xiàn)方面，F(xiàn)FT主要有遞歸結(jié)構(gòu)、級聯(lián)結(jié)構(gòu)、并行結(jié)構(gòu)和陣列結(jié)構(gòu)等，并行結(jié)構(gòu)和陣列結(jié)構(gòu)運(yùn)算速度塊，但控制復(fù)雜，資源消耗多，適用于對速度要求很高的場景。遞歸結(jié)構(gòu)通過重復(fù)使用蝶形運(yùn)算單元、存儲(chǔ)器等方式有效的降低資源的消耗程度。蘇斌、劉暢等提出了一種的高速、高精度的FFT處理器架構(gòu)，但該架構(gòu)由8路并行運(yùn)算實(shí)現(xiàn)，故資源占用率很高。綜合上述考慮，本文設(shè)計(jì)了一種基4算法的、采樣點(diǎn)數(shù)為1024的FFT處理器，輸入輸出數(shù)據(jù)為13bit，采用遞歸結(jié)構(gòu)降低資源消耗，良好的數(shù)據(jù)調(diào)度模式使蝶形運(yùn)算單元滿負(fù)荷運(yùn)行，設(shè)計(jì)實(shí)現(xiàn)了一種新穎的定點(diǎn)算法，通過簡單位移操作，有效地提高了運(yùn)算精度。

1 基4-FFT算法

設(shè)X(n)為N點(diǎn)有限長序列，其離散傅里葉變換(discrete fourier transform，DFT)為：

其中，旋轉(zhuǎn)因子為：

當(dāng)序列長度N滿足N=時(shí)，按時(shí)鐘抽取的DFT算法為：

進(jìn)行變量替換后有：

由上式可知，每一組4點(diǎn)數(shù)據(jù)進(jìn)入蝶形運(yùn)算單元后先進(jìn)行復(fù)數(shù)乘法，由于A所對應(yīng)的旋轉(zhuǎn)因子不需要乘，故只有3次旋轉(zhuǎn)因子乘法，隨后進(jìn)行兩級復(fù)數(shù)加法按同址輸出結(jié)果。

2 FFT的設(shè)計(jì)方案

2.1 FFT整體結(jié)構(gòu)

如圖1所示，F(xiàn)FT整體結(jié)構(gòu)包括7個(gè)部分：RAM地址生成單元，用于在各個(gè)階段生成讀寫兩組RAM的地址；旋轉(zhuǎn)因子地址生成單元，本設(shè)計(jì)中對RAM和ROM的訪問并不同址；蝶形運(yùn)算單元；存放蝶形運(yùn)算數(shù)據(jù)的兩組RAM，每組RAM由四塊容量為256的單口RAM構(gòu)成；三塊存儲(chǔ)旋轉(zhuǎn)因子的ROM；控制單元，由控制運(yùn)算階段跳轉(zhuǎn)的狀態(tài)機(jī)構(gòu)成；多個(gè)移位模塊，其和定點(diǎn)運(yùn)算的優(yōu)化有關(guān)。一組1024個(gè)定點(diǎn)數(shù)據(jù)通端口串行輸入，經(jīng)過移位處理后亂序存入A組RAM中，隨后在RAM地址生成單元和旋轉(zhuǎn)因子地址生成單元的控制下，從A組RAM和ROM中提取運(yùn)算數(shù)據(jù)和旋轉(zhuǎn)因子放入蝶形單元中進(jìn)行運(yùn)算，將結(jié)果進(jìn)行移位優(yōu)化處理后寫入B組RAM中，繼續(xù)執(zhí)行下一級蝶形運(yùn)行，此時(shí)B組RAM成為數(shù)據(jù)源，A組RAM成為數(shù)據(jù)存儲(chǔ)目標(biāo)，當(dāng)五次蝶形運(yùn)算結(jié)束后，結(jié)果存放于B組RAM中，將數(shù)據(jù)通過端口串行輸出。

圖1 FFT整體結(jié)構(gòu)圖

2.2 定點(diǎn)算法優(yōu)化

M級蝶形運(yùn)算后都需要將數(shù)據(jù)暫存到RAM中，由于蝶形單元輸出結(jié)果的位寬和RAM位寬的差異導(dǎo)致必須進(jìn)行數(shù)據(jù)截?cái)嗪蟛拍艽鎯?chǔ)，從而造成數(shù)據(jù)精度降低。將數(shù)據(jù)存儲(chǔ)范圍最高位與數(shù)據(jù)最高有效位之間（不計(jì)入符號位，下同）的位差定義為移位因子，數(shù)據(jù)左移位后不會(huì)發(fā)生溢出。本設(shè)計(jì)提出的定點(diǎn)運(yùn)算優(yōu)化方案具體實(shí)現(xiàn)如圖2所示。

圖2 蝶形運(yùn)算階段的移位機(jī)制

每一級蝶形運(yùn)算前，對所有數(shù)據(jù)進(jìn)行移位因子提取，可得｛｝，最后取其中最小值做為移位公因子。在蝶形單元中，數(shù)據(jù)與旋轉(zhuǎn)因子的乘法，加減法都進(jìn)行運(yùn)算位寬拓展，保證數(shù)據(jù)在運(yùn)算中為滿精度運(yùn)算。最終運(yùn)算結(jié)果需要進(jìn)行截去旋轉(zhuǎn)因子和運(yùn)算帶來的位寬，記為T，傳統(tǒng)定點(diǎn)算法通過直接截去低T位來滿足存儲(chǔ)位寬。本設(shè)計(jì)考慮移位公因子S對運(yùn)算的影響，由于所有數(shù)據(jù)的最高S位都為無效位，最終運(yùn)算結(jié)果的最高S位也將是無效位，在截去數(shù)據(jù)時(shí)，將這部分截掉，再截去低(T－S)位，被存儲(chǔ)的結(jié)果相對于傳統(tǒng)定點(diǎn)算法多保留了S位的有效數(shù)據(jù)，數(shù)據(jù)值擴(kuò)大了2S倍。每級移位公因子S對運(yùn)算結(jié)果的影響是累加的，在五級蝶形運(yùn)算結(jié)束后，將給出對輸出結(jié)果的增益。

2.3 旋轉(zhuǎn)因子存儲(chǔ)優(yōu)化

在蝶形運(yùn)算過程中通過查找表方法取出所需的旋轉(zhuǎn)因子，第M級運(yùn)算需要4M－1個(gè)旋轉(zhuǎn)因子，旋轉(zhuǎn)因子間地址間距為4L－M。首先定義參考計(jì)數(shù)器C[7:0]，旋轉(zhuǎn)因子地址位寬為10bit，由此W p的地址如圖3所示。W2p的地址為2倍W p，W3p的地址為3倍W p。

圖3 旋轉(zhuǎn)因子W p地址產(chǎn)生規(guī)律圖

2.4 地址產(chǎn)生模塊的設(shè)計(jì)

為了實(shí)現(xiàn)遞歸結(jié)構(gòu)下的最大運(yùn)算利用率，避免運(yùn)算階段蝶形單元空置，通過單周期數(shù)據(jù)取存，即每個(gè)周期下讀取4個(gè)復(fù)數(shù)據(jù)進(jìn)行蝶形運(yùn)算。為此，需要將參與運(yùn)算的4個(gè)數(shù)據(jù)需要存放在不同的RAM塊中，杜兆勝的基于FPGA的FFT處理器設(shè)計(jì)與實(shí)現(xiàn)一文采用了“正序輸入，整序輸出”的結(jié)構(gòu)，因此其在最終數(shù)據(jù)輸出時(shí)仍然需要一級地址變化才能正序輸出數(shù)據(jù)，引入了較為復(fù)雜的整序邏輯。本設(shè)計(jì)在輸入時(shí)將數(shù)據(jù)整序，經(jīng)過5級蝶形運(yùn)算后，數(shù)據(jù)按順序存入RAM中，故在輸出時(shí)不在需要地址變化即可正序輸出。

RAM的地址產(chǎn)生如圖4所示，計(jì)數(shù)器為每個(gè)階段的選址提供參考，每個(gè)階段的RAM訪問地址都是由計(jì)數(shù)器數(shù)值進(jìn)行重排列得到的，在輸入階段，輸入數(shù)據(jù)整序后寫入A組RAM中，在五級蝶形運(yùn)算階段，對兩組RAM的地址尋址相同，由所處的級數(shù)決定是讀操作還是寫操作，在輸出階段，數(shù)據(jù)從B組RAM中順序輸出，此時(shí)A組RAM空閑可以寫入下次待運(yùn)算數(shù)據(jù)。

圖4 RAM地址生成示意圖

3 功能驗(yàn)證與FPGA實(shí)現(xiàn)

在使用Verilog完成整體設(shè)計(jì)后，使用Modelsim進(jìn)行功能仿真，并與Matlab模型進(jìn)行結(jié)果對比，顯示功能設(shè)計(jì)正確。為了進(jìn)行信噪比分析，利用Matlab生成的隨機(jī)測試激勵(lì)包，分別使用Matlab自帶的fft函數(shù)、本設(shè)計(jì)進(jìn)行仿真，取1000次信噪比結(jié)果，最終得到輸出信噪比為65.4dB。

使用Xilinx Artix7 XC7A200T進(jìn)行原型機(jī)驗(yàn)證，兩組RAM通過調(diào)用ISE中提供的IP來實(shí)現(xiàn)，經(jīng)過ISE 14.7的綜合實(shí)現(xiàn)，資源報(bào)告如表1所示。

表1 FPGA資源報(bào)表

從資源報(bào)表中可以看出設(shè)計(jì)的顯著低資源開銷特性，時(shí)序報(bào)告顯示設(shè)計(jì)能工作的最小周期是7.972ns，即最大工作頻率是125.429MHz。

4 ASIC實(shí)現(xiàn)

本設(shè)計(jì)FFT通過Synopsys Design Compiler(DC)來進(jìn)行綜合，采用的工藝庫為SMIC 130nm標(biāo)準(zhǔn)單元庫，在工藝電壓溫度（PVT）為ss/1.08V/125℃條件下，電路所能達(dá)到的最高時(shí)鐘頻率為133.3MHz，面積為36kGE（等效門）。為了衡量FFT對數(shù)據(jù)處理的能力，引入FFT吞吐量特性指標(biāo)。本設(shè)計(jì)FFT進(jìn)行一次完整運(yùn)算共有數(shù)據(jù)輸入、蝶形計(jì)算、輸出三個(gè)階段，由于數(shù)據(jù)輸入和結(jié)果輸出時(shí)分別對應(yīng)一組RAM，所以可以并行執(zhí)行。1024點(diǎn)數(shù)據(jù)輸入所需時(shí)鐘周期為1024，運(yùn)算階段共需1340個(gè)時(shí)鐘周期，總計(jì)時(shí)鐘數(shù)為2360。輸入輸出數(shù)據(jù)位寬為13位。根據(jù)吞吐量計(jì)算得到本設(shè)計(jì)FFT最大吞吐量為1.50Gbps，為時(shí)鐘速率的11倍。

表2顯示了本設(shè)計(jì)與其它FFT處理器的部分指標(biāo)對比，杜兆勝的基于FPGA的FFT處理器設(shè)計(jì)與實(shí)現(xiàn)一文實(shí)現(xiàn)了一種2蝶流水線型基4的FFT，可以看出本設(shè)計(jì)在FFT點(diǎn)數(shù)相同、接口位寬近似的情況下，吞吐量下降了28%但是面積降低了77%且輸出信噪比提高了29%。

表2 關(guān)鍵指標(biāo)

本文介紹了按時(shí)間抽取的基4 FFT算法，在傳統(tǒng)實(shí)現(xiàn)結(jié)構(gòu)的基礎(chǔ)上，研究了一種基于遞歸結(jié)構(gòu)的高精度FFT設(shè)計(jì)。采用雙RAM的遞歸結(jié)構(gòu)使蝶形單元的利用率達(dá)到最大、保證較低的硬件開銷，同時(shí)配合靈活的地址尋址方式來降低系統(tǒng)的復(fù)雜性。針對定點(diǎn)算法精度低的問題，提出一種新穎的實(shí)現(xiàn)結(jié)構(gòu)，只需增加少量的移位邏輯，即可有效地提高了運(yùn)算精度。通過分析仿真結(jié)果得到信噪比為64.4dB，相比與其他已經(jīng)存在方案，有較好的精度表現(xiàn)。最后，在SIMC 130nm工藝下得到ASIC結(jié)果，面積僅為36.34kGE，顯示了本設(shè)計(jì)硬件開銷小的優(yōu)點(diǎn)。