一種節(jié)省硬件資源的DFT實(shí)現(xiàn)算法研究

廖曉慧 彭永健 曹森

摘要：工程項(xiàng)目中DFT算法實(shí)現(xiàn)需使用大量FPGA資源。文章設(shè)計(jì)一種非2n點(diǎn)數(shù)的DFT算法，通過(guò)算法流程的改進(jìn)、旋轉(zhuǎn)因子的周期性，該算法可大量減少DFT的運(yùn)算量，并在FPGA芯片上予以實(shí)現(xiàn)。實(shí)驗(yàn)仿真表明該算法優(yōu)化了硬件資源，減少了存儲(chǔ)資源和DSP資源。文章算法解決了工程DFT應(yīng)用使用資源多的問(wèn)題。

關(guān)鍵詞：DFT；資源；FPGA

中圖分類(lèi)號(hào)：中圖分類(lèi)號(hào)? 文獻(xiàn)標(biāo)志碼：A文獻(xiàn)標(biāo)志碼

0 引言

FPGA處理DFT運(yùn)算，F(xiàn)PGA有內(nèi)置高速乘法和加法器，高速性能好，處理速度快。基2或基4FFT算法［1］，可計(jì)算得到時(shí)域序列長(zhǎng)度N=2nDFT運(yùn)算結(jié)果。N≠2n時(shí)，DFT直接進(jìn)行運(yùn)算，將使用大量乘法器，運(yùn)算量較大，占用FPGA資源較多。工程應(yīng)用，運(yùn)算量大，布局布線(xiàn)困難，同時(shí)增加系統(tǒng)成本和功耗［2］。

為減少DFT算法使用FPGA資源，降低布局布線(xiàn)難度，本文介紹一種節(jié)省硬件資源的DFT實(shí)現(xiàn)算法。該算法從DFT原理出發(fā)，在已知頻率的系統(tǒng)當(dāng)中進(jìn)行定點(diǎn)DFT運(yùn)算，通過(guò)算法流程的優(yōu)化，節(jié)省FPGA資源，解決工程DFT應(yīng)用使用資源多、不易實(shí)現(xiàn)的問(wèn)題。

1 DFT原理

X（k）=∑N-1n=0x（n）exp（-2πnk/N），k取0，1，2…N-1，x（n）為時(shí)域信號(hào)，X（k）為頻域信號(hào)［3］。exp（-2πnk/N）=cos（2πnk/N）+j×sin（2πnk/N） X（k）=∑N-1n=0x（n）cos（2πnk/N）+j×∑N-1n=0x（n）sin （2πnk/N），F(xiàn)PGA計(jì)算cos（2πnk/N）、sin（2πnk/N）會(huì)使用乘法器和邏輯資源［4］。k從0到N-1全部計(jì)算，將消耗大量的邏輯資源。本文算法通過(guò)已知k值，計(jì)算出頻域值，節(jié)省資源。

2 算法分析以及實(shí)現(xiàn)

從DFT原理分析可知，旋轉(zhuǎn)因子、并行處理都將使用大量處理資源。本文算法優(yōu)化旋轉(zhuǎn)因子模塊同時(shí)優(yōu)化算法流程解決處理資源問(wèn)題。

旋轉(zhuǎn)因子模塊設(shè)計(jì)。FPGA直接計(jì)算cos（2πnk/N）、sin（2πnk/N）消耗大量的資源，不易實(shí)現(xiàn)［5］。Matlab直接計(jì)算出旋轉(zhuǎn)因子的實(shí)部和虛部，然后乘以一個(gè)整數(shù)將浮點(diǎn)變化成為定點(diǎn)，將定點(diǎn)數(shù)以二進(jìn)制補(bǔ)碼形式存儲(chǔ)在FPGA內(nèi)部ROM中。定點(diǎn)數(shù)采用有符號(hào)位，在進(jìn)行加減運(yùn)算時(shí)不會(huì)溢出，其包含一位符號(hào)位、一位整數(shù)位、多個(gè)小數(shù)位，誤差的大小決定于表示小數(shù)的位數(shù)。硬件設(shè)計(jì)簡(jiǎn)單、易于控制。

n取值范圍0到N-1，k取值范圍0到N-1， nk最大值（N-1）×（N-1）。nk值從0到（N-1）×（N-1）全部存儲(chǔ)，控制電路簡(jiǎn)單但需要消耗大量的存儲(chǔ)資源。利用cos（2πnk/N）、sin（2πnk/N）的周期性，ROM當(dāng)中只存儲(chǔ)nk從0到N-1的值。用較小的控制資源，節(jié)省大量的存儲(chǔ)資源。

串行運(yùn)算設(shè)計(jì)。x（n）串行采樣數(shù)據(jù)輸入。并行計(jì)算X（k）值，需將x（n）先存儲(chǔ)，消耗大量存儲(chǔ)資源、同時(shí)消耗大量乘法器。以串行不斷累加的方式計(jì)算X（k）的值，不占用存儲(chǔ)資源存儲(chǔ)x（n）的值，同時(shí)復(fù)用乘法器，降低存儲(chǔ)資源，同時(shí)降低乘法器資源。

3 FPGA實(shí)現(xiàn)流程

旋轉(zhuǎn)因子實(shí)現(xiàn)流程。每個(gè)Clk更新n、nk。n累加1，從0到N-1。

如流程圖1所示：DFT數(shù)據(jù)初始化，輸入k，Qn、n賦初值0。具體步驟如下：

（1）k與Qn相加，累加得到Qn。

（2）利用旋轉(zhuǎn)因子周期性。比較Qn和N，若Qn大于N，則Qn=Qn-N；否則Qn=Qn。

（3）將Qn作為下一個(gè)Qn累加的輸入。

（4）同時(shí)將Qn作為存儲(chǔ)模塊地址的索引值，得到cos（2πnk/N）、sin（2πnk/N）。

（5）斷時(shí)域輸入序號(hào)n是否小于N-1。若n小于N-1，則繼續(xù)計(jì)算nk的值；若大于等于N-1，則Qn賦值為0。

Matlab根據(jù)DFT點(diǎn)數(shù)N，計(jì)算旋轉(zhuǎn)因子實(shí)部和虛部的值，存入FPGA的ROM中。Qn的計(jì)算值作為旋轉(zhuǎn)因子ROM的索引地址，索引得到旋轉(zhuǎn)因子的值。旋轉(zhuǎn)因子模塊接口如圖2所示。

如圖3所示，DFT算法實(shí)現(xiàn)流程如下：

（1）根據(jù)n，k的值生成旋轉(zhuǎn)因子索引地址。

（2）將索引地址輸入存儲(chǔ)旋轉(zhuǎn)因子ROM中，得到旋轉(zhuǎn)因子的值。

（3）將時(shí)域序列x（n）與旋轉(zhuǎn)因子相乘。

（4）將每一個(gè)相乘的值進(jìn)行累加，得到DFT的計(jì)算結(jié)果Xk。

4 仿真結(jié)果及算法實(shí)現(xiàn)

本文分析算法使用乘法器個(gè)數(shù)，驗(yàn)證算法有效性。若DFT點(diǎn)數(shù)為N，并行4路時(shí)域數(shù)據(jù)輸入，則DFT直接計(jì)算需要使用4N個(gè)乘法器。本文提出的DFT算法一路數(shù)據(jù)輸入時(shí)，實(shí)部和虛部各需要一個(gè)乘法器。4路并行數(shù)據(jù)輸入，本文提出的算法只需要8個(gè)乘法器，減少了硬件資源。兩種算法乘法器使用個(gè)數(shù)對(duì)比如表1所示。

為進(jìn)一步驗(yàn)證算法的有效性，在Xilinx公司的ISE軟件上進(jìn)行實(shí)際驗(yàn)證和調(diào)試。FPGA芯片是Virtex-5系列的XC6VLX240T。

整個(gè)系統(tǒng)算法仿真實(shí)現(xiàn)，DFT點(diǎn)數(shù)260，模塊編譯后進(jìn)行綜合，綜合報(bào)告如圖4所示。分析結(jié)果和用ISE軟件實(shí)現(xiàn)結(jié)果相符。

驗(yàn)證算法的正確性和可實(shí)現(xiàn)性，在Matlab、ModelSim中對(duì)算法進(jìn)行仿真，輸入不同時(shí)域正弦波信號(hào)x（n）進(jìn)行仿真。x（n）=cos（2πnf/fs），n=0，1…N-1。ModelSim進(jìn)行仿真，x（n）乘以256進(jìn)行量化，將浮點(diǎn)數(shù)轉(zhuǎn)化為定點(diǎn)數(shù)。

設(shè)置N=260，采樣率fs=520 MHz，f、k4組不同的變量，Matlab，ModelSim計(jì)算得到DFT的實(shí)部和虛部值。

圖5和圖6分別為f=12 MHz、k=6時(shí)Matlab計(jì)算DFT的結(jié)果，ModelSim仿真DFT的結(jié)果。FPGA當(dāng)中時(shí)鐘采樣率太高，時(shí)序不能滿(mǎn)足要求。為滿(mǎn)足時(shí)序要求，ModelSim輸入4路并行260MHz的AD數(shù)據(jù)，idata_ch0、idata_ch1、idata_ch2、idata_ch3。同時(shí)通過(guò)旋轉(zhuǎn)因子模塊得到4路AD數(shù)據(jù)對(duì)應(yīng)的旋轉(zhuǎn)因子的值。計(jì)算處理得到DFT的結(jié)果。

表2為4組不同的f、k變量通過(guò)Matlab和ModelSim計(jì)算得到的結(jié)果。

由仿真結(jié)果可知當(dāng)f=12、k=6時(shí)Matlab實(shí)部計(jì)算結(jié)果為33 267，ModelSim實(shí)部計(jì)算結(jié)果為33 266，? 虛部計(jì)算結(jié)果都為0，誤差3×10-5 。其他組的數(shù)據(jù)ModelSim仿真結(jié)果與Matlab計(jì)算結(jié)果相符，驗(yàn)證了算法的正確性。

5 結(jié)語(yǔ)

針對(duì)直接計(jì)算DFT使用FPGA存儲(chǔ)和DSP資源較多的問(wèn)題，本文提出一種簡(jiǎn)化的算法，能夠減少存儲(chǔ)和DSP資源，解決了工程應(yīng)用中的問(wèn)題。

參考文獻(xiàn)

［1］劉順杰.數(shù)字信號(hào)處理［M］.西安：西安電子科技大學(xué)出版社，2005.

［2］REDINBO G R.Tensor Product DFT Codes vs Standard DFT Codes［J］.IEEE Transactions on Computers，2019（11）：1678-1688.

［3］昌攀，鐘誠(chéng).通過(guò)DFT變換提取DNA序列特征聚類(lèi)物種［J］.小型微型計(jì)算機(jī)系統(tǒng)，2018（3）：463-467.

［4］RAO K R.Fast Fourier Transform：Algorithms And Applications［M］.北京：機(jī)械工業(yè)出版社，2010.

［5］HE Y Z，CUI G F，LI P X，et al.Timing Advanced Estimation Algorithm of Low Complexity Based on DFT Spectrum Analysis for Satellite System［J］.China Communications，2015（4）：140-150.

（編輯 王永超）

Research on a DFT implementation algorithm for saving hardware resources

Liao? Xiaohui， Peng? Yongjian， Cao? Sen

（The 29th Research Institute of China Electronics Technology Group Corporation， Chengdu 610036， China）

Abstract： The implementation of DFT algorithm in engineering projects uses a lot of FPGA resources. A non 2n points DFT implementation algorithm is designed， through the improvement of algorithm flow and periodicity of rotation factor， which can greatly reduce the computation of DFT and is implemented on FPGA chip. The simulation results show that the hardware resources can be optimized， and the storage resources and DSP resources are reduced. This algorithm solves the problem of using too many resources in engineering DFT applications.

Key words： DFT; resources; FPGA