才 華, 陳廣秋, 劉廣文, 耿振野, 杜兆圣

(長(zhǎng)春理工大學(xué) 電子信息工程學(xué)院, 長(zhǎng)春 130022)

快速Fourier變換(FFT)作為一種有效計(jì)算離散Fourier變換(DFT)的方法, 在通信、 濾波及數(shù)字譜分析等領(lǐng)域應(yīng)用廣泛. 利用現(xiàn)場(chǎng)可編程門陣列(FPGA)可設(shè)計(jì)FFT處理器的硬件架構(gòu)[1].

隨著FFT算法的不斷完善, 在基-2FFT算法[2]的基礎(chǔ)上, 文獻(xiàn)[3-6]又提出了基-4、 基-8和基-16固定基以及分裂基等算法. 隨著基數(shù)r的增加, 算法分解級(jí)數(shù)逐漸減少, 所需運(yùn)算量(乘法和加法)也逐漸減少, 但其算法控制的復(fù)雜度增大. 由于可實(shí)現(xiàn)的點(diǎn)數(shù)受到限制, 因此需引進(jìn)混合基算法兼顧FFT的運(yùn)算量和復(fù)雜度[7].

常用的FFT處理器硬件結(jié)構(gòu)有4種[8]： 順序結(jié)構(gòu)、 流水線結(jié)構(gòu)、 并行結(jié)構(gòu)和陣列結(jié)構(gòu). 其中順序結(jié)構(gòu)運(yùn)算速度慢, 實(shí)時(shí)性差； 流水線結(jié)構(gòu)比順序結(jié)構(gòu)的運(yùn)算速度提高了logrN倍(其中：N為序列點(diǎn)數(shù)；r為基數(shù)), 所需的硬件資源有所增加； 陣列結(jié)構(gòu)的運(yùn)算速度最快, 但所需硬件資源和功耗也最大. 由于流水線結(jié)構(gòu)包含多個(gè)獨(dú)立的蝶形運(yùn)算單元, 每個(gè)單元負(fù)責(zé)一級(jí)蝶形運(yùn)算, 各級(jí)蝶形運(yùn)算單元間采用流水線方式進(jìn)行工作, 通過增減結(jié)構(gòu)中蝶形運(yùn)算單元可實(shí)現(xiàn)不同點(diǎn)數(shù)序列的FFT, 此外流水線結(jié)構(gòu)還具有芯片面積小、 功耗低以及高數(shù)據(jù)吞吐量等優(yōu)點(diǎn), 因此可采用流水線結(jié)構(gòu)處理硬件資源與處理速度間的關(guān)系.

正交頻分多址技術(shù)(OFDMA)是基于正交頻分復(fù)用技術(shù)(OFDM)的新一代無線接入技術(shù), 在IEEE802.16e物理層標(biāo)準(zhǔn)中, 不同帶寬的OFDMA系統(tǒng)采用的FFT點(diǎn)數(shù)不同, 如3 M帶寬采用256點(diǎn), 10 M帶寬采用1 024點(diǎn), 20 M帶寬采用2 048點(diǎn)等[9-10]. 本文利用FPGA硬件架構(gòu), 采用優(yōu)化的基-4/2混合基分解算法及流水線硬件結(jié)構(gòu)實(shí)現(xiàn)可變點(diǎn)FFT處理器的設(shè)計(jì), 并將其應(yīng)用于OFMDA系統(tǒng)中.

1 按頻率抽取基-2/4混合基算法原理

1.1 按頻率抽取基-2FFT算法原理

設(shè)序列點(diǎn)數(shù)N=2L(L為整數(shù)), 按頻率抽取(DIF)基-2FFT算法將輸入x(n)按n的順序分為前后兩部分, 將結(jié)果X(k)按k的奇偶進(jìn)行分組[11-12]. 其中

(1)

按k的奇偶性, 將X(k)劃分為

(2)

圖1 DIF基-2蝶形運(yùn)算單元Fig.1 Radix-2 DIF butterfly operation unit

由式(2)可得DIF基-2蝶形運(yùn)算單元, 如圖1所示.

1.2 按頻率抽取基-4FFT算法原理

(3)

對(duì)X(k)進(jìn)行分組

(4)

由式(4)可得DIF基-4蝶形運(yùn)算單元, 如圖2所示. 由圖2可見, 基-4比基-2蝶形運(yùn)算復(fù)雜, 結(jié)構(gòu)差別較大, 規(guī)律性較差, 不適合硬件實(shí)現(xiàn)混合基運(yùn)算, 因此需對(duì)上述算法進(jìn)行優(yōu)化. 將式(4)中的序列重新分組, 可得優(yōu)化的DIF基-4FFT算法為

(5)

由式(5)可得優(yōu)化后的DIF基-4蝶形計(jì)算單元, 如圖3所示.

圖2 傳統(tǒng)DIF基-4蝶形運(yùn)算單元Fig.2 Traditional radix-4 DIF butterfly operation unit

圖3 優(yōu)化后的DIF基-4蝶形運(yùn)算單元Fig.3 Optimized radix-4 DIF butterfly operation unit

通過計(jì)算可知, 優(yōu)化后的DIF基-4蝶形運(yùn)算比傳統(tǒng)的DIF基-4蝶形運(yùn)算可減少4個(gè)復(fù)數(shù)加法運(yùn)算, 其結(jié)構(gòu)與DIF基-2蝶形結(jié)構(gòu)相同, 信號(hào)流圖具有較強(qiáng)的規(guī)律性, 適合硬件實(shí)現(xiàn)混合基運(yùn)算. 圖4為優(yōu)化后N=16的DIF基-4FFT流圖.

圖4 優(yōu)化后的DIF基-4FFT流圖(N=16)Fig.4 Flow graph of optimized radix-4 DIF FFT (N=16)

由圖4可見, 優(yōu)化后DIF基-4FFT與DIF基-2FFT的各級(jí)流圖在結(jié)構(gòu)形式上一致, 僅旋轉(zhuǎn)因子不同.

2 混合基FFT算法原理

N點(diǎn)DFT的計(jì)算表達(dá)式為

(6)

其中N=r1r2…rL為復(fù)合數(shù), 按整數(shù)的多基多進(jìn)制表示形式, 式(6)中的n和k可分別表示為

(7)

其中:ni=0,1,…,rL-i-1;ki=0,1,…,ri+1-1,i=0,1,…,L-1. 將式(7)中n和k的值代入式(6)可得

(8)

由式(8)可知, 當(dāng)滿足r1=r2=…=rL-1=rc時(shí), 可將N點(diǎn)DFT分解為(L-1)個(gè)基-rcFFT及一個(gè)基-rLFFT級(jí)聯(lián)的形式, 從而縮短完成DFT運(yùn)算所需時(shí)間, 并解決基-rcFFT算法無法實(shí)現(xiàn)rc非整數(shù)次冪DFT算法的問題, 因此本文提出的可變點(diǎn)FFT算法可將DIF基-4和基-2進(jìn)行級(jí)聯(lián)計(jì)算, 且優(yōu)化后的DIF基-4與基-2算法具有相同蝶形單元結(jié)構(gòu), 更適合硬件實(shí)現(xiàn)混合基運(yùn)算[13-14].

3 可變點(diǎn)FFT處理器的硬件架構(gòu)設(shè)計(jì)及仿真和驗(yàn)證

3.1 FFT處理器流水線結(jié)構(gòu)

基-2或基-4FFT處理器主要有4種流水線結(jié)構(gòu)[15-16], 分別為基-2多路延時(shí)轉(zhuǎn)換(R2MDC)結(jié)構(gòu)、 基-2單路延時(shí)反饋(R2SDF)結(jié)構(gòu)、 基-4單路延時(shí)反饋(R4SDF)結(jié)構(gòu)與基4多路延時(shí)轉(zhuǎn)換(R4MDC)結(jié)構(gòu). R2SDF和R4SDF比R2MDC和R4MDC能更有效利用存儲(chǔ)器, R4SDF比R2SDF能更有效利用乘法器, 但R2SDF比R4SDF具有更簡(jiǎn)單的蝶形結(jié)構(gòu)及更低的控制復(fù)雜度. 在混合基算法中, 基-2FFT流水線結(jié)構(gòu)采用R2SDF結(jié)構(gòu), 優(yōu)化后的基-4FFT流水線結(jié)構(gòu)采用改進(jìn)的R2SDF結(jié)構(gòu), 稱為基-22單路延時(shí)反饋(R22SDF)結(jié)構(gòu). 以16點(diǎn)FFT為例, R2SDF結(jié)構(gòu)如圖5所示.

圖5 R2SDF結(jié)構(gòu)(N=16)Fig.5 Structure of R2SDF (N=16)

首先將輸入數(shù)據(jù)分成上下兩部分, 上半部分?jǐn)?shù)據(jù)串行輸入第一級(jí)延時(shí)緩存器中, 下半部分第一個(gè)數(shù)據(jù)與緩存單元中的第一個(gè)數(shù)據(jù)送入第一級(jí)基-2蝶形單元(數(shù)據(jù)點(diǎn)間距為N/2)進(jìn)行運(yùn)算, 將二者之和送到下一級(jí)運(yùn)算單元, 二者之差送到本級(jí)的延時(shí)緩存器中, 覆蓋第一個(gè)數(shù)據(jù), 對(duì)所有數(shù)據(jù)依次進(jìn)行上述處理, 可得第一級(jí)蝶形運(yùn)算的全部結(jié)果, 結(jié)果的上半部分依次送入下一級(jí)繼續(xù)計(jì)算, 下半部分依次存入本級(jí)的延時(shí)緩存單元； 對(duì)進(jìn)入第二級(jí)基-2蝶形運(yùn)算單元的數(shù)據(jù)也分為上下兩部分, 上半部分?jǐn)?shù)據(jù)串行輸入第二級(jí)延時(shí)緩存器中, 下半部分第一個(gè)數(shù)據(jù)與緩存單元中的第一個(gè)數(shù)據(jù)送入第二級(jí)基-2蝶形單元進(jìn)行運(yùn)算(數(shù)據(jù)點(diǎn)間距為N/4), 各級(jí)基-2蝶形運(yùn)算單元均采用相同的處理機(jī)制, 從而保證各級(jí)數(shù)據(jù)流的連續(xù)性, 最后得到計(jì)算結(jié)果.

由圖1和圖2可知, 優(yōu)化后的基-4蝶形單元與基-2蝶形單元具有相同結(jié)構(gòu), 僅在BF2Ⅰ階段需乘以一個(gè)-j, 對(duì)R2SDF結(jié)構(gòu)進(jìn)行改進(jìn)得到優(yōu)化后的基-4FFT流水線單路延時(shí)反饋結(jié)構(gòu), 其數(shù)據(jù)流的計(jì)算過程與R2SDF結(jié)構(gòu)相同, 如圖6所示.

圖6 R22SDF結(jié)構(gòu)(N=256)Fig.6 Structure of R22SDF (N=256)

在圖6的BF2Ⅰ單元中,t為控制輸出與-j相乘的時(shí)鐘, 可實(shí)現(xiàn)實(shí)部與虛部位置互換. 不同流水線結(jié)構(gòu)所需硬件資源及控制復(fù)雜性的比較列于表1. 由表1可見, R22SDF流水線結(jié)構(gòu)在乘法器和存儲(chǔ)器所需數(shù)量均最少, 因此本文采用R22SDF結(jié)構(gòu).

表1 不同流水線結(jié)構(gòu)所需硬件資源及控制復(fù)雜性的比較

3.2 可變點(diǎn)FFT處理器的硬件架構(gòu)設(shè)計(jì)

采用基-4/2混合基算法和流水線R22SDF結(jié)構(gòu)設(shè)計(jì)可變點(diǎn)FFT處理器的硬件架構(gòu), 如圖7所示. 由圖7可見, 可通過增減蝶形單元實(shí)現(xiàn)不同點(diǎn)數(shù)的FFT, 從而實(shí)現(xiàn)OFDMA系統(tǒng)的核心功能. 各級(jí)運(yùn)算模塊結(jié)構(gòu)類似, 均包括控制單元、 蝶形運(yùn)算數(shù)據(jù)存儲(chǔ)單元、 旋轉(zhuǎn)因子存儲(chǔ)單元、 復(fù)數(shù)乘法運(yùn)算單元和蝶形運(yùn)算單元五部分. 其中蝶形運(yùn)算單元為核心部分, 該單元完成BF2,BF2Ⅰ和BF2Ⅱ的復(fù)數(shù)加法運(yùn)算, 其運(yùn)算單元結(jié)構(gòu)如圖8所示.

3.3 功能仿真驗(yàn)證

采用Matlab軟件產(chǎn)生一個(gè)64=43點(diǎn)的序列, 作為仿真軟件Modelsim和FFT處理器的輸入, Modelsim仿真結(jié)果如圖9(A)所示, 通過Quartus中的Signaltap邏輯分析儀采樣得到FFT處理器運(yùn)行結(jié)果, 如圖9(B)所示. 由圖9可見, (A)和(B)的結(jié)果一致, 表明設(shè)計(jì)的FFT處理器各功能模塊及整個(gè)系統(tǒng)滿足設(shè)計(jì)要求, 功能與時(shí)序正確.

圖7 可變點(diǎn)FFT處理器的硬件架構(gòu)Fig.7 Hardware architecture of variable points FFT processor

圖8 BF2Ⅰ(A)和BF2/BF2Ⅱ(B)的運(yùn)算單元結(jié)構(gòu)Fig.8 Operation unit structure of BF2Ⅰ (A) and BF2/BF2Ⅱ (B)

圖9 Modelsim仿真結(jié)果(A)與FFT處理器運(yùn)行結(jié)果(B)Fig.9 Simulation results of modelsim (A) and operation results of FFT processor (B)

3.4 信號(hào)仿真驗(yàn)證

利用Matlab軟件對(duì)正弦波和鋸齒波進(jìn)行采樣, 得到輸入序列, 將FFT處理器運(yùn)算結(jié)果通過Matlab做ifft和生成頻譜, 并與Matlab中fft( )函數(shù)產(chǎn)生的頻譜進(jìn)行比較.

3.4.1 正弦波信號(hào)仿真 利用Matlab函數(shù)產(chǎn)生一組1 024=45點(diǎn)正弦波序列點(diǎn), 信號(hào)的采樣頻率為500 Hz, 為顯示方便, 幅值放大104倍.

x(t)=sin(2π×10×t).

(10)

通過Matlab中fft( )函數(shù)產(chǎn)生的頻譜和FFT處理器運(yùn)行結(jié)果如圖10所示. 由圖10可見, FFT處理器輸出的結(jié)果通過函數(shù)ifft( )得到的時(shí)域信號(hào)與輸入正弦波信號(hào)相同, 輸出的頻譜與Matlab所得頻譜一致, 時(shí)域誤差與頻域誤差極小.

(A) 正弦信號(hào)時(shí)域信號(hào)(N=1 024); (B) 利用IFFT得到的時(shí)域信號(hào); (C) 時(shí)域信號(hào)誤差;(D) Matlab FFT運(yùn)算結(jié)果; (E) 本文FFT運(yùn)算結(jié)果; (F) 頻域信號(hào)誤差.圖10 1 024點(diǎn)正弦波運(yùn)算結(jié)果Fig.10 Operation results for 1 024 points sine wave

3.4.2 鋸齒波信號(hào)仿真與驗(yàn)證 利用Matlab軟件產(chǎn)生一組2 048=2×45點(diǎn)鋸齒波序列點(diǎn), 作為輸入信號(hào), 信號(hào)的采樣頻率為50 Hz, 為顯示方便, 幅值放大104倍, 通過Matlab中fft( )函數(shù)產(chǎn)生的頻譜和FFT處理器運(yùn)行結(jié)果如圖11所示. 由圖11可見, FFT處理器輸出的結(jié)果通過函數(shù)ifft( )得到的時(shí)域信號(hào)與輸入三角波信號(hào)相同, 輸出的頻譜數(shù)據(jù)與Matlab所得頻譜一致, 時(shí)域誤差與頻域誤差較小.

(A) 鋸齒波信號(hào)時(shí)域信號(hào)(N=2 048); (B) 通過IFFT得到的時(shí)域信號(hào); (C) 時(shí)域信號(hào)誤差;(D) Matlab FFT運(yùn)算結(jié)果; (E) 本文FFT運(yùn)算結(jié)果; (F) 頻域信號(hào)誤差.圖11 2 048點(diǎn)鋸齒波信號(hào)運(yùn)算結(jié)果Fig.11 Operation results for 2 048 points sawtooth wave

綜上, 本文設(shè)計(jì)了一種基于FPGA的可變點(diǎn)FFT處理器, 采用DIF基-4/2混合基算法, 通過優(yōu)化使得基-4算法流圖中具有基-2蝶形結(jié)構(gòu), 有效減少了蝶形迭代的次數(shù), 降低了運(yùn)算的復(fù)雜度, 采用流水線R22SDF結(jié)構(gòu), 可減少所需存儲(chǔ)器和乘法器的數(shù)量, 提高各級(jí)間的運(yùn)算速度, 每級(jí)蝶形運(yùn)算可在部分?jǐn)?shù)據(jù)完成計(jì)算和存儲(chǔ)后即開始新一級(jí)運(yùn)算, 實(shí)現(xiàn)多級(jí)運(yùn)算交叉進(jìn)行, 進(jìn)一步提高了FFT運(yùn)算速度, 降低控制難度. 最后通過實(shí)驗(yàn)對(duì)FFT處理器進(jìn)行功能和信號(hào)的仿真驗(yàn)證, 實(shí)驗(yàn)結(jié)果表明, FFT處理器的有效性和執(zhí)行效率均滿足OFDMA系統(tǒng)應(yīng)用的需求.

[1] CHEN Jiyang, LEI Yuanwu, PENG Yuanxi, et al. Configurable Floating-Point FFT Accelerator on FPGA Based Multiple-Rotation CORDIC [J]. Chinese Journal of Electronics, 2016, 25(6): 1063-1070.

[2] 劉寶軍, 王中訓(xùn), 鐘強(qiáng), 等. 基于FPGA的FFT算法設(shè)計(jì)與實(shí)現(xiàn) [J]. 光電技術(shù)應(yīng)用, 2016, 31(3): 46-49. (LIU Baojun, WANG Zhongxun, ZHONG Qiang, et al. Design and Implementation of FFT Algorithm Based on FPGA [J]. Electro-Optic Technology Application, 2016, 31(3): 46-49.)

[3] Prabhu E, Mangalam H, Karthick S. Design of Area and Power Efficient Radix-4 DIT FFT Butterfly Unit Using Floating Point Fused Arithmetic [J]. Journal of Central South University, 2016, 23(7): 1669-1681.

[4] 樊恩辰, 姚馨, 何書專, 等. 基于SystemC的可配置FFT周期精確模型 [J]. 微電子學(xué)與計(jì)算機(jī), 2014, 31(11): 83-87. (FAN Enchen, YAO Xin, HE Shuzhuan, et al. Cycle-Accurate Configurable FFT Modeling with System C [J]. Microelectronics & Computer, 2014, 31(11): 83-87.)

[5] Huang S J, Chen S G. A High-Throughput Radix-16 FFT Processor with Parallel and Normal Input/Output Ordering for IEEE 802.15.3c Systems [J]. IEEE Transactions on Circuits & Systems Ⅰ: Regular Papers, 2012, 59(8): 1752-1765.

[6] Joshi S P, Paily R. Distributed Arithmetic Based Split-Radix FFT [J]. Journal of Signal Processing Systems, 2014, 75(1): 85-92.

[7] Kim E J, Lee J H, Sunwoo M H. Novel Shared Multiplier Scheduling Scheme for Area-Efficient FFT/IFFT Processors [J]. IEEE Transactions on Very Large Scale Integration Systems, 2015, 23(9): 1689-1699.

[8] 王英喆, 杜蓉. 基于FPGA流水線結(jié)構(gòu)并行FFT的設(shè)計(jì)與實(shí)現(xiàn) [J]. 電子設(shè)計(jì)工程, 2015, 23(4): 47-50. (WANG Yingzhe, DU Rong. A Pipelining Architecture Design of Parallel FFT Based on FPGA [J]. Electronic Design Engineering, 2015, 23(4): 47-50.)

[9] Harikrishna K, Rama R T, Labay V A. FPGA Implementation of FFT Algorithm for IEEE 802.16e (Mobile WiMAX) [J]. International Journal of Computer Theory and Engineering, 2011, 3(2): 197-203.

[10] Yang K J, Tsai S H, Chuang G C H. MDC FFT/IFFT Processor with Variable Length for MIMO-OFDM Systems [J]. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(4): 720-731.

[11] 許朋, 周立青, 劉宇航, 等. 基于FPGA的高性能浮點(diǎn)型FFT處理器設(shè)計(jì) [J]. 武漢大學(xué)學(xué)報(bào)(工學(xué)版), 2015, 48(1): 120-124. (XU Peng, ZHOU Liqing, LIU Yuhang, et al. Design of a High-Performance Floating-Point Fast Fourier Transform Processor Based on FPGA [J]. Engineering Journal of Wuhan University, 2015, 48(1): 120-124.)

[12] 蘇斌, 劉暢, 潘志剛. 基于FPGA的高速浮點(diǎn)FFT/IFFT處理器設(shè)計(jì)與實(shí)現(xiàn) [J]. 中國(guó)科學(xué)院大學(xué)學(xué)報(bào), 2015, 32(2): 259-263. (SU Bin, LIU Chang, PAN Zhigang. Design and Implementation of High-Speed Floating Points FFT Processor Based on FPGA [J]. Journal of University of Chinese Academy of Sciences, 2015, 32(2): 259-263.)

[13] 周景龍. 基于高速FFT結(jié)構(gòu)的頻域抗干擾算法的FPGA實(shí)現(xiàn) [J]. 微電子學(xué)與計(jì)算機(jī), 2014, 31(5): 32-35. (ZHOU Jinglong. An FPGA Implementation of Frequency-Domain Anti-jamming Algorithm Based on a Structure of High-Speed FFT [J]. Microelectronics & Computer, 2014, 31(5): 32-35.)

[14] Lakshmi D V V, Satya N C, Anil K R. Butterfly Design for RADIX-4K DIF FFT [J]. International Journal of Research in Computer and Communication Technology, 2014, 3(10): 1348-1353.

[15] WANG Zeke, LIU Xue, HE Bingsheng, 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.

[16] 王天. 基于混合基算法的快速傅立葉變換和反變換在VDSL2中的應(yīng)用與實(shí)現(xiàn) [D]. 西安： 西安電子科技大學(xué), 2009. (WANG Tian. Application and Implementation of FFT/IFFT Based on Mixed Radix in VDSL2 System [D]. Xi’an: Xidian University, 2009.)