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

費(fèi) 超，盧 浩，陳杰男，胡劍浩

（電子科技大學(xué) 通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，四川 成都 611731）

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

費(fèi) 超，盧 浩，陳杰男，胡劍浩

（電子科技大學(xué) 通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，四川 成都 611731）

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

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

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

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

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

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

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

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

1 FFT分解與WFTA算法

1.1 FFT長(zhǎng)度較大時(shí)的分解

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

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

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

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

這樣可以先做N1點(diǎn)的FFT：

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

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

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

1.2 較小長(zhǎng)度時(shí)的WFTA算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

1）正則符號(hào)數(shù)（CSD）運(yùn)算

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

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

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

2）利用Horner法則與減少計(jì)算樹(shù)高

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

3 算法性能與硬件消耗

3.1 定點(diǎn)化信噪比

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

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

對(duì)于5點(diǎn)FFT，100 000組隨機(jī)輸入后其定點(diǎn)化信噪比大約為73.514 dB，3點(diǎn)FFT為73.919 dB，2點(diǎn)因?yàn)椴簧婕俺朔ǎ盘?hào)精度保持不變所以沒(méi)有給出。

3.2 設(shè)計(jì)硬件消耗

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

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

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

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

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

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

3.3 硬件消耗比較

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

表4 FPGA上資源消耗對(duì)比（以L(fǎng)UT計(jì)算）

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

表5 硬件資源對(duì)比

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

4 結(jié)束語(yǔ)

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

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

費(fèi)超（1993－），男，碩士，主要從事通信專(zhuān)用集成電路方面的研究。