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

沈耀坡， 梁 煜， 張 為

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

快速傅里葉變換(Fast Fourier Transform，F(xiàn)FT)作為時域數(shù)據(jù)變換為頻域數(shù)據(jù)進(jìn)行分析的快速方法，廣泛應(yīng)用于雷達(dá)和數(shù)字通信等多種領(lǐng)域中，成為信號處理的一種高效手段．隨著無線電技術(shù)的高速發(fā)展，為了能夠?qū)崟r快速測量和分析信號的變化，需要FFT處理速度更快[1]．由于FFT計算量較大，為了滿足實時處理的需要，必須采用硬件電路實現(xiàn)以提升計算速度．因此設(shè)計高效的快速傅里葉變換的硬件結(jié)構(gòu)具有重要意義．

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

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

1 基22SDF結(jié)構(gòu)FFT原理分析

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

1.1 基22FFT算法的基本原理

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

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

式(2)為基22算法的蝶形單元運(yùn)算表達(dá)式，由此可以得到基22算法的蝶形結(jié)構(gòu)如圖1所示．

圖1 基22算法的蝶形結(jié)構(gòu)圖2 16點(diǎn)基22SDF FFT的結(jié)構(gòu)圖

1.2 基22SDF結(jié)構(gòu)FFT結(jié)構(gòu)

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

2 新型常數(shù)乘法器

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

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

圖3 復(fù)數(shù)乘法器架構(gòu)圖

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

表1 16點(diǎn)FFT的旋轉(zhuǎn)因子系數(shù)

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

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

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

表2 旋轉(zhuǎn)因子擴(kuò)大后的系數(shù)值

表2為3個旋轉(zhuǎn)因子系數(shù)小數(shù)點(diǎn)右移6位和舍入操作后的系數(shù)值．

通過表2中移位和舍入系數(shù)的分解，可以得到3個相應(yīng)的新型常數(shù)乘法器的電路結(jié)構(gòu)圖，如圖4所示．

圖4 3個新型常數(shù)乘法器的電路結(jié)構(gòu)圖圖5 新型復(fù)數(shù)乘法器

再根據(jù)圖3和表1，用這3個新型常數(shù)乘法器便可以組成相應(yīng)的復(fù)數(shù)乘法器，如圖5所示．

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

圖6 16點(diǎn)FFT在0.18μm工藝下的版圖

3 實驗結(jié)果對比分析

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

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

4 結(jié) 束 語

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

[1] 張亞洲, 張超, 王保銳, 等. 實時頻譜分析儀中并行FFT算法的FPGA設(shè)計[J]. 單片機(jī)與嵌入式系統(tǒng)應(yīng)用, 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實現(xiàn)技術(shù)研究[J]. 電子設(shè)計工程, 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ìn)調(diào)制解調(diào)器設(shè)計[J]. 計算機(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 點(diǎn)高性能FFT處理器的設(shè)計[J]. 微計算機(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.