費 超，盧 浩，陳杰男，胡劍浩

（電子科技大學(xué) 通信抗干擾技術(shù)國家級重點實驗室，四川 成都 611731）

面向LTE的超低復(fù)雜度FFT處理單元設(shè)計

費 超，盧 浩，陳杰男，胡劍浩

（電子科技大學(xué) 通信抗干擾技術(shù)國家級重點實驗室，四川 成都 611731）

該文提出了一種超低復(fù)雜度的、面向長期演進(jìn)（LTE）上行的快速傅里葉變換（FFT）混合基處理單元的設(shè)計與實現(xiàn)。由Cooley－Tukey算法與質(zhì)因數(shù)算法，LTE上行所需FFT可以分解到基2，3，5上。該文基于Winograd傅里葉變換設(shè)計了FFT處理單元，利用折疊技術(shù)對多模下FFT進(jìn)行了算法單元復(fù)用，利用正則符號數(shù)（CSD）乘法結(jié)合樹形結(jié)構(gòu)與Horner法則優(yōu)化其中的乘法器結(jié)構(gòu)。相比已有方法，關(guān)鍵路徑時間降低16.7，乘法器面積降低78.9，總面積降低62.1。

快速傅里葉變換；長期演進(jìn)計劃；Winograd傅里葉變換；正則有符號數(shù)；

長期演進(jìn)（LTE）上行通信系統(tǒng)［1］需要35種不同長度的離散傅里葉變換（DFT），其長度可以被表達(dá)［2］為：

式中，α，β，γ為整數(shù)。

由于采用了非基于2的FFT的模式，因此傳統(tǒng)基于2點的FFT優(yōu)化算法不能直接應(yīng)用到LTE的上行電路中。

在未來的通信中，對硬件復(fù)雜度和能耗都提出了很高的要求，特別是在面向綠色通信的系統(tǒng)設(shè)計中，減少硬件復(fù)雜度是很重要的一個需求。

為減少FFT的計算復(fù)雜度與硬件復(fù)雜度，Cooley－Tukey（CTA）算法［3］通過數(shù)學(xué)分解使長度為NP點的FFT計算量大幅降低，同時N為2的電路實現(xiàn)已經(jīng)被廣泛研究過［4－6］；當(dāng)FFT長度可以被質(zhì)因數(shù)分解時，質(zhì)因數(shù)算法（PFA）［7］可以比CTA算法計算量更少。WFTA算法［6］通過對旋轉(zhuǎn)因子矩陣分解進(jìn)一步降低硬件消耗，文獻(xiàn)［9－10］中提出了基于WFTA算法的長度可變，效率提升的電路實現(xiàn)方法。這些設(shè)計與算法都試圖減少乘法器個數(shù)等方式減少硬件消耗。

由此，可以根據(jù)CTA與PTA算法，將LTE所需FFT逐步分解到2，3，5點上，然后再由小點數(shù)2，3，5的WFTA算法來進(jìn)行FFT實現(xiàn)。因此可以先分解然后計算，并利用復(fù)用技術(shù)，將混合基下的多種FFT模式進(jìn)行計算單元的復(fù)用。本文基于WFTA算法設(shè)計了基2，3，5復(fù)用的FFT電路，針對資源消耗較大的乘法器部分，利用正則有符號數(shù)［11］表示方法，結(jié)合樹形方法與Horner法則［12］進(jìn)行優(yōu)化。相比目前FFT處理單元設(shè)計，在FPGA上，乘法器的查找表資源消耗（LUTs）降低了84.2，總消耗降低了70.9；在硬件邏輯面積開銷上，乘法器面積減少了78.9，總面積消耗減少了62.1，同時處理的關(guān)鍵路徑時間減少了16.7。

1 FFT分解與WFTA算法

1.1 FFT長度較大時的分解

N點的離散傅里葉變換（DFT）與旋轉(zhuǎn)因子表達(dá)式為：

式中，k∈［0，N－1］，其矩陣形式為X＝W x。文獻(xiàn)［10］給出一種對N＝N1N2分解算法：

一維角標(biāo)（n，k）被映射為（n1，n2）和（k1，k2），將［0，N－1］映射成［0，N1－1］×［0，N2－1］。

N1，N2互質(zhì)由PFA算法將DFT公式改寫為：

這樣可以先做N1點的FFT：

N1，N2不滿足互質(zhì)條件時由CTA算法將DFT原式可改寫為：

這樣將計算過程轉(zhuǎn)化為先計算N1點的FFT y［k1，n2］，經(jīng)過旋轉(zhuǎn)因子乘法后再進(jìn)行N2點FFT計算來得到結(jié)果。

這樣，利用PFA算法和CTA算法可以將LTE中較大的FFT逐步分解，到2點、3點和5點的FFT上。

1.2 較小長度時的WFTA算法實現(xiàn)

當(dāng)點數(shù)較小時，WFTA算法針對FFT的旋轉(zhuǎn)因子矩陣進(jìn)行分解：

式中，S矩陣和T矩陣的元素只有0和正負(fù)1，C矩陣是對角矩陣，只有在與C作計算時候會涉及乘法。文獻(xiàn)［8］中給出了具體數(shù)學(xué)推理過程與分解結(jié)果。

2 設(shè)計與實現(xiàn)

2.1 電路及復(fù)用設(shè)計

依據(jù)WFTA算法，混合2點、3點和5點硬件分時復(fù)用的FFT設(shè)計如圖1所示。首先設(shè)計5點的處理電路，電路中先進(jìn)行T51到T57預(yù)加法，再分別點乘旋轉(zhuǎn)因子，再經(jīng)過后級加法。然后進(jìn)行硬件復(fù)用，3點時預(yù)加法T31與T51復(fù)用，T32與T52復(fù)用；乘法M32與M52，M33和M53復(fù)用；后級加法X32與S52，X33與S54復(fù)用。2點FFT時，X21由M51計算得出，同時由M52和S54來計算X22。

圖1 2點、3點和5點復(fù)用FFT處理單元設(shè)計

2.2 基于CSD表示的乘法器優(yōu)化

考慮乘法器都是常系數(shù)乘法器，可以進(jìn)一步優(yōu)化從而縮短處理時延和減少硬件開銷。

1）正則符號數(shù)（CSD）運算

數(shù)字的CSD表示中含有的非零位是所有表示法中最少的，利用CSD數(shù)表示結(jié)合移位相加可以實現(xiàn)常數(shù)乘法而且加法數(shù)量最少。

由文獻(xiàn)［11］的迭代算法將各乘法器系數(shù)轉(zhuǎn)換為CSD數(shù)，結(jié)果如表1所示。C51與C31在二進(jìn)制上較為簡單沒有給出，C54系數(shù)超過了CSD的表示范圍，所以改寫成十進(jìn)制的－1加上CSD表示的－0.538 8。通過CSD表示方式，原本有48個非零位被轉(zhuǎn)換成了27個非零位。按照給出的算法循環(huán)可得到各個乘法器系數(shù)的CSD表示，如表1所示。

表1 乘法器系數(shù)的CSD表示

2）利用Horner法則與減少計算樹高

因為采用的計算方式為固定字長，在計算過程中部分和與部分積將被截斷，這會帶來截斷誤差。為實現(xiàn)計算精度，速度與硬件開銷的相互折中，首先，應(yīng)該盡量推遲同一括號內(nèi)的公共縮放運算［12］以減少截斷誤差。其次，同時計算多個加法時候，將順序的加法排列成樹形結(jié)構(gòu)并盡量降低樹高。最后，為避免溢出，可以再額外縮放一位。再經(jīng)過上述優(yōu)化，可以得到各個系數(shù)的計算方法：

3 算法性能與硬件消耗

3.1 定點化信噪比

FFT的算法仿真定點化信噪比將由下式?jīng)Q定：

式中，Sfloat指浮點信號值，取平方后表示信號功率，Sfix表示定點信號值。frame表示計算的幀數(shù)。式［8］是將浮點輸出信號的功率求和比上定點化與浮點之間的功率差，然后按功率取對數(shù)得出。

對于5點FFT，100 000組隨機(jī)輸入后其定點化信噪比大約為73.514 dB，3點FFT為73.919 dB，2點因為不涉及乘法，信號精度保持不變所以沒有給出。

3.2 設(shè)計硬件消耗

信號位寬18位，設(shè)計環(huán)境為XILINX ISE，驗證的FPGA為Virtex7，門級電路仿真在Synopsys Design Compiler中進(jìn)行。最終各器件消耗的查找表（LUTs）、硬件面積消耗和關(guān)鍵路徑時間結(jié)果如表2和表3所示。

表2 各乘法器資源消耗與關(guān)鍵路徑

因電路需要按IQ兩路展開處理，表中每個乘法器需要2個，18位選通器共需要8個，18位加法器共需34個。關(guān)鍵路徑時間單位為納秒（ns）。邏輯面積單位為平方微米（μm2）。

表3 加法與選通器資源消耗

由表2與表3的仿真結(jié)果可以看出，在FPGA上，處理單元中18 bit乘法器的LUT消耗為576，選通器共占72個LUT資源，加法器消耗的LUT為612。

在消耗的硬件面積上，常數(shù)乘法器面積消耗為16 546.22，選通器總面積為1 501.68，加法總面積為19 679.2。同時關(guān)鍵路徑的處理時間為7.72 ns。

3.3 硬件消耗比較

如今絕大部分LTE中FFT設(shè)計都直接使用18位的實數(shù)乘法器資源［4－6］，在FPGA中實現(xiàn)時其查找表LUTs資源對比如表4所示，其中Xilinx 18位實數(shù)乘法器資源為364LUTs，Altera為367LUTs。

表4 FPGA上資源消耗對比（以LUT計算）

可看出在FPGA上仿真時，LUT資源消耗大幅度減少，乘法器資源開銷減少至使用IPCORE的16左右，總資源開銷降至原來的30左右。而邏輯面積開銷與關(guān)鍵路徑時長如表5所示，對比的方法為在Synopsys Design Compiler下直接相乘。

表5 硬件資源對比

由表5可以看出乘法器的關(guān)鍵路徑得到減少，從而處理單元的關(guān)鍵路徑得到了減少，其次乘法器面積開銷縮減了78.9，總面積減少了62.08。

4 結(jié)束語

LTE系統(tǒng)中不同的35種長度的FFT可以由算法分解到基2，3，5上，本文首先介紹了LTE上行的FFT分解算法，然后基于WFTA算法利用折疊技術(shù)構(gòu)建了2點、3點和5點分時復(fù)用的電路，并針對硬件資源消耗較大的乘法器，利用CSD乘法，依據(jù)Horner法則與減少樹高的方式進(jìn)行優(yōu)化，相比較已有FFT處理單元設(shè)計，在FPGA上乘法器資源減少了84.2，總資源開銷減少至70.9；在處理單元邏輯面積開銷上，乘法器面積縮減了84.2，總面積降低了62.08，同時將處理關(guān)鍵路徑縮減了大約16.7。

［1］3GPP LTE.Evolved universal terrestrial radio access（EUTRA）；Physical Channels and Modulation［S］.2008.

［2］XILINX.Discrete Fourier transform V3.0 product specification［EB／OL］.［2008－06－27］.http：／／www. xilinx.com.

［3］COOLEY JW，TUKEY J W.An algorithm for the machine calculation of complex Fourier series［J］.Mathematics of Computation，1965，19（90）：297－301.

［4］CHEN J，HU J，LI S.High throughput and hardware efficient FFT architecture for LTE application［C］／／Wireless Communications and Networking Conference（WCNC），2012：826－831.

［5］CHANG Y N.An efficient VLSI architecture for normal I／O order pipeline FFT design［J］.Circuits and Systems II：Express Briefs，2008，55（12）：1234－1238.

［6］PENG S Y，SHR K T，CHEN C M，et al.Energy－efficient 128～2048／1536－point FFT processor with resource block mapping for 3GPP－LTE system［C］／／International Conference on Green Circuits＆Systems.［S.l.］：［s.n.］，2010：14－17.

［7］GOOD I J.The interaction algorithm and practical Fourier analysis［J］.Journal of the Royal Statistical Society（Series B），1960，20（2）：361－372.

［8］SILVERMAN H F.An introduction to programming the Winograd Fourier transform algorithm（WFTA）［J］.IEEE Transactions on Acoustics Speech＆Signal Processing，1977（25）：152－165.

［9］CHEN J，HU J，LEE S，et al.Hardware efficient mixed radix－25／16／9 FFT for LTE systems［J］.IEEE Transactions on Very Large Scale Integration（VLSI）Systems，2015，23（2）：221－229.

［10］CHEN J，HU J.A variable length FFT module for LTE applications［C］／／IEEE International Conference on Communications Technology＆Applications.［S.l.］：IEEE press，2009：376－380.

［11］REITWIESNER GW.Binary arithmetic［J］.Advances in Computers，1960（1）：231－308.

［12］PARHI K K.VLSI digital signal processing systems：Design and implementation［M］.New York：John Wiley＆Sons Press，1999：372－374.

Low－Complexity Mixed－Radix FFT Design and Implementation for LTE－Oriented

FEI Chao，LU Hao，CHEN Jienan，HU Jianhao
（National Key Laboratory of Science and Technology on Communication，University Of Electronic Science And Technology Of China，Chengdu 611731，China）

In this paper，a low cost mixed－radix FFT processor is proposed based on the uplink of LTE standards.Firstly CTA and PFA are employed to factorize large length FFT to small mixed－radix FFTs.After that，WFTA is utilized to implement the mixed－radix FFTs with reusing technology.Finally，a CSD multiplier with Horner structure is employed to optimize the constant multiplier.Compared with existing methods，the proposed method has78.9hardware saving in multiplier and 62.1in total design，as well as16.7processing time reduction.

fast Fourier transform；long term revolution；WFTA；CSD；

TN929.5

A

10.3969／j.issn.1672－4550.2016.06.011

2015－04－20；修改日期：2016－11－21

國家自然科學(xué)基金（61371104）。

費超（1993－），男，碩士，主要從事通信專用集成電路方面的研究。