一種高性能快速傅里葉變換的硬件設計

沈耀坡， 梁 煜， 張 為

(天津大學 微電子學院，天津 300072)

快速傅里葉變換(Fast Fourier Transform，FFT)作為時域數據變換為頻域數據進行分析的快速方法，廣泛應用于雷達和數字通信等多種領域中，成為信號處理的一種高效手段．隨著無線電技術的高速發展，為了能夠實時快速測量和分析信號的變化，需要FFT處理速度更快[1]．由于FFT計算量較大，為了滿足實時處理的需要，必須采用硬件電路實現以提升計算速度．因此設計高效的快速傅里葉變換的硬件結構具有重要意義．

近年來，有眾多學者對FFT的硬件實現展開了大量研究．文獻[2]使用公式變換法將傳統復數乘法器中的4個實數乘法器減少為3個，減小了一定的硬件開銷，但乘法器關鍵路徑較長而導致FFT整體計算速度提升并不大; 文獻[3]使用數字信號處理(Digital Signal Processing，DSP)模塊實現復數乘法器單元，計算速度有一定提升，但硬件開銷仍然較大; 文獻[4]使用正則有符號數(Canonic Signed Digit，CSD)乘法器取代了傳統復數乘法器，同時也省去了只讀存儲器(Read Only Memory，ROM)存儲單元，雖然大大節省了硬件開銷，但是計算速度仍然不夠高，達不到實際應用要求; 文獻[5]提出了一種單路延時反饋(Single Delay Feedback，SDF)和單路延時轉換(Single Delay Conversion，SDC)相結合的流水線結構，可以時分復用乘法器和加法器，計算速度有很大的提升，但是硬件資源消耗較大．

目前研究多集中于FFT算法構架研究和復數乘法器結構優化方面，而文中利用了FFT旋轉因子乘法中一個乘數為常數的特點，提出用常數乘法器替代傳統復數乘法器的方法來實現旋轉因子相乘．另外，文中還提出一種新型常數乘法器設計方法即系數放大法，通過將旋轉因子常系數放大的方法使相應的常數乘法器所需要的加法器數量減少到最低，同時也縮短了關鍵路徑．對比現有其他構架，文中設計的16點SDF結構基22FFT大大減小了硬件資源消耗，提高了計算速度，使硬件效率大大提升．

1 基22SDF結構FFT原理分析

對于FFT算法的實現技術，按數據組合方式可以分為時域抽取和頻域抽取，按數據抽取方式可分為基2、基4、基22和基24算法等[6]．其中，基22算法與基4算法具有相同的乘法復雜度，且具有基2算法的蝶形結構，即將基4算法進一步分解成更小的多級基2運算，從而便于硬件實現[7]．在實際應用中，隨著對數字通信系統實時性要求的提高，已有多種硬件構架被提出．其中，流水線結構以其高實時性，較強的數據連續處理能力，較高的資源利用率等特性取得了廣泛的應用．流水線結構FFT有多種實現方案，最常用的可分為3類: 多路徑延時轉換結構、單路徑延時轉換結構和單路徑延時反饋結構[8]．文中重點研究基22頻域抽取算法與單路徑延遲反饋結構．

1.1 基22FFT算法的基本原理

FFT的實質是將較長序列的離散傅里葉變換(Discrete Fourier Transform，DFT)運算逐次分解為較短序列的DFT運算[9]．序列x(n)的DFT定義為

理論分析，式(1a)可以通過基22算法變換為

式(2)為基22算法的蝶形單元運算表達式，由此可以得到基22算法的蝶形結構如圖1所示．

圖1 基22算法的蝶形結構圖2 16點基22SDF FFT的結構圖

1.2 基22SDF結構FFT結構

圖2給出了16點基22SDF FFT的結構圖．共有4個蝶形單元[10]，4個延遲反饋單元，旋轉因子存儲ROM，旋轉因子復數乘法器單元及計數器控制單元．SDF結構中只有1條數據通路，蝶形運算后的兩個結果其中一個會暫時保存在延遲反饋單元中，另一個會輸出到下一級．SDF結構的優勢就是可以高效地利用存儲器，減少硬件電路的復雜度．

2 新型常數乘法器

復數乘法器是FFT中最重要的運算單元之一，不僅占用最多的硬件資源，而且在一定程度上決定著FFT的計算速度，因此設計出一種高效的復數乘法器將對FFT的整體性能有很大的影響．FFT中的旋轉因子復數乘法[11]可表示為

(xre+jxim)(cosα-j sinα)=(xrecosα+ximsinα)+j (ximcosα-xresinα) ．(3)

圖3 復數乘法器架構圖

復數乘法器架構圖如圖3所示．從圖3中可以看出，復數乘法器共需要4個實數乘法器和兩個加法器．由于實數乘法器占用硬件資源較多，導致復數乘法器對硬件資源的消耗較大．而從式(3)中可以看出，旋轉因子系數 cosα和 sinα可以提前計算出來存儲在ROM中供乘法計算使用．根據這個特點，可以將實數乘法器改為常數乘法器，常系數即為旋轉因子系數．16點FFT的所有旋轉因子系數如表1所示．

表1 16點FFT的旋轉因子系數

從表1中可以看出，當θ=0時，旋轉因子系數為1，此時輸入數據不需要經過乘法器，直接送到下一級即可; 當θ= π/2 時，旋轉因子系數為 -j，此時只要先將輸入數據的實部取反，再將實部和虛部互換輸出即可; 當θ為其他角度時，此時旋轉因子系數有 ±0.923 9、±0.382 7 和 ±0.707 1，共6個，根據旋轉因子的對稱性[12]，只需要設計出 0.923 9、0.382 7 和 0.707 1 對應的3個常數乘法器，就可以完成所有旋轉因子復數乘法操作．

文中提出了一種新型常數乘法器設計方法即系數放大法，可以進一步減小常數乘法器的硬件面積，縮短關鍵路徑，提升其性能．方法步驟如下：考慮到實現小數常數乘法器會使用較多數量的加法器，而整數常數乘法器可以減少加法器的使用量，所以先通過將小數點向右移位和舍入操作將小數擴大并近似為一個整數，此整數的特點是可以通過較少的移位相加操作便可以實現其對應的常數乘法器；最后，再通過向左移位的方式將其還原為原來的小數，便可以實現加法器數量最少的小數常數乘法器．

右移位數的選定是通過右移小數點和舍入操作將小數近似為一個整數，故必然會存在一定的誤差，而此誤差與小數點右移位數有關．當右移位數較小時，誤差較大; 當右移位較大時，誤差較小，但此時會消耗更多的資源．以 0.382 7 為例，當小數點右移2位時，擴大為 1.530 8，舍入近似為2，此時的誤差為 2/4- 0.382 7，即 0.117 3，誤差較大; 當小數點右移9位時，擴大為 195.942 4，舍入近似為196，此時的誤差為 196/ 512- 0.382 7，即 0.000 1，誤差較小，但是 196= 27+ 26+ 22+ 21，需要3個加法器，資源消耗較大; 當小數點右移6位時，擴大為 24.492 8，舍入近似為24，此時誤差為 24/ 64- 0.382 7，即 0.007 7，誤差較小，且 24= 24+ 23，只需要1個加法器．0.923 9 和 0.707 1 的計算過程與此過程類似．故在權衡了資源消耗和誤差的情況下，文中將移位操作選定為6位．

表2 旋轉因子擴大后的系數值

表2為3個旋轉因子系數小數點右移6位和舍入操作后的系數值．

通過表2中移位和舍入系數的分解，可以得到3個相應的新型常數乘法器的電路結構圖，如圖4所示．

圖4 3個新型常數乘法器的電路結構圖圖5 新型復數乘法器

再根據圖3和表1，用這3個新型常數乘法器便可以組成相應的復數乘法器，如圖5所示．

從圖5中可以看出，文中的0.923 9常數乘法器使用1個加法器，0.382 7 常數乘法器使用1個加法器，0.707 1 常數乘法器使用2個加法器，最后組成的新型復數乘法器共使用12個加法器; 而文獻[4]中，0.923 9 常數乘法器使用4個加法器，0.382 7 常數乘法器使用2個加法器，0.707 1 常數乘法器使用4個加法器，最后組成的CSD復數乘法器共使用24個加法器．故文中提出的新型復數乘法器比CSD復數乘法器的加法器數量少了一半，節省了大量的硬件資源; 另外，新型復數乘法器的關鍵路徑延約為兩個加法器，有效提高了FFT的系統性能．

圖6 16點FFT在0.18μm工藝下的版圖

3 實驗結果對比分析

文中設計了16點SDF基22FFT架構，將其用硬件描述語言Verilog HDL進行編碼，并用Modelism進行功能仿真，采用中芯國際集成電路制造(上海)公司(Semiconductor Manufacturing International Corporation，SMIC) 0.18 μm 工藝進行了綜合和布局布線．圖6為文中設計的FFT在 0.18 μm 工藝下的版圖．通過計算和仿真報告分析可知，文中設計的FFT在 0.18 μm 工藝下的最大時鐘頻率可達到約 710 MHz，面積約為 0.12 mm2，功耗約為 3.30 mW．表3為文中設計的FFT分別在專用集成電路(Application Specific Integrated Circuit，ASIC)、Spanrtan-3、Virtex-4和Virtex-5中和現有其他構架的電路性能與硬件開銷的比較，相比之下，文中設計大大減少了FPGA中的基本邏輯單元(Slices)和查找表(Look Up Tables，LUTs)單元的使用，并提升了硬件效率．

表3 電路性能和硬件開銷比較

4 結 束 語

文中設計了16點SDF基22FFT，使用常數乘法器代替了傳統復數乘法器，并且用系數放大法設計了一種新型的常數乘法器，將所需加法器數量減少到最低．文中設計的16點FFT在 0.18 μm 工藝下的最大時鐘頻率可達 710 MHz，面積約為 0.12 mm2; 另外，文中在Xilinx Virtex-4上實現了 16 bit 16點FFT，所需Slices數量減少8%，單位Slices吞吐率為1.273，對比其他構架，提高了約1倍; 在Xilinx Virtex-5上實現了 16 bit 16點FFT， 所需LUTs數量減少44%，單位LUTs吞吐率為0.978，對比其他構架，提高了約1倍．

[1] 張亞洲, 張超, 王保銳, 等. 實時頻譜分析儀中并行FFT算法的FPGA設計[J]. 單片機與嵌入式系統應用, 2016(5): 23-26.

ZHANG Yazhou, ZHANG Chao, WANG Baorui, et al. FPGA Design of Parallel FFT Algorithm in Real-time Spectrum Analyzer[J]. Microcontrollers & Embedded Systems, 2016(5): 23-26.

[2] ZHOU B, HWANG D. Implementations and Optimizations of Pipeline FFTs on Xilinx FPGAs[C]//Proceedings of the 2008 International Conference on Reconfigurable Computing and FPGAs. Piscataway: IEEE, 2008: 325-330.

[3] ZHOU B, PENG Y, HWANG D. Pipeline FFT Architectures Optimized for FPGAs[J]. International Journal of Reconfigurable Computing, 2009, 2009(5): 9.

[4] WANG H Y, WU J J, CHIU C W, et al. A Modified Pipeline FFT Architecture[C]//Proceedings of the 2010 International Conference on Electrical and Control Engineering. Piscataway: IEEE, 2010: 4611-4614.

[5] WANG Z, LIU X, HE B, et al. A Combined SDC-SDF Architecture for Normal I/O Pipelined Radix-2 FFT[J]. IEEE Transactions on Very Large Scale Integration Systems, 2015, 23(5): 973-977.

[6] 胡錦濤, 李路, 姚如貴, 等. 基于FPGA的面積有效FFT實現技術研究[J]. 電子設計工程, 2016, 24(8): 94-97.

HU Jintao, LI Lu, YAO Guru, et al. Research on the Effective Area FFT Implementation Based on FPGA[J]. Electronic Design Engineering, 2016, 24(8): 94-97.

[7] 吳金紅, 曹建, 趙巖. 基于FPGA的OFDM改進調制解調器設計[J]. 計算機測量與控制, 2010, 18(12): 2815-2817, 2835.

WU Jinhong, CAO Jian, ZHAO Yan. Design of OFDM Improved Modulator and Demodulator Based on FPGA[J]. Computer Measurement & Control, 2010, 18(12): 2815-2817, 2835.

[8] 鐘冠文, 盧亞偉, 付欣瑋, 等. 基于FPGA的 1 024 點高性能FFT處理器的設計[J]. 微計算機信息, 2012, 28(8): 66-67.

ZHONG Guanwen, LU Yawei, FU Xinwei, et al. Design of 1 024 Point FFT Processor Based on FPGA[J]. Microcomputer Information, 2012, 28(8): 66-67.

[9] HE S, TORKELSON M. New Approach to Pipeline FFT Processor[C]//Proceedings of the 1996 IEEE Symposium on Parallel and Distributed Processing. Piscataway: IEEE, 1996: 766-770.

[10] QURESHI I A, QURESHI F, SHAIKH G M. Efficient FPGA-mapping of 1 024 Point FFT Pipeline SDF Processor[C]//Proceedings of the 2014 International Symposium on Parallel Architectures, Algorithms and Programming. Piscataway: IEEE, 2014: 29-34.

[11] TANG A, YU L, HAN F, et al. CORDIC-based FFT Real-time Processing Design and FPGA Implementation[C]//Proceedings of the 2016 IEEE 12th International Colloquium on Signal Processing and Its Applications. Piscataway: IEEE, 2016: 233-236.

[12] TRAN T H, KANAGAWA S, NGUYEN D P, et al. ASIC Design of MUL-RED Radix-2 Pipeline FFT Circuit for 802. 11ah System[J]. IEEE Low-Power High-Speed Chips, 2016, 1(3): 9-11.