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

沈耀坡， 梁 煜， 張 為

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

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

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

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

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

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

1.1 基22FFT算法的基本原理

FFT的實(shí)質(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個(gè)蝶形單元[10]，4個(gè)延遲反饋單元，旋轉(zhuǎn)因子存儲(chǔ)ROM，旋轉(zhuǎn)因子復(fù)數(shù)乘法器單元及計(jì)數(shù)器控制單元．SDF結(jié)構(gòu)中只有1條數(shù)據(jù)通路，蝶形運(yùn)算后的兩個(gè)結(jié)果其中一個(gè)會(huì)暫時(shí)保存在延遲反饋單元中，另一個(gè)會(huì)輸出到下一級(jí)．SDF結(jié)構(gòu)的優(yōu)勢就是可以高效地利用存儲(chǔ)器，減少硬件電路的復(fù)雜度．

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

復(fù)數(shù)乘法器是FFT中最重要的運(yùn)算單元之一，不僅占用最多的硬件資源，而且在一定程度上決定著FFT的計(jì)算速度，因此設(shè)計(jì)出一種高效的復(fù)數(shù)乘法器將對(duì)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個(gè)實(shí)數(shù)乘法器和兩個(gè)加法器．由于實(shí)數(shù)乘法器占用硬件資源較多，導(dǎo)致復(fù)數(shù)乘法器對(duì)硬件資源的消耗較大．而從式(3)中可以看出，旋轉(zhuǎn)因子系數(shù) cosα和 sinα可以提前計(jì)算出來存儲(chǔ)在ROM中供乘法計(jì)算使用．根據(jù)這個(gè)特點(diǎn)，可以將實(shí)數(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時(shí)，旋轉(zhuǎn)因子系數(shù)為1，此時(shí)輸入數(shù)據(jù)不需要經(jīng)過乘法器，直接送到下一級(jí)即可; 當(dāng)θ= π/2 時(shí)，旋轉(zhuǎn)因子系數(shù)為 -j，此時(shí)只要先將輸入數(shù)據(jù)的實(shí)部取反，再將實(shí)部和虛部互換輸出即可; 當(dāng)θ為其他角度時(shí)，此時(shí)旋轉(zhuǎn)因子系數(shù)有 ±0.923 9、±0.382 7 和 ±0.707 1，共6個(gè)，根據(jù)旋轉(zhuǎn)因子的對(duì)稱性[12]，只需要設(shè)計(jì)出 0.923 9、0.382 7 和 0.707 1 對(duì)應(yīng)的3個(gè)常數(shù)乘法器，就可以完成所有旋轉(zhuǎn)因子復(fù)數(shù)乘法操作．

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果對(duì)比分析

文中設(shè)計(jì)了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è)計(jì)的FFT在 0.18 μm 工藝下的版圖．通過計(jì)算和仿真報(bào)告分析可知，文中設(shè)計(jì)的FFT在 0.18 μm 工藝下的最大時(shí)鐘頻率可達(dá)到約 710 MHz，面積約為 0.12 mm2，功耗約為 3.30 mW．表3為文中設(shè)計(jì)的FFT分別在專用集成電路(Application Specific Integrated Circuit，ASIC)、Spanrtan-3、Virtex-4和Virtex-5中和現(xiàn)有其他構(gòu)架的電路性能與硬件開銷的比較，相比之下，文中設(shè)計(jì)大大減少了FPGA中的基本邏輯單元(Slices)和查找表(Look Up Tables，LUTs)單元的使用，并提升了硬件效率．

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

4 結(jié) 束 語

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

[1] 張亞洲, 張超, 王保銳, 等. 實(shí)時(shí)頻譜分析儀中并行FFT算法的FPGA設(shè)計(jì)[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實(shí)現(xiàn)技術(shù)研究[J]. 電子設(shè)計(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ìn)調(diào)制解調(diào)器設(shè)計(jì)[J]. 計(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]. 微計(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.