一種高精度低開銷的FFT設計

北方工業大學信息學院 戴 瀾 皮義強

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

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

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

1 基4-FFT算法

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

其中，旋轉因子為：

當序列長度N滿足N=時，按時鐘抽取的DFT算法為：

進行變量替換后有：

由上式可知，每一組4點數據進入蝶形運算單元后先進行復數乘法，由于A所對應的旋轉因子不需要乘，故只有3次旋轉因子乘法，隨后進行兩級復數加法按同址輸出結果。

2 FFT的設計方案

2.1 FFT整體結構

如圖1所示，FFT整體結構包括7個部分：RAM地址生成單元，用于在各個階段生成讀寫兩組RAM的地址；旋轉因子地址生成單元，本設計中對RAM和ROM的訪問并不同址；蝶形運算單元；存放蝶形運算數據的兩組RAM，每組RAM由四塊容量為256的單口RAM構成；三塊存儲旋轉因子的ROM；控制單元，由控制運算階段跳轉的狀態機構成；多個移位模塊，其和定點運算的優化有關。一組1024個定點數據通端口串行輸入，經過移位處理后亂序存入A組RAM中，隨后在RAM地址生成單元和旋轉因子地址生成單元的控制下，從A組RAM和ROM中提取運算數據和旋轉因子放入蝶形單元中進行運算，將結果進行移位優化處理后寫入B組RAM中，繼續執行下一級蝶形運行，此時B組RAM成為數據源，A組RAM成為數據存儲目標，當五次蝶形運算結束后，結果存放于B組RAM中，將數據通過端口串行輸出。

圖1 FFT整體結構圖

2.2 定點算法優化

M級蝶形運算后都需要將數據暫存到RAM中，由于蝶形單元輸出結果的位寬和RAM位寬的差異導致必須進行數據截斷后才能存儲，從而造成數據精度降低。將數據存儲范圍最高位與數據最高有效位之間（不計入符號位，下同）的位差定義為移位因子，數據左移位后不會發生溢出。本設計提出的定點運算優化方案具體實現如圖2所示。

圖2 蝶形運算階段的移位機制

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

2.3 旋轉因子存儲優化

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

圖3 旋轉因子W p地址產生規律圖

2.4 地址產生模塊的設計

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

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

圖4 RAM地址生成示意圖

3 功能驗證與FPGA實現

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

使用Xilinx Artix7 XC7A200T進行原型機驗證，兩組RAM通過調用ISE中提供的IP來實現，經過ISE 14.7的綜合實現，資源報告如表1所示。

表1 FPGA資源報表

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

4 ASIC實現

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

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

表2 關鍵指標

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