基于乘法器復(fù)用技術(shù)的FFT處理器的設(shè)計(jì)實(shí)現(xiàn)分析

-.z基于乘法器復(fù)用技術(shù)的FFT處理器的設(shè)計(jì)與實(shí)現(xiàn)龍**，耿雙利，*曉昆，李彩霞摘要：提出了一種基于乘法器復(fù)用技術(shù)的FFT優(yōu)化算法，該算法主要利用了旋轉(zhuǎn)因子關(guān)于y軸和y=*的對(duì)稱(chēng)性，使用兩個(gè)實(shí)數(shù)乘法器即可分時(shí)共享完成4個(gè)復(fù)數(shù)旋轉(zhuǎn)因子的計(jì)算，從而減少硬件資源消耗；采用該算法采用流水線構(gòu)造，設(shè)計(jì)了基2的16點(diǎn)IFFT處理器，使用7個(gè)實(shí)數(shù)乘法器即可完成，進(jìn)一步優(yōu)化可僅使用5個(gè)。通過(guò)ALTERACycloneⅡ系列的EP2C70F896C6器件進(jìn)展下載驗(yàn)證。FPGA輸出結(jié)果與MATLAB計(jì)算結(jié)果比擬，單點(diǎn)最大相對(duì)誤差約***。關(guān)鍵字：FFT,乘法器復(fù)用，F(xiàn)PGAAbstract:ThispaperproposesanoptimizedFFTalgorithmbasedonmultipliermultiple*ingtechnology,itreducesthehardwareresourceconsumptionbytakingtheadvantageoftherotationfactorsymmetryonthe

y-a*is

andy=*;Onlyuse7realmultipliertodesignapipelinedradi*-2,16-pointIFFTprocessor,furtheroptimization

can

only

use

5.TheverificationiscarriedoutthroughthedownloadedALTERACycloneⅡseriesEP2C70F896C6device．whoseresultislessthan***differenceparedwiththeresultfromtheMATLABcalculationKeyWords：FFT；multipliermultiple*ing；FPGA1引言FFT(快速傅里葉變換)是數(shù)字信號(hào)處理中的重要模塊，作為時(shí)域和頻域轉(zhuǎn)換的根本運(yùn)算．是數(shù)字譜分析的必要前提，在信號(hào)處理、圖像處理、生物信息學(xué)、計(jì)算物理、應(yīng)用數(shù)學(xué)等方面都有著廣泛的應(yīng)用。在高速數(shù)字信號(hào)處理中，F(xiàn)FT的處理速度往往是整個(gè)系統(tǒng)設(shè)計(jì)性能的關(guān)鍵所在[1]。對(duì)于FFT的硬件實(shí)現(xiàn)，大致可以分為3種方案：通過(guò)數(shù)字信號(hào)處理器(DSP)實(shí)現(xiàn)；通過(guò)專(zhuān)用FFT芯片實(shí)現(xiàn)；通過(guò)FPGA實(shí)現(xiàn)[2]。用DSP完成FFT運(yùn)算需要占用大量DSP的運(yùn)算時(shí)間，使整個(gè)系統(tǒng)的吞吐量降低；專(zhuān)用的FFT處理芯片，雖然速度較快，但其可擴(kuò)展性差，且本錢(qián)昂貴。FPGA不僅有大量的片內(nèi)資源，而且易于組織流水和并行構(gòu)造，可以大大提高FFT的處理速度。將FFT的實(shí)時(shí)性要求與FPGA的靈活性相結(jié)合，不僅可以提高處理速度，而且可以方便的移植到ASIC中。2FFT算法根本原理對(duì)于N點(diǎn)序列，其離散傅立葉變換(DFT)變換可寫(xiě)為：，〔2-1〕其中：。由式〔2-1〕分析可知，假設(shè)直接計(jì)算DFT，乘法和加法次數(shù)都和N2成正比，當(dāng)N很大時(shí)，運(yùn)算量是很可觀的。FFT算法的根本思想：可以將一個(gè)長(zhǎng)度為N的序列的離散傅里葉變換逐次分解為較短的離散傅里葉變換來(lái)計(jì)算，這些短序列的DFT可重新組合成原序列的DFT，而總的運(yùn)算次數(shù)卻比直接的DFT運(yùn)算少得多，從而到達(dá)提高速度的目的[3]。這種分解根本上可分為兩類(lèi)，一類(lèi)是將時(shí)間序列*(n)進(jìn)展逐次分解，稱(chēng)為按時(shí)間抽取算法(DecimationInTime)；另一類(lèi)將傅立葉變換序列*(k)進(jìn)展分解，稱(chēng)為按頻率抽取算法(DecimationInFrequency)。本文主要介紹了按時(shí)間抽取基一2FFT算法。我們已經(jīng)知道FFT算法主要是利用的性質(zhì)，通過(guò)把序列逐漸分解為短序列實(shí)現(xiàn)運(yùn)算量的減少。的以下三種性質(zhì)在FFT運(yùn)算中得到了應(yīng)用[4]：性質(zhì)1：的周期性性質(zhì)2：的對(duì)稱(chēng)性性質(zhì)3：的可約性，基2算法中，序列的長(zhǎng)度N為2的整數(shù)次冪，即，其中M為正整數(shù)。最初通過(guò)將分解為奇數(shù)項(xiàng)序列和偶數(shù)項(xiàng)序列的形式使FFT運(yùn)算分為兩組。設(shè)：，設(shè)，，利用的性質(zhì)可得的DFT運(yùn)算為：〔2-2〕式〔2-2〕的運(yùn)算可用下列圖的蝶形信號(hào)流圖表示：圖1蝶形運(yùn)算流圖由此可見(jiàn)，一個(gè)Ｎ點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)的DFT，從而實(shí)現(xiàn)了運(yùn)算量的減少，再經(jīng)過(guò)逐次分解最終分解為２點(diǎn)的DFT，實(shí)現(xiàn)了FFT運(yùn)算。3乘法器復(fù)用的FFT實(shí)現(xiàn)構(gòu)造文獻(xiàn)[5]提出了一種蝶形運(yùn)算的新構(gòu)造：即先進(jìn)展前一級(jí)4點(diǎn)蝶形運(yùn)算，再進(jìn)展本級(jí)的與旋轉(zhuǎn)因子復(fù)乘運(yùn)算，如圖2所示。這種構(gòu)造節(jié)省了一個(gè)旋轉(zhuǎn)因子復(fù)乘模塊。圖2文獻(xiàn)4所設(shè)計(jì)的FFT硬件實(shí)現(xiàn)框圖文獻(xiàn)[2、6]中改良的旋轉(zhuǎn)因子復(fù)數(shù)乘法的原理均為：一個(gè)復(fù)數(shù)和旋轉(zhuǎn)因子相乘，結(jié)果仍為復(fù)數(shù)，，可見(jiàn)完成一次復(fù)數(shù)乘法操作需要進(jìn)展4次實(shí)乘和2次實(shí)加運(yùn)算。為減少乘法的次數(shù)，將做以下變換：，，從而完成一次復(fù)乘只需進(jìn)展3次實(shí)乘和5次實(shí)加，較變換前減少一次實(shí)數(shù)乘法運(yùn)算，從而減少了使用面積。本文采用原理圖輸入與AHDL語(yǔ)言相結(jié)合的方法，來(lái)完成IFFT的設(shè)計(jì)。其中原理圖輸入的方法主要完成實(shí)乘和實(shí)加操作，而當(dāng)參加加法運(yùn)算的兩個(gè)數(shù)位數(shù)長(zhǎng)度不一致時(shí)，AHDL語(yǔ)言將二者補(bǔ)齊。本設(shè)計(jì)中，首先完成2點(diǎn)IFFT的設(shè)計(jì)，然后將其封裝為.bsf格式的符號(hào)文件。之后多點(diǎn)的IFFT設(shè)計(jì)，設(shè)計(jì)流程如下列圖3所示。N=4點(diǎn)的IFFT中，旋轉(zhuǎn)因子為,乘法運(yùn)算相當(dāng)于實(shí)部虛部互換操作，可以合并到蝶形運(yùn)算中且不增加硬件消耗。圖3設(shè)計(jì)流程圖N=8點(diǎn)的IFFT中，1與不需要乘法器來(lái)運(yùn)算，只需要2次旋轉(zhuǎn)因子的復(fù)乘運(yùn)算，即與，其中與的位置如下列圖4。圖4N=8時(shí)旋轉(zhuǎn)因子分布由圖4可知與關(guān)于軸對(duì)稱(chēng)，假設(shè)令，則。又因?yàn)椋瑒t有〔3-1〕上式〔3-1〕可以看出兩次復(fù)乘運(yùn)算的結(jié)果均為*個(gè)復(fù)數(shù)與相乘，由此可以采用時(shí)分復(fù)用的方法，將參與復(fù)乘運(yùn)算的兩個(gè)數(shù)的實(shí)部和虛部按照上式相加減之后，經(jīng)過(guò)串并變換，依次進(jìn)入乘法器運(yùn)算。這樣完成一個(gè)8點(diǎn)的IFFT運(yùn)算，僅需要1個(gè)實(shí)數(shù)乘法器即可完成，大大節(jié)省了芯片的資源與面積。而文獻(xiàn)[5]中，假設(shè)完成N=8點(diǎn)的IFFT運(yùn)算需要做兩次復(fù)乘運(yùn)算，經(jīng)改良后仍需4個(gè)實(shí)數(shù)乘法器；文獻(xiàn)[6]中，則需要6個(gè)實(shí)數(shù)乘法器才能完成設(shè)計(jì)。另外，以及本應(yīng)為-1~+1之間的小數(shù)，為了防止浮點(diǎn)運(yùn)算，這里乘以256歸一化為9BIT有符號(hào)數(shù)，即令，最終輸出時(shí)再右移8位即可。N=16點(diǎn)的IFFT中，1與不需要乘法器來(lái)運(yùn)算，共需要6次旋轉(zhuǎn)因子的復(fù)乘運(yùn)算，這6個(gè)旋轉(zhuǎn)因子分別為、、、、、，其位置關(guān)系如下列圖。圖5N=16時(shí)旋轉(zhuǎn)因子分布利用旋轉(zhuǎn)因子關(guān)于軸以及直線的對(duì)稱(chēng)性質(zhì)，令，則，，，其中，，則有〔3-2〕由上式可以看出，等式右側(cè)均為〔3-3〕因此與N=8點(diǎn)的IFFT一樣，將乘法器時(shí)分復(fù)用，經(jīng)過(guò)串并變換，將4路串為1路，這樣在流程圖的蝶形單元中采僅需要5個(gè)實(shí)數(shù)乘法器〔實(shí)現(xiàn)式〔3-3〕需要4個(gè)實(shí)數(shù)乘法器，與還需要額外的1個(gè)實(shí)數(shù)乘法器來(lái)實(shí)現(xiàn)〕，在流程圖的兩個(gè)N/2點(diǎn)〔4點(diǎn)〕的IFFT中還需要2個(gè)實(shí)數(shù)乘法器。這樣按照時(shí)分復(fù)用的方法完成一個(gè)16點(diǎn)的IFFT運(yùn)算總共需要7個(gè)實(shí)數(shù)乘法器即可。4.IFFT處理器的FPGA加載實(shí)驗(yàn)結(jié)果本文在ALTERACycloneⅡ系列的EP2C70F896C6芯片上實(shí)現(xiàn)了16點(diǎn)的IFFT處理器，在8個(gè)時(shí)鐘周期內(nèi)，僅使用7個(gè)實(shí)數(shù)乘法器即可。另外由式(3-3)可已看出，本設(shè)計(jì)可以進(jìn)展進(jìn)一步的優(yōu)化，將實(shí)部和虛部中所有乘數(shù)為(或者)的數(shù)據(jù)，經(jīng)過(guò)串并變換，將8路串為1路，這樣又可以減少實(shí)數(shù)乘法器的使用個(gè)數(shù)，僅使用5個(gè)實(shí)數(shù)乘法器。同時(shí)為了防止浮點(diǎn)乘法運(yùn)算將旋轉(zhuǎn)因子擴(kuò)大256倍后將最終結(jié)果輸出右移8位，假設(shè)乘法器的輸入為9bit*8bit，輸出的結(jié)果為17bit，為了進(jìn)一步減少資源消耗，將乘法輸出只取高12位，并將最終的結(jié)果右移3位輸出。N=8時(shí)，〔a〕傳統(tǒng)算法〔b〕改良后算法圖6N=8時(shí)的編譯結(jié)果中資源占用情況由圖6可以看出，將乘法器輸出只取高12位后，LE節(jié)省了19%。圖7IFFT輸出結(jié)果仿真圖由圖7可知，N=8時(shí)，IFFT的輸出結(jié)果與matlab的仿真結(jié)果完全一樣。N=16時(shí)，圖8N=16時(shí)IFFT輸出結(jié)果仿真圖由圖8將輸入與輸出結(jié)果導(dǎo)出，并與matlab計(jì)算結(jié)果相比擬，可得到下表，表1FPGA輸出結(jié)果與MATLAB計(jì)算結(jié)果比擬輸入AFPGA輸出BMatlab計(jì)算結(jié)果C-3-2i-4+5i-4.0000+5.0000i2+1i4-7i-1+0i-3+1i-2.1716+1.8995i0-3i3+4i4.1157+4.9361i1+2i-6-11i-3-1i-8+0i3+1i-8-4i-2+2i-8-2i0-2i2-1i-2+3i-20+10i-19.4562+9.4095i-1+1i-8-18i2-1i4+7i5.1981+7.5492i3+0i12-1i-1+3i3-13i-3+2i-11-4i1-1i-6-3i由可以計(jì)算出16點(diǎn)平均相對(duì)誤差約0.68%。由本文算法可進(jìn)一步推廣到32,64,128,256,..…等多點(diǎn)IFFT的實(shí)現(xiàn)，根據(jù)旋轉(zhuǎn)因子關(guān)于y軸和y=*的對(duì)稱(chēng)性，使用兩個(gè)實(shí)數(shù)乘法器可分時(shí)共享即可完成4個(gè)復(fù)數(shù)旋轉(zhuǎn)因子的計(jì)算，因此占用乘法器數(shù)量?jī)H為傳統(tǒng)算法的1/8左右，可以大大節(jié)省資源占用情況，減少整個(gè)系統(tǒng)的資金投入。參考文獻(xiàn)[1]SansaloniT,Perez-pascualA,VallsJ.Area-efficientFPGA-basedFFTProcessor[J].ElectronicsLeeters,2003,39(19):1369-1370.[2]侯志堅(jiān)，董軍軍，李杰等.OFDM中的FFT處理器設(shè)計(jì)及FPGA實(shí)現(xiàn)[J].中國(guó)現(xiàn)代教育裝備。2010年第21期[3]A．V．奧本海姆，R．w．謝弗著．離散