STMV波束形成算法并行處理實現(xiàn)方法研究?

周亦軍 劉千里

STMV波束形成算法并行處理實現(xiàn)方法研究?

周亦軍 劉千里

（海軍駐武漢四三八廠軍事代表室 武漢 430060）

在討論了STMV（導(dǎo)向最小方差）波束形成算法原理的基礎(chǔ)上，提出了STMV波束形成算法的逆QR（正交分解）分解SMI（采樣矩陣求逆）實現(xiàn)方法，討論了逆QR分解SMI算法的Systolic陣列并行實現(xiàn)結(jié)構(gòu)，分析組成Systolic陣列的各PE（處理單元）單元的基本運算模塊的實現(xiàn)，并研究了逆QR分解SMI算法基于Systolic陣列結(jié)構(gòu)的FPGA（現(xiàn)場可編程門陣列）并行實現(xiàn)方法。

導(dǎo)向最小方差；采樣矩陣求逆；波束形成；Systolic陣列；FPGA

AbstractOn the basis of discussing STMV（steered minimum variance）beam-forming algorithm principle，the implementa?tion method of STMV beam-forming algorithm with inverse QR（orthogonal decomposition）into the SMI（sample matrix inver?sion）is proposed.The Systolic array parallel structure of inverse QR decomposition of the SMI algorithm has been discussed.The composition of Systolic array each PE（processing unit）basic operations module is analyzed.Inverse QR decomposition of the SMI algorithm is based on the Systolic array structure of the FPGA（field programmable gate array）parallel implementation method.

Key WordsSTMV，SMI，beam-forming，Systolic array，F(xiàn)PGA

Class NumberTP23

1 引言

隨著人們對水聲傳播原理認(rèn)識的深入和各種新的信號處理算法在聲納中的應(yīng)用，聲納逐漸向?qū)拵А⒌皖l、遠(yuǎn)距離或是近場、高頻、高分辨率等方向發(fā)展［1］。由于這些新的信號處理方法或技術(shù)通常需要的運算量大幅增加，且算法結(jié)構(gòu)一般也比較復(fù)雜。為了使這些新方法能夠在聲納系統(tǒng)中得以實時實現(xiàn)，需要開發(fā)高速并行處理系統(tǒng)和設(shè)計相應(yīng)的并行計算方法。

空間譜估計在聲吶、雷達(dá)、通信等領(lǐng)域具有重要意義。最早的空間譜估計方法常規(guī)波束形成（conventional beam-forming，CBF）的方位分辨力由瑞利限決定［2］。為了提高方位分辨力，Capon提出了最小方差無畸變波束形成方法（minimum vari?ance distortion less response，MVDR）［3］。處理寬帶信號時，MVDR將寬帶分成若干頻點，在每個頻點上估計空間譜，相加得到寬帶結(jié)果，這是非相干累積，因此會損失信息，處理相干源時方位分辨能力下降，而且需要不少于陣元數(shù)的快拍數(shù)才能達(dá)到收斂。針對這些問題，Krolik和Swingler提出了導(dǎo)向最小方差波束形成（steered minimum variance，ST?MV）［4］。STMV是基于導(dǎo)向協(xié)方差矩陣（steered co?variance matrix，STCM）對不同頻點的互譜密度矩陣進(jìn)行相干積累，計算寬帶空間譜。STMV可以獲得寬帶增益并減少收斂時間，并且能直接處理相干源。

任何數(shù)字信號處理算法的實用性歸根到底取決于該算法在計算上的可行性［5］。本文從STMV波束形成的并行實現(xiàn)角度入手，在討論了STMV波束形成算法原理的基礎(chǔ)上，提出了STMV波束形成算法的逆QR（正交分解）分解SMI（采樣矩陣求逆）的實現(xiàn)方法，討論了逆QR分解SMI算法的Systolic陣列并行實現(xiàn)結(jié)構(gòu)，分析組成Systolic陣列的各PE單元的基本運算模塊的實現(xiàn)，并研究逆QR分解SMI算法基于Systolic陣列結(jié)構(gòu)的FPGA并行實現(xiàn)方法。

2 STMV波束形成算法原理

文獻(xiàn)［6］提出的一種相干波束形成算法：基于導(dǎo)向協(xié)方差矩陣（steered covariance matrix，STCM）的寬帶導(dǎo)向最小方差波束形成算法（Steered Mini?mum Variance-STMV），其原理是通過波束旋轉(zhuǎn)使指定方向θ的響應(yīng)為1，而波束形成的輸出能量最小。

按照常規(guī)時延求和波束形成，對每個陣元輸出信號插入時延 τm(θ)=md cos(θ)/c，m=0，…，M-1，則時延后輸出為

加權(quán)的時延波束形成輸出為

式中：W為一組權(quán)矢量。波束的功率為

當(dāng)快拍的長度足夠長k≠m時，X(fk)與X(fm)是不相關(guān)的，因此有：

式中ηk是第k個頻點的加權(quán)系數(shù)即為該頻點的信噪比。

最優(yōu)波束形成問題就是求權(quán)向量W使目標(biāo)方向θ的響應(yīng)為1，而波束輸出功率式（4）最小，即

式（6）中1M表示M×1的1的向量。

導(dǎo)向協(xié)方差矩陣由于綜合利用了各子帶的信息，只要滿足子帶數(shù)與快拍數(shù)的乘積不小于導(dǎo)向協(xié)方差矩陣的維數(shù)，導(dǎo)向協(xié)方差矩陣就是可逆的［6］。

3 STMV算法的逆QR分解SM I實現(xiàn)方法

從上節(jié)分析我們知道最優(yōu)波束形成問題就是求權(quán)向量W使目標(biāo)方向θ的響應(yīng)為1，而波束輸出功率式（4）最小。下面介紹SMI算法：

線性約束最小方差（LCMV）準(zhǔn)則可描述為

這里μ為常數(shù)，y(n)表示第n個采樣時刻下的波束輸出，a為期望信號導(dǎo)向矢量，P為功率可進(jìn)一步表示為

這里Rxx為輸入矢量的協(xié)方差矩陣。該準(zhǔn)則的物理意義為：在保證對有用信號的增益為常數(shù)的前提下，輸出總功率最小。該準(zhǔn)則實際上與輸出信噪比最大等效。式（7）的拉格朗日解可表示為

對于在定向方向的單位增益約束（即μ=1，wHa=1），LCMV退化為最小差無失真響應(yīng)（MV?DR）波束形成器。根據(jù)最大似然準(zhǔn)則，采樣信號矢量x的n次采樣可構(gòu)成Rxx的最佳估計R?xx：

用 R?xx代替 Rxx求解式（8）便是SMI算法。

對采樣信號矢量x的n次采樣Rxx作DFT轉(zhuǎn)換到頻域，即可得到Rcsdm(fk)，根據(jù)導(dǎo)向協(xié)方差矩陣定義即可求得Rstcm(θ)，由此可以采用SMI算法來求權(quán)向量W。

QR分解SMI算法需要前向和后向帶入才能獲得自適應(yīng)權(quán)向量W［7］，這不但增加了系統(tǒng)的硬件規(guī)模，同時也造成了軟件實現(xiàn)的復(fù)雜性。本文在前面論述的基礎(chǔ)上，對算法結(jié)構(gòu)進(jìn)行了進(jìn)一步的改進(jìn)，實現(xiàn)了一種不需要前向后向回帶的QR分解SMI算法，由于該方法用到了三角陣求逆進(jìn)行推導(dǎo)，稱之為逆QR分解SMI算法［7］。

設(shè)第 n次快拍時輸入信號為x(n)=[x1(n)，x2(n)，…，xM(n)]T，設(shè) vn=A-nHa，則可以得到n次快拍在LCMV條件下的權(quán)向量Wn：

式（10）給出了另外一種自適應(yīng)權(quán)向量的求解方法，即將求解Wn轉(zhuǎn)換成求解下三角矩陣A-Hn和中間向量vn的問題。

下面討論A-nH矩陣的遞推更新問題。設(shè)n-1時刻已經(jīng)實現(xiàn)輸入數(shù)據(jù)矩陣的三角化，那么在n時刻存在酉陣Q(n)=GM(n) GM-1(n)…G1(n)使下式成立：

式中x(n)是n次快拍時各陣元接收數(shù)據(jù)構(gòu)成的列向量，所以有：

對式（11）作如下處理：

根據(jù)矩陣求逆引理，對上式兩邊同時求逆，有：

令中間變量 z(n)=A-nH-1x*(n ) ，t(n)=，上式可簡化為

進(jìn)一步，令 q(n)=A-n1-1z(n)/t(n ) ，則qH(n)=zH(n) A-nH-1/t(n)，上式可寫成：

這樣我們得到如下結(jié)論：必然存在一個酉陣P(n)使下式成立：

根據(jù)表達(dá)式t(n)得到t2(n)=1+zH(n) z(n)，則有下式成立：

比較式（16）和式（17）可知，當(dāng)一個酉矩陣通過輸入1向量把z(n)變換成零向量的時候（該酉矩陣通過一系列Givens旋轉(zhuǎn)產(chǎn)生［8］），相同的旋轉(zhuǎn)變換通過輸入0向量將A-nH-1更新為A-nH，由此實現(xiàn)矩陣的遞推更新。實現(xiàn)了矩陣的遞推更新，下面討論另一個變量vn的更新方法。將式（15）兩邊同時右乘a左乘aH，經(jīng)過適當(dāng)?shù)淖冃慰傻玫剑?/p>

設(shè) β(n)=qH(n) a，同時考慮到vn=A-nHa，上式可改寫成：

則有下式成立：

式（20）說明，相同的酉矩陣P(n)能通過輸入0向量將vn-1更新為vn。

4 逆QR分解SM I算法的Systolic陣列實現(xiàn)

自適應(yīng)波束形成中都需要大量的矩陣運算，其中矩陣分解或是求逆又是其主要工作。因此，矩陣運算往往成為自適應(yīng)陣列處理系統(tǒng)中實時性能的瓶頸［9］。在實際應(yīng)用中，SMI算法需要實時地進(jìn)行數(shù)據(jù)矩陣的更新，數(shù)據(jù)矩陣更新需要相應(yīng)的迭代算法與之相對應(yīng)，基于Systolic結(jié)構(gòu)的并行運算結(jié)構(gòu)更適合于這種數(shù)據(jù)更新的運算，僅需要將新采集的數(shù)據(jù)按順序送入Systolic陣列中即可。

4.1 Systolic并行處理陣列

Systolic并行處理器是一種流水線型的陣列結(jié)構(gòu)，它是1978年H.T.Kung等在以大規(guī)模并行處理為目的而研究專用VLSI結(jié)構(gòu)時提出的［10］。Systolic系統(tǒng)是一個節(jié)律性的完成數(shù)據(jù)計算并通過系統(tǒng)傳遞數(shù)據(jù)的處理器網(wǎng)絡(luò)。其結(jié)構(gòu)具有模塊化、規(guī)則化、局部連接、高度流水以及高同步化多重處理等重要特性。

圖1 Systolic陣列的基本原理

圖1 給出了Systolic陣列的基本原理。Systolic陣列中，數(shù)據(jù)一旦從存儲器中取出后，就沿著陣列從一個PE“泵”到另一個PE，而在它通過的每個PE上，數(shù)據(jù)都可以被有效的利用。這樣，在從存儲器調(diào)出的數(shù)據(jù)又返回存儲器之前，使之通過盡可能多的PE，進(jìn)行流水線式的處理，減輕了主機的輸入輸出負(fù)擔(dān)。Systolic陣列具有高效率的原因在于主機端負(fù)責(zé)數(shù)據(jù)的存儲，且主機端還可以選擇所需的數(shù)據(jù)，并將數(shù)據(jù)流水式的送入陣列。

4.2 逆OR分解SM I算法的Systolic實現(xiàn)

綜合上面的論證和分析，可以得到LCMV準(zhǔn)則下避免前向后向帶入的逆QR分解SMI算法的實現(xiàn)步驟：

2）遞推更新（k=1，2，…）：計算中間向量z(n)，并根據(jù)式（17）計算得到旋轉(zhuǎn)所用的酉陣P(n)，并用P(n )通過式（16）和式（20）更新下三角陣A-nH和中間向量vn。

根據(jù)上述逆QR分解SMI算法的內(nèi)在數(shù)據(jù)處理并行性，我們能得到該算法的Systolic陣列實現(xiàn)結(jié)構(gòu)。圖2給出以四陣元為例的逆QR分解SMI算法的Systolic并行實現(xiàn)結(jié)構(gòu)。

圖2 逆QR分解SMI算法的Systolic結(jié)構(gòu)

從圖中可以看出，通過算法的改進(jìn)該Systolic陣列避免了傳統(tǒng)QR分解SMI算法的前向后向帶入過程，使得實現(xiàn)過程變得簡潔。從圖中可以看出，該Systolic陣列共包含四種PE單元，它們分別表示：中間向量v，各vi單元完成對vi的存儲和更新；中間向量z(n)，各單元zi單元用來產(chǎn)生系統(tǒng)進(jìn)行Givens旋轉(zhuǎn)更新所需的旋轉(zhuǎn)因子；下三角矩陣B=A-nH的下三角部分bij單元存儲并更新A-nH的各元素；wi單元完成權(quán)向量的更新和輸出。圖3給出了各功能單元的具體實現(xiàn)方法。

圖3 各PE單元的功能實現(xiàn)

5 STMV算法的FPGA并行實現(xiàn)方法

圖4給出了STMV波束形成算法的硬件實現(xiàn)原理圖，并給出了逆QR分解SMI自適應(yīng)波束權(quán)矢量提取算法在FPGA上實現(xiàn)的原理結(jié)構(gòu)。

在該實現(xiàn)結(jié)構(gòu)中，每路陣元的接收信號均連有一個FIFO（先入先出）存儲器，該存儲器用以完成A／D采集信號的接收、存儲和讀取。存入各路FIFO的數(shù)據(jù)通過寫使能（REN）的控制接入Systolic陣列權(quán)提取模塊，進(jìn)行接收信號的自適應(yīng)權(quán)矢量提取。要想完成整個波束形成的設(shè)計，還應(yīng)在Systol?ic陣列權(quán)提取模塊后加入波束形成模塊，或是將該FPGA的全矢量輸出和采集數(shù)據(jù)接入DSP處理器由DSP完成波束形成部分的運算。

圖4 逆QR分解SMI算法在FPGA上的實現(xiàn)結(jié)構(gòu)

圖4 中的FIFO存儲器是通過調(diào)用XILINX公司的IP核生成軟件Core Generator生成的，所使用的IP核為Asynchronous FIFO v6.1。該異步FIFO可以對寫入和讀出端分別進(jìn)行時序控制。數(shù)據(jù)輸入端的數(shù)據(jù)總線（DIN）可直接與A/D端的數(shù)據(jù)總線相連接，配合寫使能（WEN）和寫時鐘（WCLK）可以完成采集信號到FIFO存儲器的存入。同時該FIFO的輸出端還配有全滿（FULL）、幾乎滿（ALMOST FULL）和全空（EMPTY）、幾乎空（ALMOSTEMPTY）信號，用以方便對其進(jìn)行時序控制，其中滿和幾乎滿信號是與寫時鐘（WCLK）同步的，空和幾乎空信號是與讀時鐘（RCLK）同步的。為了更進(jìn)一步對FIFO進(jìn)行時序控制，該IP核還提供寫計數(shù)（WR COUNT）與讀計數(shù)（RD COUNT）輸出信號，用以標(biāo)識該FIFO讀寫狀態(tài)。配合算法的輸入時序，各路FIFO的輸出信號可通過讀使能（REN）信號的控制進(jìn)行輸出。數(shù)據(jù)輸出總線（DOUT）直接連入Systol?ic陣列的各路輸入，經(jīng)過該Systolic陣列即可完成自適應(yīng)權(quán)矢量的提取和輸出。

6 結(jié)語

本文從STMV波束形成算法的并行實現(xiàn)角度入手，在討論了STMV波束形成算法原理的基礎(chǔ)上，提出了STMV波束形成算法的逆QR分解SMI的實現(xiàn)方法，討論了逆QR分解SMI算法的Systolic陣列并行實現(xiàn)結(jié)構(gòu)，分析組成Systolic陣列的各PE單元的基本運算模塊的實現(xiàn)，并研究了逆QR分解SMI算法基于Systolic陣列結(jié)構(gòu)的FPGA并行實現(xiàn)方法和STMV波束形成算法并行實現(xiàn)的硬件構(gòu)架。

［1］李啟虎.聲納信號處理引論（第二版）［M］.北京：北京海洋出版社，2003：12-15.

LIQihu.Sonar signal processing Introduction（Second Edi?tion）［M］.Beijing：Beijing Ocean Press，2003：12-15.

［2］VAN TREE L.Optimum array processing［M］.New York：John Wiley&Sons Inc.，2003：48.

［3］CAPON J.High resolution frequency-wave number spec?trum analysis［J］.Proceeding of the IEEE，1969，57（8）：1404-1418.

［4］KROLIK J，SWINGLERD.Multiple broadband source lo?cation using steered covariance matrices［J］.IEEE Trans Acoustics Speech and Signal Processing，1989，37（10）：1481-1494.

［5］貢三元.VLSI陣列處理［M］.南京：東南大學(xué)出版社，1990：56-80.

GONG Sanyuan.VLSI array processing［M］.Nanjing：Southeast University Press，1990：56-80.

［6］J.Krolik.D.Swingler.Multiple Broadband Source Loca?tion Using Steered Covariance Matrices.IEEE Trans.AS?SP.1989，37（10）：1481-1494.

［7］馮地耕.基于QR分解的ADBF算法及其DSP實現(xiàn)研究［D］.西安：西安電子科技大學(xué)，2004：35-43.FENG Digeng.ADBF algorithm based on QR decomposi?tion and its DSPRealization［D］.Xi’an：Xi’an University of Electronic Science and Technology，2004：35-43.

［8］石斌斌，錢林杰.基于CORDIC的滑窗最小二乘遞推算法［J］.系統(tǒng)工程與電子技術(shù)，2010，32（11）：2304-2309.

SHI Binbin，QIAN Linjie.CORDIC-based sliding window recursive least squares algorithm［J］.Systems Engineering and Electronics，2010，32（11）：2304-2309.

［9］白振鋒，蕭寶瑾.智能天線自適應(yīng)波束形成算法的研究［J］.山西電子技術(shù)，2007（1）：54-57.

BAIZhenfeng，XIAO Baojin.Study of Smart antenna adap?tive beam-forming algorithm［J］.Shanxi Electronic Tech?nology，2007（1）：54-57.

［10］孫世新，盧光輝.并行算法及其應(yīng)用［M］.北京：機械工業(yè)出版社，2004：33-45.

SUN Shixin，LU Guanghui.Parallel algorithm and its ap?plication［M］.Beijing：Mechanical Industry Press，2004：33-45.

Research of STMV Beam-form ing A lgorithm Parallel Processing Im p lementation M ethod

ZHOU Yijun LIU Qianli
（Military Representative Office of Navy in Wuhan 438 Factory，Wuhan 430060）

TP23

10.3969/j.issn.1672-9722.2017.09.009

2017年4月17日，

2017年5月27日

周亦軍，男，高級工程師，研究方向：水聲工程。劉千里，男，博士研究生，工程師，研究方向：水聲工程。