一種并行大分數(shù)快速傅立葉變換的fpga實現(xiàn)

一種并行大分數(shù)快速傅立葉變換的fpga實現(xiàn)

0網(wǎng)絡(luò)數(shù)字化有機融合的實現(xiàn)方案在現(xiàn)代電子戰(zhàn)中，數(shù)字技術(shù)在ew無線傳感器中得到了廣泛應(yīng)用。數(shù)字化接收機具有高截獲概率、高精度、高靈敏度、大動態(tài)、高度靈巧性、小體積的優(yōu)勢。同時運用數(shù)字信號處理技術(shù)對信號進行多分辨分析獲取雷達信號的原始細微特征。由于EW接收機需要覆蓋比較寬的瞬時帶寬,必須使用高速的AD變換器完成模擬信號的數(shù)字化,信號處理機要能處理高速的數(shù)據(jù)流,實現(xiàn)對雷達信號的準實時處理,提高數(shù)字化接收機的截獲概率,并提供出雷達信號更為精確的多種參數(shù)特征。這對數(shù)字化接收機的信號處理能力提出了很高的要求。因此,數(shù)字化接收機信號處理的軟、硬件部分就成了整個EW接收機的關(guān)鍵部件,同時也是整個研制任務(wù)中難度最大的的技術(shù)難點之一。由于數(shù)字化接收機需要處理的數(shù)據(jù)量比較大,選擇高效的算法是非常重要的。通過對數(shù)字化接收機的算法分析,我們發(fā)現(xiàn),高效率的快速傅立葉變換(FFT)算法仍然是對雷達信號處理的基礎(chǔ)和核心算法,其它的如快速相關(guān),卷積都可以通過快速傅立葉變換(FFT)算法得到。在具體硬件實現(xiàn)上,大致可分為兩種方案。一種是通過通用數(shù)字信號處理器(如TI公司的TMS320C6X系列)構(gòu)成多處理器系統(tǒng),通過算法分解和任務(wù)調(diào)度,實現(xiàn)并行計算以提高處理速度。另一種方案是使用專用的FFT處理芯片(最為典型的是SHARP公司的LH9124)作為實現(xiàn)算法的工具。專用FFT芯片本身就是一種高度集成化的并行硬件處理器,通過一些外圍存儲器的配合,就能實現(xiàn)高效的FFT算法。通用DSP處理器構(gòu)成的FFT處理機采用循環(huán)編碼算法,程序量小,但存在大量的冗余運算,且需要許多跳轉(zhuǎn)操作,處理速度較慢,不能滿足數(shù)字化接收機實時性的要求。在多處理器構(gòu)成的并行處理系統(tǒng)中,使用抽取的方法實現(xiàn)對輸入數(shù)據(jù)的分解,達到并行處理的目的,可顯著提高計算的速度,但在進行大點數(shù)FFT計算時,存在并行算法與DSP處理器的尋址能力不相適應(yīng),不能有效利用數(shù)據(jù)傳輸?shù)膸捄瓦\算能力的問題,造成硬件資源的浪費。雖然通用的DSP處理器在結(jié)構(gòu)上已考慮了對各種算法的優(yōu)化,同時具有很大的靈活性,但對FFT這種高度結(jié)構(gòu)化的算法,其效率仍然不是很高。我們提出一種新的思路,把專用的FFT處理芯片的處理速度與FPGA芯片的靈活性結(jié)合起來,實現(xiàn)并行算法與硬件結(jié)構(gòu)的優(yōu)化配置,提高FFT處理速度,滿足對雷達信號處理實時性的要求。1下標映射加解二通道fft對N點序列x(n),其DFT變換的定義為:k=0,1,K,N-1,利用WN的對稱性和周期性可推導(dǎo)出其快速算法FFT。對N=2r點的DFT可推導(dǎo)出基2的FFT算法:完成一個N點的FFT所需的復(fù)數(shù)乘法和復(fù)數(shù)加法分別減少到(N/2)log2N和Nlog2N次。當選用的專用FFT處理芯片計算點數(shù)為一個定值時,計算長點數(shù)大N點的FFT就必須分解為若干個小N點的FFT,該方法由Winograd提出,利用下標映射把大點數(shù)的DFT分解為小點數(shù)的DFT,具體步驟如下:(1)將輸入序列按n=n1+N1n2分為N2個長度為N1的子序列,構(gòu)成x(n1,n2)的列,即(2)對x(n1,n2)的每一行求N2點的FFT,共N1個N2點FFT得g(n1,k2)。(3)對g(n1,k2)的第n1行第k2列元素g(n1,k2)乘以因子構(gòu)成新矩陣(4)對矩陣(n1,k2)的第一列求N1點FFT,共N2個N1點FFT得X(k1,k2)。(5)由X(k1,k2)和k=N2k1+k2即可求出X(k),可見重復(fù)算法實質(zhì)上是將一N點FFT分解為N1個N2點FFT和N2個N1點FFT以及N次與W的乘積。2在vetex系列器件中的fpga信號傳統(tǒng)的專用FFT處理器采用ASIC電路來實現(xiàn),受到應(yīng)用范圍的局限,已經(jīng)逐漸跟不上半導(dǎo)體工藝的發(fā)展,有的已停止了生產(chǎn),越來越多的設(shè)計開始轉(zhuǎn)移到可編程邏輯電路上實現(xiàn)。由于在性能、成本、靈活性和功耗等方面的優(yōu)勢,基于FPGA(現(xiàn)場可編程邏輯陣列)的信號處理器已進入各種電子戰(zhàn)、通信設(shè)備中。FPGA提供了極強的靈活性,可讓設(shè)計者開發(fā)出滿足多種要求的產(chǎn)品。大多數(shù)FPGA廠商都提供了可配置的邏輯核(CORE)實現(xiàn)各種算法功能,在XILINX公司的Vertex系列器件中,一個24×24bit復(fù)數(shù)乘法器,完成一次復(fù)數(shù)計算所需的時間為10ns,除此之外,在器件中我們還能構(gòu)造一條能夠精確匹配所需算法的數(shù)據(jù)通道,使數(shù)字信號處理的算法效率得到極大的提高。Xilinx公司的1024點復(fù)數(shù)FFT邏輯核(Logicore),可在其X2V300以上的器件中配置,對16位精度的復(fù)數(shù)執(zhí)行一次1024點的復(fù)數(shù)FFT可在10μs內(nèi)完成,包括位倒序轉(zhuǎn)換在內(nèi)。而一個先進的軟件DSP計算一次的時間約為60μs,還不包括位倒序轉(zhuǎn)換。該FFT邏輯核的方框圖如圖1所示。Xilinx公司的FFT邏輯內(nèi)核采用標準的基4Cooley-Tukey算法,一個計算單元可分配到每個蝶形陣列,一個1024點的FFT可在1024個時鐘周期內(nèi)完成,若采用100MHz的時鐘,變換時間為10μs。上述1024點的FFT占用Vertex系列FPGA器件約1900個邏輯單元,還可以利用FPGA提供的高速IO帶寬,片上存儲器和邏輯等多種資源,從而使FFT的高度并行處理成為現(xiàn)實。比較FPGADSP和其它DSP系統(tǒng)時,一個極為重要的系統(tǒng)參數(shù)是輸入/輸出(I/O)帶寬,FPGA上幾乎所有的引腳均可提供給用戶使用,這使得FPGA信號處理方案具有非常高性能的I/O帶寬。大量可靈活配置的I/O引腳和片上存儲器可獲得優(yōu)越的并行處理能力。隨著FPGA供應(yīng)商和第三方IP設(shè)計商提供越來越多的FPGAIP內(nèi)核,我們利用這些資源,就能將精力集中在系統(tǒng)設(shè)計上,而無須關(guān)心底層模塊的細節(jié),這樣可極大地縮短產(chǎn)品開發(fā)周期。3數(shù)據(jù)合并處理單元數(shù)據(jù)的輸出在FFT陣列處理器中,使用Xilinx公司的1024點FFT邏輯內(nèi)核構(gòu)成陣列處理器的一個處理單元,采用第1節(jié)中介紹的下標映射原理把大點數(shù)的輸入數(shù)據(jù)分解為多個1024點的數(shù)據(jù)由FFT處理單元并行計算,計算結(jié)果存入緩沖存儲器,最后進行數(shù)據(jù)合并處理。FFT陣列處理器的結(jié)構(gòu)框圖如圖2所示。在數(shù)字接收機中,模數(shù)轉(zhuǎn)換器產(chǎn)生的數(shù)字信號由數(shù)據(jù)緩沖、分配單元按一定的順序抽取(即輸入數(shù)據(jù)從一維到二維的映射),輸入到每個FFT處理單元的輸入存儲器中,輸入數(shù)據(jù)分配完成后,啟動FFT處理單元進行并行的1024點計算。經(jīng)過1024個時鐘周期,完成對一次小點數(shù)的FFT計算,這時,即可進行下一輪的數(shù)據(jù)分配過程。各FFT處理單元的輸出存儲器在地址發(fā)生器的作用下,實現(xiàn)數(shù)據(jù)矩陣的重構(gòu)并存儲于緩沖存儲器中,當一次計算的所有數(shù)據(jù)的中間值得到后,就由數(shù)據(jù)合并處理單元對重構(gòu)的數(shù)據(jù)矩陣的每一列數(shù)據(jù)進行新的FFT,最終的結(jié)果仍舊存儲在緩沖存儲單元中等待輸出。從以上分析可以看到,并行計算主要集中在第一級1024點的FFT,第二級FFT(相當于對數(shù)據(jù)矩陣的列)由于受輸入數(shù)據(jù)長度的影響,FFT的長度不固定,不能實現(xiàn)并行處理,可使用一片通用DSP芯片,使用軟件計算以增加對數(shù)據(jù)的適應(yīng)性。由于基于FPGA的FFT陣列處理器采用定點方式計算,為了防止計算溢出,計算中使用逐級移位的塊浮點方式處理,輸入精度為16bit,輸出精度為32bit。輸入數(shù)據(jù)要求為1024的2n倍,不足部分的采用補零的方法對齊數(shù)據(jù),這對基于硬件的FFT處理器是最好的辦法,對計算效率影響不大。考慮到對高速存儲器容量的限制,最大處理的數(shù)據(jù)長度限制為256k。在高速FPGA芯片中,已經(jīng)能在單周期內(nèi)完成一次復(fù)數(shù)乘法和加法,對數(shù)據(jù)傳輸時間的要求也就同樣重要,理論上的一些優(yōu)化算法如分裂基、WFTA算法在結(jié)構(gòu)上帶來的復(fù)雜性對數(shù)據(jù)傳輸產(chǎn)生了不利的影響。規(guī)范的結(jié)構(gòu)和高速的數(shù)據(jù)傳輸帶寬對FFT性能的影響也是至關(guān)重要的。在基于FPGA的FFT陣列處理器中,高速的硬件FFT處理單元與數(shù)據(jù)通道的結(jié)合可帶來性能上的飛速提高。下面以256k點的數(shù)據(jù)為例分析一下它的性能:假定FFT陣列處理器中包含16個1024點的FFT單元,系統(tǒng)時鐘為100MHz,則第一級FFT就需要進行256k/16k=16次,每次所需的時間為41μs;一次計算未完成時下一批數(shù)據(jù)必須等待傳送,不能按流水線方式工作,進行256k數(shù)據(jù)傳送的時間為256k/100M=2.56ms必須另外記入;第一級FFT得到的結(jié)果存人緩沖存儲器可以和輸入數(shù)據(jù)同時進行,則不需再算;第二級為1024個256點的FFT,假定一個256點的FFT計算時間為10μs(對TI的TMSC64X器件是容易達到的),就可以得出處理時間為:16×0.041+2.56+1024