基于激光導引頭信號的并行高速FFT算法設計

朱立坤，賈方秀*，李興隆

(1.南京理工大學 智能彈藥國防重點學科實驗室，南京 210094； 2.中國工程物理研究院 化工材料研究所，綿陽 621900)

基于激光導引頭信號的并行高速FFT算法設計

朱立坤1，賈方秀1*，李興隆2

(1.南京理工大學 智能彈藥國防重點學科實驗室，南京 210094； 2.中國工程物理研究院 化工材料研究所，綿陽 621900)

為了減少激光半主動武器中測量光學器件光斑點坐標時噪聲和干擾對探測精度影響、增加脈沖信號的測量帶寬、提取信號的有效值，同時克服串行快速傅里葉變換(FFT)運算耗時及時間復雜度較大的問題，基于多核和并行架構的SoC-FPGA平臺以及OpenCL軟件，提出了實現并行FFT的計算方法。結果表明，利用該方法可使FFT(1-D)的時間復雜度下降到原來的1/Q，得到了較好的加速效果;通過3種平臺(先進精簡指令集微處理器、數字信號處理器和片上系統現場可編程門陣列)的運算耗時實驗對比，該算法運算耗時為6.0449ms(1-D 4096點)，要比同點數其它兩種平臺運算耗時少。并行FFT算法不僅滿足激光半主動導引頭信號實時性的要求，而且可以達到去噪的效果，能有效地降低噪聲和背景光的影響。

測量與計量；并行快速傅里葉變換；SoC-FPGA；OpenCL；時間復雜度；激光半主動

引 言

激光半主動尋的制導武器(laser semi-active search guide weapons，LSSGWS)具有制導精度高、抗干擾能力強、結構簡單、成本低、使用方便等優點，因而被廣泛應用于武器裝備中，成為使用頻率最高的光電精確制導武器[1-4]。半主動激光制導武器主要依靠武器前端的激光導引頭起作用[5]。激光導引頭由光學系統收集激光照射目標物體上反射的回波，利用位置敏感探測器(position sensitive detector，PSD)或者四象限探測器(quadrant detector，QD)等光學位置傳感器進行制導。

采用10脈沖/s～20脈沖/s脈沖激光進行制導時，探測器多采用速度響應快的光學位置傳感器，探測器會輸出納秒級的脈沖信號[6]。實際使用過程中，探測儀器性能要受到噪聲及干擾的影響和限制。光學探測器主要的噪聲來源包括熱噪聲、散粒噪聲和閃爍噪聲等[7]；干擾主要由暗電流、背景光等引起的。當激光制導過程中，目標的反射率低或者傳輸距離遠時，光信號會更加微弱，這時就需要盡可能消除探測器上噪聲和干擾的影響提取有用的信號以獲得準確的光斑位置。

ZHAO[8]等人研究并實現了基于通用并行計算架構平臺的快速傅里葉變換(fast Fourier transformation,FFT)并行計算，但是只局限于NVIDIA公司的統一通用并行計算架構平臺。YIN[9]等人利用小波理論對PSD信號進行有用信號的提取，但是小波轉換在常規處理器上實現很復雜。而采用FFT對光學位置探測器所獲得的信號進行處理，不但可以有效地消除誤差，增加光斑位置探測的精度，而且可以很方便地在彈載計算機上實現。但是常規的數字信號處理器(如數字信號處理器(digital signal processing,DSP)、先進精簡指令集微處理器(advanced risc machine,ARM)、FFT處理器等)在處理速度及處理時間上都無法滿足彈載計算機對時間及功耗的要求。ZHAN等人[10]利用現場可編程門陣列(field-programmable gate array,FPGA)實現了多路并行結構的 FFT 處理器，但是進行FPGA開發時，需要了解FPGA硬件開發的特定領域的知識，并且VHDL和Verilog硬件描述語言可移植性較低，在移植的過程中受到FPGA邏輯單元陣列數量的限制。

本文中提出了使用OpenCL實現FFT算法的方法，通過一個高級語言合成工具映射到片上系統(system on chip,SoC)-FPGA上實現OpenCL并行運行。該方法的主要優點是：(1)增加了FFT算法的高效性、可靠性，利用OpenCL在SoC-FPGA上實現并行FFT可以大大減少FFT算法的運行時間，利用FPGA實現硬件加速器，大大增加了算法運行的可靠性,并且OpenCL具有“一次編寫、各設備上運行”等優勢，使得面向OpenCL的程序具有高度可移植性；(2)減少了實現機制的功耗和增加了便捷性，SoC-FPGA實現了硬核處理系統(hard proceisor system,HPS)性能(在設計中加入了隨機存取存儲器(random access memory,RAM)、只讀存儲器(read only memory,ROM)、串行外設接口(serial peripheral interface,SPI)、控制器局域網絡(controll area network,CAN)等常用模塊，極大擴展了SoC的應用領域，方便系統增加各類常用的傳感器)的同時又兼顧低功耗的特性，這使得SoC-FPGA很適合作為數字信號處理器應用到激光半主動武器系統中。

1 激光半主動光電位置探測器件信號特點

為了增強激光發射器在大氣中的峰值功率，一般激光發射器都會發射重頻較低、脈寬較窄的脈沖光。直接照射到目標上經過目標的反射，被導引頭的光學系統探測到并且光電位置探測器會產生相應的信號，并有相關數字信號處理電路，最后控制導彈的姿態并命中目標。光電位置傳感器單一引腳經過單一I/V(電流/電壓)轉換后輸出的波形如圖1中1通道波形所示。

Fig.1 The waveform of position sensor

a—outside the darkroom with high intensity b—in the darkroom with high intensity c—in the darkroom with low intensity

輸出波形的主要特點是：(1)由于背景光的影響，波形輸出時有個直流變量，表現在圖1a中就是初始值并不是在零點位置；(2)消除背景光影響后在光強較強的情況下，波形完美可以進行數據采集，但是在光強較弱的情況下各種噪聲比較多，原始信號幾乎被泯滅在噪聲中，表現在圖1c中就是幾乎辨別不出原始信號；(3)周期T=10Hz～20Hz。所以就要求4路信號的運算在50ms～100ms之內完成，單路信號的運算在12.5ms～25ms之內完成。

2 面向OpenCL的SoC-FPGA并行高速FFT設計

由于FFT具有蝶型單元和組的概念等特點，所以對FFT算法進行并行化處理是快速、可靠的方法之一。MAIMAITIJIANG等人[11]研究了FFT算法并行計算的實現。SoC-FPGA不僅具有FPGA結構可方便實現FFT的并行操作，而且具有ARM處理器，很容易對數據進行管理和分配處理。

為了在SoC-FPGA實現并行FFT運算，需要在芯片內部進行外圍電路和網絡互連的協議(internet protocol,IP)核添加，圖2是添加完成后的主要系統框圖。

Fig.2 Hardware architecture of SoC-FPGA for FFT

為了更方便地實現FFT的并行化處理，選用OpenCL作為設計的主體語言，SoC-FPGA的OpenCL主要面向信號處理類應用的客戶，是用C語言開發FPGA的新方法。而SoC-FPGA具有的并行和多核處理的架構非常適用于基于異構平臺運行應用程序接口的OpenCL的運行。

一個完整的OpenCL運行程序通常由兩部分組成：一個宿主機程序和一個或多個內核組成的集合。宿主機程序是在宿主機(本次為ARM)上運行，內核在OpenCL設備上執行，它是完成整個OpenCL應用的具體工作。

圖3展示了作者設計的并行高速FFT的主要組成及基本工作流程。內核函數的設計會在接下來進行討論。

Fig.3 Action of OpenCL in SoC-FPGA

2.1 FFT算法

FFT本身具有很好的分治特性，根據這個特點來研究它的并行性特征[12],實現在SoC-FPGA平臺的運行。

對N點序列x(n)，其離散傅里葉變換(discrete Fourier transform,DFT)的變換對定義為：

作為初一新生的數學教師，常會聽到學生說“這題怎么這么難啊”，而且原本在小學反應不錯的學生，課上也默不作聲了，學習數學的熱情也減了幾分，更別提對數學有興趣了。因而如何引導他們盡快過渡、是我們每一位初中數學教師的重要責任。所以我根據學生的心理特點，試著從教法與學法入手，做了一些探索。

W0=1,WN/2=-1,

采樣點為N時，按時間抽取基-2 FFT共需log2N級的蝶形運算，且每一級有N/2個蝶形運算。實現時先對輸入采樣點進行倒位序調整，再逐級作蝶形運算，最后得到正序的FFT輸出。

由于FFT中每一級的蝶形運算存在相互獨立性，根據蝶形運算的原理，引入并行執行的思想。

2.2 算法并行化

歸并過程是整個FFT變換的核心。并行歸并算法的初始思想就是將輸入元素均勻的分布在處理機上[12]。對于具有N個采樣點的FFT序列，需要M=log2N級來計算得到最終的輸出結果。第1級先計算得到N/2個兩兩元素組成的FFT序列，第2級將前一級歸并為N/4個元素的FFT序列，以此類推，直到求出最后的FFT序列。用OpenCL實現FFT的過程具體如圖4所示。

Fig.4 FFT for 64-element sequence with 4 work items

具體在SoC-FPGA上用OpenCL實現FFT并行計算時主要涉及到內核的硬件實現，實現過程是通過FPGA的軟件開發工具包編譯OpenCL的內核產生一個電阻晶體管邏輯電路項目，從而實例化一個寬的流水線結構。主機程序是按照初始化平臺、尋找設備、打印設備信息、創建設備上下文、在設備上下文中創建指令隊列、載入設備代碼、編譯設備代碼、創建核函數對象、設置核函數參量、運行核函數、等待核函數運行結束、清除所有對象等流程進行編寫[13]。內核的執行流程見圖5。工作項目流程是一個平行的流水線FFT加速器。已進入加速器的工作項目連續交錯正好經歷一個時鐘周期，當工作項目之間需要數據交換時，必須停止當前的工作項目，在柵欄的作用下進行同步化，之后各個工作項目繼續進行下一階段的計算，直到整個項目完成。

Fig.5 Flow of N-D parallel FFT algorithm

整個FFT并行具體計算過程是：假設N點的數據序列，在進行FFT變換時，每級都需要經過N/2個蝶形運算；Kernel函數含有一個基-nFFT引擎，每一時鐘周期能夠處理n(n為2的冪)個數據點，這個引擎通過一個固定的順序處理塊(蝴蝶、旋轉、交換、重新排序、乘法等)，產生n個輸出點的FFT變換。在一個工作項目任務中，Kernel函數被設計為一個循環調用的過程。通過循環調用FFT引擎M次，最后將數據從設備端輸出到主機端完成整個FFT變換。

本次設計每一時鐘周期能夠處理8個數據點的基-4 FFT內核主要框架如下：(1)設計FFT蝶型塊、數據旋轉塊、數據交換塊；(2)定義全局轉換FFT的點數N=4096；(3)調用FFT蝶型塊、數據旋轉塊、數據交換塊；(4)接下來(log2N-2)階段交替兩個計算模式(在此之前要調用一次#pragma unroll來指示編譯器完全展開循環以增加流水線并行性)；(5)最后(log2N-1)階段就是移動滑動窗口內容，在此過程中如果編譯器能夠完全展開循環，硬件就可以將整個內容并行。

此內核函數被配置為作為單個工作項的內核，它使用一個滑動窗口來表示延遲元件。該內核函數在運行時首先從全局內存中讀取輸人數據，并將數據饋送到8個數據點的基-4 FFT內核然后將存儲結果保存到全局內存。數據時順序輸入然后反比特輸出，在編譯時編譯器利用流水線的并行性，通過重復FFT內核的源代碼，進行循環的迭代，每一個時鐘周期啟動一次迭代。

3 實驗結果及分析

為了和常規串行FFT進行對比，需要對設計的程序進行運算耗時的對比，主要是根據本次實驗并結合FFT在進行1024和4096個元素的變換時在ARM[14-15],DSP[16-17]等處理器上的運行時間進行對比，具體結果見表1，運算耗時是微處理器最重要的性能指標之一。分析表1可知，具有NEON的ARM Cortex-A8平臺在計算FFT時耗時最長，實時性最差，基于TI的C6713單核DSP運算平臺對FFT實現性能次之。對于4096點復數數據的FFT并行運算耗時僅為6.0449ms，這主要是因為在并行FFT運算中需要進行多次同步化操作，而同步化很耗時間。對于實時性要求較高的數字信號處理的微處理器，SoC-FPGA完全滿足性能的要求。

Table 1 Comparison of operation time of ARM, DSP and SoC-FPGA

為了驗證本文中提出的方法，搭建實驗室實驗環境，具體如圖6所示。

Fig.6 Experiment of laser semi-active diffuse reflection

在實驗室內，將激光指示器發射的激光照射到漫反射屏上，調整三軸轉臺，使固定在三軸轉臺上的導引頭能接收到激光信息，利用數采卡進行數據采集。

將數據采集卡通道設置為4，采樣率F=2000Hz，采集時間設置為10s。編寫相關的程序并下載到目標板內，運行程序。

將原始數據和SoC-FPGA產生的數據進行繪圖，如圖7所示。

Fig.7 Original signal and FFT transform result of laser semi-active photoelectric detector

在多級的歸并運算過程中，數據的截尾會產生誤差，影響運算的精度。但由于該誤差較小，不影響后續頻譜的分析和處理。首先根據所得數據，計算某點n所代表的頻率Fn=(n-1)F/N。第1個點表示的是直流分量(即0Hz)，直流分量的存在主要是雜散光等環境因素造成的，所以在計算光斑點坐標時，首先是將第1個點的模值除以N，得到直流分量；之后根據n=FnN/F+1計算特定頻率下的模值，再除以(N/2)得到原始信號的峰值，從而達到去除其它頻率噪聲的目的。最后也可根據FFT之后的坐標點計算相位關系。

對于4096點數據的FFT并行運算耗時為6.0449ms，由于并行FFT運算中需要進行多次同步化操作，而同步化很耗時間，所以對OpenCL程序進行進一步的優化設計，還可以得到更好的性能。對于實時性要求較高的激光半主動導引頭的數字信號處理，SoC-FPGA完全滿足性能的要求。

4 結 論

通過分析激光半主動導引頭信號的特征，利用FFT算法的并行性和OpenCL并行編程的特點，實現FFT的并行計算方法，該方法運行在具有并行和多核處理架構的SoC-FPGA上。通過實驗驗證，在保證可以精確計算坐標數據量的前提下，本文中提出的運行于SoC-FPGA的OpenCL的并行FFT方法，其運行時間遠小于單周期的激光信號，可以有充足的時間接下來進行其它操作。另外，考慮到SoC-FPGA和OpenCL未來廣泛的應用領域，可以將現有的并行FFT計算方法與其在相關領域中的應用結合起來，進一步提高其應用價值。

[1] WANG W F, LIU Zh G, WANG Sh Ch,etal. Design of energy simulation system for laser guided weapons[J]. Laser Technology, 2012, 36(6):844-848(in Chinese).

[2] SHI D H, XIONG Sh Y. A review on semi active laser guided bomb[J]. Infrared Technology, 2000, 22(2):28-34(in Chinese).

[3] WANG K B. Status quo, key technology and development of laser guided weapon[J]. Infrared & Laser Engineering, 2007, 36(5):651-655(in Chinese).

[4] ZHANG T F, ZHANG H X, HUI J J,etal. A review on development and application of laser-guided weapons[J]. Electronics Optics & Control, 2015, 22(10):62-67(in Chinese).

[5] LIANG W W, HUANG Zh Y, ZHANG W P,etal. Study on error signal of quadrant detectors in laser seekers[J]. Laser Technology, 2014, 38(4):569-573(in Chinese).

[6] KARAPUZIKOV A I, PTASHNIK I V, SHERSTOV I V,etal. Modeling of helicopter-borne tunable TEA CO2, DIAL system employment for detection of methane and ammonia leakages[J]. Infrared Physics & Technology, 2000, 41(2):87-96.

[7] YU Y N. Research on weak current detection system of position sensitive detector[D]. Wuhan: Wuhan University of Technology, 2012: 5-11(in Chinese).

[8] ZHAO L L, ZHANG Sh B, ZHANG M,etal. High performance FFT computation based on CUDA[J]. Application Research of Computers, 2011, 28(4):1556-1559(in Chinese).

[9] YIN G X, WANG G, LI Y J,etal. Data analysis of PSD test system based on wavelet theory[J]. Electro-Optic Technology Application, 2011, 26(3):85-88(in Chinese).

[10] ZHAN X Ch, CAI F Y, WANG W. FPGA-based implementation technologies of multi-channel parallel FFT algorithm[J]. Modern Electronics Technique, 2015, 38(19):33-36(in Chinese).

[11] MAIMAITIJIANG Y, WEE H C, ROULA A,etal. Evaluation of parallel fft implementations on gpu and multi-core pcs for magnetic induction tomography[C]//World Congress on Medical Physics and Biomedical Engineering. Munich, Germany: Springer, 2009:1889-1892.

[12] WANG W Y, QIOU Y. A new algorithm for parallel mergesorting[J]. Computer Engineering & Applications, 2005, 41(5):71-72(in Chinese).

[13] ZHAN Y, ZHAO X C, TAN T D. Parallel programming of heterogeneous system based on OpenCL[J]. Computer Engineering & Design, 2012, 33(11):4191-4186(in Chinese).

[14] WANG J D, CHEN Y Q. Out-of-place fft optimization based on ARM Cortex-A8 platform[J]. Modern Electronics Technique, 2008, 31(23):144-147(in Chinese).

[15] LI H J, WEI Q L. High-efficient implementation of FFT algorithm based on ARM920T core[J]. Computer Engineering & Applications, 2008, 44(3):114-116(in Chinese).

[16] LIU Q L, LIU Ch L. Fast fourier transform on CCS with FFT library[J]. Techniques of Automation & Applications, 2009, 28(2):59-62(in Chinese).

[17] CHEN H L, JIANG Y. Design and realization of real FFT based on DSP[J]. Journal of Dynamics & Control, 2005, 3(2):50-53(in Chinese).

Designofparallelhigh-speedFFTalgorithmbasedonlaserseekersignal

ZHULikun1，JIAFangxiu1，LIXinglong2

(1.Minsterial Key Laboratory of Intelligent Ammunition, Nanjing University of Science and Technology, Nanjing 210094, China; 2.Institute of Chemical Materials, Chinese Academy of Engineering Physics, Mianyang 621900, China)

In order to reduce the influence of noise and interference on the detection accuracy of optical spot coordinates in semi-active laser weapons, the measurement bandwidth of pulse signal increased and the effective value of the signal was extracted. By overcoming the great time-consuming and complexity of the serial fast Fourier transform (FFT) operation, parallel FFT computing method was proposed based on multi-core and parallel architecture system on chip-field-programmable gate array (SoC-FPGA) platform and OpenCL software. By this method, the time complexity of FFT (1-D) can be reduced to 1/Qtimes and the better acceleration effect was obtained. After comparing the computational time-consuming experiments of three platforms (advanced risc machines, digital signal processing and SoC-FPGA), the caculating time of the proposed algorithm is to 6.0449ms (1-D 4096 points) and less than that of the other two platforms with the same number of points. The results show that parallel FFT algorithm not only meets the requirement of the real-time performance of laser semi-active seeker and achieves the effect of denoising, but also can effectively reduce the influence of noise and background light.

measurement and metrology; parallel fast Fourier transform; SoC-FPGA; OpenCL; time complexity; laser semi-active

1001-3806(2018)01-0089-05

國家自然科學基金資助項目( 61201391)

朱立坤(1991-)，男，碩士研究生，現主要從事數字信號處理、并行異構運算方面的研究。

*通訊聯系人。E-mail:jiafangxiu@126.com

2017-01-18；

2017-03-09

TJ765.3+32; TN911.74

A

10.7510/jgjs.issn.1001-3806.2018.01.017